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.
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 · list | Output · list or int | Remove |
|---|
Loading the default specification…
Ready.
The DSL, in full
| Term | Type | Meaning |
|---|---|---|
xs | list → list | the input (identity, cost 0) |
reverse, sort, tail | list → list | reverse; ascending sort; drop the first element |
take(k), drop(k) | list → list | first k / after the first k; k ∈ {1, 2, 3}; clamped |
map(f) | (int → int) → list → list | apply f to every element |
filter(p) | (int → bool) → list → list | keep the elements that satisfy p |
count(p) | (int → bool) → list → int | how many elements satisfy p |
sum, length, max, min, first, last | list → int | aggregates. max, min, first, last of [] are 0 |
pipe(f, g) | list → list then list → T | apply f, then g; T is list or int |
+1, +2, ×2, ×3, −x | int → int | element functions for map |
even, odd, >0, >1, >2, <2 | int → bool | predicates 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.
| # | Program | Cost | Fails | Score | Check |
|---|
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.
Pruning changes the cost, not the answer.
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)).
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.
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.
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
- 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. - 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.
- 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.
- 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.
- Watch deduplication. Choose “Two programs, one behaviour” and compare the duplicate counter with deduplication on and off.
pipe(take(3), map(×2))andpipe(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 →