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
– Blorgbeard, Commented Aug 24, 2015 at 1:17
You don't need recursion, and you should really avoid global variables. — Cyphase
– Cyphase, Commented Aug 24, 2015 at 1:21
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
– Jonathan Holland, Commented Aug 24, 2015 at 1:23
The problem is a bug - the second [ will jump to the first [, which should not happen. (Investigating why) — Amadan
– Amadan, Commented Aug 24, 2015 at 1:26

Amadan · Accepted Answer · 2015-08-24 01:51:25Z

1

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()

edited Aug 24, 2015 at 1:51

answered Aug 24, 2015 at 1:41

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

The_Basset_Hound Over a year ago

Amazing, thank you. Works well now, as far as I can tell.

Collectives™ on Stack Overflow

Maximum recursion depth exceeded in cmp, Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related