The long-awaited next installment of this glorious series is finally here! (Sorry that was definitely over-glorified.)

In this post, my intention is simply to explain how arrays can be implemented in Brainfuck.

(If none of this makes any sense, see my previous posts: Part 1, Part 2)

Disclaimer: There is a very high probability that I made a mistake (or many mistakes) in this post; feel free to let me know about them and I’ll gladly fix them!

When I say arrays, I am referring to statically-sized arrays with random-access. The random-access part is what makes this tricky. Brainfuck’s memory model is inherently non-random-access. Thus, to implement random-access memory, we have to be somewhat clever.

Additionally, it now occurs to me that it probably wouldn’t be very hard to make these arrays resizable, but that’s an exercise I might just leave for the reader.

This is an implementation that I came up with some time ago. It may not be the most efficient way to do it, but I haven’t found an better way.

Memory Layout

Let’s take a look at the data structure/memory layout of one of these arrays. In the following example, we will look at an array that contains four single-cell elements. Note that the size of the array elements must all be the same, similar to arrays in languages such as C. (There are caveats to that but let’s not get into it.)

I will use d to represent a data cell; an array element, f to represent a flag cell, and t to represent the temporary cell.

0 d f d f d f d f t 0

The beginning and end cells of the array are 0; they are sentinel cells. We’ll look at how they’re used later, but, they must be 0. Additionally, the flag cells should be initialized to 1 when the array is created. The flag is intended to only be 1 or 0 and should be controlled only by the array operations.

When we want to access an element in the array, we need some way to find that element. Since Brainfuck’s memory is non-random-access, we must iteratively search the array for the correct cell index. This is done in a process using the flag cells and the temporary cells.

This iterative process is used for both setting an element in the array as well as getting an element out of the array.

Algorithms

The algorithms for getting/setting elements in the array as well as determining the length of the array are large but not actually as complicated as they may look. They all involve similar common steps. I will describe how these operations work with annotated Brainfuck code.

In all of these examples, assume the following initial setup:

0 0 0 0 5 1 6 1 7 1 8 1 0 0
      ^

Address 0, 1 and 2 are cells that we will use for performing the get/set operations. The cell that the data pointer is currently at (the ^) is the first cell in the array, the 0 sentinel. The data elements of the array are initialized as 5, 6, 7, and 8. The flag cells are all initialized as 1 as required by the array implementation. The cell at the end of the array is also initialized to 0 as required.

Length

We’ll start by looking at the simplest array operation: calculating its length. We’ll calculate the length of the array and put the result in cell 0.

Remember that any character that is not a Brainfuck
command is ignored and basically treated like a comment.

First we'll clear the array's temporary cell just in case it isn't 0.

>>		Skip the first element
>>		Skip the second element
>>		Skip the third element
>>		Skip the fourth element
>		Go to the array's temporary cell
[-]		Clear it
<< << << <

At this point the data pointer is at the first flag in the array.

[		Loop while the flag we're on is set
	-	Clear it

	>>	Go to the next flag
	[	Loop while the flag we're on is set
		>>	Go to the next flag
	]

	<	Go to the array's temporary cell from the end sentinel
	+	Increment the array's temorary cell

	<	Go to the last flag in the array
	[	Loop while the flag we're on is set
		<<	Go to the previous flag
	]

	+	Set the flag we cleared
	>>	Go to the next flag
]

At this point the data pointer is at the end sentinel of the array.

Next we'll move the value of the temporary cell to cell 0, our result cell.

<		Go to the array's temporary cell
[		Loop while it is >0
	-	Decrement it
	<< << << << <

	At this point the data pointer is at the beginning sentinel.

	<<<	Go to cell 0
	+
	>>>	Go to the beginning sentinel

	>> >> >> >> >
]

<< << << << <

<<<		Go to cell 0

At this point the array's length has been computed and moved into cell 0.

Note: this algorithm is less efficient than it could be; we count the length in the array’s temporary cell. However, you could count the length in the result cell of the length operation.

Set

Next we’ll look at the set operation. This is a bit simpler than the get operation but it demonstrates all the working parts of the get operation.

Say we want to set the third element to 2:

<<<		Go to address 0
++		Set the cell at address 0 to 2
>>		Go to address 1
+++		Set the cell at address 1 to 3

Cell 0 will be the value we are trying to put into the array
Cell 1 will be the index in which to place the value

The first thing we want to do is copy the index (cell 1)
into the temporary cell of the array.

We will use the cell at address 2 as our temporary cell
for the copy operation.

This loop will move the index cell into our
temporary cell and the array's temporary cell

[		Loop while the index cell is >0
	-	Decrement the index cell
	>	Go to the temporary cell
	+	Increment the temporary cell
	>	Go to the array's beginning sentinel
	>>	Go to the first flag
	>>	Go to the second flag
	>>	Go to the third flag
	>>	Go to the fourth flag
	>	Move from the last flag to the array's temporary cell
	+	Increment the array's temporary cell
	< << << << << <
	<<	This will get us back to cell 2 (the index cell)
]

At this point the data pointer is at cell 2. The contents of
cell 2 have been moved into cell 3 (our temporary cell) and
the array's temporary cell.

Now we will move the value of our temporary cell into cell 2
to complete the copy operation.

>		Go to the temporary cell
[		Loop while it is >0
	-	Decrement the temporary cell
	<	Go to the index cell
	+	Increment it
	>	Go back to the temporary cell
]

At this point the contents of the temporary cell have
been moved back into the index cell and the data pointer
is at the temporary cell.

Now the index we are trying to set has been
copied into the array's temporary cell.

Next we need to locate the cell in the array that
the index refers to. To do this, we will use an
iterative process which will result in the flag
of the element referred to by the index to be cleared.

>		Go to the beginning of the array (the sentinel)
>>		Go to the first flag in the array
[		Loop while whatever flag we're on is set
	-	Clear the flag we are currently on
	>>	Go to the flag to the right of us
	[	This loop will take us to the end sentinel
		>>
	]
	<	Go to the array's temporary cell

	[	If the temporary cell is >0
		-	Decrement the array's temporary cell
		<	Go to the last flag in the array
		[	This loop will take us back to the flag we cleared
			<<
		]
	]

	If the temporary cell is 0, we won't go back into the array
	We'll stay at the temporary cell.

	+	Set the flag we cleared (or increment the temporary cell)
	>>	Go to the next flag (or one past the end of the array)
]
<<	Go to the temporary cell
-	Decrement it (it was set at the end of the previous loop)

I know it looks complicated but if you read through it and understand
the memory layout, you should be able to understand it.

The result of that giant block of code is that the flag of the
element we are trying to set in the array will be cleared.
The flag being cleared will allow us to easily go to it from
the beginning or end of the array. This is how we implement
random-access.

Next, we want to copy the value we are trying to set the element
in the array to into the array's temporary cell. This will be
much the same process as when we copied the index into
the temporary cell.

<	Go to the last flag in the array (from the temporary cell)
<<	Skip the fourth element
<<	Skip the third element
<<	Skip the second element
<<	Skip the first element
<	Go to the beginning sentinel

<<<	Go to cell 0, the value cell

[		Loop while the value is >0
	-	Decrement it
	>>	Go to the temporary cell
	+	Increment it
	>	Go to the beginning sentinel of the array
	>>	Go to the first flag
	>>	Go to the second flag
	>>	Go to the third flag
	>>	Go to the fourth flag
	>	Go to the array's temporary cell
	+	Increment it
	< << << << << <
	<<	Go back to the value cell
]

Now the value has been moved into the temporary cell
and the array's temporary cell. The data pointer is at cell 0.

Now we'll move the value from the temporary cell
back to the value cell.

>>		Go to the temporary cell
[		Loop while it is >0
	-	Decrement it
	<<	Go back to the value cell
	+	Increment it
	>>	Go back to the temporary cell
]

At this point the value has been moved from the temporary
cell back into the value cell. The data pointer is at
the temporary cell.

Next we will clear the data cell of the array element we are setting.

>		Go to the beginning sentinel of the array
>>		Go to the first flag of the array
[		Loop while the flag we are on is set
	>>	Go to the next flag
]

At this point the data pointer is at the flag of the array
element we are trying to set.

<		Go to the data cell for the array element being set
[-]		Clear it
>>>		Go to the flag of the array element after this one

Note that if we are at the last element of the array,
this will still work; the following loop just won't run.

[		Loop while the flag we're on is set
	>>	Go to the next flag
]
<		Go from the end sentinel to the array's temporary cell

The next loop will move the value of the array's temporary cell
into the data cell of the array element being set.

[		Loop while the array's temporary cell is >0
	-	Decrement it

	<	Go to the last flag
	[	Loop while the flag we're on is set
		<<	Go to the previous flag
	]

	<	Go to the data cell of this array element
	+	Increment it
	>>>	Go to the flag of the element after this one

	[	Loop while the flag we're on is set
		>>	Go to the next flag
	]
	<	Go to the array's temporary cell
]

Finally we just need to set the flag of the array element
we were setting and that's it!

<		Go to the last flag in the array
[		Loop while the flag we're on is set
	<<	Go to the previous flag
]

+		Set the flag of the array element we set

[		Loop while the flag we're on is set
	<<	Go to the previous flag
]

At this point, the array element at the specified index
has been set to the specified value. The value and index cells
have not been stomped on. The data pointer is at the beginning
sentinel of the array.

People might hate me for this but I think I’ll leave the set operation as an exercise for the reader. Based on all I showed, it shouldn’t be hard to figure out how to implement the set operation. It’s just a slightly different configuration of the parts of these algorithms that I’ve shown. The key difference is that the value in the array must be moved out and thus it must be copied back in.

I’ll leave you with a link to the Lua code that generates all of this stuff.

Note: the FrainBuck repository is in an incomplete state. I was transitioning to a more general programming model that takes values that are larger than one cell into account, but it’s far from complete.

Finally, a few things to note: the elements of the array I showed in this post were only a single cell in size, however, it’s trivial to have multi-cell elements (the flags would still only be one cell). Also, this array only supports 255 elements; multi-byte math is needed for >255 elements. Thus, the code would be a lot more complicated.

Alright, that’s all! :)