4
\$\begingroup\$

Here's the first, straightforward version of BF interpreter:

def run(step_limit, memo, m_i, code):
    """ Runs valid BF code. """

    if len(code) == 0:
        return

    i = 0
    for step in range(step_limit):
        cmd = code[i]

        # Switch - case
        if cmd == '+':
            memo[m_i] += 1
        elif cmd == '-':
            memo[m_i] -= 1
        elif cmd == '>':
            m_i += 1
        elif cmd == '<':
            m_i -= 1
        elif cmd == '.':
            print (memo[m_i])
        elif cmd == ',':
            memo[m_i] = int ( input ( "Input: " ) )
        elif cmd == '[':
            if memo[m_i] == 0:
                i = code.find(']', i, len(code) )
        else: # if cmd == ']'
            if memo[m_i] != 0:
                i = code.find('[', 0, i )

        i += 1
        if i == len(code):
            break

And the second one:

""" Second version of the same method. """
# I tried to use namedtuples but I failed. Using simple, usual tuples instead.

def plus (args):
    return args[1]+1, args[2]+1, args[3]

def minus (args):
    return args[1]+1, args[2]-1, args[3]

def rigth (args):
    return args[1]+1, args[2], args[3]+1

def left (args):
    return args[1]+1, args[2], args[3]-1

def output (args):
    print (args[2])
    return args[1]+1, args[2], args[3]

def u_input (args):
    return args[1]+1, int (input ("Input: ") ), args[3]

def loop_begin (args):
    if args[2] == 0:
        return args[0].find(']', args[1], len(args[0]))+1,args[2],args[3]
    else:
        return args[1]+1, args[2], args[3]

def loop_end (args):
    if args[2] != 0:
        return args[0].find('[', 0, args[1] )+1, args[2], args[3]
    else:
        return args[1]+1, args[2], args[3]

def nothing (args): # So that memo[m_i] wouldn't go out of index
    return args[1], args[2], args[3]

commands = {
    '+' : plus,
    '-' : minus,
    '>' : rigth,
    '<' : left,
    '.' : output,
    ',' : u_input,
    '[' : loop_begin,
    ']' : loop_end,
    ' ' : nothing }

def run(step_limit, memo, m_i, code):
    """ Runs valid BF code. """

    if len(code) == 0:
        return

    code += ' ' # So that memo[m_i] wouldn't go out of index
    i = 0
    for step in range(step_limit):
        args = (code, i, memo[m_i], m_i)
        i, memo[m_i], m_i = commands[ code[i] ] ( args )
        if args[1] == len(args[0]) - 1 or code[i] == ' ':
            break

# Now we have to add space after program so that memo[m_i] wouldn't go out of index
run(1000000000, [478234, 5161845], 1, "[-<+>]<. ") # TEST, adds two numbers

Yes, I know I should have used dictionaries to increase readability because now the indexes are horrible, but this is just a quick concept.

Question: would you ever prefer second structure over the first one, and under what conditions? Maybe you know a solution better than both of these versions?

Some of my thoughts:

  • Second version is 2x slower. Benchmarked with run(1000000000, [478234, 5161845], 1, "[-<+>]<. "), finishes in 73.5s while first one does the job in 36s.
  • In my opinion, second version is more decompositioned, thus easier to maintain and expand in very big projects, but not worthy the effort in the small ones.
\$\endgroup\$
1
\$\begingroup\$

A few coding points:

  1. I think you could simplify the arguments a lot by using kwargs, rather than passing a tuple of arguments.

  2. Having your dict in the global namespace, rather than the function's local namespace, will slow it down considerably.

  3. 0 is False, so if args[2] != 0: can just be if args[2].

  4. For unused variables, like step, I consider it better to mark it as such by using _ as the variable name.

  5. Half of the functions are simple one-liners that can use lambdas.

  6. Although half of the functions can be lambdas, some of them would work better by doing in-place operations on memo.

  7. If you want to search until the end, you don't need to specify an end to find.

  8. You add 1 to i in every case, so that can be moved out of the functions.

As for your questions:

There are three major situations where I would use the dict structure.

  1. The functions can either be lambdas or external functions that are short and easy-to-read as dict values. Usually this is better with only one or a few consistent arguments.

  2. The functions are so long that putting them in an if chain makes it hard to keep track of the flow. Again, usually this is better with only one or a few consistent arguments.

  3. There are a huge number of possible inputs, which makes for an overly long if test chain, but where there are again only one or a few consistent arguments.

The problem with your case is that this is in-between, they are simple enough that you can follow the flow easily in an if test, but they are not all so simple that they can be put into lambdas without sacrificing clarity (it is possible to put all but one in lambdas, but half would be really hard to read). Further, there are not so many situations that it becomes hard to read in an if chain (although it is getting close), and there are enough arguments (or enough inconsistency in the arguments) that it is getting to the point where I would not use the dict approach even if all the other criteria were satisfied (although again it is kind of borderline).

Ultimately, what it comes down to is whether the dict approach helps or hurts readability. In your case, I think it hurts it. If the criteria I described above hold, then it will probably help it (although you really need to look on a case-by-case basis, since there will be corner cases either way).

\$\endgroup\$
1
\$\begingroup\$

If you want performance, then your best bet would be to avoid function calls by dispatching the commands using the if-elif chain. Brainfuck is a simple enough language that you can manageably fit all of the commands in one function. Writing each command as a separate function doesn't really improve the code much.


I'm much more concerned about correctness, though. Both of your interpreters are buggy.

  • Input/output: The . command is supposed to print the character corresponding to the ASCII code at a memory location. Instead, you are printing the decimal value of the number at that location. Similarly, the , command is supposed to read a single character and store its ASCII code. Instead, you are reading a line of input and interpreting it as a base-ten integer.
  • Looping: The [ and ] commands are both wrong. They are supposed to conditionally jump to their counterpart of a matching pair. You are making no attempt to match the brackets. As a result, your [ will break if loops are nested. Your ] will break if it's not the first loop in the program. See this answer for a suggestion on how to jump to matching brackets efficiently.
  • Termination: A Brainfuck program is supposed to end when the instruction pointer reaches the end of the code. A sensible loop could be:

    while 0 <= i < len(code):
        …
        i += 1
    
        # Optional mechanism to prevent infinite loops
        step_limit -= 1
        if step_limit == 0:
            break
    

The second one program has additional quality issues.

  • Parameter passing: I'm puzzled why you pass args as a tuple rather than as three named parameters. Rather than return args[1]+1, args[2]+1, args[3], you should write:

    def plus(ip, memo, m_i):
        return ip + 1, memo[m_i] + 1, m_i
    
  • Function naming: right is misspelled as rigth.
  • Handling unrecognized commands: All characters other than +, -, <, >, ., ,, [, and ] are supposed to be treated as comments. Your second treats spaces as an "exit" command, and crashes on all other code.
  • PEP 8 compliance: There should be no space preceding an opening parenthesis. The commands constant should be named using ALL_CAPS.
\$\endgroup\$

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.