When Code Writes Itself

Imagine telling a computer what you want — "turn full names into Last, First-initial" — and having it write the how for you, the actual code, correct on every case. That's the dream of program synthesis: programs that write programs, from a specification or just a handful of examples.

The obvious approach is to search: try candidate programs until one fits. But the space of all programs is infinite — there are always longer, weirder programs to consider. Searching blindly never ends, and in full generality, deciding whether a correct program even exists is undecidable, a relative of the halting problem.

And yet — you've probably used program synthesis. When a spreadsheet's Flash Fill guesses your formatting after two examples, or an AI assistant writes a function from a comment, that's synthesis, made practical by shrinking the search to a clever, restricted space.

Try it — a miniature Flash Fill. Give a couple of examples of the transformation you want (an input and the output you'd like), then hit Synthesize. A tiny search engine hunts through a small library of string operations for a program that matches all your examples.

<p class="hint">{{hint}}</p>
<table class="ex"><thead><tr><th>{{th_input}}</th><th>{{th_arrow}}</th><th>{{th_wanted}}</th></tr></thead><tbody id="rows"></tbody></table>
<div class="testrow">{{label_test}} <input id="test" type="text" value="Grace Hopper" /></div>
<button id="go" type="button">{{btn_synth}}</button>
<div id="out" class="out"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.ex { border-collapse: collapse; width: 100%; max-width: 440px; margin-bottom: .7rem; }
.ex th { font: 600 12px system-ui; color: #777; text-align: left; padding: .2rem .3rem; }
.ex td { padding: .15rem .3rem; }
.ex td.arrow { color: #aaa; text-align: center; }
.ex input { font: 600 14px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #cdd9e2; border-radius: 6px; width: 100%; }
.testrow { font: 600 14px system-ui; color: #1d3557; margin-bottom: .7rem; display: flex; align-items: center; gap: .5rem; }
.testrow input { font: 700 14px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #cdd9e2; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1.1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
.out { margin-top: .8rem; font: 600 14px system-ui; line-height: 1.6; min-height: 3em; }
.out .prog { font-family: ui-monospace, monospace; background: #1d2733; color: #e6edf3; padding: .5rem .7rem; border-radius: 8px; display: block; margin: .4rem 0; font-size: 12.5px; }
.out .pred { font-size: 1.05rem; }
.out .pred b { color: #0a7d33; font-family: ui-monospace, monospace; }
.out .none { color: #c0392b; font-weight: 700; }

// Code not found

When it finds one, it shows the program it discovered and applies it to a fresh input. Change the examples and watch the synthesized program change too. With just two examples it usually guesses right — but notice: more examples pin it down better, because a few cases never fully specify what you mean.

Synthesis is the art of taming an impossible search:

• The space is infinite. There are infinitely many programs, of every length — no exhaustive search can cover them all.
• In general it's undecidable. Deciding whether some program meets an arbitrary specification reduces to questions like halting; there's no universal synthesizer.
• Examples under-specify. A few input-output pairs are consistent with many different programs — which one did you mean? The synthesizer has to guess, usually preferring the simplest (Occam's razor).
• Restrict to win. Limit programs to a small domain-specific language (DSL) — say, string slicing and concatenation — and the search becomes finite and fast. That's exactly how Flash Fill works.
• Smart search. Enumerative search with pruning, SMT-solver-guided synthesis (CEGIS: guess, find a counterexample, repeat), and version-space algebras make even rich DSLs practical.
• The LLM era. Large language models now synthesize code from natural language directly — a different, statistical approach that complements the classical, guarantee-driven one.

So synthesis lives on the line between the impossible (any program) and the easy (a tight DSL), and progress is about drawing that line in just the right place.

Code that writes code is quietly everywhere:

• Spreadsheets: Excel's Flash Fill synthesizes formatting from examples — synthesis used by millions who've never heard the term.
• AI coding assistants: turning comments and prompts into functions.
• Data wrangling: tools that infer cleaning and transformation scripts from sample rows.
• Low-code / no-code: letting non-programmers build logic by example.
• Compilers and optimization: synthesizing fast, provably-equivalent code sequences (superoptimization).

Each one works by picking a domain narrow enough that the infinite search becomes a solvable one.

Program synthesis is the most optimistic hard problem on this site: the goal is to make computers do our programming for us. In full generality it's undecidable — the space of programs is endless, and no oracle can always find the right one. Yet the dream isn't dead; it's just been scoped. Narrow the language, prefer the simplest fit, search cleverly, and synthesis becomes the everyday magic behind Flash Fill and AI coding.

It captures a theme running through this whole site: when a problem is impossible in the abstract, the win comes from changing the problem — a smaller language, a few good examples, a willingness to guess. The infinite search for "any program" gives way to a finite, friendly search for a useful one — and increasingly, the code writes itself.