Example-Driven Synthesis: from BDD examples to working PatLang code

First published 2026-09-01.

For new readers

This is a second, different synthesis engine from Inductive Synthesis. That one induces logical rules (Prolog-style clauses) from Given/Then examples. This one is closer to classic program synthesis (in the FlashFill/Blaze family): given input→output examples, it enumerates compositions of PatLang's own primitive operations — string, arithmetic, list — smallest first, until it finds one that reproduces every example exactly, then emits the result as real, runnable PatLang source. If "GOAP" or action_add/plan is unfamiliar, the goal-oriented demo page introduces the planner this system builds alongside, and the BDD framework page introduces the Given/When/Then vocabulary reused throughout.

The author never writes the function body. A BDD scenario is parsed into example pairs automatically, the search finds the smallest composition of primitives that satisfies them, and that composition is emitted as source and run for real — against a real file, in one worked example below. Every example on this page is real, runnable PatLang: self_hosting/lib/primitive_registry.patlang (the contract-checked primitive set), self_hosting/lib/synthesis_by_example.patlang (the enumerator), self_hosting/lib/bdd_examples.patlang and bdd_file_scenarios.patlang (BDD parsing, including a real end-to-end file-scenario runner), and self_hosting/lib/composite_library.patlang (a persistent, on-disk library of everything derived so far, organized by domain, re-verified against its own stored examples on every load).

Primitives, contracts, and a persistent library

Each primitive is registered with a declared argument/return type (comparisons on mismatched types are a fatal error in PatLang, so the search must know a candidate's type before constructing it, not discover a mismatch by trying it) and an optional per-argument contract — a predicate checked against a candidate's actual value before it's built at all, not after. substr's count argument, for instance, carries a "must be non-negative" contract, reusing the same guard already written into its safe wrapper rather than re-deriving it. Primitives are also indexed by what they produce, so a caller can ask "what produces a string?" instead of hand-curating a primitive list for every new problem.

A derived function is registered back into the same primitive set under its own name, with its own contract and its own call-site template for emission — a later, larger search can then call it exactly like any other primitive. That's what makes composition affordable: a function too large to search for directly can still be found by searching for two or three smaller, independently-specified pieces first, then searching for how they combine. Every derived composite is also saved to disk, one JSON file (plus a human-readable .feature rendering of its own examples) per composite, organized into domains (http, text, list, numeric, markdown). Loading the library re-runs every composite's own stored examples against its own stored AST before trusting it — a composite that no longer holds (a primitive changed underneath it, say) is reported and excluded, never silently reused.

A primitive can also declare an argument as generically-typed (cond's two branches, below, accept a value of any type) rather than one fixed type — which needed its own small fix: two such positions on the same call must resolve to the same concrete type together, not independently, since letting them vary independently allowed a branch's type to silently differ between examples and crash a later comparison on whichever example happened to pick the mismatched branch.

Worked example: a file search-and-replace utility, specified as BDD alone

The whole utility is specified as Given/Then scenarios. The pure text transform is split into two independent searches — the smaller, and the only shape this engine can currently search directly at this size:

Feature: find_position -- where original first occurs in text

Scenario: match at the very start
  Given text = "cat sat mat"
  Given original = "cat"
  Then result = 0

Scenario: match in the middle
  Given text = "the quick fox"
  Given original = "quick"
  Then result = 4

Feature: replace_in_text -- the first occurrence of original in text replaced with replacement

Scenario: replace in the middle
  Given text = "the quick fox"
  Given original = "quick"
  Given replacement = "slow"
  Then result = "the slow fox"

Scenario: replace at the start
  Given text = "cat sat mat"
  Given original = "cat"
  Given replacement = "hat"
  Then result = "hat sat mat"

Scenario: replacement longer than the original
  Given text = "a b c"
  Given original = "b"
  Given replacement = "banana"
  Then result = "a banana c"

find_position, take_before, and take_after (three small, separately-specified pieces — the middle two use the same length-based "take everything from here to the end, letting substr's own clamping do the trimming" idiom, so a genuinely long held-out example is what forces the general formula rather than a fixed guess) are searched for directly and succeed immediately. splice composes the first two; replace_in_text composes splice with find_position. Every one of these is emitted, not paraphrased — this is the actual generated source, produced by the engine itself:

make a function called find_position takes text, original returns result
  let result = gc_find_substr(text, original)
  return result
end

make a function called take_before takes text, position returns result
  let result = substr(text, 0, position)
  return result
end

make a function called take_after takes text, position returns result
  let result = substr(text, position, (text).length)
  return result
end

make a function called splice takes text, position, original_len, replacement returns result
  let result = (take_before(text, position) + (replacement + take_after(text, (position + original_len))))
  return result
end

make a function called replace_in_text takes text, original, replacement returns result
  let result = splice(text, find_position(text, original), (original).length, replacement)
  return result
end

A second, separate BDD scenario then drives the whole thing end-to-end against a real file on disk — the only hand-written code anywhere in this example is the few lines of I/O plumbing that read the file, call the derived function, and write the result back, the same boundary the goal-oriented web-service demo draws around its own socket-handling loop:

Feature: search-replace on a real file

Scenario: replace text in a real file
  Given a file named "synth_demo_search_replace_fixture.txt" containing "the quick fox jumps"
  And the original is "quick"
  And the replacement is "slow"
  When I run "search-replace" on "synth_demo_search_replace_fixture.txt"
  Then the file "synth_demo_search_replace_fixture.txt" contains "the slow fox jumps"

> ok: file synth_demo_search_replace_fixture.txt has the expected contents
> tests: 1 passed, 0 failed
> ALL TESTS PASSED

Once derived, every piece is saved to the on-disk library. A second, completely independent process — containing no call to the search at all — loads and reuses all five pieces directly:

> search-replace: reusing find_position/take_before/take_after/splice/replace_in_text from the composite library

Breadth: the same engine, three more domains

Nothing above is specific to text. The same primitive-and-contract mechanism, unchanged, derives small functions in other domains directly from their own Given/Then text. A numeric example, two scenarios varying all three inputs at once (to rule out any one argument being ignored by a smaller, wrong candidate):

Given a = 1, b = 2, c = 5
Then result = 8

Given a = 10, b = 1, c = 1
Then result = 12

> sum3(a, b, c) = a + (b + c)

A plain list example: second(xs) = list_get(xs, 1), derived from a single Given xs = [10, 20, 30] / Then result = 20 scenario. A harder list example needs a genuinely new capability: finding the first list entry that exceeds a given threshold requires picking between two already-computed values based on a comparison — conditional selection, not just composition. A cond(test, a, b) primitive (plus a plain gt comparison) makes this an ordinary Call node like any other, so the same enumerator reaches it directly. Boundary values matter here exactly the way length variation mattered above — two of the five scenarios sit precisely either side of the first cutoff:

Given xs = [10, 20, 30], threshold = 5
Then result = 10

Given xs = [10, 20, 30], threshold = 9
Then result = 10

Given xs = [10, 20, 30], threshold = 10
Then result = 20

Given xs = [10, 20, 30], threshold = 19
Then result = 20

Given xs = [10, 20, 30], threshold = 20
Then result = 30

make a function called first_exceeding takes xs, threshold returns result
  let result = list_get(xs, sbe_pat_cond((10 > threshold), 0,
    sbe_pat_cond((list_get(xs, 1) > threshold), 1, 2)))
  return result
end

> advice: 2 other structurally different candidate(s) of the same minimal
  size also satisfy every given example -- if the intended behavior is
  more specific than what's shown, add a disambiguating example

The advice is worth heeding literally here. Every scenario above uses the same list, so the search found a formula that hard-codes that list's own first value (10) in place of a genuine comparison against xs[0] — correct on every scenario given, wrong the moment the list changes: evaluated against xs = [5, 50, 500], threshold = 7, it returns 5 where the correct answer is 50. A second list among the training scenarios (the same fix worked twice already, for after_space and sum3 above) is the obvious next step to force the general comparison.

Tried directly rather than left as a claim: three more scenarios over a second list (xs = [5, 50, 500], thresholds 1/7/60) were added and the same search re-run. It did not finish that first time — by search-tree depth 17 the candidate pool had reached 102,318 entries and process memory had climbed past 45GB before it was stopped, without a match. gt/cond together roughly quadruple the branching factor per level (each "any"-typed argument position is resolved across every concrete type), and evaluating each candidate against eight scenarios instead of five compounds that further.

Two real fixes, not one. Candidate evaluation is independent per candidate, so it now runs across real OS threads (the interpreter's own parallel_map) once a level's candidate count crosses a threshold — chunked into a small, fixed number of groups rather than one thread per candidate, since the first attempt at this spawned tens of thousands of threads at once and made the whole machine, not just the search, unresponsive. Separately, the candidate pool itself is now bounded to a sliding window of recent search-tree depths (leaves exempt, since they're cheap and exactly what a late-level candidate reaches back for) rather than retained forever, which is what actually addresses the 45GB figure. Re-run with both fixes: an under-sized window completed safely in ~3 minutes but returned a confident, wrong-shaped failure — it had evicted exactly the pieces (list_get(xs, 0), list_get(xs, 1)) the true answer needed. A wider window found it for real, in ~53 minutes, memory healthy throughout. Asked whether that's fast: no — but, in Pat's own words, it's "doing a metric shed load of work."

make a function called first_exceeding takes xs, threshold returns result
  let result = list_get(xs, sbe_pat_cond((list_get(xs, 0) > threshold), 0,
    sbe_pat_cond((list_get(xs, 1) > threshold), 1, 2)))
  return result
end

Real comparisons against xs[0] and xs[1], no hard-coded constants anywhere — genuinely general this time, confirmed against both lists and both boundary thresholds. Tracked and closed as issue #73.

And the simplest case, a single-argument numeric function:

Given n = 5
Then result = 6

> increment(n) = n + 1

The Markdown domain shows where the boundary of what's directly searchable currently sits: find_position, take_before/take_after (renamed second_marker/inner_text here), and wrap_strong (an HTML <strong> wrapper) all derive individually in well under a second, giving a working ATX-heading converter (h1_line: "# Hello" → "<h1>Hello</h1>") immediately. Composing all six pieces into one inline-bold transform in a single search, however, runs into the same scaling wall described below — a genuine, reported current limit, not a hidden one.

When the search can't find an answer, it says why

Two kinds of situation get a real, generated recommendation rather than a bare failure. First: more than one differently-shaped candidate of the same minimal size satisfies every example given — a sign the examples under-specify the intent, not that the search is broken:

Given hay = "hello world", needle = "world"
Then result = 6

> result: OK   [Call, find_substr, [hay, needle]]
> advice: 1 other structurally different candidate(s) of the same minimal
  size (3) also satisfy every given example -- if the intended behavior is
  more specific than what's shown, add a disambiguating example

Second: the search pool grows fast enough, for long enough, that finishing is impractical — the same signal that motivated splitting replace_in_text into smaller pieces above, now generated automatically rather than noticed by inspection:

> result: ERR
> advice:
  - search pool grew 2.8x at size 4 (sustained fast growth) -- if this
    gets slow, consider decomposing the target into smaller,
    independently-specified composites
  - reached max_size without a match -- consider decomposing the target
    rather than raising max_size further

Both notes are generated directly from the search's own telemetry (candidate-pool growth per level; how many distinct minimal-size candidates survive), not authored per-domain.

Current limits

No loops (issue #72). The search only builds loop-free expression trees over a bounded number of composition steps, so a target genuinely requiring unbounded iteration (reversing a string of arbitrary length, for example) is correctly reported as unreachable rather than guessed at — a real architectural boundary, not a missing example.
Composing more than three or four already-derived pieces in one search still scales poorly (issue #69). The Markdown inline-bold example above needs six composed pieces and currently doesn't finish in reasonable time as one search; each of the six pieces individually is fast. The practical workaround (derive in stages, composing progressively) works today; making the engine detect this shape of problem and stage the composition itself does not yet.
Contracts are per-argument only (issue #70). A relational constraint spanning two argument positions (e.g. "the start index must not exceed the text's own length") is still only enforced at evaluation time, inside a primitive's own safe wrapper — not used to prune candidates before they're built the way a single-argument contract already is.
Not yet unified with the GOAP planner (issue #71). The goal-oriented planner already does efficient, deduplicated search over world-state; this engine currently does its own, separate arity-based enumeration instead. Modelling a primitive's effect as a declarative property a planner could search over, rather than a concrete example match, would let the two systems share one search strategy — a real design effort, not yet started.
A too-small memory window fails quietly, not loudly (issue #73, resolved). Genuinely polymorphic primitives like cond used to be able to exhaust available memory before finishing (the first_exceeding case above hit 102,318 candidates and 45GB+ before being stopped). Fixed on two fronts: candidate evaluation now runs across real OS threads in bounded chunks (naive per-candidate threading briefly made the whole machine, not just the search, unresponsive), and the candidate pool is now capped to a sliding window of recent search depths. The window's size still matters directly: too small, and the search completes quickly and safely but silently discards a piece the true answer needed, reporting a confident failure rather than an out-of-memory crash — worth knowing before trusting a small window's "no" on a new domain.