BrainF**k interpreter in python

Question

Here's what I've come up with:

def bf_interpreter(code: str) -> str:
    """
    Interprets BrainF**k code

    Examples:
        ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
        Hello World!

        +++++>++++[<+>-]++++++++[<++++++>-]<.
        9

    """

    outputs = []

    ptr = 0

    values = [0]
    length = 1

    brackets = []

    index = 0
    code_length = len(code)

    while index < code_length:
        char = code[index]

        while length <= ptr:
            length += 1
            values.append(0)

        if char == '>': ptr += 1
        if char == '<': ptr -= 1

        if char == '+': values[ptr] = (values[ptr] + 1) % 256
        if char == '-': values[ptr] = (values[ptr] - 1) % 256

        if char == '[':
            brackets.append(index)

        if char == ']':
            if values[ptr] == 0:
                brackets.pop()
            else:
                index = brackets[-1]

        if char == '.':
            outputs.append(chr(values[ptr]))

        if char == ',':
            values[ptr] = ord(input())

        index += 1

    return ''.join(outputs)

How do I make this look better? (More consistent, as well as strictly following PEP 8 conventions)

Answer 1

All of your if char == '>': ptr += 1 and similar checks should use elif after the first check. By using if for all of the checks, you're forcing them all to run, even once you've found a match. This is wasteful because the checks are necessarily exclusive of each other. Once one check is true, none of the other checks can be. For example, you should have:

if char == '>': ptr += 1
elif char == '<': ptr -= 1

elif char == '+': values[ptr] = (values[ptr] + 1) % 256
elif char == '-': values[ptr] = (values[ptr] - 1) % 256

Now the checks stop once a match is found which prevents unnecessary equality checks.

---

I'd also try to break this down into a few functions to help testing. Right now, you can only test bf_interpreter as one whole. You could have a function that takes the current character, and the state of the program (the brackets, ptr, outputs...), and returns a new state. That way you can easily test for a given state if a certain command produces a correct new state.

---

I'm assuming this loop is just to add padding so you don't go off the end of the slots?:

while length <= ptr:
    length += 1
    values.append(0)

You could make that a little neater by just using math and some concatenation. You could also just get rid of length and use len(values):

needed = ptr - len(values)
values += [0] * needed

ptr - len(values) calculates how many slots are needed, then [0] * needed produces that many 0s, and += adds them to values. If needed is negative, [0] * needed will produce [], and essentially cause no change.

If you want to avoid the temporary list that [0] * needed creates, you could replace that with:

values += (0 for _ in range(needed))

Now += just pulls from a generator that produces values as needed.

---

And then, just like how you don't need length, you don't need code_length either. len(code) is fine; len runs in constant time. You don't need to cache it for performance reasons.

Here's some timings to show the difference in runtime this can cause:

import timeit

TEST_CODE = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."

>>> timeit.timeit(lambda: bf_interpreter_orig(TEST_CODE), number=int(2e5))  # Two hundred thousand tests
77.3481031  # Takes 77 seconds

>>> timeit.timeit(lambda: bf_interpreter_len(TEST_CODE), number=int(2e5))
88.93794809999997

Where bf_interpreter_orig is your original code, and bf_interpreter_len is your original code but using len.

Yes, there's a difference. Note though, that's a ~11 second difference across 200,000 calls. That works out to roughly 58 microseconds per call to the interpreting function.

Unless you're calling bf_interpreter hundreds of thousands of times in a tight loop, the difference is unlikely to matter. This also likely has nothing to do with the fact that you're requesting a length, and more to do with one extra function call. Function calls aren't super fast in Python. Likely any extra call to any function would have similar effects.

Answer 2

+1 on specifying argument code: str and return type -> str.

I implemented a class seen below which has the advantage of seeing chars and their corresponding functions at a glance. Adding new chars if need be is incredibly easy.

        self.actions = {
            '>': self.greater_than,
            '<': self.less_than,
            '+': self.plus,
            '-': self.minus,
            '[': self.left_bracket,
            ']': self.right_bracket,
            '.': self.dot,
            ',': self.comma
        }

You can use a

try:
    ...
except KeyError:
    ...

to detect unrecognised chars.

Complete Class

class BFInterpreter:
    def __init__(self):
        self.outputs = []

        self.ptr = 0

        self.values = [0]
        self.length = 1

        self.brackets = []

        self.index = 0

    def greater_than(self):
        self.ptr += 1

    def less_than(self):
        self.ptr -= 1

    def plus(self):
        self.values[self.ptr] = (self.values[self.ptr] + 1) % 256

    def minus(self):
        self.values[self.ptr] = (self.values[self.ptr] - 1) % 256

    def left_bracket(self):
        self.brackets.append(self.index)

    def right_bracket(self):
        if self.values[self.ptr] == 0:
            self.brackets.pop()
        else:
            self.index = self.brackets[-1]

    def dot(self):
        self.outputs.append(chr(self.values[self.ptr]))

    def comma(self):
        self.values[self.ptr] = ord(input())

    def evaluate(self, code):
        self.code = code
        self.code_length = len(self.code)

        self.actions = {
            '>': self.greater_than,
            '<': self.less_than,
            '+': self.plus,
            '-': self.minus,
            '[': self.left_bracket,
            ']': self.right_bracket,
            '.': self.dot,
            ',': self.comma
        }

        while self.index < self.code_length:
            char = self.code[self.index]

            while self.length <= self.ptr:
                self.length += 1
                self.values.append(0)

            self.actions[char]()

            self.index += 1

        return ''.join(self.outputs)

Usage

bf = BFInterpreter()
print(bf.evaluate('+++++>++++[<+>-]++++++++[<++++++>-]<.'))

code has been specified as an argument in the evaluate method rather than in the constructor to be able to evaluate without creating new objects.