Contents > Memory

Implementation

Memory consists of a rectangular pile with large, yet finite, dimensions. It stores an ordered list of bytes in a sequence of nodes in its top-two rows. The nodes are evenly-spaced, ten columns apart, starting from column 0.

To perform a read-modify-write operation, the agent builds a function on top of the bytes to be changed. The function’s output—a row of 8, 16, or 24 evenly-spaced nodes—is the initial segment of a new surface of a taller pile. The agent raises the remaining surface flush with the function’s output by constructing identity functions over all the remaining bytes. The new surface contains the same data as the original surface, except for the bytes targeted by the operation.

To make this clear, the following visualization depicts the layers of a rectangular pile resulting from a read-modify-write operation. The bottom layer shows the initial memory state: five bytes, all zeros. The agent built an 8-bit increment function, INC, above byte 2. INC's output created the first segment of the top layer (the yellow cell). Then the agent built identify functions over the remaining bytes (the up-arrows). The outputs of those functions formed the rest of top layer. The final memory state consists of five bytes, all zeros, except for byte 2, which was incremented.

In the more elaborate example below, the agent assigned byte 0 the sum of bytes 1, 2, 3, and 4, via a sequence of read-modify-write operations.

Here is an explanation each operation:

1. COPY_B_A copied byte 1 to byte 0.
2. ADD_AB_FB put the sum of bytes 1 and 2 into byte 1.
3. SWAP exchanged bytes 1 and 2.
4. ADD_AB_FB put the sum of bytes 2 and 3 into byte 2.
5. SWAP exchanged bytes 2 and 3.
6. ADD_AB_FB put the sum of bytes 3 and 4 into byte 3.
7. SWAP exchanged bytes 2 and 3.
8. SWAP exchanged bytes 1 and 2.
9. SWAP exchanged bytes 0 and 1.

The SWAP function provides a way to move values around in memory. Above, the agent used it bring values together for the add functions. And it finished with three consecutive SWAPs to shuttle the computed sum from byte 3 to byte 0.

Memory capacity is always finite, but the agent can expand it endlessly. To allocate a byte, the agent drops eight horizontal I-tetrominoes onto the playfield floor, evenly-spaced, ten columns apart, immediately to the right of the pile. That introduces eight new 0-nodes:

Then the agent stacks identity functions above the new nodes until the output reaches the height of the rest of the pile.

The process is portrayed in the following example. It shows a newly allocated byte appended to the sum pile.

The agent never deallocates memory. The pile's width either remains constant or it increases.

The agent loads the initial memory state by dropping a sequence of horizontal I-tetrominoes (0-nodes) and O-tetrominoes (1-nodes) onto the playfield floor, evenly-spaced, ten columns apart, starting from column 0. For instance, here is a single byte, the value 42:

Since the agent clears newly allocated bytes, all memory locations after the final byte of the initial state effectively contain zero.