Introduction

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.

From Examples

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">Give a couple of examples of the transformation you want, then Synthesize. The engine searches a small library of string operations for a program matching <b>all</b> examples and applies it to the test input.</p>
<table class="ex"><thead><tr><th>input</th><th>→</th><th>wanted output</th></tr></thead><tbody id="rows"></tbody></table>
<div class="testrow">test input: <input id="test" type="text" value="Grace Hopper" /></div>
<button id="go" type="button">Synthesize</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Program synthesis by enumeration over a tiny string-transform DSL (Flash Fill style). The engine returns the first program in its library consistent with ALL examples — preferring simpler ones — then applies it to a new input.
function toks(s) { return (s || '').trim().split(/\s+/).filter(Boolean); }
const cap = w => w ? w[0].toUpperCase() + w.slice(1) : '';
const LIB = [
  { name: 'last + ", " + first[0] + "."', f: s => { const t = toks(s); return t.length < 2 ? '' : t[t.length - 1] + ', ' + t[0][0].toUpperCase() + '.'; } },
  { name: 'first[0] + ". " + last', f: s => { const t = toks(s); return t.length < 2 ? '' : t[0][0].toUpperCase() + '. ' + t[t.length - 1]; } },
  { name: 'first + " " + last (unchanged)', f: s => toks(s).join(' ') },
  { name: 'last + " " + first', f: s => { const t = toks(s); return t.length < 2 ? '' : t[t.length - 1] + ' ' + t[0]; } },
  { name: 'first[0] + last[0] (initials)', f: s => { const t = toks(s); return t.length < 2 ? '' : (t[0][0] + t[t.length - 1][0]).toUpperCase(); } },
  { name: 'UPPERCASE the whole thing', f: s => (s || '').toUpperCase() },
  { name: 'lowercase the whole thing', f: s => (s || '').toLowerCase() },
  { name: 'first name only', f: s => toks(s)[0] || '' },
  { name: 'last name only', f: s => { const t = toks(s); return t[t.length - 1] || ''; } },
  { name: 'last (UPPER) + ", " + first', f: s => { const t = toks(s); return t.length < 2 ? '' : t[t.length - 1].toUpperCase() + ', ' + cap(t[0]); } }
];

function rows() {
  return [...document.querySelectorAll('#rows tr')].map(tr => ({
    in: tr.querySelector('.in').value, out: tr.querySelector('.out-cell').value
  })).filter(r => r.in.trim() && r.out.trim());
}

function synth() {
  const ex = rows(); const out = document.getElementById('out');
  if (ex.length < 1) { out.innerHTML = '<span class="none">Give at least one input → output example.</span>'; return; }
  const prog = LIB.find(p => ex.every(e => p.f(e.in) === e.out));
  if (!prog) { out.innerHTML = '<span class="none">No program in my little library matches all those examples.</span> Try a transformation it knows (initials, reorder, case…), or add an example.'; return; }
  const test = document.getElementById('test').value;
  out.innerHTML = fmt('Synthesized program:<span class="prog">output = %name%</span><span class="pred">On <code>%test%</code> → <b>%v%</b></span>', { name: prog.name, test: test, v: prog.f(test) || '—' });
}

function init() {
  const seed = [['Ada Lovelace', 'Lovelace, A.'], ['Alan Turing', 'Turing, A.'], ['', '']];
  document.getElementById('rows').innerHTML = seed.map(([i, o]) =>
    fmt('<tr><td><input class="in" type="text" value="%i%" placeholder="e.g. Jane Doe"/></td><td class="arrow">→</td><td><input class="out-cell" type="text" value="%o%" placeholder="e.g. Doe, J."/></td></tr>', { i: i, o: o })).join('');
  document.getElementById('go').addEventListener('click', synth);
  synth();
}
init();
Result
Console

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.

The Hard Part

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/program-synthesis/Content licensed under CC BY-NC 4.0.