Presets
Playback
Task
Choose the hidden function and how many examples the search may see.
Search
Size limit, constants, operators and the pruning rules.
Experiment
Measure what the number of examples changes.
Layers
Model checks
The science
The task
Programming by example: find an expression e in a small language e ::= x | 1 | 2 | ... | (e + e) | (e - e) | (e * e) whose output equals the hidden function on every example, e(x_i) = y_i. The size of a program is its number of nodes (leaves plus operators), so only odd sizes exist.
Bottom-up enumeration
Programs are built in order of size: size 1 is x and the constants; a program of size s combines a kept program of size i with one of size j and an operator, i + j = s - 1. With T leaf symbols and B operators the number of distinct trees of size 2k + 1 is a(2k + 1) = C_k T^(k+1) B^k, where C_k = (2k)! / (k! (k+1)!) is a Catalan number; equivalently a(s) = B * sum a(i) a(s - 1 - i). Each extra two nodes multiply the count by roughly 4 T B, which is why blind enumeration dies quickly.
Pruning by observational equivalence
The signature of a program is the vector of its outputs on the examples, sigma(e) = (e(x_1), ..., e(x_n)). Every operator acts point by point, so if two programs share a signature then sigma(C[e]) = sigma(C[e']) for every larger program C that contains them. Keeping only the first (smallest) program per signature therefore loses no signature of any size: a solution exists in the pruned space exactly when it exists in the full space, and the smallest solution has the same size. The kept programs are exactly the distinct signatures; the page checks this against a brute-force enumeration.
Symmetry breaking
a + b and b + a (and the same for multiplication) have identical signatures, so skipping the mirrored operand order cuts the number of candidates tested by about half without changing which signatures are kept.
Why few examples mislead
The search returns the first smallest program that fits the examples, which need not be the hidden function. With two examples many unrelated programs fit; with more examples the signature space is finer, fewer programs merge (more are kept) and the answer is better constrained. The page measures the share of unseen integer points x = -10..10 where the found program equals the hidden function.
Simplifications
A tiny arithmetic language with exact integer arithmetic, no conditionals, loops, types or cost model; real synthesisers use much richer languages and guided search. Capsule traffic in the 3D workshop shows a sample of at most about nine candidates per second, the glass columns use a log scale (each tick is a factor 10^2), and the jar shows at most 120 pruned capsules. Counts are exact; timings and speeds are only for display. Pruning is stopped after 120,000 stored programs or 3 million tested candidates (the budget), which is how the no-pruning preset ends.
What to try
- Start with the linear preset and watch the green columns stay far below the amber ghost columns: pruning keeps only distinct signatures.
- Press the preset with two examples: the search stops at a program that fits both points but is wrong elsewhere; compare the accuracy on unseen points with the six-example preset.
- Switch off pruning and rerun the hardest target: the candidate count grows many times larger.
- Switch off symmetry breaking and see about twice as many candidates tested for the same kept set.
- Allow only + and the constant 1 and see how much larger the programs become.
- Press the experiment button to get the table for 2 to 6 examples.