Section 1.3
Looping
So for, we’ve only been able to increment and decrement values in a cell manually, print out an ASCII representation of the cell value, change which cell the current pointer is pointing to. Now, we will introduce a tool that will significantly increase the complexity and sophistication of Brainfuck programs you are able to write: looping.
A left and right bracket are used to enclose code that is run so long as the current pointer does not point to an empty (zero) cell. For instance, the program [-] decrements the value of the cell until it reaches zero. If you were to run this on a blank tape, nothing would happen because the pointer begins pointing at an empty cell. However, the code +++[-] would increment the current cell three times, then decrement three times until it is empty again. If we instead substituted the - for a = such that the code became +++[+], we would enter an infinite loop in which the current cell value would continue to be incremented with no end.
Note that a loop is technically the same as a conditional in Brainfuck; a piece of code is reserved for execution only if a binary condition is met. However, this tool is so often used to perform the operation of looping that it is colloquially simply referred to as ‘looping’.
Looping is much more interesting when we move the pointer within the loop code. The canonical example is to increase the syntactic efficiency of our Hello World! program using looping and some simple arithmetic. The ASCII code for H is 72. Rather than incrementing 72 times, we can increment in 9 batches of 8. We’ll begin by incrementing the value of the initial pointed cell 9 times, representing the number of times we need to increment 8 times. Then, while this ‘counter’ cell is not empty, we will move the pointer right one to the ‘data cell’, increment by eight, move the pointer left one, and decrement. After each execution of the loop, we have ‘exchanged’ 1 from the ‘counter’ cell for 8 in the data cell. After 9 exchanges, the loop will terminate because the counter cell will be 0. After the loop is exited, we move right to access the data cell and print out the ASCII representation of the value.
+++++++++ increment by 9
[ open loop
> move right to data cell
++++++++ increment by 8
< move left to counter cell
- decrement counter cell
] close loop
> move right to data cell
. print data cell ASCII value
We can shorten this into one line:
+++++++++[>++++++++<-]>.
Let’s trace the execution of this script. We begin with a blank initialized tape:
A blank initialized tape.
...[0][0][0][0][0][0][0]...
^
This pointer is demarcated as pointing to the counter cell; the value is incremented by 9.
...[0][0][0][9][0][0][0]...
^
We check to verify upon the loop opening that the current cell is not empty/zero. Indeed it is not, so the first command (moving right) is executed.
...[0][0][0][9][0][0][0]...
^
The data cell is incremented by 8.
...[0][0][0][9][8][0][0]...
^
The pointer is moved back to the counter cell.
...[0][0][0][9][8][0][0]...
^
To ensure that the loop terminates after 9 batches of 8 have been added, we decrement the counter cell by one.
...[0][0][0][8][8][0][0]...
^
This continues until the counter cell reaches 0. At this point, the pointer is shifted right to the data cell and the H corresponding to the code 72 is printed out.
...[0][0][0][0][72][0][0]...
^
The next character is e, which has ASCII value 101. We could destroy the value of our current counter nad data cells - now that the desired character H has been printed to the output - using [-], then incrementing in 10 batches of 10 and adding 1 to the end.
[-] destroy all data in data cell
< move left tocounter cell
[-] destroy all data in counter cell
++++++++++ increment counter cell by1 0
[ open loop
> move right to data cell
++++++++++ increment by 10
< move left to counter cell
- decrement counter cell
] close loop
> move right to data cell
. print data cell ASCII value
This will, indeed, give you an e. However, it’s a bit inefficient, because we have already stored 72 from the H. Rather than deleting everything and adding 101, we can simply increment by \(101 - 72 = 29\). 29 is a prime number, and therefore not cleanly divisible by two reasonably large numbers. In this case, we want to find an efficient representation of 29 by multiplying two reasonably large numbers and adding or subtracting. Several possibiilties are outlined below:
Increase in 6 batches of 4; then add 5
++++++[>++++<-]>+++++.
Increase in 7 batches of 4; then add 1
+++++++[>++++<-]>+.
Increase in 10 batches of 3; then subtract 1
++++++++++[>+++<-]-.
Increase in 8 batches of 4; then subtract 3
++++++++[>++++<-]---.
Out of all these possibilities, the second (increase in 7 batches of 4; then add 1) has the shortest syntactic representation, so we’ll choose that one. Assuming that we’ve just printed out the H, our pointer is now pointing at the data cell. We begin by moving left to the counter cell, which is empty/zero (having been depleted via looping).
+++++++[>++++<-]+.
Adding this code after the code used to print H prints out an e. This logic can be continued to somewhat tediously but syntactically efficiently print out the rest of the Hello World! sequence.
A simple application of looping that is slightly less tedious is to print out all uppercase letters of the alphabet. These codes are all adjacent (A at 65 and Z at 90). We’ll begin by getting to 65 by first getting to 66 in 11 increments of 6, then subtracting one.
+++++++++++[>++++++<-]>-
Our tape layout looks like such after the execution of the script (with the pointer pointing at the data cell):
Data
v
...[0][0][0][0][65][0][0]...
^
Counter
Now, we need to print and increment the data loop 26 times, since there are 26 letters in the alphabet. In order to do this, we’re going to need to fill up the counter again. We could accomplish this simply by moving left to the counter cell and incrementing 26 times:
<
+++++
+++++
+++++
+++++
+++++
+
Alternatively, we could express 26 as \(5 \cdot 5 + 1\) and express this using loops.
< move back to counter cell
< move back to 'secondary' counter cell
+++++ add five to the 'secondary' counter cell
[>+++++<-] while not empty, move right and add five to the counter cell
> move back to the counter cell
+ add one to the counter cell
Great! Now, the counter cell contains the value 26. We can now print the ASCIi characters corresponding to the integers in the data cell:
[
> move right
. print out ASCII character
+ increment value
< move left
- decrement counter
]
The complete code is as follows:
+++++++++++[>++++++<-]>- add 65 to data cell
<<+++++[>+++++<-]>+ add 26 to counter cell
[>.+<-] print out characters