Tape Abstractions

Overview

The data-tape is considered a stack, where each function owns a stack frame. Each frame is composed of slots: a return-slot (if the function returns a value), argument-slots (if the function takes arguments) and local data-slots (variables and temporaries used in the function). A slot is a series of (logical) cells that contains a variable of some data-type, used by the function. The size of a slot depends on the number of cells required to represent the type of the variable. Instead of using single BF-cells to compose slots, logical cells or macro-cells are used. Each macro-cell contains 9 actual BF-cells, referred to as fields from now on, each of which serves a different purpose. $$\text{BF Cell} \longrightarrow \text{MacroCell} \longrightarrow \text{Slot} \longrightarrow \text{Frame} \longrightarrow \text{Tape}$$ A macro-cell contains the following fields (in arbitrary order), each of which will be discussed in more detail in Section Cells and Macro-Cells.

1. Value0: Low-byte of the semantic value of the macro-cell.

2. Value1: High-byte of the semantic value of the macro-cell.

3. Scratch0: General-purpose scratch-cell.

4. Scratch1: General-purpose scratch-cell.

5. Payload0: Low-byte of a payload (or another scratch-cell).

6. Payload1: High-byte of a payload (or another scratch-cell).

7. Flag: Dedicated flag cell to guard BF-loops.

8. FrameMarker: Dedicated cell to mark the start of a new frame.

9. SeekMarker: Dedicated cell to mark arbitrary locations on the tape.

Central to the macro-cells are the two value-fields that hold the actual value of the logical cell. By having two value fields, we allow for 16-bit data types to be implemented within the same logical-cell, rather than having to allocate two macro-cells for a single 16-bit variable. The other fields hold temporary data or metadata required to perform higher level functions like arithmetic, flow control and dynamic pointer movement. When the compiler needs to generate code that moves the BF-pointer to location known only at runtime (for example when dereferencing pointers or accessing array elements by a dynamic index), these fields can hold temporary values or metadata necessary to perform the move. Other non-value fields include temporary scratch-pads (heavily used when performing arithmetic operations), payload-fields (used to transport data to locations known only at runtime) and a flag cell that is dedicated to the evaluation of loop-conditions. Having all these fields near one another on the BF-tape has the nice consequence of BF-algorithms being relatively short due to tight pointer-move-sequences.

Example: Fibonacci (continued)

Figure 45 shows the tape hierarchy described above, applied to the Fibonacci example from before and evaluated immediately after fib was first called. Even though this program made no use of any global data, this frame is still depicted for completeness’ sake. Zooming in on Frame 2, used by the fib function, we see how a frame starts with the slots we previously encountered in Section Basic Block Scheduling: the TargetBlock and Run slots, which are used to determine where to jump next and whether to continue execution at all. Since fib does not return anything, no return slot has been allocated to this frame. Instead, the local data immediately follows: first the arguments passed to the function (initialized by the caller), then the local data used within the function. Only the variables c and i have been explicitly allocated by the programmer, but temporary slots have been created by the compiler to store the result of a + b and i < n.

Zooming in further on two of the slots, we see that they both contain only a single macro-cell and its 9 constituents. The first slot of the frame (TargetBlock), which still holds ID 1 (the block-ID of the first block of the function) in its value-field, also has its FrameMarker field set, indicating that this is where a new frame starts on the data-tape. The b-slot has its value-field set to 1 as well, corresponding to the value of b that was passed to fib from main.

The sections below go into more detail about each of the layers of abstraction.

Cells and Macro-Cells

BF operates on the most fundamental level of raw cells. Each consecutive sequence of 9 such cells constitutes a logical macro-cell as mentioned before in Chapter Tape Abstractions. In this section, we will cover each of the 9 fields of a macro-cell in more detail and cover some of their use cases.

Value0 and Value1

The value fields together hold the semantic value of the macro-cell. The Value0 field contains the low byte and the Value1 field holds the high byte of an integer of at most 16 bits. Acus implements four integer data types using these two fields: unsigned 8-bit (u8), unsigned 16-bit (u16), signed 8-bit (s8) and signed 16-bit (s16). When referring to 8-bit values, the Value1 field is simply ignored. Signed integers are represented using two’s complement; some algorithms need to do some additional work (like evaluating the sign bit) before applying the usual operations.

Scratch0 and Scratch1

Many BF algorithms need temporary cells as scratch-pads. These cells can be temporarily claimed by an algorithm and must be left behind empty for the next algorithm to use. An example of a simple algorithm that makes use of these values is the non-destructive addition. Say we want to add the contents of cell x to those of cell y without destroying x in the process. We can achieve this by decrementing x while at the same time incrementing y until x becomes zero. However, in order to restore x to its original value, we need to use a scratch-pad to construct a copy of x which is moved back after the addition has been completed. This algorithm is shown in Listing 6, where instead of denoting pointer-movement with sequences of < and >, we simply write the name of the variable/slot to indicate a move to that (known) location on the tape.

# Algorithm for y += x
# tmp is a scratch-cell assumed 0

# Step 1: add x to both y and tmp, destroying x
x[- y+ tmp+ x]

# Step 2: add tmp back to the now empty x
tmp[- x+ tmp]

Flag

The Flag field is reserved to store a value that determines whether or not a BF-loop should be entered. An algorithm can store an intermediate, temporary, value in the flag-cell and use that as a branch or loop-condition. Whereas scratch-cells are general purpose temporary storage locations, the flag-cell is meant to be used for this purpose alone to avoid confusion. The subsection below includes an example that also utilizes this field in Listing 7.

FrameMarker

The FrameMarker field is only set when the macrocell marks the start of a new frame. When performing dynamic pointer movements, a marker like this (the SeekMarker is used in a similar way) can be used to move from a still unknown to a known location on the tape. Let’s say we know the data-pointer is somewhere in Frame 2, but we don’t know where because we just performed some (dynamic) movement (i.e. an algorithm that moves the pointer by an amount that depends on runtime data). We know that the start of the frame is to the left of the current position, so we can perform the algorithm below and be sure that we’re pointing at the start of the frame when the algorithm is finished. This algorithm is shown in the pseudo-BF of Listing 7. This works because every macro-cell has the same width and because exactly one FrameMarker is set at the start of the active frame.

1. Move the pointer to the FrameMarker field of the current cell. Even though the current offset is unknown, the current field is known so we are able to switch between fields reliably.

2. Construct the logical NOT of the FrameMarker and store the result in the Flag field, then move the pointer to the Flag field.

3. Enter a loop, conditioned on the flag, where the pointer is moved 9 cells to the left on each iteration until a non-zero FrameMarker is encountered. In each iteration, the logical NOT has to be constructed and stored in the Flag field as before. Note that when inside a loop (meaning the flag was nonzero), the flag needs to be cleared before moving to the adjacent cell.

# Algorithm to move the pointer back to the start of the frame
# Current macro-cell offset is unknown; all moves are relative
# field-switches within the same macro-cell, except for the
# 9 left-moves, which take us exactly one macro-cell to the left.

# Assumed: there are already implementations for assignment and
#          the logical NOT operator.

ASSIGN(Flag, NOT(FrameMarker))
Flag [-                            # Reset flag before moving away from it
  FrameMarker  <<<<<<<<<           # Move to the frame-marker field of
                                   #   neighboring macro-cell
  ASSIGN(Flag, NOT(FrameMarker))   # Compute exit-condition
  Flag                             # Check exit-condition
]

# Out of the loop: pointer is at the start of the frame

SeekMarker

The purpose of the SeekMarker field is very similar to that of the FrameMarker field, in the sense that it is used to mark certain cells to make dynamic movement possible. For example, a known location can be marked before performing a dynamic move, in order to be able to move back to that known location using an algorithm similar to that of Listing 7. Also, when a dynamic move has been completed, its location can be marked to make future excursions to this location more efficient. Contrary to the FrameMarker, which is specifically used to mark the start of a frame, the SeekMarker field may be set for any macro-cell on the tape.

Payload0 and Payload1

The payload fields are used to store values that need to be transported along to dynamically determined locations. Algorithms that move the pointer to such locations can be trivially extended to move data along using these fields: one for the low byte and one for the high byte of the value. Additionally (but this is not the intended use-case), a payload cell may be used as a scratch-pad (when an algorithm has exhausted the available scratch cells), provided it is not being used to transport any values at that time.

Slots

A slot is a storage location for one object. Single 8 or 16-bit integers occupy a single macro-cell, while larger objects like arrays or structs occupy a sequence of macro-cells. A slot is bound to a stack frame; its offset is defined as the index of its first macro-cell with respect to the start of the frame, not the start of the actual BF data-tape.

In addition to a name and offset, a slot holds information about its scope (to determine access, allow for name-shadowing and keep track of lifetime) and its kind. Most slots are of the local kind, representing data local to the current function, but slots can also be tagged global, available (representing a free block of memory that was previously occupied), temp (for temporary slots that should be freed after use) and cache (Chapter Caching). Figure 46 shows a section of a frame and how local slots could be organized given their data-types and sizes. Note that the size of a slot is expressed in terms of the number of macro-cells rather than raw BF cells.

Data Types

Slots reserve space on the tape, but the compiler also needs to know how that space should be interpreted. This is the role of data types. A data type determines how many macro-cells are needed to store a value, which sub-slots exist inside that value, and which algorithms may be used to copy, compare, increment or otherwise manipulate it.

Primitive integer types (such as u8 or s16) are stored directly in the value fields of a single macro-cell (even 16-bit integers fit in a single logical cell). Compound types (arrays and structures) are constructed from these primitives. An array is represented as a sequence of equally sized elements, while a structure is represented as a sequence of fields at fixed offsets. As a result, the compiler can compute the size of every type and the offset of every field at compile-time.

Slot Proxies and Materialization

Most expressions encountered by the compiler can be resolved directly into a slot. For example, assume x is an array of structs that contain an age field, e.g.

struct Person {
  id:  u16
  age: u8
};

let x: array<Person, 5>;

In this context, the expressions x, x[2] and x[2].age all refer to known slots or sub-slots (assuming square brackets represent array indexing and a dot represents field access for struct objects). The compiler knows in which slot the array x is stored, how to find the offset of element 2 and how to find the offset of the age field.

However, when the index is not a compile-time constant, things change. The expression x[i].age has the same shape as x[2].age (they might even refer to the same data), but now the compiler has no way to compute the desired offset at compile-time. At this point, the expression can no longer be represented by a single statically known slot. The array itself still has a known base location, and the layout of each Person object is still known, but the particular element that should be accessed depends on a value computed at runtime. In Brainfuck terms, the compiler must now generate code that moves through the tape dynamically, using the value of i to reach the correct element before applying the fixed offset of the age field.

This is where Acus introduces the notion of a slot proxy. A slot proxy is not necessarily a slot by itself, but a description of how a value can be accessed. Some proxies are direct: they simply refer to an already known slot. Others are indirect: they describe an access path that must be resolved at runtime. The expression x[2].age can be reduced to a direct sub-slot, while x[i].age becomes a proxy that says, in effect: start from the slot occupied by x, use the runtime value of i to select an element, and then access the age field within that element. In general, modifications made to that element (e.g. x[i].age += n) will need a read-modify-write cycle where the element is first materialized into a known, temporary slot (much like a hardware register), modified and written back using a dynamic write-algorithm. This process of materialization and write-back is shown conceptually in Figure 47.

The distinction between actual slots and proxies that represent them allows the compiler to treat simple variables, struct fields, array elements and pointer dereferences in a uniform way. Code that needs to read from or write to an expression does not have to know immediately whether the target is a fixed slot or a dynamically computed location. It can ask the proxy to materialize the value into a concrete slot, or to write a concrete value back through the described access path.

For the purposes of this chapter, slot proxies should therefore be understood as compiler-level access paths. They bridge the gap between the static memory layout known at compile-time and the dynamic addresses that sometimes have to be computed at runtime. This idea becomes especially important in the caching system (Chapter Caching), which is designed to limit unnecessary materialization and synchronization events.

Local Memory Management

Declaring a local variable means reserving a slot inside the current function frame. The slot is assigned a type, a size and an offset relative to the start of the frame. From that point onward, the variable name refers to this slot until it goes out of scope. Since the offset is fixed, accessing a local variable does not require a runtime search through the tape.

Temporary slots are allocated in the same frame when the compiler needs short-lived storage. This happens, for example, when evaluating intermediate expressions, materializing a slot proxy, or running algorithms that require additional scratch space. Unlike named locals, temporaries are not part of the source-level program and may be released as soon as the generated code no longer depends on their contents.

When a slot is freed, either because a local variable leaves scope or because a temporary can be dismissed, its region is marked as available. The contents of the underlying macro-cells are not necessarily cleared immediately; freeing a slot only means that the compiler is allowed to reuse that region for later storage. When a new slot is allocated, a sufficiently large available region may be split into an occupied part and a smaller remaining available part. Conversely, when a slot is freed, neighbouring available regions are merged back together. This prevents the local frame from becoming unnecessarily fragmented and allows larger slots to be allocated later when enough adjacent macro-cells have become free. This management system is discussed in more detail in Chapter Memory Management.

Frames and Calls

A frame groups all data belonging to one function activation. Each frame contains the local control cells, optional return storage, arguments, named locals and compiler-generated temporaries (and cached values). Function calls can then be viewed as transitions between frames: the caller prepares the callee frame, moves the data-pointer to the start of the frame and sets the TargetBlock value to the callee’s entry block. When a function returns, the data-pointer is moved back to the caller’s frame and execution continues at the first block beyond the call. Each of these steps will be described in more detail in the sections below.

Reference Frames

Each stack frame acts as a frame of reference, or coordinate system, to the data-pointer. Since function calls happen dynamically, stack frames are allocated dynamically as well. This means that the compiler has no way of knowing where the data-pointer is located in an absolute sense (i.e. with respect to the start of the BF-tape). Instead, it keeps track of the pointer-location with respect to the start of the current frame. Pushing a new frame on top of the stack and moving the pointer to the start of this frame can then be seen as performing a coordinate transformation—or rebase—of the pointer: the origin is now in the frame of the callee rather than the caller.

Global Data Frame

Global data is allocated in its own frame at the very start of the data-tape, i.e. frame 0. This frame is not owned by any function and is accessible from any other frame to fetch data from or write to. Like dynamic array accesses or pointer dereferences, a global slot is accessed through a slot-proxy and will be materialized locally before any work can be done on it. This introduces synchronization issues across call boundaries, which will be addressed in Chapter Caching. In the sections below, the concept of (stack) frames refers to frames actually tied to the functions being executed, not the global frame.

Frame Layout

The exact layout of a frame depends on the nature of the function that it belongs to, depending on the return-type and number of arguments it takes. However, each instance of a function-call will cause an identical frame-layout to be generated as a result. In general, a frame is laid out as follows (in terms of macro-cells):

1. TargetBlock: a macro-cell whose Value fields are set to the index of the next block scheduled for execution and whose FrameMarker is set to 1, indicating the start of a new frame.

2. Run: a macro-cell dedicated to storing a local copy of the program’s run-state. As soon as this flag is set to 0 (from any frame), none of the blocks will execute and the main loop will be aborted.

3. ReturnSlot: Depending on the return-type of the function, a slot is allocated to hold the return-value. Note that this slot is located at a fixed offset, so it can be reached easily even from within the caller’s frame in order to fetch the return-value. If the function returns void, this slot does not exist at all.

4. Locals: Data local to the frame, which can be categorized further:

   1. local variables (including function arguments), organised in slots as discussed before in Section Slots.

   2. compiler-generated temporaries

   3. cached materializations

Calls, Returns and Meta-Blocks

Calls

To call a function, the caller has to perform the following actions:

1. Set the caller’s TargetBlock to the ID of a compiler-generated meta-block. This is the continuation that will run after the callee returns (described in the next paragraph).

2. Copy or materialize the function arguments into the argument slots of the next frame. The offsets are known relative to the caller’s frame, so this does not require a runtime search.

3. Initialize the control cells of the callee frame: its Run cell is set and its TargetBlock is set to the callee’s entry block.

4. Move the data pointer to the start of the callee frame and treat this position as the new origin.

After these steps, the runtime naturally dispatches to the block whose ID is now stored in the TargetBlock cell of the freshly initialized stack frame.

Meta-blocks

These are compiler-generated code-blocks that are scheduled at the time of the call, while still in the caller’s frame. When the pointer is popped back to this frame after the callee returns, this is the value that is observed and used to determine the next block to be executed. This block is then responsible for making sure that

1. the return value is fetched from the callee’s frame and copied into the return-slot of the caller (if provided; it may also be ignored),

2. the state of the run-flag is copied back into the caller’s frame (to propagate its state in case the callee changed it), and

3. the TargetBlock cell is set to the ID of the block following the call.

Propagating the run-flag like this makes early termination compositional: if a callee stops the program, the caller observes the same stopped state after the return metablock has run. This allows a (builtin) function like abort() to be implemented.

Returns

To return control to the caller, we only need to make sure that the return-slot is populated appropriately and pop the data-pointer back to the frame below. The meta-block has already been scheduled and will take control immediately, finishing the transaction as described above.

Figure 48 shows data transfers and the setup that occurs while performing a call and returning from it. At the call-site, the target-blocks are set and arguments are copied over to the next frame. When returning and control has been passed to the meta-block, return-data is copied back from the callee’s frame into the current one.

Notice that the return address is not stored on a hardware stack. It is encoded as a block ID in the caller’s TargetBlock cell. Returning to the caller therefore means restoring the caller frame; the scheduler will then execute the metablock whose ID was already waiting there.