Brainfuck interpreter written in PHP Jan 29, 2015

brainfuck  php  interpreter 

Brainfuck redered mandlebrot

Why write a PHP Brainfuck interpreter?

I visited the PHPBenelux 2015 conference last weekend where I followed the Cute little interpreters track by Anthony Ferrara and Igor Wiedler. It was an interesting talk, we started implementing our own interpreter for a simple language that had only a couple operators. I noticed the similarity with brainfuck, so I decided to see if I could convert it to a brainfuck interpreter.

The language

Brainfuck has 8 operators and is Turing complete, you can find some examples on the web, which came in handy because writing your own will take a lot of work. I even found a Brianfuck compiler en highlevel language to brainfuck converter.

Brainfuck operations screenshot from wikipedia Brainfuck operations

Goal

My initial goal was to get “Hello World!” running. It uses all the operations and is in itself a cool little program. You can find the source with comments below. This will give you an idea how hard it is to even write a simple program with Brainfuck.

[ This program prints "Hello World!" and a newline to the screen, its
  length is 106 active command characters [it is not the shortest.]

  This loop is a "comment loop", it's a simple way of adding a comment
  to a BF program such that you don't have to worry about any command
  characters. Any ".", ",", "+", "-", "<" and ">" characters are simply
  ignored, the "[" and "]" characters just have to be balanced.
]
+++++ +++               Set Cell #0 to 8
[
    >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
    [                   as the cell will be cleared by the loop
        >++             Add 2 to Cell #2
        >+++            Add 3 to Cell #3
        >+++            Add 3 to Cell #4
        >+              Add 1 to Cell #5
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop till Cell #1 is zero; number of iterations is 4
    >+                  Add 1 to Cell #2
    >+                  Add 1 to Cell #3
    >-                  Subtract 1 from Cell #4
    >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
]                       Loop till Cell #0 is zero; number of iterations is 8

The result of this is:
Cell No :   0   1   2   3   4   5   6
Contents:   0   0  72 104  88  32   8
Pointer :   ^

>>.                     Cell #2 has value 72 which is 'H'
>---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
+++++++..+++.           Likewise for 'llo' from Cell #3
>>.                     Cell #5 is 32 for the space
<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
<.                      Cell #3 was set to 'o' from the end of 'Hello'
+++.------.--------.    Cell #3 for 'rl' and 'd'
>>+.                    Add 1 to Cell #5 gives us an exclamation point
>++.                    And finally a newline from Cell #6

Creating the first working interpreter turned out to be a fairly simple task, the only problems I had were with the [ and ] operations. After I finishing my initial interpreter I decided to add some optimisation becayse my initial version was very slow.

Optimizations

  • Cache loop begin and end statements.

    This saves a lot of processing because the interpreter doesn’t have to go look for a beginning or ending statement, it can just jump to the right location.

  • Convert sequential +/-/</> commands to shorter custom op.

    As an experiment I converted long chains of commands to a custom operator.

    ++++++++ became !+8

    It had a small performance improvement (5%) on some scripts, but not what I was expecting.

These optimizations made the interpreter about 50% faster.

Conclusion

It was a fun challenge writing this, my next project will be a interpreter written in Rust. Why Rust? After writing the interpreter in PHP I came to the conclusion that writing one is a good way to learn a language. The projects is small and forces you to learn string manipulation and basic commands. Also apparently strings in Rust are a lot of fun.

Github repository

If you have any comments, suggestions or questions, please let me know by leaving a comment.

This interpreter is utterly not performant! The Mandelbrot image you see took a half hour to render. (3184466242 operations processed)


Comments