Brainfuck Tutorial – part 2

In this tutorial I will talk more about loops and how to do basic higher level stuff in Brainfuck. If you already know BF operators, you can start from this part. Else, read the previous tutorial.

[] operators are used for creating conditional loops in BF. As long as value of current pointer is non zero (when program executes [ command), it loops between [ and ]*You obviously know this if you read previous tutorial.

So what can we do with this information? Well, pretty much everything. Here are some higher level stuff that you can do with loops.

The first and easiest one is clearing a cell. It is simply

[-]

If cell is non zero, it enters this loop and decreases it until it is zero. You might ask what is the use of this. It is usually used when implementing booleans or if conditions.

Another one is moving a cell to another.

[->+<]

Let's say our array is like this

...ab...
...^

Initially pointer points to a. With this loop it decreases a until it is zero and increases b by 1 on each iteration. So it basically moves content of a from b. (Actually if b is non zero, it is *b=*b+*a; *a=0;, in this tutorial I will assume cells are 0 unless it is specified).

And finally, copy operation

[->+>+<<]

It moves (adds) current cell to two cell on the right.

These are most basic things in brainfuck. While implementing more complex stuff, you will those a lot. For example let's draw a triangle like this.

...*
..***
.*****
*******

So in C, this is done like this.

int k = 4; //line num
int i, j;
for(i=0; i<k; i++){//for each line
   for(j=0; j<k-i-1; j++) printf(" ");
   for(j=0; j<i*2+1; j++) printf("*");
   printf("\n");
}

Implementing this directly in BF would be a lot harder, some higher level operators a lot harder to implement. I will 'simplify' it for BF.

int k = 4; //line num
int a, b, i, j;
a = k;
b = 1;
while(a--){
  i = a;
  while(i--) printf(" ");
  j = b;
  while(j--) printf("*");
  printf("\n");
  b+=2;
}

So this does the same thing but it is a lot easier for BF. Basically a holds the number of spaces while b holds the number of stars for each line. Before starting writing my program, i will first decide my structure for array.

ktabijs*n
012345678

This is my array structure that I will use in my program. First line is the name of each cell and second line is indices of each cell. I already decided which cells will hold which values. k, i, j, a, b are the values in previous C code. t is a temp cell. "s*n" are the cells that will contain ascii values for ' ' (space), '*' and '\n' (newline).

So first lets begin with building "s*n". Space is 32, '*' is 42 and '\n' is 10. I will use cell j as a temporary cell to make a loop and set these cells to correct value. Initially pointer is at cell k (0th cell).

!bf!>>>>> (move cell j)
+++++ +++++ (set j to 10)
[- (as long as j is non zero)
  > +++ (increase cell s by 3)
  > ++++ (increase cell * by 4)
  > + (increase cell n by 1)
  <<< (move back to cell j)
]

So after this code, s will be 30, * will 40 and n will be 10 (and j will be 0). But we want 32, 42 and 10 so let's increase s and * by 2

>++>++

So the cells that holds the ascii values are ready! Now let's input cell k from user. I am assuming user will enter a single digit. But it is in ascii so I have to decrease it by 48 ('0') to convert it to a real number. With the addition of previous code, now the pointer is at cell *. Move it back to cell k, input a character and decrease it by 48. While at it let

!bf!<<<<<<< (move back to cell k)
, (input a character)
> +++ +++ (set t to 6)
[ - < ---- ---- >] (decrease k by 8 for each iteration of t) (in total 48)

Now cells ks*n are ready. Now let's initialize cell a and b. a should be initially equal to k and b should be 1. In previous code we were at j.

!bf!< (move back to cell k)
[->+>+<<] (copy k to t and a)
> [-<+>] (move t back to k)
>> + set b to 1

Some of those look familiar? Basically we are creating two copies of cell k at cell t and cell a then move t back to cell k. We can't copy a cell to directly to another without clearing content of the first. We have to create 2 copies, move 1 to back.
After that it sets b to 1. So our initializing process is done. Let's look at our current structure.

!bf!k  0  k  1  0  0  32  42  10
k  t  a  b  i  j  s   *   n
0  1  2  3  4  5  6   7   8
            ^

First line holds the values, second line is the name of the cells and last line is the index of each cell. Now we can start actual programming!

First line of C code is while(a--). This is our main loop, as long as a is non zero create a loop. After beginning of each iteration it decreases a by 1 How could we achieve such a thing in Brainfuck. In our previous code, we left pointer at b. We want a loop that runs until a is non zero.

!bf!< (move back to a)
[
  - (decrease a by 1)
  {snip}
]

And that is all!. In snip part we should implement inside of the main while loop. Our first operation is printing number of spaces that is equal to a. For that we copy a to i, and print space as long as i-- is true. Pointer is at a

!bf!!nr![- <+> >>+<<] (make copies of a at t and i)
<[->+<]> (move t back to a) 
>> [->>.<<] (move to i and print spaces (cell s) until it is 0)

First we make two copies of cell a at t and i. And then move t back to a so value of a is not changed (We will need it on next iteration) after that it simply moves pointer to i, enters a loop and for each iteration it moves to cell s (contains ' ' (space)) and prints it). That is it, we already printed our spaces. Now move to the starts, it is basically same code but on different cells. (instead of a i s, it is b j *). In the last code we left pointer at cell i.

!bf!!nr!
<
[- <<+>> >>+<<] (make copies of b at t and j)
<<[->>+<<]>> (move t back to b) 
>> [->>.<<] (move to j and print stars(cell *) until it is 0)

As you can see, I just modified previous code a little. With this we printed our spaces and starts. Finally let's print a new line and end finish this line. With last code, pointer is now at cell j

!bf!!nr!>>>. (move to cell n and print it)

Finally. We printed all necessary stuff and done for this line. However before beginning to next iteration, we have to change value of a and b correctly. After each line, number of spaces is decreased by 1 (a) (which we did in the beginning) and number of stars are increased by 2. We were at cell n

!bf!<<<<< ++(move to cell b and increase it by 2)
<  (and move back to a)

That is it! We implemented {snip} part of our main loop. As you can notice, pointer is at cell a so we have to move pointer to a in the end. Let's merge all of our stuff and test it!

!bf!>>>>> (move cell j)
+++++ +++++ (set j to 10)
[- (as long as j is non zero)
  > +++ (increase cell s by 3)
  > ++++ (increase cell * by 4)
  > + (increase cell n by 1)
  <<< (move back to cell j)
]
>++>++ (set s to 32 and * to 42)

<<<<<<< (move back to cell k)
, (input a character)
> +++ +++ (set t to 6)
[ - < ---- ---- >] (decrease k by 8 for each iteration of t) (in total 48)

< (move back to cell k)
[->+>+<<] (copy k to t and a)
> [-<+>] (move t back to k)
>> + set b to 1

(while(a minus minus){)
< (move back to a)
[
  - (decrease a by 1)

  (i=a; while(i minus minus) printf(" ");
  [- <+> >>+<<] (make copies of a at t and i)
  <[->+<]> (move t back to a) 
  >> [->>.<<] (move to i and print spaces (cell s) until it is 0)

  (j=b; while(j minus minus) printf("*");
  <
  [- <<+>> >>+<<] (make copies of b at t and j)
  <<[->>+<<]>> (move t back to b) 
  >> [->>.<<] (move to j and print stars(cell *) until it is 0)

  (printf("\");)
  >>>. (move to cell n and print it)

  (b = b plus 2)
  <<<<< ++(move to cell b and increase it by 2)

  <  (and move back to a)
] (} end of while(a minus minus)

And let's remove all comments from code abd format it a little(Enter input 'a' for more fun!)

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

(I added extra >> there to make it triangle)

And we build our first complex program, yay! Before finishing my post, I want to emphasize a couple of things.

  • Before starting coding, first you should build your structure on your mind (and write it in a paper/text editor). Which cells will be used for what, name each cell etc... You should decide it at the beginning. The structure I used is not the best, I could make a more compact one and it would reduce the code size a lot.
  • Try to split your program into smaller parts. For example in this program, first part creates ascii values for printed parts, second part inputs k and initialized a and and final parts prints stuff. If you separate them like this, you can test them separately and it will be much easier to write. Use a debugger if necessary, that shows your the content of each cell and see if you are doing correctly. This one is quite good and very fast
  • Always know where your pointer is. While coding, I usually put comments that shows where am I now. For example
    !bf!!nr!
      [- <+> >>+<<]a (make copies of a at t and i)
      <t[->+<]>a (move t back to a) 
      >> i[->>.<<] (move to i and print spaces (cell s) until it is 0)
      <b
    

    I don't write comments between () they are way too unnecessary. Only occasional comments like a, b, i, t in this example that shows where is the cursor at that point of comment. I also copy paste my array structure a lot to move my pointer correctly. After a while, basic algorithms will be easy for you (like copying, moving stuff etc) as long as you know where you are.

  • With more practice, you will be able to think how to write higher level stuff in BF. You will be able to make a general algorithm in your mind and after that it is just patience.
  • Well that is all for now. This was a fairly complex program (CS 101 stuff), I hope that I explained it well. I am planning on more tutorial with more complex examples).

    Brainfuck – Tutorial 1

    Hello Internet!

    In this tutorial I will talk about BF and how to make programs with it. Let’s start with what is BF and why you should love it.

    Brainfuck (unfortunate name, can’t really put it on your CV) is a minimalist esoteric language. Even simplest programs are a challenge in BF and that is the beauty of it. If you love the challenge and want some headaches, BF is the one for you.

    In BF you have an infinitely long *debatable, in some implementations it is constant, in others it reallocates new space as you need it 8bit byte array *again, it is usually byte but can be bigger and a pointer that points to one of the elements in this array. In a BF program, you move this pointer, alter the cell that it points to or do I/O operations for current cell. It is basically a turing machine, only even more simpler.

    BF has a full set of 8 operations. These are “+-<>[].,“. Any character other those 8 characters are disregarded by the interpreter and can be used as comments (and you will need them).

    Let’s talk about these 8 operations.

      Movement

    Movement operations are <>. They move pointer (or cursor, if you prefer) ‘left’ or ‘right’. Initially cursor points to beginning of the array and you use these operations to move the cursor. In some implementations it is forbidden to move left side of the initial position, in others it reallocates array or simply wraps to the other side of the array. So be careful about that. I always assume you can’t move left side of the initial position.

    These operations only move it 1 cell. For example initially you are at position 0 and if you call > it moves to position 1. If you call >>> after that it moves to position 4.

      Increment/Decrement

    As you probably guessed +- are increment and decrement operations *+ is increment, - is decrement if you didn't. They increase or decrease the content of the current. That is it. You have no other way (other than I/O) altering the contents of the current cell.

    At the beginning of the program, each cell is set to 0. These operations can cause integer overflows so if you call - when cell is 0, it will be -1 (or 255, if you don’t want to bother with signs) and + will cause it to overflow 0 again.

    You can’t set a cell to a constant. If you want a cell to be set to 10, you need to call ++++++++++*assuming it was 0 before, if you want to set it to 50 you will need 50 + operations*There are easier ways of course, I will talk about them in 'advanced' section ­čÖé

    So here is a very simple program that uses all operations we learned.

    ++++>+++--

    First we increase the cell0 by 4 then move cursor to the left. It increases cell1 by 3 and decreases it by 2 to set it 1. In the end our cell is “31000000…..” and cursor points to 1 (cell1)

      Input/Output

    We have an input and an output operator in BF. Basically they input a byte (or character) from stdin or outputs a byte (or character) to stdout. . outputs content of current to cell to stdout and , inputs a byte from stdin. Again they only alters/uses current cell.

    You will need basics of ascii to input/output meaningful data. For example if you set a cell to 48 and call . it will print ‘0’ to the console because ascii value for ‘0’ is 48. If you call , and press 2 it will set current cell to 50 (ascii value of 2).

    So here is a much more complicated BF program! You can press run to see output of the program.

    !bf!+++++ +++++ +++++ +++++
    +++++ +++++ +++++ +++++
    +++++ +++++ ++ set current cell to 52 (4)
    . print 4
    -- decrease current cell by 2 set it to 50 (2)
    . print 2
    > +++++ +++++ . go to cell1 and set it to 10 and print (\n)
    , input a charcter (i assume that user will press something between 0 and 9)
    + increase the inputted value
    . print new character

    First part is obvious, it first sets cell to ‘4’, prints it then set it to ‘2’ and prints it again. You get the answer to the life. It prints a \n after that to go next line.

    In second part it inputs a character from user and increases its value by and outputs it. If user inputs ‘0’ it is 48 in ascii, after + it is set to 49 and when printed it prints ‘1’. If user inputs 5, it prints 6. If he inputs 9, no it does not print 10. It prints ‘:’ because ascii value after ‘9’ is equal to ascii value of ‘:’. Printing two digit numbers are very tricky.

    That is all for I/O. Now comes the tricky part.

      Branch/Loops

    Our final two operations are []. These are used for creating loops or conditional statements. Every [ operation is matched by a ]. Any command between these two operations are evaulated if only a certain condition is satisfied.

    When a BF interpreter reaches a [ statement, it checks if value of current cell is zero or non zero. If it is zero, than code between [] is not evaulated and it jumps to the operator that comes after ]. If it is non zero than it simply jumps next operator after [ and continue to execute normally. When it finally reaches ] it rewinds back to [ and again if current cell is zero or non zero. It loops until current cell is non zero.

    It is basically a while loop that uses value of current cell as a boolean. zero = false, non-zero = true.

    Be careful that when it rewinds to the back, it does not move cursor to the old position. If you are using <> operations between [], you will probably want number of < is equal to >. And it does not alter the content of the current cell so you will want to decrease (or increase) current cell to break loop at some point.

    Now let's write a program that prints 10 exclamation marks using a loop.

    !bf!+++++ +++++ +++++ +++++
    +++++ +++++ +++ set current cell to 33 (!)
    > move cell1
    +++++ +++++ set cell 1 to 10
    [ start loop at cell 1
    < move cell 0 (contains !)
    . print !
    > move cell 1 again
    - decrease cell 1 by 1
    ] end loop

    First we set cell0 to ascii value of ! then it moves to cell1 and sets it to 10. Cell 1 is our test cell, as long as it is non zero this loop will be executed.
    At each iteration of loop it moves back to cell0 and prints it. Then it again moves back to cell 1 and decrease it. When it rewinds back to [ it will test if cell1 (current cell) is nonzero and if it is non-zero it will execute again. During the execution cell1 will be 10 9 8 .. 1 and finally 0 and execution of loop will stop.

    Previously I said that you can use a simpler/shorter way to set a cell to 50. Here it is

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

    It first sets cell0 to 7 and loops until it is zero. In each loop it moves to cell 1 and increases it by 7 again. It is basically a multiplaction operation at the end of the loop cell1 is 7x7=49. We increase it once again and set it to 50. Easier than +++++...+ times 50!

    That is it! Now you can write a doom clone in BF!

    I am planning more complex tutorials on BF. There are some tricks I learned that makes writing more complex program easier. I will make and explain some code examples that shows some essential stuff (printing two digit numbers for example :)). Stay tuned!