The CGT SDK

18.1 Installation and layout

The SDK is a Python package, cgtsdk, with no dependencies outside the standard library (Python 3.10 or later). From a clone of the repository:

cd sdk
python3 -m pip install -e .            # or simply: export PYTHONPATH=sdk/src
python3 -m unittest discover -s tests  # the full test suite

The complete, generated API reference is on the SDK reference page.

18.2 Three layers in one call

Every structure exposes grammar(), and execute returns an ExecutionResult with one field per layer:

from cgtsdk.structures import QueueStructure

g = QueueStructure([1, 2]).grammar()
for expr in ["enqueue(3); dequeue; front", "dequeue; dequeue; dequeue", "enqueue()", "push(1)"]:
    r = g.execute(expr)
    print(f"{expr:28s} syntax_ok={r.syntax.ok!s:5s} defined={r.defined!s:5s} values={r.values} cost={r.cost.total}"
          + (f"  [{r.syntax.error or r.reason}]" if (not r.syntax.ok or not r.defined) else ""))

enqueue(3); dequeue; front   syntax_ok=True  defined=True  values=[None, 1, 2] cost=10
dequeue; dequeue; dequeue    syntax_ok=True  defined=False values=[2, 3] cost=11  [dequeue on empty queue]
enqueue()                    syntax_ok=False defined=None  values=[] cost=0  [call 0: enqueue takes 1 argument(s) ('x',), got 0]
push(1)                      syntax_ok=False defined=None  values=[] cost=0  [call 0: unknown move 'push'; signature is ['dequeue', 'enqueue', 'front', 'len']]

Notice that the structure is stateful: the second expression continues from the state left by the first (the queue then held $2, 3$), which is why its third dequeue is undefined. The reason for each failure is reported — r.reason for the semantic layer, r.syntax.error for an arity error and an unknown move. (The first expression’s ten steps are $3$ for enqueue — two arithmetic operations for the ring index and one write — $5$ for dequeue and $2$ for front.)

18.3 Cost models

A Cost records counts by category (read, write, compare, arith, pointer, hash, probe, alloc, edge, rule). A CostModel weights categories, so one execution can be reported under several models without rerunning it. The SDK ships UNIT (every step costs one) and MEMORY (only memory traffic: reads, writes, pointer hops, probes):

from cgtsdk import MEMORY, UNIT, CostModel
from cgtsdk.structures import ArrayStructure, LinkedListStructure

CACHE_MISS = CostModel("pointer-heavy", 64, (("pointer", 100.0), ("read", 1.0), ("write", 1.0)))
for S in (ArrayStructure, LinkedListStructure):
    r = S(range(1000)).grammar().execute("get(600)")
    print(f"{S.name:12s} unit={r.cost.weighted(UNIT):6.0f}  memory={r.cost.weighted(MEMORY):6.0f}  pointer-heavy={r.cost.weighted(CACHE_MISS):8.0f}")

array        unit=     3  memory=     1  pointer-heavy=       3
linked_list  unit=   603  memory=   602  pointer-heavy=   60003

The third model is a caricature in which a pointer hop costs a hundred times a sequential read — a crude stand-in for cache misses. Cost models are assumptions, and the SDK makes them explicit and swappable instead of hiding them in a single “time”.

18.4 Comparing implementations

compare_functions runs implementations on identical inputs, checks every output against an independent oracle, and reports build and query cost separately. Here are three ways to answer LCA queries on a random tree, with the Euler-tour index’s preprocessing reported as build cost:

import random
from cgtsdk.algorithms import EulerLCA, NaiveLCA
from cgtsdk.lab import compare_functions, format_table, random_parent_array

par = random_parent_array(3000, seed=1, shape="random")
oracle = NaiveLCA(par)
rng = random.Random(2)
queries = [(rng.randrange(3000), rng.randrange(3000)) for _ in range(400)]
def scheme(cls):                     # build once (cost reported as build), then query
    return lambda c: (lambda u, v, cost, _i=cls(par, c): _i.query(u, v, cost))
rows = compare_functions({"walk up (depths only)": None, "Euler tour + sparse table": None},
                         queries, oracle=lambda u, v: oracle.query(u, v),
                         builds={"walk up (depths only)": scheme(NaiveLCA),
                                 "Euler tour + sparse table": scheme(EulerLCA)})
print(format_table(rows))

implementation                    build    per query   space(w) correct
-----------------------------------------------------------------------
walk up (depths only)              3000        14.77          - True
Euler tour + sparse table        133619         6.00          - True

Both schemes preprocess: the walk-up scheme only computes depths (one write per vertex), the Euler scheme builds its tour and sparse table. The richer index pays for its extra build only after $(B_{\text{Euler}} - B_{\text{walk}}) / (q_{\text{walk}} - q_{\text{Euler}})$ queries — cgtsdk.break_even computes this kind of number (Chapter 12).

18.5 Recording experiments

An ExperimentRecord stores the hypothesis, the seed, the parameters and the results, together with the environment. Its fingerprint is a SHA-256 hash of everything deterministic — excluding the environment and any field whose name mentions wall-clock time — so two runs of the same experiment on different machines can be compared by a single string:

import random
from cgtsdk import Cost
from cgtsdk.algorithms import heapsort, merge_sort
from cgtsdk.lab import ExperimentRecord

def run(seed):
    rng = random.Random(seed)
    rec = ExperimentRecord("demo-sorting", "merge sort makes fewer comparisons than heapsort on random input",
                           seed, {"n": 1000}, falsification="heapsort makes fewer comparisons on some seed")
    a = rng.sample(range(10**6), 1000)
    for f in (merge_sort, heapsort):
        c = Cost(); f(a, c)
        rec.results.append({"algorithm": f.__name__, "compare": c.counts["compare"]})
    return rec

r1, r2 = run(7), run(7)
print(r1.results)
print("fingerprints equal:", r1.fingerprint() == r2.fingerprint(), r1.fingerprint()[:16])

[{'algorithm': 'merge_sort', 'compare': 8697}, {'algorithm': 'heapsort', 'compare': 16846}]
fingerprints equal: True b1dc23626e0eb76a

18.6 Extending the SDK

A new structure subclasses Structure and provides four things (the BoundedCounter of Chapter 7 and the Workspace of Chapter 17 are complete examples):

1. SIGNATURE — the moves, as Move(name, params, doc, mutates);
2. abstract() — the abstract value the representation stands for;
3. denote(state, call) — the pure reference semantics, returning (new_state, value) or raising Inadmissible;
4. apply(call, cost) — the instrumented representation, counting every step it performs.

The contract a new structure must satisfy is the adequacy property of Chapter 7: on every expression, apply and denote agree on values and on the first undefined call. The SDK’s tests check this for every built-in structure on thousands of random calls, including undefined ones (tests/test_grammar_structures.py); a new structure should be added to that test. New algorithms should be added with an independent oracle test — brute force on small inputs, or a second algorithm — as every algorithm in tests/test_algorithms.py is.

Report an erratum or an unclear passage in this chapter