Course / Act III · The five interfaces Lecture 10

Logic as search.

A specification is a set of examples. A program is a term in a grammar. The task is to find the term — not to fit the weights. This lecture treats program synthesis, inductive logic programming, and theorem proving as search over discrete structures: how the space is built, why a found answer is checkable, what a guarantee is worth, and where heuristic search helps or hurts.

~45 min read 4 objectives 4 worked examples 1 interactive lab Updated 2026-11-16

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:

Table 0.1 · A finite specification. Find a program in the DSL that maps every input to its output.
#InputOutput
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.

Caveat · three examples do not determine a function

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.

Definition · a synthesis 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:

p* = argminp ∈ L(D) c(p)   subject to   ∀i. ⟦p⟧(xi) = yi
(1.1)

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

N(h) = b + u · N(h − 1) + q · N(h − 1)2
(1.2)

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.

A schematic search tree for the hook, with one pruned branch The root is the specification. map(plus one), map(times two), and filter(even) disagree with the examples; map(even) is pruned because its argument is a predicate; the composite pipe of map times two and map plus one agrees and is accepted. specification: 3 examples [1,2,3,4] → [3,5,7,9] … map(even) type error · pruned map(+1) [2,3,4,5] ≠ map(×2) [2,4,6,8] ≠ filter(even) [2,4] ≠ pipe(map(×2), map(+1)) [3,5,7,9] ✓ take(3) · sort other cost-2/3 branches fail pipe(map(+1), reverse) [5,4,3,2] ≠ accept: first consistent cost 5 · checked on all examples
Fig. 1.1 A schematic of the search, not the full tree. The shape that matters: one type-pruned branch, several branches that fail the examples, one accepted program. The counts in the text come from the lab's enumerator, not this drawing.

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

Table 1.1 · Three prunings. Only the first is sound by construction; the other two need an argument.
PruningWhat it removesWhy it is safe — or not
Type / arityTerms 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 equivalenceTerms that behave identically on a probe setSafe for the probe set only. Two terms can agree on the probes and differ elsewhere.
Learned / heuristicTerms a model or score judges unpromisingUnsafe 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).

Caveat · the first program is the simplest, not the intended

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:

∃f. ∀x. φ(x, f(x))
(2.1)

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

sum(map(×2, xs)) = 2 · sum(xs)   for every list xs
(2.2)

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.

Caveat · the specification is the product

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

B ∪ H ⊨ e for every e ∈ E+   and   B ∪ H ⊭ e for every e ∈ E−
(3.1)

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

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

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.

Caveat · ILP is only as good as its bias

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.

1. ¬P ∨ Q (the implication) 2. P (the premise) 3. ¬Q (the negated conclusion) 4. Q resolve 1 and 2 5. □ resolve 4 and 3

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.

A resolution proof tree for the Socrates argument The clauses not M of x or D of x, and M of s, resolve with substitution x maps to s to give D of s. D of s resolves with not D of s to give the empty clause. ¬M(x) ∨ D(x) every man is mortal M(s) Socrates is a man D(s) resolve with {x ↦ s} ¬D(s) negated goal □ empty clause
Fig. 4.1 A resolution refutation of the Socrates argument. {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.

Caveat · completeness is not a budget

“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:

f(s) = g(s) + hθ(s)
(5.1)

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.

Table 5.1 · Three ways to use a learned score. Only the third keeps a symbolic guarantee without an extra argument.
UseMechanismCompletenessWhat it buys
OrderingBest-first priority, beam, or a ranked frontierPreserved if every node is eventually expanded; lost if the beam is truncatedFinds a solution sooner on average; no worst-case guarantee
PruningDiscard low-scoring branchesLost unless the discard is provably safeLarge speedups, and a real risk of pruning the answer
Proposal + checkGenerate candidates; a sound checker filtersInherited from the checker, not the modelSoundness 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.

Caveat · the guidance can be the failure

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.

Table 6.1 · What each method can promise, and what the promise is relative to.
MethodSpecificationSoundnessCompletenessFailure mode
Enumeration by costExamples, cost boundEvery output agrees with every exampleUp to the bound; first output is cost-minimalNo program within the bound; underdetermined answer
Version space / ILPPositives, negatives, background, clause languageCovers positives, excludes negatives (if exhaustive)Not for the intended concept; only for the sampleOvergeneralization; noise; wrong bias
Sketching / CEGISFull spec plus a sketchIf the verifier is sound and the hole search is exhaustiveFor the hole domain, if finite and exhaustedBounded verifier; incomplete search; bad sketch
Resolution / tacticsPremises and a goalA derived □ is a valid refutationRefutation-complete; may not terminateTimeout means unknown, not false
Neural-guided searchWhatever the checker checksInherited from the checkerOnly if guidance is an ordering and the space is exhaustedFalse 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.
Caveat · a check is only as strong as its checker

“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.

Table 7.1 · Five systems that search a symbolic space, and the role of learning in each.
SystemSpecificationSpace and searchLearned partCheckerLesson
FlashFill (Gulwani, POPL 2011)Input–output stringsString DSL; version-space algebraNone; a cost heuristicExact evaluation on the examplesA restricted DSL plus examples can be a product
DeepCoder (Balog et al., ICLR 2017)Input–output listsFlashFill-style DSL; DFS enumerationA network predicts which functions occurAn interpreter on the examplesLearned proposals shrink the DSL; the checker decides
DreamCoder (Ellis et al., 2020)Tasks with programsGrowing library; wake–sleep searchRecognition model; abstraction inventionProgram executionThe hypothesis space can be learned by compression
AlphaGeometry (Trinh et al., Nature 2024)Geometry goalsAuxiliary constructions; DDAR deductionA language model proposes constructionsA symbolic deduction engineProposal plus deduction yields checkable proofs
GPT-f (Polu & Sutskever, 2020)Metamath goalsProof-step searchA language model proposes steps and premisesThe Metamath kernelThe 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.

Caveat · benchmarks are not the world

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.

01

State a synthesis problem as a DSL, a cost, and a specification; write p* = argmin c(p) subject to the examples.

02

Estimate a grammar's size; explain why enumeration by cost is sound, bound-complete, and cost-optimal.

03

Distinguish type/arity pruning (sound), observational deduplication (sound for probes), and learned pruning (unsound without an argument).

04

Separate deductive synthesis (correct by construction) from inductive synthesis (consistent with examples), and say what each guarantees.

05

Read an ILP hypothesis as a clause with coverage; explain refinement and negative examples.

06

Explain resolution as refutation search, and why a found proof is checkable while a failed search is not a disproof.

07

Describe neural guidance as a policy, a value, or a proposal — and which preserves completeness.

08

State a guarantee relative to its language, specification, and resource bound; name the weakest link.

Exercises

  1. 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?
  2. 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?
  3. Find the ambiguity. Construct examples consistent with both pipe(take(3), map(×2)) and pipe(map(×2), take(3)). Are they equivalent on all lists? Prove it or give a separating input.
  4. Resolution by hand. Prove {P → Q, Q → R, P} ⊨ R. List the clauses, resolvents, and unifiers, and count the available pairs at each step.
  5. 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?
  6. 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

Survey

A Deductive Approach to Program Synthesis

Manna & Waldinger · ACM TOPLAS, 1980

Deduction

DeepCoder: Learning to Write Programs

Balog et al. · ICLR 2017

Guidance

Generalization as Search

Mitchell · Artificial Intelligence, 1982

Induction