Maximum recursion depth exceeded in cmp, Python

Question

I am a beginning programmer in Python, trying to practice by building a BF interpreter. However, it will not work with the Hello, World! program:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

giving a RuntimeError: maximum recursion depth exceeded in cmp. My code is below.

import sys

script, file = sys.argv


tape, tapeslct, cmdslct = [0], 0, 0
code = open(file)
program = filter(lambda x: x in ['.', ',', '[', ']', '<', '>', '+', '-'], code.read())
print(str(program))
program = list(program)

def execute(cmd):
    global tape
    global tapeslct
    global cmdslct
    if cmd == "+":
        tape[tapeslct] += 1
    if cmd == "-":
        tape[tapeslct] -= 1
    if cmd == ">":
        tapeslct += 1
        if tapeslct == len(tape):
            tape.append(0)
    if cmd == "<":
        tapeslct -= 1
    if cmd == ".":
        print(chr(tape[tapeslct]))
    if cmd == ",":
        tape[tapeslct] = ord(input())
    if cmd == "[":
        if tape[tapeslct] >= 1:
            loopend = 0
            testfor = cmdslct
            while loopend == 0:
                testfor += 1
                if program[testfor] == "]" and tape[tapeslct] >= 0:
                    testfor = cmdslct + 1
                    execute(program[testfor])
                elif program[testfor] == "]" and tape[tapeslct] == 0:
                    loopend = 1
                    cmdslct = testfor + 1
                else:
                    execute(program[testfor])
        else:
            while loopend == 0:
                testfor += 1
                if program[testfor] == "]":
                    loopend = 1
while len(program) > cmdslct:
    execute(program[cmdslct])
    cmdslct += 1

The lambda snippet was taken from another BF interpreter in Python, found here.

I've missed something, most likely.

I don't think you need to use recursion here. Try rewriting without the recursive calls. A loop, instead? — Blorgbeard
You don't need recursion, and you should really avoid global variables. — Cyphase
It has already been said that this would serve fine as an iterative method but if you do end up needing recursion (i.e. you are switching to multiple calls), Stackless python allows infinite recursive calls — Jonathan Holland
The problem is a bug - the second [ will jump to the first [, which should not happen. (Investigating why) — Amadan

Amadan Amadan · Accepted Answer · 2015-08-24T01:41:08

From what I see, your [ and ] implementation is wonky. You start using a different instruction pointer (testfor instead of cmdslct) while inside a subroutine; but when you hit another [, you start your next loop from cmdslct instead of the current testfor, which makes nested loops impossible.

I suggest you don't treat your loops as special. When [ comes, just push the current location into a stack; when ] comes, pop it, then either jump or ignore depending on the tape. This way, you don't even need recursion.

Alternately, pass the instruction pointer, not cmd, into the recursion.

if cmd == "[":
    # remember loop start
    stack.append(cmdslct)
    if tape[tapeslct] == 0:
        # end of loop; find the matching loop end
        loops = 1
        while not (program[cmdslct] == ']' and loops > 0):
            cmdslct += 1
            if program[cmdslct] == '[':
                loops += 1
            elif program[cmdslct] == ']':
                loops -= 1
if cmd == ']':
    if tape[tapeslct] != 0:
        # jump back
        cmdslct = stack[-1]
    else:
        # forget about this loop and move on
        stack.pop()

Maximum recursion depth exceeded in cmp, Python

1 Answers