Course / Lectures / Lecture 10 / Lab Lab 10

The program is in the space.

Give the synthesizer a few input–output examples. It enumerates a small typed list language by cost, prunes what cannot be well typed, and returns the first program that agrees. Turn pruning off and watch the search get larger — without changing the answer.

7 presets 5 cost bound 2 panels · search & ranking Deterministic · no install

The program synthesis lab

01 · The specification

Choose a preset, or edit the examples. Press Run search to enumerate, or Step to expand one candidate at a time.

#Input · listOutput · list or intRemove

Loading the default specification…

Ready.

The DSL, in full
TermTypeMeaning
xslist → listthe input (identity, cost 0)
reverse, sort, taillist → listreverse; ascending sort; drop the first element
take(k), drop(k)list → listfirst k / after the first k; k ∈ {1, 2, 3}; clamped
map(f)(int → int) → list → listapply f to every element
filter(p)(int → bool) → list → listkeep the elements that satisfy p
count(p)(int → bool) → list → inthow many elements satisfy p
sum, length, max, min, first, lastlist → intaggregates. max, min, first, last of [] are 0
pipe(f, g)list → list then list → Tapply f, then g; T is list or int
+1, +2, ×2, ×3, −xint → intelement functions for map
even, odd, >0, >1, >2, <2int → boolpredicates for filter and count

Cost. Every constructor costs 1: map(f) costs 1 + cost(f); pipe(f, g) costs 1 + cost(f) + cost(g). Enumeration is by increasing cost, so the first consistent program is the cheapest one in this order. The bound is a choice, not a theorem about the world.

02 · The search

Space at this bound: — (raw / well typed)

Trace

The last 16 candidates the search dequeued. “Pruned” means the type checker rejected the term before evaluation; “duplicate” means an earlier program behaved identically on the examples and the fixed probes.

    03 · The ranking

    A second way to order the same typed candidates. The score is cost + prior; the prior is hand-set and never looks at the examples. The check column is the search.

    #ProgramCostFailsScoreCheck

    Read this honestly. A hand-set prior is not a learned model, and a score is not a proof. In this shallow space, cost order is already optimal in cost; the prior can only win if it reorders within a cost layer. The panel is here to show the mechanism, not to claim a speedup.

    WHAT TO NOTICE

    Pruning changes the cost, not the answer.

    REGIME 01 · PRUNING ON

    The typed space

    At cost 4 the grammar has 486 well-typed programs; at cost 5 it has 3,103. The enumerator only builds terms that can have a value, so every candidate it evaluates is a real program. The default preset expands 1,041 candidates before it finds pipe(map(×2), map(+1)).

    REGIME 02 · PRUNING OFF

    The raw term space

    The same bound has 7,801 arity-respecting terms at cost 4 and 81,563 at cost 5. Most are ill-typed: map(even), filter(+1), pipe(sum, reverse). The search must expand them to discover that they cannot be programs. The default preset expands 53,083 before the same answer.

    REGIME 03 · NO SOLUTION

    The bound is real

    The “Impossible: add an element” preset asks for a longer list, which no term in this DSL can produce. The search exhausts 300 typed candidates and says so. A synthesizer that always returns something is not synthesizing; it is guessing.

    What this shows — and what it does not

    It shows a real enumerator over a fixed typed DSL: exact counts, exact type checks, exact example checks, a real search trace, and a real ranking. It does not show a neural synthesizer, a learned heuristic, a library-learning system, or a theorem prover. The DSL is tiny and fixed; the bound is 5; the examples are the whole specification; and deduplication is only relative to the example inputs and ten fixed probes. A program that is consistent here can still be wrong on an input you did not give.

    Things to try

    1. Watch one candidate at a time. Choose “Add one”, press Reset, then Step until map(+1) appears. Count the candidates before it: the trace shows the type-pruned, duplicate, and failing ones.
    2. Turn pruning off. Choose “Double, then add one”, run once with pruning on, note the expanded count, then uncheck type/arity pruning and run again. The answer is the same; the expanded count is not.
    3. Break the specification. Choose “Impossible: add an element” and run. The search reports no program. Now add an example that a program in the DSL can satisfy, and watch the answer change.
    4. Compare the two orders. Choose “Sort, then reverse” and read the ranking panel. The hand-set prior checks more candidates than cost order. Choose “Double, then add one” and it checks fewer. A prior is a bet, not a guarantee.
    5. Watch deduplication. Choose “Two programs, one behaviour” and compare the duplicate counter with deduplication on and off. pipe(take(3), map(×2)) and pipe(map(×2), take(3)) agree on every list; the enumerator stops at the first, and the counter shows how many earlier candidates were already covered.

    Read §1 · the search space · Read §3 · induction and ILP · Back to Lecture 10 · Slides →