Rail (data structure)

In Brainfuck programming, a rail is a global stack allocated in spare memory. Rail management can be used to write stack-oriented Brainfuck programs. A program can have any finite fixed number of rails.

Memory layout

A rail is a contiguous row of cells where every other cell is non-zero. The non-zero cells are called the spine and the cells in-between the spine are called data. The canonical layout for a rail involves putting the spines to the left and the data to the right, which we call spine-left; the alternative layout is spine-right. Rails always grow to the right, but they can either have the top-of-stack cell at the left or right; the rail is upright when top-of-stack is at the left, and upside down when top-of-stack is at the right.

For ease of traversal, the rail traditionally has two empty cells to its left, which act as a sort of padding for the spine. The padding enables programs to find the top of the stack without risking pointing to the left of the starting position, which could misinterpret a register or crash.

When a program is using a rail, it generally has a restricted structure. Zero or more registers are placed at the bottom of memory and the rail is placed immediately on top of them. The pointer is kept at the bottom of the rail when the rail is upright, or the top of the rail when the rail is upside down. When the rail is upside-down, access to the top-of-stack data is somewhat inconvenient for fixed registers sitting at the left near the origin. Of course, some algorithms take advantage of the unbounded space to the right of the rail and will prefer an upside-down rail.

A diagram may help. Let S represent spine cells and D0, D1, etc. represent data. A program with one spine-left upright rail and no registers is laid out, left-to-right, like so, with two cells of zero padding:

v--v--v--v--v--v--v--v--
0  0  S  D0 S  D1 S  D2 …

It is possible to have interleaved rails, which permit more than one rail in a single program. An interleaved rail layout is still contiguous, but each component rail is broken up into pairs of spine cells and data cells. The idea is that each component rail in an interleaved layout has its own spine cells and thus its own independent length. Let R0D0, R0D1, etc. be the data cells for the first rail, R1D0, R1D1, etc. for the second rail, etc. There are several possible padding schemes; one simple approach is to have one padding region per rail. A program with three spine-left upright rails and no registers is laid out left-to-right like so, with three padding regions totalling six zeroed cells:

v----v----v----v----v----v----v----v----v----v----v----v----v----v----v----v----
0    0    0    0    0    0    S    R0D0 S    R1D0 S    R2D0 S    R0D1 S    R1D1 …

Algorithms

These algorithms all assume that there is one spine-left upright rail.

In general, the pointer is either pointing to the spine or a datum. Switching between them is done with > and <. To move one cell to the right, while still pointing to spine/data, we use >>, and << moves one cell to the left. The key to the rail is that we can detect the end of the spine. Therefore, here is the first important algorithm, to move from anywhere on the spine to the end of the spine:

[>>]<<

This works by probing to see if a cell is non-zero, and thus part of the spine, looping as long as a spine cell is detected. Once the loop exits, the pointer must be just beyond the spine and can be manually shifted back to the final spine cell. The same traversal can be performed to the left, looping until hitting the padding:

[<<]>>

To treat the spine as a stack, we must be able to allocate and deallocate data cells. We also must be able to copy data an unpredictable distance up the stack. To push an empty cell to the top of an upright rail, start at the bottom and recursively copy cells right until the top is reached.

[>>]<<    go to the bottom; point to spine
[         do while spine
>[->>+<<] point to data; move data to right
<[->>+<<] point to spine; move spine to right
<<        point to next cell
]         now we are in the padding
>>+       point to locus of top of stack; make spine cell

To destroy the top cell, there are a couple possible approaches. One approach is to clear the top cell entirely, copy from right to left, and then rewind the pointer after copying is complete. This algorithm assumes that the pointer is at the top of the spine.

[-]>[-]>  zero out top spine and data
[         do while spine
[-<<+>>]  move spine to left
>[-<<+>>] move data to left
>         point to next spine cell
]         now we are pointing 1 cell above the final data cell where a spine would be
<<        point at spine
[<<]>>    scroll back to top; land in padding and point to spine