2
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by 200_success, yuri, pacmaninbw, esote, ferada May 6 at 23:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – 200_success, yuri, pacmaninbw, esote, ferada
If this question can be reworded to fit the rules in the help center, please edit the question.

2
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Awesome, thank you! I was actually in the middle of working on a fairly promising solution but was having problems with what seems to be weird pointer magic? I tried something similar to yours in function, and in the process realized that both your code, my new code, and my old code don't do what I want: it evaluates the entire and up to the last clause up front, instead of lazily doing it. Here's what I had: gist.github.com/christopherdumas/…. \$\endgroup\$ – Gort May 4 at 20:21
  • \$\begingroup\$ Currently, I'm trying to get this to work: gist.github.com/christopherdumas/…. However, when the actual final possibilities generator is evaluated, it seems to have been set to the result of the final clause evald with a blank possibilities? It's very strange. And if I try to keep track of the possibilities, in a stack, they all turn out to have the exact same contents, and I can't figure out why. \$\endgroup\$ – Gort May 4 at 20:27
  • \$\begingroup\$ @Gort I'm not going to help you further. If you post a working question on Code Review I might. \$\endgroup\$ – Peilonrayz May 4 at 20:33
  • \$\begingroup\$ Okay that's fine. I'm just grateful for any sort of help. Also I did more research and I was indeed wrong about looping (:. I'll continue to try to figure this out and post an answer here when I'm done. \$\endgroup\$ – Gort May 4 at 20:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.