# BF interpreter in Python that uses recursion to handle loops

I wrote a Brainfuck interpreter in Python and I'm wondering how to simplify it.

I handle separately loop commands and the others. A recursive function deals with loops.

import sys
array = [0] # byte array
ptr = 0 # data pointer


Read and execute commands except loop

def readNoLoop(char):
global ptr
# Increment/Decrement the byte at the data pointer
if char=='+':
array[ptr] += 1
elif char=='-':
array[ptr] -= 1
if array[ptr] < 0:
raise ValueError("Negative value in array")
# Increment/Decrement the data pointer
elif char=='>':
ptr += 1
while(ptr>=len(array)-1):
array.append(0)
elif char=='<':
ptr -= 1
if ptr < 0:
raise ValueError("Negative value of pointer")
# Output the byte at the data pointer
elif char=='.':
sys.stdout.write(chr(array[ptr]))
# Store one byte of input in the byte at the data pointer
elif char==',':


Recursive function to deal with loops

def interpret(charChain):
it = 0
loopBegin = []
while(it<len(charChain)):
if charChain[it]=='[':
loopBegin.append(it)
elif charChain[it]==']':
subChain = charChain[loopBegin[-1]+1:it]
while(array[ptr]>0):
interpret(subChain)
loopBegin.pop()
else:
it+=1


Main

if __name__ == "__main__":
# Brainfuck program to print "Hello World!"
code = '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'
try:
interpret(code)
except:
raise


My main concern is to know if it's possible to have a simpler code without recursion.

• Hi, welcome to Code Review! I hope you receive great answers! – Tunaki Apr 13 '16 at 20:17

There are a number of issues with your code that makes your interpreter somewhat buggy:

• iterate over characters instead of indexes. The for loop in Python is one of it's key feature. It lets you easily iterate over elements of a collection without having to handle indexes to access each of them. You still need indexes for other purposes? enumerate is your friend, then.

def interpret(char_chain):
loop_begin = []
for it, character in enumerate(char_chain):
if character == '[':
loop_begin.append(it)
elif character == ']':
# ... and so on

• command '>': since you can only increment data_pointer by one at a time, you'll never have to catch up with a gap between the size of byte_array and the value of data_pointer. At maximum, you’ll be adding 1 extra cell.

elif char == '>':
data_pointer += 1
if data_pointer == len(byte_array):
byte_array.append(0)

• except: raise: never use bare excepts, always specify which kind of exceptions you’re expecting. You never know what could happen (ValueErrors that you are raising, KeyboardInterrupt, RuntimeError… the list goes on) but want to handle everything the same way. Moreover, you’re not prepared to handle anything because the only thing you do with your exception is re-raise it… just let the exception be and remove your try .. except instead.

• command ',': your interpreter does not handle end of files when reading the input. sys.stdin.read(1) can return '' when EOF is reached and ord('') is a TypeError. See what the issue is about and example of programs that handle different conventions. The key point here is, whatever the convention you choose to apply, you need to handle EOFs.
• command '[': your recursion is broken. The completely innefficient '+++++++++++++++++++++++++++++++++.' should output !. Same for '[+]+++++++++++++++++++++++++++++++++.' since the first cell is at 0 when starting the interpreter and thus the loop will be skipped. However your interpreter does nothing when encountering '[' to signal that the loop should be skipped or not and thus the next character will always be handled by read_no_loop. Recursion can be a powerfull tool here to handle going back and forth between the beginning and the end of the loop; or you could handle indexes by hand like you do, but both seems a bit inefficient.

What you'll need to have, though, is a flag telling you if you should skip interpreting the loop. And if you have it manage nested levels of loops, it's even better.

def interpret(char_chain):
skip = 0
for it, character in enumerate(char_chain):
if skip:
skip += character == '[' # Increment the level of nested loops to skip
skip -= character == ']' # Decrement the level of nested loops to skip
continue # Do nothing else, since we have to skip that character

if character == '[':
while byte_array[data_pointer]:
# Recurse to interpret the loop
interpret(char_chain[it+1:])
# Skip the loop when the current cell is 0
skip = 1
elif character == ']':
# End the recursion when reaching the end of the loop
return
else:


Here I use the fact that booleans are a subclass of integers and that False is 0 and True is 1. This is considered rather bad practice but I like the conciseness of that form. If it feel more natural to you, you can write if character == '[': skip += 1 instead of skip += character == '['.

One last thing to note is that it would be better if the user could be able to provide the BF code on the command line when invoking the program instead of having to modify the code to do so. The complete program would look like:

import sys

byte_array = [0]
data_pointer = 0

global data_pointer
# Increment/Decrement the byte at the data pointer
if char == '+':
byte_array[data_pointer] += 1
elif char == '-':
byte_array[data_pointer] -= 1
if byte_array[data_pointer] < 0:
raise ValueError("Negative value in byte_array")
# Increment/Decrement the data pointer
elif char == '>':
data_pointer += 1
if data_pointer == len(byte_array):
byte_array.append(0)
elif char == '<':
data_pointer -= 1
if data_pointer < 0:
raise ValueError("Negative value of pointer")
# Output the byte at the data pointer
elif char == '.':
sys.stdout.write(chr(byte_array[data_pointer]))
# Store one byte of input in the byte at the data pointer
elif char == ',':
if character:
byte_array[data_pointer] = ord(character)
else: # EOF
byte_array[data_pointer] = 0 # choose you convention and document it.

def interpret(char_chain):
skip = 0
for it, character in enumerate(char_chain):
if skip:
skip += character == '['
skip -= character == ']'
continue # Actually skip that character

if character == '[':
while byte_array[data_pointer]:
# Recurse to interpret the loop
interpret(char_chain[it+1:])
# Skip the loop when the current cell is 0
skip = 1
elif character == ']':
# End the recursion when reaching the end of the loop
return
else:

if __name__ == "__main__":
try:
code = sys.argv[1]
except IndexError:
print("You should provide the BF code as first argument of this program")
else:
interpret(code)
# Be nice with the user and output a newline to not mess up his shell
print()

• Besides, I didn't see this issue when '[' is the first command ! My first idea was to avoid infinite recursion when a loop is not closed. Your approach is better, I'll add a test using regex to check if loops are closed and avoid infinite recursion. – cromod Apr 14 '16 at 22:45
• @cromod There is no need for that. If there is no closing bracket, the recursion will stop at the end of the string and standard rules apply: if the current cell is positive, we recurse again, otherwise we skip the loop (terminating the program). – 301_Moved_Permanently Apr 15 '16 at 5:57
• Yes you're right but don't you think sending an exception would be more user-friendly if there's no closing bracket ? No need to use regex for that, a test skip>0 is enough at the end of forloop. – cromod Apr 15 '16 at 9:07
• @cromod The end of the for loop means the end of the program. You won't reach it in case of an infinite loop somewhere. Be it because the is no matching ']' or because there is indeed a true infinite loop somewhere (thinking of '[+]' in the middle of the program). – 301_Moved_Permanently Apr 15 '16 at 9:15
• With +[-+- we reach the end of for loop but there's no matching ']'. – cromod Apr 15 '16 at 9:32

As you didn't mention what are you looking for in a review, I will make some general comments regarding your code.

Formatting and variables

• indent your code using 4-spaces TAB
• try removing redundant parentheses from your while loop loops
• function names should be lower case (so try renaming your def readNoLoop(). Perhaps something like read_no_loop().
• variable in functions should also be lowercase

Name conventions

Try renaming you variables based on their usage. For example: it - what is it ? What is its purpose ? Think about this when you are naming your methods / variables.

array = [0]  # byte array
ptr = 0  # data pointer


Will become:

byte_array = [0]
data_pointer = 0


So far, we would have something like this:

import sys

byte_array = [0]
data_pointer = 0

global data_pointer
# Increment/Decrement the byte at the data pointer
if char == '+':
byte_array[data_pointer] += 1
elif char == '-':
byte_array[data_pointer] -= 1
if byte_array[data_pointer] < 0:
raise ValueError("Negative value in byte_array")
# Increment/Decrement the data pointer
elif char == '>':
data_pointer += 1
while data_pointer >= len(byte_array) - 1:
byte_array.append(0)
elif char == '<':
data_pointer -= 1
if data_pointer < 0:
raise ValueError("Negative value of pointer")
# Output the byte at the data pointer
elif char == '.':
sys.stdout.write(chr(byte_array[data_pointer]))
# Store one byte of input in the byte at the data pointer
elif char == ',':

def interpret(char_chain):
it = 0
loop_begin = []
while it < len(char_chain):
if char_chain[it] == '[':
loop_begin.append(it)
elif char_chain[it] == ']':
sub_chain = char_chain[loop_begin[-1] + 1:it]
while byte_array[data_pointer] > 0:
interpret(sub_chain)
loop_begin.pop()
else:
it += 1

if __name__ == "__main__":
# Brainfuck program to print "Hello World!"
code = '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'
try:
interpret(code)
except:
raise


Those elifs are bothering me, so you can try doing something like this:

instructions = {
'+': increment,
'-': decrement,
# and so on
}


As per your code, I can't see much of improvement at the functionality level. Perhaps I will let others to do this.

More, I like how you used recursion in this code. In general, you have a nice structure.

• Thanks for your answer ! I'll try to use a dictionnary instead of elif. Moreover, I'll edit my post to ask if it's possible to have a simpler structure without recursion. This was my implicit but not clear question :P – cromod Apr 14 '16 at 8:35
• Replacing if statements by python dictionaries is so powerful ! It really improves readability. Thanks a lot ! – cromod Apr 14 '16 at 20:59