It's arrays all the way down

I keep picturing ticker tape. Given a long enough strip, I ought to be able to write down a tree, a graph, or whatever other structure I need. In my mind, the branches are information. Why should that information need user pointers?

Floatyboat, my array-language experiment, needs an answer. I've been quite enthusiastic about leaving features out.

It would be annoying to discover that I've also left out the ability to do anything useful.

Writing the information down seems achievable, but how do I use it efficiently?

I can put a shopping list in a photograph too, but I wouldn't want to implement a shopping-list application that way.

A long enough tape

Turing's computing machine has a tape divided into squares, symbols written on them, and rules for reading, writing and moving between squares. His universal machine reads an encoded description of another machine and performs its computation.

I like that simplicity. What goes on the tape? The entries and relationships the structure needs. A more elaborate thing doesn't demand a more elaborate tape, and a finite tree doesn't need little branches growing out of the memory to preserve its relationships. The operations need a way to read them.

I'm borrowing the tape as a way to think about linear storage. Several arrays can do that job.

Start with something that has fields

Two records are an easy place to begin:

{id: 31, score: 12}
{id: 46, score: 18}

I can give each field a column, with position zero in each column belonging to the first record and position one belonging to the second. The grouping survives even though the fields aren't stored beside one another.

Records with id 31 and score 12, and id 46 and score 18, become an id column of 31 and 46 and a score column of 12 and 18. Matching positions preserve the records. — **Figure 1 - Keep the grouping by position.** The dotted guides join fields belonging to the same record. Reading one field across all records needs only its column.

To add the scores, I can read that column without fetching the IDs along the way. If I'm mostly asking for whole records instead, I'll be reaching into both columns every time.

So far, this is a pleasant exercise in moving fields about. A tree asks a more interesting question. How does nesting survive?

The tree is in the relationships

Here is a little directory tree. Give every entry a position in a flat collection, called a node pool:

0 project
├── 1 src
│   ├── 3 main.fb
│   └── 4 helpers.fb
└── 2 README

A parent column can hold the relationships. Entry three's parent is entry one and entry one's parent is entry zero. And the root? It has no parent. I can record that with a separate validity flag.

Figure 2 - The nesting survives in a column. Arrows follow parent positions.

The zero in the root's parent slot isn't a secret extra node, it's unused data, and checking the flag tells the operation to stop instead of treating zero as a parent and reading the root forever.

I quite like being able to draw the tree and then lay it out flat without losing anything.

Give me a few boxes and arrows and I can entertain myself for ages, although eventually the arrows start crossing and I'd want another sheet of paper.

The picture helps me understand the directories. Their memory can be arranged differently. My first instinct is to try the parent column. Going upwards takes one indexed read. What about going down? Finding children means searching for matching parent positions, and doing that for every directory would soon get tiresome. I'd group the children too if that's the operation I keep asking for.

And the index is still a reference. Reading parent[parent[3]] means fetching entry three's parent before I know which position the next read should use. Renaming pointers to integers hasn't made that dependency disappear. I'm quite pleased with the encoding, well, until I start following the reads.

Put the variable-length parts on the tape too

Trees are a fairly friendly case. Now let two entries share a destination or let a path lead back to where it started. Those relationships belong on the tape too. Copy a branch each time? That would lose the shared destination and leave me copying forever when the path loops back. Here's a graph with four vertices and their neighbours:

A → B, C
B → C
C → A
D → nothing

How many slots per vertex? A has two neighbours, B has one and D has none, so leaving spare slots beside each vertex asks me to choose how much space to reserve for each list, including an empty one like D's. One position won't do. Instead, I can flatten the lists into one target column and record each list's start in an offsets column:

vertices = [A, B, C, D]
offsets  = [0, 2, 3, 4, 4]
targets  = [1, 2, 2, 0]

Start with B at vertex position one. Where is its list? Read offsets one and two. They contain two and three. B's neighbours occupy target positions from two up to three but excluding three, so that range contains only 2, the position of C.

There is one more offset than there are vertices, so the final list has an end too. D's two offsets are both four. Its list is empty, without needing a special empty allocation.

The graph A to B and C, B to C, C to A and D to nothing is stored as offsets zero, two, three, four, four and targets one, two, two, zero. C's neighbour range is targets three to four, containing A. D's range four to four is empty. — **Figure 3 - Each pair of offsets describes a list.** Dashed outlines mark C's two offsets and its target entry. C reads [3, 4). D reads [4, 4), which contains no entries. Target values are vertex positions.

I can send both A and B to C, and C back to A. I don't have to decide which branch of a nested value C belongs in, or keep copying it as the graph loops back. Both target entries name the same vertex position.

This is the organisation behind compressed row storage, used for sparse matrices. A row's entries are grouped into one range. Here the same organisation gives me an array of variable-length lists, whose entries can name positions in another array, including a position that another list already names.

Strings can use a related arrangement, with offsets into a shared byte buffer which mark each boundary without requiring a separate heap allocation for every string. A few familiar structures start looking less exotic:

What I want to represent	One possible array encoding	What still needs choosing
Records	One column per field	Whole-record or field-wise access
Strings and nested lists	Packed contents and offsets	Boundaries, empty values and updates
Trees	Node columns and relationship indices	Which traversal directions to support
Graphs	Offsets and target indices	Traversal order and changing edges
Sets and maps	Sorted entries or a hash table	Point lookup, ranges and insertion costs

I can choose per operation. A sorted key column helps with ranges while a hash table organises point lookups differently, so choosing between them is still a real decision even though both are arrays underneath.

Which column? Vertex positions and target-column positions are both integers and in this tiny graph both even have four possible values. Three can mean vertex D or the target entry containing A. Both reads are within bounds but they answer different questions. Only I know which one I meant to ask.

Does it keep the machine busy?

I've got a tree into arrays.

Lovely.

I'd be disappointed to go to all this trouble and keep the same waiting. Packing related entries together can bring several into cache with one fetch, but a pointer-based tree can use a pool too.

With the graph, I've got each vertex's neighbours together and I can read through that little run because I know where it starts and ends. Following a whole path is another matter. I have to read an edge before I know which vertex it leads to.

Several queries at once. I could have unrelated parent lookups in progress while one of the reads waits. Following one entry all the way to the root still has a chain of dependencies, but the separate lookups give me other work to do.

Following main.fb to src to project requires the previous parent read before the next position is known. Independent parent lookups have separate inputs. A graph neighbour range can be read in order after its offsets are known. — **Figure 4 - Flat storage leaves different kinds of work.** Arrows in the first path mean the next read depends on the previous result. Separate lookups and a contiguous range offer other ways to organise the reads.

My harvester picture is still driving this. Reading the neighbours is a neat run through targets, but using those positions to read another column can send me all over it again.

Right, then I have to build the thing. I'd be cheating myself if I timed only the part after all the sorting and grouping had finished. If every tiny change makes me do that preparation again, the read path could cost more than it saves.

For now, I'd build a value and do plenty of work against it. Bulk changes would produce the next value. One change at a time? A priority queue receiving a change that determines its next change is a different problem. I can't turn that dependency into independent work by storing the queue in an array.

I'm trying to leave these choices to the compiler without making the caller write a storage plan. The lifetime question asks who can still read a value. Here I'm also asking who can observe its arrangement, and which operations actually need that arrangement.

This integer belongs over there

Checking the correct flavour of three isn't how I'd like to spend my time. I'm considering %link[vertices] to attach the intended collection to a position in the type information, distinct from a position in targets.

Position three in vertices reaches D, while position three in targets reaches zero, which names A. Both columns have four entries. A proposed typed link identifies the intended target column, even when the numeric ranges agree. — **Figure 5 - Being in bounds isn't the whole question.** The proposed link annotation names the target collection. It gives the compiler information that the integer three alone doesn't contain.

Let me use the graph without owning its columns

The link wouldn't be a machine address. It would identify the collection a position belongs to, with the ordinary integer index underneath, so the compiler could reject a tagged edge position passed where a vertex position is required. Bounds and absence remain separate questions. “Vertex position” doesn't make an arbitrary integer valid and the root still needs its no-parent case. The tag would keep the intended relationship attached as the value passes through operations.

Do correct tags keep offsets and targets consistent? Not when a caller can replace one column and forget the other. If everybody can construct the storage directly, everybody has acquired a little graph-maintenance job.

This is where I'm considering an abstract qualifier. Here's the sort of declaration I have in mind:

abstract type Graph struct {
    vertices Column[Vertex]
    offsets  Column[Int]
    targets  Column[%link[vertices]]
}

The package implementing the graph would own access to those fields and the operations that construct them, so callers could ask for neighbours or build a graph from edges without manufacturing matching offsets by hand.

Callers use graph construction and neighbour operations. Inside the proposed graph package boundary, vertices, offsets and targets are kept consistent. Direct field access and construction from outside the package are closed off. — **Figure 6 - Keep the representation inside its package.** Operations cross the boundary. Constructing and reading the underlying columns belongs to the graph implementation.

I can put the fiddly rules in there and stop asking every caller to remember them. Offsets must be ordered, their final value must agree with the target count, and every target must name a vertex. The graph implementation has to establish those facts when it builds the value. The abstract qualifier locks the door. Somebody inside still has to do the housekeeping.

Hiding the fields would leave room to change their storage without requiring every caller to change. That freedom appeals to me. Moving entries would mean updating every affected link and preserving any positions or ordering the caller can observe.

I'd start with this graph and give it more than a neat sweep through the targets, following paths and changing edges in batches before querying it again. Can I keep thinking about the graph? Let the compiler deal with the arrays underneath.