Table of contents
- What is Brainfuck
- 8 primitives!!
- Writing a Brainfuck interpreter
- Implementation
- Syntax
- Loops in a method chain
- Learnings and next step
![Hello World! [β]](../images/brain-fuck-hello-world.png)
I have been sick for the last couple of days, and 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 such thing 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. Since its an esolang it means it's likely not a language an everyday developer will want to use for work.
8 primitives!!
Think about it 8 keywords!! And it's said to be Turing complete, meaning it should be able to tackle the same problems we throw at modern languages. But the interesting fact here is, although Brainfuck is easy to learn it's not exactly easy to create a program in it. This makes it a perfect language to challenge one's 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 Devless, it's instead based on a DSL made up of method chains.
Yes, there are arguments that pushing method chains to handle external logic makes it's complicated and loses 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 away 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 fewer overheads.
Implementation
01:
02: include 'brainFuck.php';
03:
04: $brainFuck = new brainFuck();
05:
06: $brainFuck
07: ->inc(10) //initialize counter (cell #0) to 10
08:
09: ->label('blckA') //use loop to set 70/100/30/10
10: ->shiftFwd()->inc(7) //add 7 to cell #1
11: ->shiftFwd()->inc(10) //add 10 to cell #2
12: ->shiftFwd()->inc(3) //add 3 to cell #3
13: ->shiftFwd()->inc(1) //add 1 to cell #4
14: ->shiftBck(4)->dec() //decrement counter (cell #0)
15: ->jmp('blckA')
16:
17: ->shiftFwd()->inc(2)->output() //print 'H'
18: ->shiftFwd()->inc(1)->output() //print 'e'
19: ->inc(7)->output() //print 'l'
20: ->output() //print 'l'
21: ->inc(3)->output() //print 'o'
22: ->shiftFwd()->inc(2)->output() //print ' '
23: ->shiftBck(2)->inc(15)->output() //print 'W'
24: ->shiftFwd()->output() //print 'o'
25: ->inc(3)->output() //print 'r'
26: ->dec(6)->output() //print 'l'
27: ->dec(8)->output() //print 'd'
28: ->shiftFwd()->inc()->output() //print '!'
29: ->shiftFwd()->output() //print '\n'
30:
31: ;A hello world example will look like the above once my method chain implementation is done. You can find my implementation here repo [β]
Syntax
Memory Stack
![sample memory stack [β]](../images/brain-fuck-memory-stack.png)
So a Brainfuck interpreter will need a memory stack to hold data and a memory pointer to access cells within the stack. In code:
01: class brainFuck
02: {
03: public $argsStack = [];
04: public $memoryStack = [];
05: public $memoryPointer = 0;
06: public $executionStack = [];
07: public $execPrimitive = false;
08:
09: public function __construct()
10: {
11: $this->memoryStack = array_fill(0, 30000, null);
12: }Input (,)
To take input in Brainfuck you use a comma , and note the input is converted to its ASCII equivalence. In code:
01: /**
02: * take character and convert to ASCII.
03: *
04: * @param string $method
05: *
06: * @return instance
07: */
08: private function input($inputValue)
09: {
10: $this->memoryStack[$this->memoryPointer] = ord($inputValue);
11:
12: return $this;
13: }Output (.)
A dot . will print out the character equivalence of a memory cell's value The value printed is the one from the current position of the memory pointer. In code:
01:
02: /**
03: * take ASCII and convert to character.
04: *
05: * @param bol $print
06: *
07: * @return instance
08: */
09: private function output($print = true)
10: {
11: $output = chr($this->memoryStack[$this->memoryPointer]);
12: if ($print) {
13: echo $output;
14: }
15:
16: return $this;
17: }Increment (+)
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:
01: /**
02: * increment cell value.
03: *
04: * @param string $num
05: *
06: * @return instance
07: */
08: private function inc($num = 1)
09: {
10: $this->memoryStack[$this->memoryPointer] += $num;
11:
12: return $this;
13: }Decrement (-)
You may also decrement the value contained in a cell by using the β keyword. In code:
01: /**
02: * decrement cell value.
03: *
04: * @param string $num
05: *
06: * @return instance
07: */
08: private function dec($num = 1)
09: {
10: $this->memoryStack[$this->memoryPointer] -= $num;
11:
12: return $this;
13: }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:
01: /**
02: * increment memory counter.
03: *
04: * @param string $label
05: *
06: * @return instance
07: */
08: private function shiftFwd($num = 1)
09: {
10: $this->memoryPointer += $num;
11:
12: return $this;
13: }Back Shift (<)
A back shift moves the pointer a cell behind. The more shifts you have the further it goes. In code:
01: /**
02: * decrease memory counter.
03: *
04: * @param string $num
05: *
06: * @return instance
07: */
08: private function shiftBck($num = 1)
09: {
10: $this->memoryPointer -= $num;
11:
12: return $this;
13: }Looping ([])
Looping in Brainfuck is done using [] where code within the block will run until the current memory cell becomes 0.
For example, ++[>+<-] will increase the current cell by 2 then move to the next cell and add 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. Now in code:
01: /**
02: * mark beginning of loop.
03: *
04: * @param string $label
05: *
06: * @return instance
07: */
08: private function label($label)
09: {
10: return $this;
11: }
12:
13: /**
14: * mark end of loop.
15: *
16: * @param string $label
17: *
18: * @return instance
19: */
20: private function jmp($label)
21: {
22: return $this;
23: }First I replaced [ with label and ] with jmp I realized I will have to do more to identify the opening and end of loops. So I decided to go with the good old label and 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 of 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 play back when you need to. Anyways here is the code implementation for the loop and the execution of the stack.
![Stacking the execution sequence brainfuck [β]](../images/stacking-brain-fuck-instructions.png)
![Executing and looping over the stack [β]](../images/executing-stack.png)
Learnings and next step
![[β]](../images/brainfuck-conclusion.png)
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 loops for the Devless DSL.
I wrote this post to serve as a doc to the repo [β] for the interpreter.
Anyways am out for now β¦.
Here is another article you might like π "Diary Of Insights: A Documentation Of My Discoveries"