BF interpreter in Python that uses recursion to handle loops

Question

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==',':
    array[ptr] = ord(sys.stdin.read(1))

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:
      readNoLoop(charChain[it])
    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.

Answer 1

I much prefer read @Dex'ter’s code with Python coding style applied, so I’ll start with that.

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:
              read_no_loop(character)
  

  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


def read_no_loop(char):
    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 == ',':
        character = sys.stdin.read(1)
        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:
            read_no_loop(character)


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

Answer 2

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

Try to read PEP8

• 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.

For example, instead of making comments right beside the variables, rename them and remove the comments:

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


def read_no_loop(char):
    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 == ',':
        byte_array[data_pointer] = ord(sys.stdin.read(1))


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:
            read_no_loop(char_chain[it])
        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.