Crazy Programming Languages Challenge - Part 1 - Brainfuck

I have been wanting to do this challenge for so long! The time has finally come.

Wikipedia, the fountain of all human knowledge, has a very long list of programming languages.

They also have a list of programming languages that are "esoteric" (nope, I have not hear of that word either until now). These are languages that are less conventional than the mainstream programming languages.

For your enjoyment and my own, I decided to go down this list and pick out five try:

  1. Brainfuck <- You are here
  2. LOLCODE
  3. Whitespace
  4. Piet
  5. Malbolge

Each week I will post my experience of 1 of these languages.

Today I kick it all off with Brainfuck.

Overview

I started with this post to help familiarise myself with the basics of Brainfuck. The language itself is really rather simple.

There an internal array, kind of like a tape, with 30,000 cells. There is a pointer that points to cell number 1 when the program starts. Each cell can contain a number and hold up to 1 byte of data.

There are just 8 commands that you can do:

< and > move the internal pointer left or right of the current cell.

+ increments the current cell's value by 1. - decrements by 1.

. prints the content of the current cell as an ASCII character.

, reads a single input into the current cell (I did not try this and so am not sure of its behaviour).

Then you have [ and ]. These enable looping. If the value of the current cell is 0 when it reaches [, it will skip to the corresponding ]. Otherwise, it will go to the next instruction within the block. If the current cell has 0 when it reaches ], it will exit the the loop to the next instruction, otherwise, it will return to the corresponding [. This is essentially a while loop but it can be confusing when thinking of the current position of the tape and the values in them (which is a running theme).

So overall, every character that is not ><+-.,[], is ignored. This includes all white space and any comments that you may write outside of the program.

Installing and Running

I decided to use this compiler to run my code because it appeared to be the most straightforward to set and use. Go to the link and save the page as a .asm file.

You will then need to install nasm:

sudo apt install nasm

Next run:

sudo nasm -f bin -o bf /path/to/bf.asm && sudo chmod +x bf

This will compile the file you just downloaded and enable you to execute it. You simply have to run ./bf from the directory you put it.

Now to run our first program.

The article that I linked gave a great simple example of a program:

++++++ [ > ++++++++++ < - ] > +++++ .

What this does is print the letter "A".

How?

The internal pointer begins in position 1. The increments the value in that cell by 1 6 times, therefore we get the value, 6, in the first cell.

Then we have a loop inside the square brackets. The loop starts by going to position 2, and then incrementing by 10. It then goes back to position 1 and decrements once.

So after the first iteration, our tape looks like this (the * shows the position of the pointer):

| 1 | 2  | 3 | 
| 5 | 10 | 0 |
| * |    |   |

It then goes back to the beginning of the loop and starts the whole thing again: go to position 2, increment by 10, go back to position 1, decrement by 1.

The loop continues until it sees 0 in the current cell that it is in at the end of the block (at the closing ]). In this case, it is when position 1 has 0 in it. The tape would look like this:

| 1 | 2  | 3 | 
| 0 | 60 | 0 |
| * |    |   |

The final part put the pointer into position 2, and increments by 4. So now we have:

| 1 | 2  | 3 | 
| 0 | 64 | 0 |
|   | *  |   |

64 happens to be the ASCII character code for the letter A. The very final thing, the . , prints what ever the pointer is on. In this case it is in position 2 and therefore the letter A is shown.

This could have been done equally with just 64 +s and a .. But this other solution demonstrates the level of think that you need to create readable programs. Also note that the spaces are ignored and are not needed.

To compile and run the code is simple. First the compiler command is:

/path/to/bf < /path/to/hello.b > /path/to/hello && chmod +x /path/to/hello

The part after && ensure that the program has the correct privileges to be executed.

So running all this:

Easy.

Building "Hello, World!"

I want to have to console print "Hello, World!" with the correct punctuation. So using the earlier example as a model, I first need to convert each character into ASCII number and then print them to the screen after generating.

The number that I need are

72 101 108 108 111 44 32 87 111 114 108 100 33

So, lets start with 72:

++++++++ [ > +++++++++ < - ] > .

This has the exact same logic as when we printed A. The difference is that since 72 is exactly 8 x 9, we do not have to do the extra adding once the loop is finished. If I run this, I see H printed onto the screen.

My tape now looks like this:

| 1 | 2  | 3 | 
| 0 | 72 | 0 |
|   |  * |   |

So now I do the next number, 101:

< ++++++++++ [ >> ++++++++++ << - ] >> + .

As you can see, I use position 1 as my counter and position 3 to store 101. So now my tape looks like this:

| 1 | 2  | 3   | 4 | 
| 0 | 72 | 101 | 0 |
|   |    | *   |   |

Next line, 2 ls:

<< +++++++++ [ >>> ++++++++++++ <<< - ] >>> ..

Same as before but with more arrows going between spaces as I move further down the tape. Also, you can see that I do 2 .s as I print the same letter twice in a row.

I kept going with this same logic until I had something like this:

<< +++++++++ [ >>> ++++++++++++ <<< - ] >>> ..
<<< ++++++++++ [ >>>> ++++++++++ <<<< - ] >>>> +++++++++++ .
<<<< +++++++++++ [ >>>>> ++++ <<<<< - ] >>>>> .
<<<<< ++++ [ >>>>>> ++++++++ <<<<<< - ] >>>>>> .
<<<<<< ++++++++ [ >>>>>>> +++++++++++ <<<<<<< - ] >>>>>>> - .
<<< . >>>>

The last line is the "o" in "World". As I have this stored previously, I simply move the pointer back to that position, print, then move it back again.

This is where it went wrong for me. As you can see, it is very easy to lose track of the where you are on the tape. Especially if you are going backwards and forwards.

Then I realised I was being silly. I did not need to store every single letter after I had printed them, only the ones that I want to reuse. So I only need to use 3 or 4 cells at most.

So I started again:

++++++++ [ > +++++++++ < - ] > . [-]

We are back to printing the letter H again. But you can see that I added [-] after I have printed. This effectively clears the current cell to 0 (remember the loop keeps going until the current cell at the ] is 0). So at this point, the tape looks like this:

| 1 | 2 | 3 | 4 | 
| 0 | 0 | 0 | 0 |
|   | * |   |   |

So, if we get to the "ll" again:

++++++++ [ > +++++++++ < - ] > . [-] 

< ++++++++++ [ > ++++++++++ < - ] > + .[-] < +++++++++ [ > ++++++++++++ < - ] > ..

So you can see for "e" we do exactly the same as the "H": get the number, print, then clear. For the "ll", we once again print twice. But as we want to reuse that letter later, we do not clear. So the next line:

< ++++++++++ [ >> ++++++++++ << - ] >> +++++++++++ .

Puts "o" into position 3:

| 1 | 2   | 3   | 4 | 
| 0 | 108 | 111 | 0 |
|   |     | *   |   |

Again, we want to keep "o" for later, so I don't clear it and use position 4 for the other letters:

<<< ++++ [ >>> ++++++++ <<< - ] >>> . [-]
<<< ++++++++ [ >>> +++++++++++ <<< - ] >>> - . [-]

At this point, we are printing:

Hello, W

And the tape looks like this:

| 1 | 2   | 3   | 4 | 
| 0 | 108 | 111 | 0 |
|   |     |     | * |

For the next letter, "o", we only need to go back to position 3 and print what is there. Also, we no longer need to store this letter so we can clear it and work in this cell:

< . [-]

So now we have

Hello, Wo

and the tape:

| 1 | 2   | 3 | 4 | 
| 0 | 108 | 0 | 0 |
|   |     | * |   |

So we carry on working in the 3rd cell, using cell 1 as the counter, the next letter is "r":

<< ++++++++++ [ >> +++++++++++ << - ] >> ++++ . [-] 

Now we are ready for "l" again. So as we are position 3, and "l" is stored in position 2, we simply have to go back 1 and print:

< . [-]

I no longer need this letter, so I can clear it and keep working here for the last 2 letters:

< ++++++++++ [ > ++++++++++ < - ] > .[-]
< +++ [ > +++++++++++ < - ] > .[-]

So if I now run this:

Woo!

Summary

So the overall program is like this:

++++++++ [ > +++++++++ < - ] > . [-] 
< ++++++++++ [ > ++++++++++ < - ] > + .[-]
< +++++++++ [ > ++++++++++++ < - ] > ..
< ++++++++++ [ >> ++++++++++ << - ] >> +++++++++++ .
<<< ++++ [ >>> ++++++++ <<< - ] >>> . [-]
<<< ++++++++ [ >>> +++++++++++ <<< - ] >>> - . [-]
< . [-]
<< ++++++++++ [ >> +++++++++++ << - ] >> ++++ . [-] 
< . [-]
< ++++++++++ [ > ++++++++++ < - ] > .[-]
< +++ [ > +++++++++++ < - ] > .[-]

Remember, the spaces and newlines are for us only. This could be minified to a single line.

There is also a much better written version of "Hello, World!" on the Wikipedia page that makes mine look terrible!

I found it to be an interesting challenge to think in terms of a tape and realising that we don't have to store everything once it is outputted to the screen.


© 2012-2017