BrainFuck Interpreter using method chaining
I have been sick for the last couple of days, and for most part of it I have not been able to get much work done. So in the spirit of being productive I decided to take a look at the little things I have long been planning to do. One of such things was to look at Brainfuck lang .
What is Brainfuck
Brainfuck is an esolang with just 8 primitives. This means there are just 8 keywords to learn to be able to write programs in brainfuck but then since its an esolang it means its not a language a working developer will want to use.
Think about it 8 keywords!! And its said to be turing complete, meaning it should be able to tackle the same problems we throw modern languages at. But the interesting fact here is, although brainfuck is easy to learn its not exactly easy to create a program in it . This makes it a perfect language to challenge ones mind. Also because it has fewer keywords, writing either a compiler or interpreter for this language should be easier compared to writing a program in it.
Writing a Brainfuck interpreter
The obvious way to implement this is to write a parser and a lexer or you may use existing ones . But these days I have been caught up in the fever of creating DSLs using method chains. For example instead of creating a parser for a new syntax for Devless its instead based on a DSL made up of method chains.
Yes there are arguments that pushing method chains to handle external logic makes its complicated and looses it value but then if you created a chain that guides the flow of external programs and not get in its business you will have a far less complex DSL. As a matter of fact in the case of Devless most users are now moving from writing logic in their preferred language to using the inbuilt DSL .
Some reasons I also chose to go with method chains for the implementation of the interpreter is the fact that I get to treat creating the interpreter as a normal program using a class and not as a language to be created, This frees up my brain plus my interpreter will have far less overheads.
With the final implementation
done using a PHP method chain
an hello world example in it
looks like the image on the
left . You can find my implementation @ repo
So a brainfuck interpreter will need a memory stack to hold data and a memory pointer to access cells on the stack. In code:
To take an input in brainfuck you use a comma
, , and note the input is converted to its ASCII equivalence. In code:
. will print out the character equivalence of a memory cells value at where the memory pointer is pointing. In code:
You may also increase the value of a cell in the memory stack using the
+ keyword the more pluses you have the high the value that is added to the cell. In code:
You may also decrement the value contained in a cell by using the
— keyword. In code:
Forward Shift (>)
In other to move the pointer to another cell you need to perform a shift. A forward shift
> moves one cell ahead. In code:
Back Shift (<)
A back shift moves the pointer a cell behind. The more shifts you have the further it goes. In code:
Looping in brainfuck is done using
 where code within the the block will run until the the current memory cell is set to 0. eg:
++[>+<-] This will increase the current cell by 2 then move to the next cell and adds one then move back to the first cell and decrement it by one then the loop goes on for the second time till the first cell is 0. You can try the code sample here.Now in code:
First of I replaced
[ with label and
] with jmp I realised I will have to do more to identify the opening and end of loops. So I decided to go with the good old
goto implementation. But then wait you will notice both the label and jmp have no code just returns the instance of the class!!
Loops in a method chain
Well there is not exactly an obvious way to loop in method chaining. When you chain a method say
$instance->one()->two()->three() , method
two will not know method
three is next on the chain also going back a step in the chain without extra work within the chain is impossible. So instead of executing the chain immediately I stopped the execution on the method calls and stored their execution sequence instead. With this I can choose which method to execute and when. This is more like having a video and being able to playback when you feel like it. Anyways here is the code implementation for the loop and the execution of the stack.
Learnings and next step
Clearly looking at the image above technically the method chained version does not use the exact keyword representation but heck brainfuck doesn’t have an official spec to follow so my implementation still holds.
Secondly I have never thought of skipping the parser lexer process for method chaining, and now that I have looping, conditionals and IO figured out it means I can have a turing complete language all with method chains. The fun part is that even if I go back to dealing with lexers and parsers, I can implement a class structure using that, then with that layer of abstraction I can implement DSLs and languages without having to go low anymore. Also am thinking of implementing the loops for the Devless DSL.
I wrote this post to serve as a doc to the repo for the interpreter. And oh one other thing am looking at is writing posts or keeping journals on changes I make to an existing codebase as I work , I want to know how effective that is over commenting :).
Anyways am out for now ….