Here is a specification a child can read: [1, 2, 3, 4] becomes [3, 5, 7, 9]; [0, 1, 2] becomes [1, 3, 5]; [2, 3] becomes [5, 7]. What is the function? The interesting part is not the answer. It is the explicit object that makes the answer checkable — and the search that finds it.
00 / The hookThree examples, one program.
A program is a discrete object: finite syntax, exact meaning. That makes a different question possible. Instead of asking a model to approximate a function from data, ask a synthesizer to find a program consistent with the data. The output is not a vector of weights. It is a term you can print, inspect, and run.
Suppose the language has a few list operations — reverse, sort, take(k), drop(k), map(f), filter(p), count(p), sum, length, and pipe(f, g) — and the examples are:
| # | Input | Output |
|---|---|---|
| 1 | [1, 2, 3, 4] | [3, 5, 7, 9] |
| 2 | [0, 1, 2] | [1, 3, 5] |
| 3 | [2, 3] | [5, 7] |
The obvious candidates fail. map(+1) gives [2, 3, 4, 5]; map(×2) gives [2, 4, 6, 8]; filter(even) gives [2, 4]. The program that works is pipe(map(×2), map(+1)): double each element, then add one. Three examples, three exact checks.
Nothing in that paragraph required a gradient. The work was done by three choices. A language decides what programs are expressible. A cost decides which program wins when several are consistent. A search decides how to find one without enumerating the language. The examples are the specification; the language and cost are the inductive bias; the search is the algorithm.
The model is not the program. The search is not the learning. The check is not optional.
This is logic as search, the third use in the course. The loss and architecture interfaces put logic inside a model; here the symbolic object is what is being found. A synthesizer searches a grammar; an ILP system searches clauses; a prover searches proofs. The structure is both hypothesis and certificate.
Any finite sample is consistent with infinitely many programs. A lookup table returning the three outputs and 0 elsewhere is consistent with Table 0.1; so is a program that agrees here and differs on input four. The synthesizer returns a program consistent in the DSL, under the cost order; the DSL excludes the table, and that exclusion does the generalizing.
01 / The search spaceA grammar, a cost, a search.
To search, you need a state space. In synthesis, a state is a (partial) program, and the space is generated by a domain-specific language (DSL): a finite set of typed constructors, closed under application. A program is a well-typed term. The grammar must be small enough to enumerate and rich enough to contain the answer — that tension is the design problem.
A DSL D = (Σ, τ, c, ⟦·⟧) has a finite signature, a type assignment, a cost, and a semantics; L(D) is the set of well-typed terms. Given examples E = {(x1, y1), …, (xn, yn)}, synthesis is:
The language decides what can be expressed; the cost decides which consistent program wins; the examples decide consistency; the search decides whether you find the minimum in time. A synthesizer is a search procedure plus a checker — usually an interpreter.
The size of the space
A grammar with b atoms, u unary, and q binary constructors has, at depth h, roughly
With b = 10, u = 10, q = 5: 610 at depth 1, 1,866,610 at depth 2, trillions at depth 3. Every technique here climbs that wall: types remove branches, costs order the frontier, examples cut the space, guidance decides where to look.
The lab's counts are exact. At cost 4 the grammar has 486 well-typed programs; at cost 5, 3,103. Without type checking: 7,801 and 81,563. The 16× and 26× gaps are the value of a type discipline, measured in candidates that never need evaluation.
Enumeration by cost
The simplest complete strategy is bottom-up enumeration: build every program of cost 1, then 2, then 3, evaluating each on the examples. The first one that agrees is returned. With a well-founded cost and finite layers, three properties follow.
- Sound for the examples. Every returned program was run on every example and agreed.
- Complete up to the bound. If a consistent program exists at cost ≤ k, enumeration reaches k and finds one.
- Optimal in cost. The first consistent program is cost-minimal — about the order, not the intended function.
A node is a partial program, an edge is a constructor application, and a goal is a complete program that agrees with the examples. Types cut edges, costs order the frontier, and examples cut subtrees.
So cost order is hard to beat in a small space: a heuristic can find a consistent program sooner, but not a cheaper one. Guidance earns its keep when the solution is deep — cost 12 after a prefix of billions — or when the space is too large to enumerate and the heuristic prunes. At a few thousand candidates, blind enumeration is near-optimal.
Enumeration also wastes work on behaviorally identical programs. Observational equivalence deduplication compares candidates on a probe set and keeps one per signature. It is sound for “consistent with this probe set,” not for all inputs. The lab uses the examples plus ten fixed lists.
Pruning, and what it costs
| Pruning | What it removes | Why it is safe — or not |
|---|---|---|
| Type / arity | Terms that cannot be well typed: map(even), filter(+1), pipe(sum, reverse) | Safe if the type system is sound: an ill-typed term has no value, so it cannot be consistent. |
| Observational equivalence | Terms that behave identically on a probe set | Safe for the probe set only. Two terms can agree on the probes and differ elsewhere. |
| Learned / heuristic | Terms a model or score judges unpromising | Unsafe unless the judgment is provably conservative. A confident model can prune the answer. |
The first row is the lab's toggle. With pruning on, every candidate is well typed. With it off, the enumerator builds all arity-respecting terms and rejects most before evaluation. The answer is the same — the type checker is sound — but the expanded count changes by 51× on the default preset (1,041 versus 53,083).
Cost order returns the cheapest consistent program under your cost. A different prior can produce a different answer; none is “the true function.” A synthesizer disciplines the choice among underdetermined hypotheses; it does not recover the one the world intended.
02 / Deductive synthesisCorrect by construction.
The oldest approach does not search over programs. It searches over proofs. The specification is a logical formula; the program is a witness extracted from a constructive proof that the formula is satisfiable. If the proof is valid, the program is correct by construction. This is deductive synthesis, stated canonically by Manna and Waldinger (“A Deductive Approach to Program Synthesis,” ACM TOPLAS, 1980). The problem is a theorem:
where φ is the full specification: a property that must hold for every input. A constructive proof of (2.1) gives a term for f. That term is the program. The proof is the search; the program is the extract.
A small example: for the specification ∀xs. sum(f(xs)) = 2 · sum(xs), the candidate pipe(map(×2), sum) has the obligation
which follows by induction: the empty case is 0 = 2 · 0; the cons case uses distributivity and the hypothesis. The proof is short because the specification is strong and the program simple. With three examples instead of a specification, no induction is available, and the same program is a guess.
The guarantee is clean, the cost high. A sound proof gives correctness for all inputs, but the prover must prove a theorem at least as hard as the program's correctness, in a logic it can handle: a permutation plus ordering for a sort, a semantic equivalence for a compiler pass, a temporal property for a controller.
Sketches and holes
A middle path keeps the programmer's insight and searches only the unknown parts. A sketch is a partial program with holes: pipe(??1, take(??2)). The shape is given; the synthesizer fills the holes to satisfy a specification, collapsing the space to a product of hole domains.
The standard loop is counterexample-guided inductive synthesis (CEGIS; Solar-Lezama et al., 2006). A synthesizer proposes a candidate for the current sample; a verifier checks it against the full specification. Acceptance stops the loop; a counterexample is added and the synthesizer tries again. It is sound if the verifier is sound and the hole search exhaustive; it terminates if the hole domain is finite and every candidate is eventually ruled out. The loop is a negotiation: the generator is inductive, the verifier deductive, and the sketch is where the programmer's insight enters.
A deductive synthesizer is only as good as its specification. A full functional spec is expensive, easy to get subtly wrong, and often harder than the program. A sketch moves the cost to the programmer's insight — and the shape is most of the design.
03 / Induction & ILPConsistent with the examples.
Inductive synthesis starts from examples and nothing else. Examples are cheap, but a finite sample is consistent with many hypotheses. The consistent hypotheses form the version space (Mitchell, “Generalization as Search,” Artificial Intelligence, 1982). Learning is search through it; the bias picks a winner.
This is induction in the logical sense: the conclusion is not entailed. The examples are consistent with the program; they do not prove it. A consistent program can be wrong on the next input — the one the user will try. More examples, a narrower language, or a specification are the only ways to strengthen the claim.
Inductive logic programming
Inductive logic programming (ILP) makes the hypothesis language explicit: definite clauses, usually in a subset of first-order logic such as Datalog. Given background B, positives E+, and negatives E−, find H such that
Here ⊨ is logical entailment. The hypothesis must cover the positives and exclude the negatives. The search refines clauses: start general and add literals to specialize, or start specific and remove literals to generalize. The ordering is usually θ-subsumption; Progol (Muggleton, 1995) and Metagol (Cropper and Muggleton) add language bias to keep refinement finite.
A family example. The background is the five facts parent(ali, sara), parent(sara, reza), parent(reza, mina), parent(ali, omar), parent(omar, hana). The positives are grandparent(ali, reza), grandparent(sara, mina), grandparent(ali, hana); the negatives include grandparent(ali, sara) and grandparent(reza, mina). The hypothesis is
covers every positive and excludes the negatives. The weaker grandparent(X, Y) :- parent(X, Y) covers a negative and is rejected. The clause grandparent(X, Z) :- parent(X, Y) leaves Z free and covers almost everything; adding parent(Y, Z) is the specialization that makes it true of the intended relation and false of the near misses.
The clause is not proved; it is the simplest consistent hypothesis under the language and cost. A different background could admit another clause; a mislabeled example could admit none. ILP searches for a logic program that fits — with all the fragility that “fits” implies.
Learning the language, not just the program
DreamCoder (Ellis et al., arXiv:2006.08381) alternates a wake phase, which searches with the current library, and a sleep phase, which compresses recurring patterns into new abstractions. The library is a learned DSL, and compression is a prior on reuse. DeepCoder (Balog et al., arXiv:1611.01989) keeps the DSL fixed but predicts which functions are likely to occur, then restricts enumeration and checks with an interpreter. Both narrow the search with a learned proposal; both keep a symbolic checker.
A model that predicts the right operator makes the search fast; a model that predicts the wrong one misses the answer if its predictions are a hard prune rather than a soft ordering.
The clause language, mode declarations, background predicates, and negatives are all bias. A hypothesis that covers the positives may be uninteresting, overfit, or wrong on the next example. ILP's guarantee is consistency with the sample under the language, not the intended concept — true, with different machinery, of every inductive synthesizer here.
04 / Proof searchA proof is a path.
Theorem proving is search with a precise goal. A calculus defines states and rules: a state is a goal, a sequent, or a clause set; a rule transforms one state into another; a proof is a path to a closed state. The goal test is “is this state closed?” — and for the right calculus, closure is decidable by inspection.
Resolution is the canonical first-order calculus. Put the premises and negated conclusion into clause form, then resolve pairs: unify a positive literal with a negative one and add the resolvent. Deriving □ means the set is unsatisfiable, so the conclusion follows. Soundness and refutation-completeness are Robinson's 1965 result; unification computes the most general substitution without guessing.
A propositional example: to prove P → Q, P ⊢ Q, negate the conclusion and clausify.
First-order logic adds substitutions. For ∀x. M(x) → D(x), M(s) ⊢ D(s), clausify to ¬M(x) ∨ D(x), M(s), ¬D(s); resolve the first two with {x ↦ s} to get D(s), then with ¬D(s) to get □. The tree's leaves are clauses; its root is the empty clause.
{x ↦ s} is the unifier; the empty clause is the contradiction. The search problem is choosing which pair to resolve next. After Robinson (1965); drawing ours.
The search problem is the choice of pair. n clauses give n(n − 1)/2 distinct pairs: 4,950 for 100, 499,500 for 1,000; each resolvent can create more. Provers impose an order and a fair iteration. Completeness says □ is derivable if the set is unsatisfiable; it gives no time bound. A found proof is a proof; a failed search is not a disproof.
Tactics and kernels
Interactive provers use tactics — functions from a goal to subgoals — and a small kernel that checks the proof term. This is the LCF architecture (Gordon, Milner, Wadsworth, 1979), the design of Coq, Isabelle, and Lean. A buggy tactic can fail to find a proof; it cannot make the kernel accept an invalid one. The domain formalization remains unchecked.
AlphaGeometry (Trinh et al., Nature, 2024): a language model proposes auxiliary constructions; a symbolic deduction engine (DDAR) applies rules and algebraic reasoning to close the goal; if it succeeds, the construction and proof are kept, otherwise the model tries another. The paper reports 25 of 30 olympiad geometry problems within the standard time limit. The model is a proposal distribution; the engine is the search and the checker. The proof is checkable, which is why the result is mathematics. GPT-f (Polu and Sutskever, arXiv:2009.03393) does the same for Metamath: the model proposes, the kernel checks.
“Complete” means the search can find a proof if one exists — not that it will before your deadline. A completeness theorem is about the limit, not the cost. In practice: which incomplete strategy is fast enough, and how much guarantee do you trade?
05 / Neural guidancePropose, order, check.
These spaces are too large for uniform search: hundreds of thousands of clause pairs, billions of programs, infinitely many proof branches. The neural contribution is not a new semantics. It is a distribution over actions: given a search state, which constructor, clause, premise, or tactic is likely to lead to a solution?
Three objects are often confused. A policy πθ(a | s) scores the next action. A value vθ(s) estimates the remaining cost. A proposal is a distribution over candidate structures that a separate checker filters. The first two guide a search; the third feeds a verifier. They can be learned from successful searches, self-play with a verifier as reward, or a corpus of proofs or programs.
In best-first search the value becomes the priority:
where g is the cost paid and hθ estimates the rest. If it is admissible — never overestimates — the search is optimal. A learned value is almost never admissible, so the guarantee is lost; what remains is a good order. This is the lab's ranking panel: the score is a prior, not a bound, and the check decides.
DeepCoder predicts likely functions and restricts enumeration; the interpreter checks. AlphaGeometry proposes constructions; DDAR checks and completes. GPT-f proposes proof steps; the kernel checks. LLM-Modulo (Kambhampati et al., arXiv:2402.01817) generalizes the pattern: a language model generates plans or formalizations, and external critics — a planner, a type checker, a simulator — accept, reject, or repair them. The model is the generator; the critics are the guarantee.
| Use | Mechanism | Completeness | What it buys |
|---|---|---|---|
| Ordering | Best-first priority, beam, or a ranked frontier | Preserved if every node is eventually expanded; lost if the beam is truncated | Finds a solution sooner on average; no worst-case guarantee |
| Pruning | Discard low-scoring branches | Lost unless the discard is provably safe | Large speedups, and a real risk of pruning the answer |
| Proposal + check | Generate candidates; a sound checker filters | Inherited from the checker, not the model | Soundness if the checker is sound; coverage depends on the proposal |
The same model can be used all three ways. A policy that orders changes the cost, not the reachable answers. A policy that prunes makes a claim about the space, and a wrong claim loses answers. A policy that proposes makes a suggestion the checker may reject. The safest architecture is the third; the fastest is often the second; the most defensible is the first plus a checker.
Why the check does not go away: a learned model has no access to the semantics beyond its training distribution. It can be confidently wrong in correlated ways. The symbolic check is cheap — an interpreter on a few examples, a type checker, a kernel — and it is the only component that can say “this candidate satisfies the specification.” The model can make the search faster; it cannot make a wrong program right. The check is what turns a candidate into a certificate; a score is not one.
A learned policy is trained on a distribution. The hard, deep, out-of-distribution problems are where its advice is least reliable. A confident prune can remove the only path; a bad order can be slower than blind enumeration. The lab's hand-set prior shows the modest version: it beats cost order on one preset and loses on another.
06 / Guarantees & costsWhat the words mean.
Sound, complete, and decidable are used loosely. They are precise, and every guarantee here is relative to three things: the language, the specification, and the resource bound. A claim that omits one is a hope with a theorem-shaped sentence.
| Method | Specification | Soundness | Completeness | Failure mode |
|---|---|---|---|---|
| Enumeration by cost | Examples, cost bound | Every output agrees with every example | Up to the bound; first output is cost-minimal | No program within the bound; underdetermined answer |
| Version space / ILP | Positives, negatives, background, clause language | Covers positives, excludes negatives (if exhaustive) | Not for the intended concept; only for the sample | Overgeneralization; noise; wrong bias |
| Sketching / CEGIS | Full spec plus a sketch | If the verifier is sound and the hole search is exhaustive | For the hole domain, if finite and exhausted | Bounded verifier; incomplete search; bad sketch |
| Resolution / tactics | Premises and a goal | A derived □ is a valid refutation | Refutation-complete; may not terminate | Timeout means unknown, not false |
| Neural-guided search | Whatever the checker checks | Inherited from the checker | Only if guidance is an ordering and the space is exhausted | False pruning; distribution shift; confident wrong candidates |
The finite-example trap: if the DSL is expressive enough and the spec is a finite sample, a lookup table is consistent and synthesis is trivial — unless the language or cost rules the table out. The lab's DSL has no cons or case analysis, so most tables cannot be written; cost order prefers short compositions. That is the work: choosing a language in which the intended program is simpler than the alternatives. A Turing-complete DSL with examples as the only spec is trivial or ill-posed; with a full functional spec it is undecidable. The interesting cases are in the middle: restricted languages, decidable fragments, specs strong enough to rule out the table but weak enough to check.
The complexity ladder is a reality check; each rung is a different problem. Propositional satisfiability is NP-complete. First-order validity is undecidable. Datalog evaluation is PTIME in the data. Resolution is semi-decidable with exponential propositional worst cases. General SyGuS with recursion and rich theories is undecidable; decidable fragments are the ones deployed. Finite-hole sketching is decidable by exhaustion. A prover that says “unknown” is respecting the ladder.
The cost model
- Search cost. Nodes expanded × cost per node. Types and deduplication reduce the first; fast evaluation the second. A learned heuristic reduces the expected count, not the worst case.
- Verification cost. Examples are cheap; proving for all inputs is expensive; checking a proof term is cheap once the proof exists. The gap between “tested” and “proved” is the specification gap.
- Specification and DSL cost. Examples are cheap but weak; a full spec is strong but expensive; a sketch encodes insight. A tighter DSL shrinks the search but makes some programs inexpressible; a looser one covers more and pays in search. The lab's 16× gap is a small version.
“Checked” can mean tested on three examples, type-checked, validated against a simulator, or proved in a kernel — not the same guarantee. This lecture uses “sound” for the strongest and “consistent” for the weakest. When a paper says “verified,” ask: against what, by what, for which inputs?
07 / CasesFive systems, one pattern.
The pattern is stable: a specification, a discrete space, a search, a checker. The differences are in which part is learned and trusted. The numbers are the papers' claims.
| System | Specification | Space and search | Learned part | Checker | Lesson |
|---|---|---|---|---|---|
| FlashFill (Gulwani, POPL 2011) | Input–output strings | String DSL; version-space algebra | None; a cost heuristic | Exact evaluation on the examples | A restricted DSL plus examples can be a product |
| DeepCoder (Balog et al., ICLR 2017) | Input–output lists | FlashFill-style DSL; DFS enumeration | A network predicts which functions occur | An interpreter on the examples | Learned proposals shrink the DSL; the checker decides |
| DreamCoder (Ellis et al., 2020) | Tasks with programs | Growing library; wake–sleep search | Recognition model; abstraction invention | Program execution | The hypothesis space can be learned by compression |
| AlphaGeometry (Trinh et al., Nature 2024) | Geometry goals | Auxiliary constructions; DDAR deduction | A language model proposes constructions | A symbolic deduction engine | Proposal plus deduction yields checkable proofs |
| GPT-f (Polu & Sutskever, 2020) | Metamath goals | Proof-step search | A language model proposes steps and premises | The Metamath kernel | The kernel is the guarantee; the model is the speed |
FlashFill synthesizes string transformations from one or two examples. Its DSL is a small algebra of concatenation, substrings, case conversion, and constants; the search uses version-space algebra, and the ranking is a cost heuristic. There is no neural network, and that is the point: a well-chosen DSL plus good search plus a ranking can be a product.
DeepCoder trains a network on random programs and their behavior; at test time it predicts which functions are likely, and the enumerator restricts itself to them and checks with an interpreter. The prediction is a proposal, not a proof: a wrong one can remove the answer, which is why the paper evaluates the trade between set size and solve rate. DreamCoder learns the library, so recurring patterns become abstractions and the DSL is a compressed record of what it has solved. Both change the space with past experience; both keep an exact checker.
AlphaGeometry's model proposes auxiliary constructions; DDAR applies the rules. The 25-of-30 result is a benchmark claim, but the architecture is the lesson: the model's output is not the theorem. The theorem is the proof term the engine derives. GPT-f makes the separation explicit: the model proposes, the kernel checks. The model is judged by how often it proposes something the checker can use, not by whether its sentences sound right.
Compositional generalization is the recurring motivation. A model trained on short programs can fail on a longer composition; a search over a grammar can, in principle, build it from the same parts. The “in principle” does a lot of work: deeper composition means a larger space and more need for guidance. The cases succeed where DSL, checker, and guidance line up — and the benchmark is narrow enough to measure it.
FlashFill is strings; DeepCoder is list programs from a fixed DSL; AlphaGeometry is olympiad geometry; GPT-f is Metamath. Each result is real within its benchmark, and each benchmark is narrower than the domain it evokes. The architecture generalizes more reliably than the numbers. Ask which of the four parts the benchmark actually tests.
08 / RecapThe search is the argument.
State a synthesis problem as a DSL, a cost, and a specification; write p* = argmin c(p) subject to the examples.
Estimate a grammar's size; explain why enumeration by cost is sound, bound-complete, and cost-optimal.
Distinguish type/arity pruning (sound), observational deduplication (sound for probes), and learned pruning (unsound without an argument).
Separate deductive synthesis (correct by construction) from inductive synthesis (consistent with examples), and say what each guarantees.
Read an ILP hypothesis as a clause with coverage; explain refinement and negative examples.
Explain resolution as refutation search, and why a found proof is checkable while a failed search is not a disproof.
Describe neural guidance as a policy, a value, or a proposal — and which preserves completeness.
State a guarantee relative to its language, specification, and resource bound; name the weakest link.
Exercises
- Count the space. Take the lab's list DSL at cost 4. Compute the number of list-output programs by hand and compare with 198 at cost 4 and 1,579 at cost 5. Where does your count diverge, and why?
- Add an operator. Add
cons(0)to the DSL. Predict how the counts at costs 4 and 5 change, then measure. Which new programs satisfy the “Impossible: add an element” preset? - Find the ambiguity. Construct examples consistent with both
pipe(take(3), map(×2))andpipe(map(×2), take(3)). Are they equivalent on all lists? Prove it or give a separating input. - Resolution by hand. Prove
{P → Q, Q → R, P} ⊨ R. List the clauses, resolvents, and unifiers, and count the available pairs at each step. - Design a guidance signal. Propose a policy that ranks the lab's candidates without looking at the examples. Measure it on the seven presets. Where does it beat cost order, and where does it lose?
- Argue the guarantee. A paper claims “our neurosymbolic system is verifiably correct.” Write three questions that reduce the claim to a precise statement, and say which answer would make it false.
Check your understanding
Ten questions with explanations. The ones you cannot answer are the reading list.
Reading list
Program Synthesis
Gulwani, Polozov & Singh · Foundations and Trends in Programming Languages, 2017
A Deductive Approach to Program Synthesis
Manna & Waldinger · ACM TOPLAS, 1980
A Machine-Oriented Logic Based on the Resolution Principle
Robinson · JACM, 1965
Solving olympiad geometry without human demonstrations
Trinh et al. · Nature, 2024
DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning
Ellis et al. · 2020
DeepCoder: Learning to Write Programs
Balog et al. · ICLR 2017
Generative Language Modeling for Automated Theorem Proving
Polu & Sutskever · 2020
LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks
Kambhampati et al. · ICML 2024
Generalization as Search
Mitchell · Artificial Intelligence, 1982