Yet another Brainfuck interpreter written in Python 3, but with a big plot twist in the implementation

brainfuck_bytecode.py

"""
Yet another Brainfuck interpreter written in Python (3.4).
Plot twist: this interpreter craft Python bytecode from the Brainfuck code and execute it.
Yep, dynamic Python bytecode generation from Brainfuck source code. Why? Because I can.
"""

from bytecode import Instr, Label, Bytecode


def bf_rle_encode(input_str):
    """
    Apply a running-length compression (RLE) algorithm to the input string.
    Yield intermediate result as tuple (char, count).
    Also filter any characters from the input string which are not valid BF opcodes.
    N.B. BF opcodes [ and ] are NOT RLE encoded.
    """
    prev, count = '', 1
    for c in input_str:
        if c not in ('>', '<', '+', '-', '.', ',', '[', ']'):
            continue
        if c != prev:
            if prev:
                yield prev, count
            prev, count = c, 1
        elif c == '[' or c == ']':
            yield c, 1
        else:
            count += 1
    else:
        yield c, count


def compile_brainfuck(bf_source, memory_size=1024*64):
    """ Compile the given Brainfuck source code into Python bytecode. """
    loop_label_stack = []
    bytecode = Bytecode()
        
    # import sys
    bytecode.extend([
        Instr("LOAD_CONST", 0),
        Instr("LOAD_CONST", None),
        Instr("IMPORT_NAME", 'sys'),
        Instr("STORE_NAME", 'sys'),
    ])
    
    # memory = bytearray(MEMORY_SIZE)
    bytecode.extend([        
        Instr("LOAD_NAME", 'bytearray'),
        Instr("LOAD_CONST", memory_size),
        Instr("CALL_FUNCTION", 1),
        Instr("STORE_NAME", 'memory'),
    ])

    # ptr = 0
    bytecode.extend([
        Instr("LOAD_CONST", 0),
        Instr("STORE_NAME", 'ptr'),
    ])

    # buffer = []
    bytecode.extend([
        Instr("BUILD_LIST", 0),
        Instr("STORE_NAME", 'buffer'),
    ])

    # write = sys.stdout.write
    bytecode.extend([
        Instr("LOAD_NAME", 'sys'),
        Instr("LOAD_ATTR", 'stdout'),
        Instr("LOAD_ATTR", 'write'),
        Instr("STORE_NAME", 'write'),
    ])

    for opcode, count in bf_rle_encode(bf_source):
        if opcode == '>':
            # ptr = (ptr + COUNT) % MEMORY_SIZE
            bytecode.extend([
                Instr("LOAD_NAME", 'ptr'),
                Instr("LOAD_CONST", count),
                Instr("BINARY_ADD"),
                Instr("LOAD_CONST", memory_size),
                Instr("BINARY_MODULO"),
                Instr("STORE_NAME", 'ptr'),
            ])
            
        elif opcode == '<':
            # ptr = (ptr + COUNT) % MEMORY_SIZE
            bytecode.extend([
                Instr("LOAD_NAME", 'ptr'),
                Instr("LOAD_CONST", count),
                Instr("BINARY_SUBTRACT"),
                Instr("LOAD_CONST", memory_size),
                Instr("BINARY_MODULO"),
                Instr("STORE_NAME", 'ptr'),
            ])
            
        elif opcode == '+':
            # memory[ptr] = (memory[ptr] + COUNT) % 256
            bytecode.extend([
                Instr("LOAD_NAME", 'memory'),
                Instr("LOAD_NAME", 'ptr'),
                Instr("BINARY_SUBSCR"),
                Instr("LOAD_CONST", count),
                Instr("BINARY_ADD"),
                Instr("LOAD_CONST", 256),
                Instr("BINARY_MODULO"),
                Instr("LOAD_NAME", 'memory'),
                Instr("LOAD_NAME", 'ptr'),
                Instr("STORE_SUBSCR"),
            ])
            
        elif opcode == '-':
            # memory[ptr] = (memory[ptr] + COUNT) % 256
            bytecode.extend([
                Instr("LOAD_NAME", 'memory'),
                Instr("LOAD_NAME", 'ptr'),
                Instr("BINARY_SUBSCR"),
                Instr("LOAD_CONST", count),
                Instr("BINARY_SUBTRACT"),
                Instr("LOAD_CONST", 256),
                Instr("BINARY_MODULO"),
                Instr("LOAD_NAME", 'memory'),
                Instr("LOAD_NAME", 'ptr'),
                Instr("STORE_SUBSCR"),
            ])
            
        elif opcode == '.':
            # write(chr(memory[ptr]) * COUNT)
            bytecode.extend([
                Instr("LOAD_NAME", 'write'),
                Instr("LOAD_NAME", 'chr'),
                Instr("LOAD_NAME", 'memory'),
                Instr("LOAD_NAME", 'ptr'),
                Instr("BINARY_SUBSCR"),
                Instr("CALL_FUNCTION", 1),
                Instr("LOAD_CONST", count),
                Instr("BINARY_MULTIPLY"),
                Instr("CALL_FUNCTION", 1),
                Instr("POP_TOP"),
            ])
            
        elif opcode == ',':
            for _ in range(count):

                label_pop_buffer = Label()
                label_get_input = Label()

                # if not buffer:
                bytecode.extend([
                    Instr("LOAD_NAME", 'buffer'),
                    Instr("POP_JUMP_IF_TRUE", label_pop_buffer),
                ])

                #     buffer.extend(input() or "\n")
                bytecode.extend([
                    Instr("LOAD_NAME", 'buffer'),
                    Instr("LOAD_ATTR", 'extend'),
                    Instr("LOAD_NAME", 'input'),
                    Instr("CALL_FUNCTION", 0),
                    Instr("JUMP_IF_TRUE_OR_POP", label_get_input),
                    Instr("LOAD_CONST", '\n'),
                    label_get_input,
                    Instr("CALL_FUNCTION", 1),
                    Instr("POP_TOP"),
                ])

                # c = buffer.pop(0)
                bytecode.extend([
                    label_pop_buffer,
                    Instr("LOAD_NAME", 'buffer'),
                    Instr("LOAD_ATTR", 'pop'),
                    Instr("LOAD_CONST", 0),
                    Instr("CALL_FUNCTION", 1),
                    Instr("STORE_NAME", 'c'),
                ])

                # memory[ptr] = ord(c)
                bytecode.extend([
                    Instr("LOAD_NAME", 'ord'),
                    Instr("LOAD_NAME", 'c'),
                    Instr("CALL_FUNCTION", 1),
                    Instr("LOAD_NAME", 'memory'),
                    Instr("LOAD_NAME", 'ptr'),
                    Instr("STORE_SUBSCR"),
                ])
                
        elif opcode == '[':
            for _ in range(count):

                label_head_of_loop = Label()
                label_end_of_loop = Label()

                # while memory[ptr]:
                bytecode.extend([
                    label_head_of_loop,
                    Instr("LOAD_NAME", 'memory'),
                    Instr("LOAD_NAME", 'ptr'),
                    Instr("BINARY_SUBSCR"),
                    Instr("POP_JUMP_IF_FALSE", label_end_of_loop),
                ])
                
                loop_label_stack.append((label_head_of_loop, label_end_of_loop))
                
        elif opcode == ']':
            for _ in range(count):
                if not loop_label_stack:
                    raise ValueError('Unmatched closing bracket.')

                label_head_of_loop, label_end_of_loop = loop_label_stack.pop()
                
                # End of while loop
                bytecode.extend([
                    Instr("JUMP_ABSOLUTE", label_head_of_loop),
                    label_end_of_loop,
                ])

    # End of program
    bytecode.extend([
        Instr("LOAD_CONST", None),
        Instr("RETURN_VALUE"),
    ])

    if loop_label_stack:
        raise ValueError('Unmatched opening bracket (%d left open).' % stack_level)

    return bytecode.to_code()


def main():
    """
    Wait for the user input and execute the given code.
    If no input is given, execute the "hello world" example.
    """
    helloworld_bf_code = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."
    bf_code = []
    s = input('Brainfuck> ')
    while s:
        bf_code.append(s)
        s = input('Brainfuck> ')
    bf_code = ''.join(bf_code) or helloworld_bf_code
    print('----- RUNNING -----')
    
    code = compile_brainfuck(bf_code)
    exec(code)


if __name__ == '__main__':
    main()