3
\$\begingroup\$

What do you think of my Brainf*ck interpreter? What else can be done to increase speed?

#!/usr/bin/env python3

class InfiniteArray:
    def __init__(self):
        self.pstack, self.nstack = [], []
    def __getitem__(self, index):
        s = self.pstack if index >= 0 else self.nstack
        i = index if index >= 0 else -index + 1
        if i >= len(s):
            return 0
        return s[i]
    def __setitem__(self, index, value):
        s = self.pstack if index >= 0 else self.nstack
        i = index if index >= 0 else -index - 1
        if i >= len(s):
            s.extend([0 for _ in range(len(s), i+1 + 100)])
        s[i] = value
    def __str__(self):
        return str(list(reversed(self.nstack))) + ' | ' + str(self.pstack)


class StateMachine:
    def __init__(self, code, jump_table, debug=False):
        self.arr = InfiniteArray()
        self.pointer = 0
        self.i = 0
        self.code = code
        self.jt = jump_table
        self.debug = debug
        self.instrcount = 0

    def putc(self):
        from sys import stdout
        stdout.write(chr(self.arr[self.pointer]))
        stdout.flush()

    def getc(self):
        from sys import stdin
        c = stdin.read(1)
        self.arr[self.pointer] = ord(c)

    def plus1(self):
        self.arr[self.pointer] += 1

    def minus1(self):
        self.arr[self.pointer] -= 1

    def mvright(self):
        self.pointer += 1

    def mvleft(self):
        self.pointer -= 1

    def matchl(self):
        if not self.arr[self.pointer]:
            self.i = self.jt[self.i]

    def matchr(self):
        if self.arr[self.pointer]:
            self.i = self.jt[self.i]

    def nextcell(self):
        self.i += 1
        self.instrcount += 1

    def __str__(self):
        return str(self.arr) + '\n\n' + ''.join(map(str, self.code))

    def run(self):
        import datetime as dt
        ops = {'+': self.plus1,
               '-': self.minus1,
               '>': self.mvright,
               '<': self.mvleft,
               '.': self.putc,
               ',': self.getc,
               '[': self.matchl,
               ']': self.matchr }
        start = dt.datetime.now()
        while self.i < len(self.code):
            c = self.code[self.i]
            ops[c]()
            self.nextcell()
            if self.debug:
                print(self)
        end = dt.datetime.now()
        print(int(self.instrcount/(end-start).microseconds * 10**6), "instr/second")


def extract(file):
    code = []
    for c in file.read():
        if c in '><+-.,[]':
            code.append(c)
    jump_table = dict()
    stack = []
    count = 0
    for i, c in enumerate(code):
        if count < 0:
            raise SyntaxError("2muh ]")
        if c == '[':
            stack.append(i)
            count += 1
        if c == ']':
            jump_table[i] = stack[-1]
            jump_table[stack[-1]] = i
            stack.pop()
            count -= 1
    if count > 0:
        raise SyntaxError("unmatched [ at positions " + ', '.join(map(str, stack)))

    return code, jump_table

def main():
    from sys import argv
    options = {'debug': False}
    for i, name in enumerate(argv[1:]):
        print('no. {}: {}'.format(i+1, name))
        try:
            if name == '-':
                f = open('/dev/stdin')
            elif name.startswith('-'):
                if name == '-debug':
                    options['debug'] = True
                continue
            else:
                f = open(name)
        except:
            print("Error: no such file :<")
            continue
        try:
            code, mt = extract(f)
            f.close()
        except SyntaxError as e:
            print("Error:", e)
        finally:
            s = StateMachine(code, mt, debug=options['debug'])
            s.run()

if __name__ == '__main__':
    main()
\$\endgroup\$
  • \$\begingroup\$ I don't mean to be a stickler, but it should be noted that brainfuck doesn't print out errors, or debug. \$\endgroup\$ – tuskiomi Jun 1 '17 at 18:22
3
\$\begingroup\$

This looks really nice to me, I have just a few minor remarks.

Imports buried in the code

Many imports are buried in some functions, for example in putc and getc, and I don't see a good reason for that. It would be better to import the required modules at the top.

Complicated command line argument parsing

The command line argument parsing in the main function looks a bit complicated. I think it should be possible to refactor that to make it easier to read, and using a context manager for the input file handling.

Mutually exclusive if statements

The second if here should be an elif:

if c == '[':
    stack.append(i)
    count += 1
if c == ']':
    jump_table[i] = stack[-1]
    jump_table[stack[-1]] = i

Don't repeat yourself

The assignment of s and i are almost identical in these two functions:

def __getitem__(self, index):
    s = self.pstack if index >= 0 else self.nstack
    i = index if index >= 0 else -index + 1
    # ...

def __setitem__(self, index, value):
    s = self.pstack if index >= 0 else self.nstack
    i = index if index >= 0 else -index - 1
    # ...

I would add some helper functions to reduce the duplication.

Too dense formatting

It would be easier to read the code with a blank line between functions.

\$\endgroup\$
  • \$\begingroup\$ I was asking primarily about performance, but nonetheless good answer. \$\endgroup\$ – enedil Jun 1 '17 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.