A toy Brainfuck implementation in Python

brainfuck.py

"""
A toy Brainfuck implementation in Python.

In this implementation, the length of tape is infinite in both directions (I used two stacks for the left and right
sides of the tape) and the values on the tape are 0 <= x < 256.
"""


def jump_to_closing_bracket(start_i, program):
    """
    Given a starting index `start_i` in `program` where there is an opening bracket, find the index 
    where that bracket is closed.
    """
    depth = 1
    for i in range(start_i, len(program)):
        if program[i] == '[':
            depth += 1
        elif program[i] == ']':
            depth -= 1

        if depth == 1:
            return i
    
    raise Exception('Cannot find a closing bracket for {}'.format(start_i))


def safe_pop(l, default):
    """
    Pop the value from the end of the list `l`. If the list is empty, return `default`.
    """
    if len(l) > 0:
        return l.pop()
    else:
        return default


def get_jumps(program):
    """
    Returns a list of tuples of the form (start_i, end_i), where `start_i` and `end_i` are the
    start and end indexes of all the jumps (pairs of open/closed brackets) in the program `program`.
    """
    jumps = []
    for i, item in enumerate(program):
        if item == '[':
            # look for a jump
            e = jump_to_closing_bracket(i, program)
            jumps.append((i,e))
    return jumps


B = 255


def execute_bf_step(program, forward_jumps, backward_jumps, output_buffer, tapeL, header, tapeR, p_i):
    """
    Execute one step of a Brainfuck program.

    Program data:
    program: the instructions
    forward_jumps: a mapping from positions of open brackets -> positions of the corresponding closed brackets
    backward_jumps: a mapping from positions of closed brackets -> positions of the corresponding open brackets

    State data:
    tapeL: the left hand starting tape
    header: the current value under the tape head
    tapeR: the right hand starting tape
    p_i: the position of the machine in the program

    This function returns a new tuple containing the new state.
    """
    c = program[p_i]
    if c == '>':
        # Move pointer right
        tapeL.append(header)
        header = safe_pop(tapeR, default=0)
    elif c == '<':
        # Move pointer left
        tapeR.append(header)
        header = safe_pop(tapeL, default=0)
    elif c == '+':
        # Increment the memory cell under the pointer
        header = (header + 1) % B
    elif c == '-':
        # Decrement the memory cell under the pointer
        header = (header - 1) % B
    elif c == '.':
        # Output the character signified by the cell at the pointer
        output_buffer.append(chr(header))
    elif c == ',':
        # Input a character and store it in the cell at the pointer
        c = input('Enter one character > ')
        output_buffer.append(ord(c[0]))
    elif c == '[':
        # Jump past the matching ] if the cell under the pointer is 0
        if header == 0:
            p_i = forward_jumps[p_i]
    elif c == ']':
        # Jump back to the matching [ if the cell under the pointer is nonzero
        if header != 0:
            p_i = backward_jumps[p_i]

    p_i += 1
    return output_buffer, tapeL, header, tapeR, p_i


def execute_bf(program, tapeL, header, tapeR, p_i):
    """
    Execute a Brainfuck program.
    program: a string/list of chars. the program to be executed
    tapeL: the left hand starting tape
    header: the current value under the tape head
    tapeR: the right hand starting tape
    p_i: the starting position of the machine in the program
    """

    # Pre-compute the jump locations - this makes the code a bit faster
    jumps = get_jumps(program)

    forward_jumps = {x:y for x,y in jumps}
    backward_jumps = {y:x for x,y in jumps}

    output_buffer = []

    l = len(program)

    # While the program pointer has not hit the end of the program
    while p_i < l:
        output_buffer, tapeL, header, tapeR, p_i = execute_bf_step(program, forward_jumps, backward_jumps, output_buffer, tapeL, header, tapeR, p_i)

    print(tapeL + [header] + list(reversed(tapeR)))
    print(''.join(output_buffer))


if __name__ == '__main__':
    tapeL = []
    header = 0
    tapeR = []

    # Prints "Hello World!"
    program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."
    p_i = 0

    execute_bf(program, tapeL, header, tapeR, p_i)