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

First published 2026-09-01.

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

EachEach 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 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

TheThe 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

NothingNothing 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 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 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 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 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, doesn't just run slowly — verified directly, twice, with no artificial cutoff imposed either time: the default sliding window (16) exhausts memory and crashes the process after about 41 minutes, having tracked 918,575 distinct candidates; a smaller window (8) doesn't help, it runs LONGER (about 66 minutes) and crashes on a LARGER pool (1,927,186) before failing the same way. The sliding window bounds how much of the past gets retained for future lookups; it does nothing about how many combinations get generated from what's already retained at a single level, which is what actually explodes here. A genuine, reported current limit, not a hidden one — see issue #69.

Bidirectional witnesses: searching backward from the goal, not just forward toward it

EverythingEverything above generates candidates forward — grow the pool one level, check each new candidate against the goal, repeat — and only ever asks "have I stumbled onto the answer yet?" self_hosting/lib/bidi_synthesis.patlang adds a second, backward direction alongside the same forward pool: at each level, before growing further, ask "does the goal decompose, via some invertible primitive, into pieces that already exist?" For string concatenation, that means trying every split point of the target and checking whether both halves are already in the pool. For addition/subtraction, classic two-sum-style inversion. Both are exact lookups against the same index the forward search already builds — no new data structure, no speculative invention of unseen values.

cond(test, a, b) doesn't invert as cleanly — a boolean-guarded selection has two branches, and which examples belong to which branch isn't known in advance. The first attempt (partition the examples into two groups every possible way, then recursively re-synthesize both branches and the separating test from scratch for each partition) is correct but wastefully expensive: an 8-example transition-logic case took 82 minutes and still returned the wrong answer. Two fixes, tried and measured in order, not assumed: first, the boolean-test sub-search was itself recursing into a full nested cond search at unbounded cost — excluding cond from that one sub-search's own primitive list dropped the same case to 29 seconds. Second, replacing full recursive re-synthesis per partition with a cheap single-pass scan for an already-built node matching each branch's targets exactly (skip the partition if no such node exists yet, rather than trying to build one) dropped the harder, correctly-disambiguated 8-example case to roughly two minutes, and the simpler 5-example case to under two seconds. Ambiguity tracking (kept from the very first version) survived both rewrites unchanged: if more than one same-size candidate satisfies every example, the result says so rather than silently picking one.

A genuinely different search shape (real A*, an admissible heuristic derived from a relaxed type-reachability search, provable early stopping) and a pure-scan alternative (no partition enumeration at all, a triple-nested scan over test/branch pools directly) were also built and measured, not just theorised. The pure scan was a clear negative result, reported rather than discarded: cubic in pool size, it crashed at size 8 alone on the same 5-example case the combined partition+scan approach solves in under two seconds. The two effective ideas that shipped — skip the wasteful nested-cond sub-search, and replace recursive re-synthesis with a cheap existence scan — both came from directly instrumenting where the time was actually going, not from guessing at the algorithm from first principles.

Structural contracts: ruling out a known-bad shape, not just hoping a better one turns up

SmallestSmallest AST that satisfies every example" has no notion of "the formula a person would actually write." A small, exhaustively-specified 3-state/2-action transition table (see the project journey for the full state-machine demo this is drawn from) derives, completely correctly, cond(eq_int(state,action), cond(eq_int(state,0),1,2), state) — comparing state directly to action, which only works because the two integer ranges happen to line up, not because that's what the logic means. Four separate attempts to force a more intuitive result by changing the examples alone — more inputs, a larger exhaustive table, disjoint integer ranges for actions, string-typed actions instead of integers — each either found a different coincidence or exhausted available memory looking for one. More or different data was not, on its own, a lever that worked.

The next lever tried instead: don't hope a better formula turns up, rule the bad one out directly. bidi_contract_ok(node) generalizes the enumerator's existing per-argument contracts (see above) to a whole-candidate constraint, checked once a cond(test,a,b) node is fully assembled: a caller sets bidi_contract_fn to a predicate over the whole AST, and a candidate that fails it is simply skipped — the search moves on to the next partition, it doesn't stop. Purely additive: unset, every existing caller (every demo above) behaves exactly as before.

Tested directly against the exact case that produced the original coincidence, with a contract narrow enough to leave a correct formula reachable (banning a direct comparison between the two named inputs specifically, not banning either input from appearing at all — the transition logic legitimately needs to reference both): the contract worked as asked. The result never once compares state to action directly, and is independently verified correct against all nine transition-table entries. It is not, however, more intuitive — it's eq_int(state, cond(eq_int(state,1), action, 2)), a differently-shaped and arguably more convoluted formula of the identical size, taking three times longer to find. This is a narrow capability — rule out one named bad pattern — not a general answer to "make the search prefer formulas a human would write." Nothing about "smallest AST subject to this constraint" implies "the AST a person would have written," and a contract can just as easily trade one coincidence for a different one as it can produce a clean result.

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

TwoTwo kinds of situation get a 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 doesn't just run slowly, it crashes (issue #69). The Markdown inline-bold example above needs six composed pieces plus the raw primitives to reassemble the surrounding text (nine candidates per level); each of the six pieces individually is fast, but composing all of them in one flat search exhausts memory and crashes the process (confirmed directly, twice, with no artificial cutoff: ~41 minutes/918,575 tracked candidates with the default memory window, ~66 minutes/1,927,186 with a smaller one that made it worse, not better). 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.
• Deliberately not unified with the GOAP planner (issue #71, resolved). The goal-oriented planner's search treats every reachable combination of facts as a distinct world-state, which is the right model when actions genuinely remove facts (moving somewhere really does mean you're no longer where you started). This engine's own actions never remove anything — a derived value, once known, stays known — which makes it a delete-free reachability problem, not a STRIPS one: modelled as world-state search anyway, ten independent starting values alone produced 1024 (2¹⁰) distinct "states" before any real composition even began. A from-scratch fact-cost relaxation engine, matching that actual shape (a running best-known cost per value, not a search over combinations of them), was built to test the idea directly and returned the exact same answer in the exact same time as the existing arity-based enumeration above — confirming the enumeration was already the right algorithm for this problem, just arrived at differently. One real bug came out of building the comparison: primitive cost (already a registered property of every primitive, not just its argument count) wasn't actually influencing which candidate search preferred — "smallest wins" meant fewest calls, not cheapest declared cost. Now fixed.
• 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.

See also

InductiveInductive Synthesis: from BDD scenarios to PatLang code is the sibling engine that induces logical rules rather than composing primitive expressions. PatLang Goal-Oriented Programming covers the action_add/plan engine referenced in the current-limits section above. PatLang BDD Framework and PatLang Design by Contract cover the Given/When/Then runner and the require/ensure contract statements this system's own primitive contracts are modelled after. The current-limits items above are tracked as GitHub issues #69 and #70 (open), #72 (open), and #71 and #73 (resolved).