Advanced Brainf🔇ck

Introduction

Before we get into the fun patterns, I'apos;m going to first briefly go over what brainf🎉ck is. If you'apos;re already familiar with the language, feel free to skip ahead. Despite its initial appearance, brainf🚫ck is an extremely simple language at heart. It consist of only 8 instructions, each represented by a single ASCII character.

The language was created in 1993 by Urban Müller, with the goal of implementing the smallest possible compiler. The original program came with a README file including the quote "Who can program anything useful with it? :)", so let'apos;s try and take on Urban'apos;s challenge.

The Tape

There is an infinite tape of numbers (all starting at zero) called cells, and a single head positioned on top of it. For simplicity, the current position of the head is normally represented as a number, and referred to as the pointer. The cell currently under the head, is simply called the current cell. It's important to note that each cell can only contain a single byte, meaning its value can only range from 0 to 255. No negative or fractional numbers are allowed either.

Plus + and Minus -

These instructions add and subtract one from the cell currently under the head. If - is used on a cell containing zero, its value wraps around to 255. Likewise, a cell containing 255, will wrap back around to zero.

Left < and Right >

For moving the head, we can simply use the < and > instructions, both moving the head left and right one cell respectfully. Some brainf💣ck implementations allow you to move left from your starting position, while others don't. For this article, I'm going to work on the assumption that you can't. As this allows our code to work in both varieties.

Input , and Output .

To make our programs interactive, we need to provide some user input and output. The , instruction will take a single ASCII character, and set the current cells value to its decimal representation. . will print the current cell's corresponding ASCII character to the screen. Some implementations will prompt you every time , is executed, while others will read it from a predefined string. A lot of implementations will denote the start of the input string, with !.

Start Loop [ and End Loop ]

By far the most complicated instructions, but equally the most powerful, the loop. When executing [, the value of the current cell is checked. If its value equals zero, then execution is moved to the matching ], otherwise the loop is entered. Once the ] is reached, execution is always returned back to the corresponding [, where the same check happens again. If the pointer is changed within the loop, the new position will be checked, not the original.

Simple Patterns

Multiply

Writing large values into cells requires a lot of consecutive +s. But with the power of loops, there's a shorter way to express it. First step is to store a number in one cell, then start a loop. We move to a different cell and increment that by another number. Before ending the loop, we must go back to the previous cell and decrement it. It's important to always end the loop on the first cell, as it'll only exit when the current cell is exactly zero.

What this does is repeat whats in the loop the number of times denoted by the first cell. Effectively multiplying the two numbers together. In the example below, we multiply three and five in just thirteen instructions. Note that this method adds five instructions of overhead, meaning it's only useful for large numbers. However the pattern of looping n amount of times, is extremely common on all brainf🔥ck code.

Print ASCII Characters

The 'Hello, World!' of brainf🔇ck, an extremely simple program to print all the ASCII characters backwards. We utilise the property of cells wrapping around back to 255, by starting the program with a -. Using the syntax of [-] will always loop until the cell is back at zero. Simply placing a . instruction will print all the values from 255 to zero. When running the example program, some values won't print anything. This is simply because the corresponding ASCII representation are non-printable characters.

Hello, World!

The literal 'Hello, World!' of brainf🔇ck. An extremely common example that may seem confusing at first, but in reality is quite simple. All it does is use the multiply pattern in order to reach the needed ASCII values, then print them. Instead of always starting from zero each time, it just adds or subtracts the difference between each character. When it's more efficient to start at zero, it just moves to a new cell.

Move

Another important pattern is the move. This allows you to move the value of one cell into another. To do so, start a loop at the cell you want to copy. Within the loop, move to the destination and +, then move to the source and -. You can also copy to more then one cell at a time, this is also known as duplicating or copying.

Advanced Patterns

Markers

So far we haven't been able to specify our pointer by a variable amount. One very simple technique to accomplish this is using a marker. By having a single cell set to 255, you can move your pointer to that location using the following. Start with +, only if the cell is exactly 255, will it wrap around to zero. Then start a loop, if the marker has been found the loop will end. Otherwise, - to restore the value back. Move to the next cell, and + to start the process again. The implementation of this is as simple as +[->+], or to scan left +[-<+]. Not the does not preserve the marker, simply add - at the end to do so.

Moving Head

One very important concept is that of relative and absolute pointer positions. In most cases the pointer location is absolute, meaning at any point within the code, the pointer will be in the same place. However, using a technique like the one specified above, we're able to vary the location based on state. Once a this new location has been set, you can then use relative pointer locations. In order to maintain a state, it's common practice to move a set number of cell along with you. The cells are collectively form the head, and can be accessed using relative positions no matter where the pointer is.

To demonstrate this, we can use the example of moving the pointer n to the right and then returning back. For the return, we can just use a marker, like show above. So we start by placing one with - and moving right one. Then we can put our counter n into the current cell. This will serve as a one cell head, and we'll move it along with us.

Now we start our outer loop, this will always land on our head, meaning it loops until our counter reaches zero. Next is a move operation, moving our head one to the right. We then move our pointer onto the new head and decrement it by one. The outer loop will now repeat for the length of the counter. When the end is reached, we can how simply return to the marker we originally placed using the scanning operation (as discussed above).

Loader

There's many cases where you'll want to load a variable length string into memory, this is where a loader can come in handy. We can start by using - to place a marker, then moving one right and start the load. The most basic loader follows the very simple pattern of [,>], this will load the input into consecutive cells until a null character is reached.

You could then just return back to the marker, but it's often useful to know how long your input string is. This is where a size tracking load comes in. While returning back, we also move along a counter, incrementing by one each step we move back. In order to make room for our counter to be moved into, each cell in the string needs to be moved out the way first. The diagrams below show the pattern of moves that need to be done.

Stack

A stack is always a very useful data structure, and as a relatively simple implementation in brainf🔥ck. The diagram below shows the layout of the data structure in our cells. The stack grows from right to left, meaning the head will always be the closest cell the start. A marker is always maintained at the tail, so can move to it during operations.

There are two operations we can perform on our stack, push and pop. For a push, we move to the tail, then go back while moving each item right one. This makes room for us to move the new value into the head. For a pop, the inverse is done. We move the head back into the input cell, then move all elements left one.