Brainfuck to Python compiler

Question

So this is (I think) a premiere for python. A function that translates brainfuck code to python code. It does a few optimizations (It chains +,-,>,< together to one operation). I don't think you can do more optimizations, but I am open for ideas. At the beginning of the created source code there will be a few imports (defaultdict and getch) and a few function definitions (add, sub, putch) and obviously the data structures data and index. Is there anything I could improve? Anything else I could optimize away?

def translate(sourcecode):
    out = [
        (0, "from collections import defaultdict"),
        (0, "from msvcrt import getch"),
        (0, "putch = lambda x: print(chr(x), end='')"),
        (0, "data = defaultdict(int)"),
        (0, "index = 0"),
        (0, "def add(x):data[index] = (data[index] + x) % 256"),
        (0, "def sub(x):data[index] = (data[index] - x) % 256"),
    ]
    level = 0
    count = 0
    operation = None
    for c in sourcecode:
        if c == operation:
            count += 1
        else:
            if operation == "+":
                out.append((level, f"add({count!r})"))
            elif operation == "-":
                out.append((level, f"sub({count!r})"))
            elif operation == ">":
                out.append((level, f"index += {count!r}"))
            elif operation == "<":
                out.append((level, f"index -= {count!r}"))
            operation = None

            if c in "+-><":
                operation = c
                count = 1
            elif c == ".":
                out.append((level, "putch(data[index])"))
            elif c == ",":
                out.append((level, "data[index] = getch()[0]"))
            elif c == "[":
                out.append((level, "while data[index]:"))
                level += 1
            elif c == "]":
                assert level
                level -= 1
    return "\n".join("    " * indent + line for indent, line in out)

print(translate("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."))

_{(if you are not on windows, you need an alternative to the getch function)}

Answer 1

The way you define your various functions is inconsistent:

• you define add, sub, putch, yet use data[index] = getch()[0] directly in the generated code;
• you group together multiple +, -, <, and > but neither . nor , (not that this last one would be of great use but still, for the sake of consistency);
• you access global data into those functions;
• putch is defined using a lambda but add and sub uses def…

Since [ and ] are special anyway as they do more than producing a string, I'd rather choose to either:

• inline everything in the generated code;
• or only use functions that take data, index and count as parameters.

---

I would also generate code that respect some standard practices: defining a main function and wrapping its call into an if __name__ == '__main__': guard. This would mean starting level at 1 as you would generate code that is inside a def main():.

You should also take a look at textwrap.dedent to simplify your header (and thus footer too) generation.

And since you are using formated strings, you could make directly use of the variable width alignment such as f'{"": >{level*4}}rest of the code'.

---

Storing generated instructions into a list that is returned at the end feels like your function would benefit from being turned into a generator. Especially if you plan on writing the generated string to a file, this would help interleaving computation and waiting for I/O.

---

Lastly your assertion feels off as they can be turned off at runtime. Instead I would raise a real exception such as ValueError with a proper error message.

---

Proposed improvements with code inlined:

import itertools
from textwrap import dedent
from contextlib import suppress


BYTECODES = {
        '+': '{0: >{1}}data[index] = (data[index] + {2}) % 256',
        '-': '{0: >{1}}data[index] = (data[index] - {2}) % 256',
        '<': '{0: >{1}}index -= {2}',
        '>': '{0: >{1}}index += {2}',
        '.': '{0: >{1}}for _ in range({2}):\n{0: >{1}}    print(chr(data[index]), end="")',
        ',': '{0: >{1}}for _ in range({2}):\n{0: >{1}}    data[index] = getch()[0]',
}


def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    yield from itertools.zip_longest(a, b)


def compile(sourcecode):
    yield dedent("""\
            from collections import defaultdict
            from msvcrt import getch


            def main():
                index = 0
                data = defaultdict(int)""")

    level = count = 1
    for operation, next_operation in pairwise(sourcecode):
        if operation == '[':
            yield f'{"": >{level*4}}while data[index]:'
            level += 1
        elif operation == ']':
            level -= 1
            if level < 1:
                raise ValueError('Unbalanced brackets, found ] before opening [')
        elif operation == next_operation:
            count += 1
        else:
            with suppress(KeyError):
                yield BYTECODES[operation].format('', level * 4, count)
            count = 1

    yield dedent("""\


            if __name__ == '__main__':
                main()""")


def translate(sourcecode):
    return '\n'.join(compile(sourcecode))


if __name__ == '__main__':
    code = '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
    for line in compile(code):
        print(line)

    print('*------*')
    print(translate(code))

Proposed improvements with functions defined:

import itertools
from textwrap import dedent
from contextlib import suppress


BYTECODES = {
        '+': '{0: >{1}}add(data, index, {2})',
        '-': '{0: >{1}}sub(data, index, {2})',
        '<': '{0: >{1}}index -= {2}',
        '>': '{0: >{1}}index += {2}',
        '.': '{0: >{1}}putchar(data, index, {2})',
        ',': '{0: >{1}}getchar(data, index, {2})',
}


def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    yield from itertools.zip_longest(a, b)


def compile(sourcecode):
    yield dedent("""\
            from collections import defaultdict
            from msvcrt import getch


            def add(data, index, x):
                data[index] = (data[index] + x) % 256


            def sub(data, index, x):
                data[index] = (data[index] - x) % 256


            def putchar(data, index, x):
                for _ in range(x):
                    print(chr(data[index]), end='')


            def getchar(data, index, x):
                for _ in range(x):
                    data[index] = getch()[0]


            def main():
                index = 0
                data = defaultdict(int)""")

    level = count = 1
    for operation, next_operation in pairwise(sourcecode):
        if operation == '[':
            yield f'{"": >{level*4}}while data[index]:'
            level += 1
        elif operation == ']':
            level -= 1
            if level < 1:
                raise ValueError('Unbalanced brackets, found ] before opening [')
        elif operation == next_operation:
            count += 1
        else:
            with suppress(KeyError):
                yield BYTECODES[operation].format('', level * 4, count)
            count = 1

    yield dedent("""\


            if __name__ == '__main__':
                main()""")


def translate(sourcecode):
    return '\n'.join(compile(sourcecode))


if __name__ == '__main__':
    code = '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
    for line in compile(code):
        print(line)

    print('*------*')
    print(translate(code))

As you can see, differences are minimal but generated code feels neater for the second version. I also kept the translate function for ease of use but the generator is simple enough to use on its own.

Answer 2

I don't think you can do more optimizations, but I am open for ideas.

Oh, you can do a lot more optimization, if you really want! Here are some ideas. To implement some of these, you have to rework your program logic. Instead of creating a new line of Python code for every character you read, you need to parse the program into an abstract syntax tree, and then look for some patterns in there to do peephole optimizations (those are the obvious optimizations that are simple to perform even when you are evaluating Brainfuck with a pen and paper).

• Combine instructions
  • Combine successive increments and decrements, i.e. +- should be a no-op, ++++- should be an increment by three.
  • Combine pointer increments as well (< and > should be combined similar to the previous item in this list.)
  • The loop [-] can be replaced by some code that sets the current cell to zero.
  • Remove increments or decrements overwritten by the input operator ,. For instance, +++, can just be translated to , because the previous value will be lost.
• Simplify loops and eliminate code
  • Skip the loops in the cells that are known to be zero. For instance, let's say there's a Brainfuck program like this: [,.+-><]+, you can skip the first loop because the in most Brainfuck implementations (including yours) the cells are initialized with zeroes.
  • Skip successive loops. [Foo][Bar], for example, should be translated as [Foo] because if you are exiting a loop, you will never enter the second one, as the cell is a known zero.
  • Detect loops that do multiplication and replace them by multiplication statements. For instance, [->+++<] multiplies the current cell by three and moves the value to the next cell.
• Combine all of the previous optimizations for greater effect. For example, you can combine the [-]-elimination and +-combination to reduce [-]+++ into one statement that directly sets the cell to three. (As opposed to doing it in two steps, i.e. setting it to 0 and incrementing by 3.)

For more on Brainfuck optimization, follow this link.