The five pages that died

A tax booklet: sixty questions, intimidating. You answer one — "Are you self-employed? No" — and section D, all five pages of it, ceases to apply to you.

Notice exactly what happened, because it's subtler than "you made progress." The booklet did not get five pages of your answers written into it. It became a different, smaller booklet — one containing every question that still matters given what you've said, and none that can no longer affect your taxes. Answer another question and that booklet shrinks again. The form-filling experience is a chain of forms, each the residual of the last under one answer.

Passport applications, insurance quotes, airport kiosks — "skip logic" is the form-design industry's name for engineered residuals. The rest of this chapter is that idea, made precise and then found running your shell, your compiler, and your database.

One prefix, one shared corridor

Imagine storing car, card, care, careful, and cargo as five complete strings. Their first three letters are copied five times. Now draw one edge per next letter. All five words walk through the same c → a → r corridor and branch only where they differ. The structure is a trie, named from “retrieval.”

After you type car, completion does not scan the whole dictionary. It follows three edges and arrives at one node. The subtree below that node is exactly the set of possible endings: empty for car itself, d, e, eful, and go. The trie made the residual physical.

Your shell is holding the residual

The same shrinking booklet lives at your command line. A deploy tool accepts commands of the shape: deploy, then an environment (staging or prod), then optionally dry. Before you type anything, the space of valid commands is the whole little language. Type deploy, and the language that remains is "an environment, then maybe dry." Type prod, and what remains is "nothing more, or dry." Completion is not intelligence — it's the residual, read aloud.

Drive it. Step the machine through the command one word at a time; the highlighted state is the residual — everything about your future the machine still needs to know. Watch what each word does to what remains.

This is why completion in zsh, fish, and nushell can be both instant and trustworthy: the machine never guesses. The residual of a finite machine is just another state of the same machine — computed by following one arrow, a constant-time step. Sixty booklet pages or sixty thousand grammar rules: fixing an answer never makes the remaining question harder, only smaller.

The algebra of stopping early

Say it once with symbols, since your hands have now done it twice. A machine (or form, or program) computes a function $F$ of many answers. Fix the ones you know — a partial assignment $p$ — and the residual is the restriction

$$F|_{p} : \text{remaining answers} \longrightarrow \text{verdicts},$$

with two properties doing all this chapter's work:

• Composition: answering in installments is answering. $(F|_{p})|_{q} = F|_{p \cup q}$ — the chain of shrinking booklets lands where the single big form would have.
• Preservation: the residual answers exactly like the original wherever they overlap. No verdict changes; only irrelevant machinery falls away.

You have seen this operation before on this trip, wearing chapter one's geometry: fixing an answer is slicing the product space along one axis and keeping your slice. The previous chapter's diagrams make the slice visible: fixing a variable in a decision diagram means taking one branch of each node that tests it — what remains is literally the sub-diagram your answers select. Skip logic, slicing, branch-taking: one operation, three pictures.

And the dead pages have a precise definition now: a question is dead under $p$ when no assignment of the remaining answers can make it matter — when it has fallen out of $F|_{p}$ entirely. Dead-code elimination and skip logic are the same theorem applied by different professions.

Commit before moving on:

Now bring your own grammar. The evaluator below is the automaton above with the training wheels off: define commands in a bounded language — one per line, staging|prod for alternatives, [dry] for optional — then type a partial command and watch the residual answer in real time: the completion chips are every word still valid, "you could stop here" is the accepting state, and a wrong word names itself. Paste your own tool's subcommands and see what your shell sees.

The same operation, three famous times

Compilers: constant folding and dead-branch elimination. A build sets DEBUG = false. The compiler restricts the program under that answer: if (DEBUG) branches fold away, the logging call inside them dies, functions reachable only from it die in turn — a residual program, provably verdict-identical for every remaining input. The academic ceiling of this move is partial evaluation: specialize an interpreter to one fixed program and the residual is a compiled program — the first Futamura projection, one of computer science's great "wait, that works?" results.

Databases: predicate pushdown. WHERE region = 'EU' known at plan time lets the engine hand each storage shard the residual query — scan only EU partitions, read only surviving column ranges. Spark and every serious SQL engine advertise exactly this under "pushdown": evaluate what's known as early as possible, ship the residual to where the data lives. Chapter one's projection asked "does anything satisfy this?"; pushdown answers "then only visit the region that could."

Shells and form engines. The completion systems of zsh, fish, and nushell maintain, in effect, the residual grammar of the command line as you type — the automaton island above, scaled to thousands of commands. Form engines with skip logic (every serious survey and tax product) are the same residual, rendered as disappearing sections. When the skip rules are declarative, "which questions can never be reached?" — dead branches — is mechanically checkable before a single user is confused by a question that cannot matter.

Where stopping early runs out

• Residuals can grow before they shrink. Restricting a diagram or automaton only ever shrinks it — but partially evaluating a general program can explode: unroll a loop over a known bound of a million and the residual is a million copies of the body. Partial evaluators fight blow-up with heuristics about what to unfold; "smaller" is a theorem for finite machines and a hard-won engineering outcome for programs.
• Only genuinely known answers may be fixed. Fold a "constant" that production later overrides (a feature flag read at runtime, an environment variable) and the residual silently answers for the wrong world. The compile-time/run-time boundary — what the trade calls binding time — is a design decision, and drawing it wrong is a classic bug family.
• General programs hit the cliff. For finite machines, "is this branch dead?" is decidable. For arbitrary code, perfect dead-code detection is the halting problem in a costume; compilers settle for sound approximations that keep some undead code. The ladder of what stays decidable is the computation track's story, and this trip's SAT chapter owes you the price tags.
• The residual is a snapshot. A residual is correct for the answers it fixed; change an answer and you must re-residualize. Systems that cache residuals (query plans, specialized code) need invalidation — and the memory chapter's cones apply to exactly this.

Lessons

• Fixing part of the input turns a machine into a smaller machine — the residual — that answers identically on everything remaining.
• A trie makes that residual literal: follow the known prefix once, and the subtree reached is the entire remaining dictionary.
• Residuals compose and commute: what's known determines what remains, regardless of the order it became known.
• Completion is the residual read aloud; skip logic is the residual rendered; constant folding is the residual shipped; pushdown is the residual mailed to the data.
• A question is dead under an assignment when no remaining answers can make it matter — mechanically detectable in finite machines, only approximable in general programs.
• Fix only what is truly known: a residual built on a wrong "constant" is a fast, confident, wrong machine.

Practice

A residual can return to where it began

Consume one letter and a finite machine moves to another residual. Sometimes, after enough inputs, it returns to a residual it has seen before. A traffic signal repeats after red, green, and yellow. A weekly calendar returns to Monday after seven steps. Ordinary arithmetic on a clock wraps for the same reason: only finitely many remainders exist.

The next chapter turns that repetition into algebra. It explains why 23 + 4 can equal 3 without contradiction, and why the same circle checks identifiers, schedules repeating events, and powers ciphers.

References

1. Jones, Gomard, Sestoft. “Partial Evaluation and Automatic Program Generation.” Prentice Hall, 1993. — the field's standard book, free online from the authors — ch. 1 is a gentle formalization of exactly this chapter
2. Brzozowski. “Derivatives of Regular Expressions.” JACM, 1964. — the residual-of-a-language paper; the finitely-many-derivatives theorem is why completion machines stay finite
3. Owens, Reppy, Turon. “Regular-expression derivatives re-examined.” JFP, 2009. — the modern, implementable retelling of Brzozowski — the best next read if you want to build the machine
4. Futamura. “Partial Evaluation of Computation Process — An Approach to a Compiler-Compiler.” Systems·Computers·Controls, 1971. — the projections: specialize an interpreter, receive a compiler; reprinted with commentary in Higher-Order and Symbolic Computation 1999
5. “The Z Shell completion system.” zsh docs. — production residual-grammar machinery; compare fish's completions for a different engineering of the same mathematics
6. “Performance Tuning: predicate pushdown.” Apache Spark docs. — the residual mailed to the data, in a system's own words
7. Muchnick. “Advanced Compiler Design and Implementation.” Morgan Kaufmann, 1997. — constant propagation and dead-code elimination as production algorithms — ch. 12–13 are this chapter with worklists
8. Fredkin. “Trie Memory.” Communications of the ACM, 1960. — the paper that introduced the term for prefix-sharing memory