---
title: "Compositional design studio"
---

<!-- PLAN (author, 2026-10-10; reviews/panel-legal-parallel.md): when this chapter is written, its design briefs and its No-AI check end with the preface's own question, "What did we leave out when we asked the question that way?", as the check before accepting a contract. -->

## Prime

Every earlier module handed you primitives and showed one or two famous algorithms built from them. This module
has no new primitives. Its subject is the act you have been rehearsing all along: taking a real, messy, system
level problem, choosing primitives, snapping them together, and stating honestly which guarantees survive the
composition and which do not. This is the skill that the whole book exists to build.

## Probe

::: {.callout-note title="Try first (no AI)"}
Design a small document store that supports three operations: add a document, ask whether a document id is
present, and find every document containing a given substring. It should answer "not present" fast, keep
ids in sorted order, and never return a wrong search result. Which primitives from earlier modules would you
reach for, and where could one of them quietly break a guarantee if you are not careful?
:::

Do not implement it yet. List the primitives, the interfaces between them, and the guarantee for which each is
responsible. That list is the design.

## Point

There is no single new idea to reveal here, only a method, which we can name.

> **Composition is choosing primitives whose guarantees compose.** For each part of a system, pick the primitive that
> supplies the property that the part needs, wire the parts through clean interfaces, and then check the seam:
> does a primitive's failure mode leak into the whole? A composition is only as strong as the assumptions that
> survive it.

The worked store in `implementations/studio_demo.py` composes three primitives from three modules:

- a **B-tree** (search chapter, tree-slack) keeps document ids in sorted order with cheap inserts;
- a **Bloom filter** (streaming chapter, fingerprint plus sketch) answers "definitely absent" instantly, with no
  false negatives;
- **Rabin–Karp** (module M3, fingerprinting) searches for a substring inside each document.

The seam that matters is the Bloom filter. It can report a false positive, so a positive is confirmed
against the real store; it never reports a false negative, so a negative is final. Stated carefully: the
Bloom filter only ever saves work, it never changes an answer. That is a guarantee that survives
composition, and the property test proves it, checking that membership has neither false negatives nor false
positives and that search is exactly a naive scan.

## Attach

The generative payoff of the whole book lives here.

> Primitives are not only for decomposing known algorithms; they are seeds for inventing new ones. Once you see
> that a tree gives slack, a fingerprint makes equality cheap, a residual edge lets you undo, and a
> certificate proves optimality, you can combine them in ways that no textbook lists, to fit a problem no one
> has handed you before.

Some system briefs to design, each ending with the same demand: name the primitives, define the interfaces,
state the guarantees, the costs (time, memory, I/O), the assumptions, and which guarantees fail under
composition.

- A resilient distributed store: indexing (M2), fingerprints for integrity (M3), coding for redundancy.
- Routing under changing traffic: shortest paths (M6) recomputed with sketched summaries (M11).
- A streaming anomaly detector: Count-Min and reservoir sampling (M11) feeding a scoring rule.
- A retrieval system for an AI agent: embeddings and nearest neighbor (M4), plus exact substring recall (M3).
- Public-resource allocation under constraints: flow and matching (M7), linear programming (M8).

## Strengthen

- Implement the document store and confirm, as the property test does, that membership never lies and
  search is always exact.
- Swap the B-tree for a skip list. Which guarantees change from worst case to with-high-probability, and
  does the system's promise change?
- Add a Count-Min sketch to report the most-searched terms. Where does its overestimate leak, and is that
  acceptable here?
- Adversarial input: an attacker who floods the store with ids engineered to collide in the Bloom filter.
  What degrades, and what stays correct?

## Test

::: {.callout-note title="No-AI check"}
Design, on paper, a system that ingests a high-rate event stream and answers two questions: "have we seen
this exact event id before?" and "what are the current heavy-hitter event types?" Name each primitive you use,
the guarantee it provides, its failure mode, and one place where composing two of them could break a
promise if you were careless. Then invent one small variant of a primitive in this book that would improve your
design, and say why it works.
:::

## Frontier map

- **Formal verification.** Prove a composed system satisfies its specification, rather than testing it.
  Signature: guarantees that must hold for all inputs. Reach for it when a failure is unacceptable.
- **Zero-knowledge and verifiable computation.** Let one party prove a computation was done correctly using
  far less work than redoing it. Signature: trust without re-execution. Reach for it when you must verify an
  untrusted result. The durable idea: a verifier can check far faster than a prover can compute.
- **Agent safety.** As algorithmic systems act on the world, composing their guarantees, and knowing which
  fail, becomes a safety question, not only an efficiency one. Signature: autonomy under constraints. This
  is where compositional thinking stops being a convenience and becomes a responsibility.
