Big table implementation in Brainfuck

In the past I had found an efficient way of implementing tables on the Brainfuck array. There were already some table implementations which used at least 2*n Brainfuck cells for storing an n sized table. My implementation needed only n+4.

Also, all known implementations had a limit of 256 cells (Or equal to the size of a cell on the Brainfuck array. For the rest of the post I will assume that the cell size is one byte).

During my road-trip to Spain, based on my old implementation, I found a new one that can use multiple indexes to implement tables of ANY size on the Brainfuck array. Additionally the table cell size can be any multiple of the Brainfuck array's cell size.

It uses a format similar to my old implementation: a head moving through the table while decreasing the index it carries, passing table data over it, until it finds the correct position,the it does it's job (read/write) and then it returns in the same way but using a copy of the index.

For a table with n cells of size k each the form of the header is:

• k empty cells: When the head need's to move to the right, it will have to move the first k cells on it's right in these empty cells before moving itself k positions to the right (thus moving itself to the next indexed position)
• n index cells: Before starting a read or write operation you will have to store the index here. The leftmost index is the most important. For example if the maximum possible value for an index is 9 (instead of 255) and you use two indexes, to access the 15th cell you would have to use 1 for the left index and 4 for the right index (not 5 because the numbering starts from 0).
• k data cells: To write to the table you will have to put the data in these cells. If you read from the table, after the end of the read operation the read data will be here. These cells MUST be cleared before starting a read operation.
• n empty (index) cells: While the index cells are reduced, these cells are increased so that, when the seek operation finishes, they will hold a copy of the original indexes which will be used for returning the head to the beginning of the table.

After the header the table data is assumed to be laying. n*k cells in total. For example for a size 400 table with 2 bytes per cell they would have this form:
Data 1 of index 0,0
Data 2 of index 0,0
...
Data 1 of index 0,255
Data 2 of index 0,255
Data 1 of index 1,0
Data 2 of index 2,0
Data 1 of index 1,1
Data 2 of index 2,1
...
...
Data 1 of index 1,143
Data 2 of index 1,143

So you will need 2*k+2*ceil(log256(n))+n*k cells on the Brainfuck array to store a table with n, k-sized cells. (ceil(log256(n)) is the number of the indexes)

Therefore the code needed to write or read from the table depends on n and k. I actually wrote some metacode that provided with n and k produces the corresponding code. I then turned the metacode into a Lua script. It's not well written but I believe that it works. I tried the following cases:

1. Writing two values to a table with n<256 and k=1 and then reading them back.
2. Writing two values to a table with 256<n<256^2 and k=2 and then reading them back.

and everything worked fine.

If you want to try the script yourself you download it from here.

Here is some example code:

n<256 k=1
Write:
>[->>+>[-<<<<+>>>>]<[->+<]<[->+<]
<[->+<]>]>>>[-]<<[->>+<<]>[-[-<+>
]<<<<[->>>>+<<<<]>>>]<<<
Read:
>[->>+>[-<<<<+>>>>]<[->+<]<<[->+<
]>]>>>[-<<+<<+>>>>]<<<<[->>>>+<<<
<]>>>[-<[-<+>]>[-<+>]<<<<[->>>>+<
<<<]>>>]<<<

256<n<256^2 k=1
Write:
>>[->>>+>[-<<<<<<+>>>>>>]<[->+<]<
[->+<]<[->+<]<[->+<]<[->+<]>>]<[-
>>>+>>[-<<<<<<+>>>>>>]<[->+<]<[->
+<]<[->+<]<[->+<]<[->+<]>>-[->>>>
[-<<<<<<+>>>>>>]<[->+<]<[->+<]<[-
>+<]<[->+<]<[->+<]>>]<]>>>>>[-]<<
<[->>>+<<<]>>[-<[-<+>]>[-<+>]<<<<
<<[->>>>>>+<<<<<<]>>>>>]<[-[-<+>]
>[-<+>]<<<<<<[->>>>>>+<<<<<<]>>>>
>-[-<[-<+>]>[-<+>]<<<<<<[->>>>>>+
<<<<<<]>>>>>]<]<<<<
Read:
>>[->>>+>[-<<<<<<+>>>>>>]<[->+<]<
[->+<]<<[->+<]<[->+<]>>]<[->>>+>>
[-<<<<<<+>>>>>>]<[->+<]<[->+<]<<[
->+<]<[->+<]>>-[->>>>[-<<<<<<+>>>
>>>]<[->+<]<[->+<]<<[->+<]<[->+<]
>>]<]>>>>>[-<<<+<<<+>>>>>>]<<<<<<
[->>>>>>+<<<<<<]>>>>>[-<<[-<+>]>[
-<+>]>[-<+>]<<<<<<[->>>>>>+<<<<<<
]>>>>>]<[-<[-<+>]>[-<+>]>[-<+>]<<
<<<<[->>>>>>+<<<<<<]>>>>>-[-<<[-<
+>]>[-<+>]>[-<+>]<<<<<<[->>>>>>+<
<<<<<]>>>>>]<]<<<<

Memory efficient Brainfuck tables

Here is a nice way to implement an indexed table in Brainfuck, using only n+4 memory for n table cells. I will soon release a new version of FBF that uses this implementation instead of the old one which used 2*n+3. (Well maybe not... I am bored...)

The table has the following structure:

0 I I D (0) (1) (2) (3) ...
^

For a table with n cells you will need n+4 cells on the Brainfuck array.
( n <= cell size) We start from where the ^ points. The first cell should be empty (zero). The second and third cells contain the index that we want to write to or read from. The fourth cell contains the data that we want to store in the table. If we want to read from the table then we should leave this cell empty and it will later carry the read data. The next cells (0) (1) ... (n-1) are the actual data stored in the table. We'll call the I I D part the "head". It works like this: Move the head to the right place: (the head moves to the right by moving the data of the next cell to the head's preceding empty cell, then moving each of the I I D cells one place to the right creating a new empty preceding cell.)

We will move the head to the right to the correct index:
>[
>>>[-<<<<+>>>>]
<
If we want to write something then we should carry the D cell too: [->+<]
<[->+<]
<[->+<]
>-]

Now we may read:
>>>[-<+<<+>>>]<<<[->>>+<<<]>
Or we may write:
>>>[-]<[->+<]<

Now we will return the head to it's initial position:
[
[-<+>]
If we have read something then we need to carry the D cell too: >[-<+>]<
<<<[->>>>+<<<<]
>>-]
<<

After a successful read the I I cells should be empty while the D cell will hold the read data.
After a successful write the I I D cells should be empty.

The pointer ends at the some place where it was before we used the algorithm, that is to the left of the first I cell.

Here is the code uncommented:

Write:
>[>>>[-<<<<+>>>>]<[->+<]<[->+<]<[->+<]>-]
>>>[-]<[->+<]<
[[-<+>]<<<[->>>>+<<<<]>>-]<<

Read:
>[>>>[-<<<<+>>>>]<<[->+<]<[->+<]>-]
>>>[-<+<<+>>>]<<<[->>>+<<<]>
[[-<+>]>[-<+>]<<<<[->>>>+<<<<]>>-]<<

FuckBrainFuck v1.7.1

Today, while improving AskWise I had to look at a part of the source code of FBF and, luckily, I found a terrible mistake in it. The SET command was supposed to set a cell in the Brainfuck array to a specific value. But in addition to this, because of the bug, it zeroed the very next cell. I do not know how that stupid bug occurred! I wonder how did the compiled FBF programs work... :-( Click here to download the new version.

Revised FuckBrainfuck Documentation

The current version of the FBF compiler is 1.7.0 and came along with the second revision of its documentation. I recently noticed that the documentation was full of mistakes and I also had forgotten to list some commands so I corrected it and now you can download the zipfile with the new documentation. The zipfile contains the compiler, the documentation, seven example programs and the Lua interpreter for Windows and Linux which is needed in order to run the FBF compiler.

FBF 1.7.0

Brainfuck is a very beautiful esoteric programming language with only 8 commands. You can make any algorithm you can think of on this language but in most cases it is very hard to do so. In Brainfuck you do not have variables, functions, constants and many other convenient features that most programming languages have. You only have an array with byte sized cells (some implementations allow for other sizes too) and a pointer. Initially all cells in the array are equal to 0 and the pointer points to the beginning of the array. Now you can only issue 8 commands that are symbolized by one character and take no arguments: "< > - + , . [ ]". "<" decreases the value of the pointer by one, while ">" increases it. "-" decreases by one the value of the pointed cell on the array, while "+" increases it. "," read a character from the keyboard and stores it in the currently pointed cell, "." prints to the screen the character stored in the currently pointed cell. "[" will jump to the command after the corresponding "]" only if the currently pointed byte equals to 0. "]" will simply jump unconditionally to the corresponding "[". That's all. With this commands you can make any calculation but it will be very hard. You can see Brainfuck as a nice brainteaser; just think of an algorithm and try making it in Brainfuck. For more information on Brainfuck read this article or visit the open directory project for Brainfuck related pages.

FuckBrainfuck (FBF) is a programming language which I made. It compiles directly to Brainfuck code and supports many features found in common programming languages so it makes creating a Brainfuck program easier. Of course you are not actually programming in Brainfuck but you will be able to create very complex Brainfuck programs. The FBF compiler is written in Lua (which is one of my favorite programming laguages) and will run on both Linux and Windows. In the zipfile you can find an extensive documentation, the source code of the compiler (GNU/GPL version 3 license), Lua interpreters for Windows and Linux and some example programs in FBF.

Here is a small program written in FBF:
#DIM char
READ char
UNEQ char '.'
IFNOTEQ char 'z'
INC char 1
END
IFEQ char 'z'
SET char 'a'
END
PRINT char
READ char
END

You can download FuckBrainfuck by clicking here.