Structures, Representations, and Operations

1.1 The question this book asks

Every programmer learns early that an array lets you read element $i$ “in constant time”, while a linked list makes you walk to it. The usual explanation is mechanical: the array’s elements sit side by side in memory, so the machine can compute where element $i$ lives; the list’s elements are scattered, so the machine must follow pointers. Both explanations are true. But notice what they are really about. They are about the relationship between a description of an operation — “element $i$” — and the machinery that carries it out.

This book is about that relationship, taken seriously and made precise. Its research program was formulated by Abed Kadaan, who arrived at it from work on programmable addresses: addresses that do more than locate a resource, because they also identify a state, select a transformation, and record a history of transitions. In such a system an address behaves less like a label and more like a sentence in a small language, and the language has a grammar. The question that follows is general:

Can the grammar of a computational structure — the formal rules saying which operations are admissible, how they compose, and what they mean — become part of the machinery by which the structure is operated on, and not merely a description of it?

The motivation is not evidence, and this book does not treat it as such. The question has to be answered the way any question in computer science is answered: by precise definitions, by algorithms and their analysis, by proofs, by reproducible experiments, and — just as importantly — by counterexamples that mark where an idea stops working. Some of the answers turn out to be positive and new; many turn out to be known results seen from a new angle; several turn out to be negative. All three kinds of answer appear in this book, labelled as such.

1.2 Elements, relations, and states

We begin with the most ordinary vocabulary.

The definition is deliberately bland. It is the standard notion of a finite relational structure from logic, and nothing in it is new. Its value is that it lets us talk about very different data structures in the same words.

The state of a structure is everything an operation can inspect or change: which tuples are present, the labels, the distinguished elements. A program that manipulates a structure moves it from state to state.

1.3 Operations are partial

An operation inspects the current state, possibly changes it, and possibly returns a value. Reading the third song of the playlist returns a value and leaves the state alone; inserting a song changes the state. Crucially, many operations are partial: reading the seventh song of a five-song playlist is not an operation that “returns an error value”; it is an operation that is not defined in this state.

This distinction matters throughout the book, so we fix it now. When an operation is undefined in a state we will say that its denotation is empty. In the formal treatment of Chapter 7, each operation $a$ denotes a relation $\sem{a} \subseteq A \times A$ between states (or elements), and “undefined at $x$” means $\sem{a}(x) = \varnothing$. Programming languages report this with exceptions, sentinel values or crashes; the mathematics simply records that there is no successor state.

1.4 Representations

A structure is a mathematical object. A representation is a concrete layout of that object in a machine’s memory: a bit string, an arrangement of memory cells and pointers. The same structure has many representations, and the representation, not the structure, determines what operations cost.

The same pattern recurs for every structure in Part I. A graph can be stored as an $n \times n$ adjacency matrix or as adjacency lists; a binary tree as linked records or as an array in “heap order”; a set as a sorted array, a hash table or a balanced tree. In each case one representation makes some operations cheap and others expensive, and a second representation reverses the trade. The comparison is only meaningful once we say how cost is counted.

1.5 Cost needs a machine model

Throughout the book costs are stated in an explicit machine model.

Three conventions follow, and the book holds itself to them strictly.

1. “$\Oh(1)$” is a claim about a model. It means: a number of word-RAM steps bounded by a constant independent of the parameters that grow, and those parameters must be named. An array access is $\Oh(1)$ as $n$ grows because one address computation suffices; it is not $\Oh(1)$ if the index itself has $n$ bits.
2. Build, storage, query, update and output are separate costs. A query that takes $\Oh(1)$ time after $\Theta(n^2)$ preprocessing is not “an $\Oh(1)$ algorithm”. Chapter 12 develops this into a full accounting discipline (the cost profile).
3. We count, we do not time. The book’s software counts elementary steps — reads, writes, comparisons, pointer hops, hash probes — under a stated cost model. Wall-clock time measured in an interpreted language mostly measures the interpreter; a flat curve of timings over a small range is not evidence of constant time.

1.6 Syntax, semantics, execution

We can now state the organizing principle of the book. Any request made of a structure raises three different questions, and conflating them is the most common source of exaggerated claims about “fast” representations.

The three questions are independent: every combination of answers occurs (CGT-PROP-002).

The SDK that accompanies this book makes the three layers concrete. Executing an expression returns a result that reports each layer separately, and checks that the representation’s answer agrees with a reference semantics:

from cgtsdk.structures import ArrayStructure, LinkedListStructure

for S in (ArrayStructure, LinkedListStructure):
    g = S([10, 20, 30, 40, 50]).grammar()
    for expr in ["get(3)", "get(7)", "fly(1)"]:
        r = g.execute(expr)
        layer = ("syntax error" if not r.syntax.ok else
                 "undefined" if not r.defined else f"value {r.value}")
        print(f"{S.name:12s} {expr:7s} -> {layer:13s} cost {r.cost.snapshot()}")

array        get(3)  -> value 40      cost {'arith': 1, 'compare': 1, 'read': 1}
array        get(7)  -> undefined     cost {'compare': 1}
array        fly(1)  -> syntax error  cost {}
linked_list  get(3)  -> value 40      cost {'compare': 1, 'pointer': 3, 'read': 2}
linked_list  get(7)  -> undefined     cost {'compare': 1}
linked_list  fly(1)  -> syntax error  cost {}

Read the output carefully. The same expression get(3) has the same meaning (the value $40$) on both structures; what differs is the execution layer — one address computation versus three pointer hops. The expression get(7) passes the syntax layer and is rejected by the semantic layer after a single bounds check. The expression fly(1) never reaches semantics: there is no such operation.

1.7 A grammar, informally

A sequence of operations such as get(2); set(0, 9); get(0) is a sentence in a small language. Its alphabet is the structure’s set of operations; its grammar says which sentences are admissible; its meaning is the composition of the meanings of the individual operations. For an array that grammar is almost trivial: every sequence of get, set, len and the rest is admissible, and indices out of range make a sentence undefined. For other structures the grammar has real content:

• for a stack, a sentence that pops more than it has pushed is undefined — and the set of defined sentences is not even a regular language (Chapter 3);
• for a binary tree, the sentences over the moves $\{L, R, U\}$ (“left child”, “right child”, “up”) are exactly the addresses and walks of the tree (Chapter 5);
• for a graph with labelled edges, a regular expression over labels describes which paths are admissible, and resolving it costs at most a factor $|Q|$ more than ordinary search, where $|Q|$ is the size of the expression’s automaton — a factor that is tight (Chapter 8).

Part II turns this informal picture into definitions. Before that, Part I examines the ordinary structures one at a time, because the definitions must fit them, not the other way round.

1.8 How evidence is labelled in this book

Every formal statement carries a badge saying what kind of claim it is:

• Definition introduces an object; it is not a discovery.
• Established marks a known result from the literature, with a citation.
• Adapted marks known ideas restated or packaged in this book’s terms.
• Proved here marks a result whose proof appears in this book. Such proofs have been checked by their authors and, where possible, by exhaustive computation on small cases, but they have not been independently reviewed.
• Empirical marks a reproducible measurement — evidence, never proof.
• Conjecture and Rejected mark open and failed hypotheses. Rejected hypotheses are kept: knowing where an idea fails is part of knowing the idea.
• Proposed marks a model or design introduced here whose novelty has not been established.

Identifiers such as CGT-THM-006 link each statement to the research ledger, the repository’s permanent record of definitions, hypotheses, experiments, results, counterexamples and decisions.

Report an erratum or an unclear passage in this chapter