Convert Tail-Call Recursive Code to Loop [closed]

So, I’m in the midst of writing a programming language interpreter in Python, and one of the problems I’m concerned about is that since I’ve been using a lot of recursions to implement the interpreter, I’ll get a stack overflow if the size of the code is too large. For example, I have a piece of code that evaluates an and operation. Since the language I’m implementing is a logic programming language (like Prolog), it needs to try out all the options, so it consumes a generator and loops over it looking at the rest of the and operation. Behold:

def evaluate_and(and_clauses, binds={}):
    if and_clauses == []:
        yield binds
    else:
        head, *tail = and_clauses
        possible = evaluate(head, binds)
        for p in possible:
            yield from evaluate_and(tail, p)

The issue with this is that if the and operation is buried deep within the program, and the call stack is already large, then if the and has too many clauses the interpreter will crash.

If anyone could suggest a way to make this not possible, that would be amazing!

PS: I have an even bigger problem, which is that since recursion is the only way to do looping in a logic programming language if you loop more than a 100 times in my language, it creates a stack overflow in my interpreter.

A quick search for “python tail call optimization” results in this SO answer which has a PyPI package, tco. Converting your code to return lists rather than generators should be all you need.

recursion is the only way to do looping in a logic programming language

This is wrong.

If you want it to stay as a generator, then you’ll have to manually handle the stack. The following doesn’t account for order so if you need that then you’ll have to figure that out yourself.

def evaluate_and(and_clauses, binds={}):
    stack = [(clauses, binds)]
    while stack:
        and_clauses, binds = stack.pop()
        if and_clauses == []:
            yield binds
        else:
            head, *tail = and_clauses
            possible = evaluate(head, binds)
            for p in possible:
                stack.append((tail, p))