The Journey of Building PatLang, Continued Yet Again: Searching Backward, and Learning What "Correct" Doesn't Mean

For new readers

This is one instalment in an ongoing, chronological diary of building PatLang, written up in numbered "Acts" as the project actually happened, warts included. This instalment leaves canvas_host behind and returns to the example-driven synthesis engine (Example-Driven Synthesis): a search that finds the smallest composition of PatLang primitives satisfying a set of input→output examples. The arc here runs from closing out a genuine research question about a different planner entirely, through a real algorithmic addition (searching backward from the goal, not just forward toward it) with two real speed breakthroughs measured along the way, a memory-safety incident serious enough to need a machine reboot, one confidently wrong claim about the project's own capabilities corrected on the spot, a run of small domain demos proving the same synthesis mechanism generalizes across objects, events, and state machines, and a close look at a genuinely open problem: a search that only optimizes for "smallest" has no notion of "the answer a person would have written," and more examples alone didn't fix that.

A direct continuation of the previous instalment (Acts LI-LVII: giving PatLang a real GUI window), though not a continuation of its subject — this arc picks back up an older thread, the synthesis engine's own unification question with the GOAP planner, left open at the end of the synthesis page's own current-limits list.

Act LVIII: closing the GOAP question, for real this time

Whether the example-driven search and the GOAP planner (action_add/plan) were secretly the same problem in two different costumes had been asked and re-asked across several sessions without a clean answer. This time it got one, built directly rather than argued abstractly: a from-scratch fact-cost relaxation engine, matching the enumerator's own actual shape (a running best-known cost per value, never removed once known) rather than GOAP's world-state model (every reachable combination of facts is a distinct state, which is the right model exactly when actions genuinely remove facts — this engine's own actions never do). Run side by side against the same problem, the relaxation engine returned the identical answer in the identical time as the existing enumerator — confirming the enumeration was already the right algorithm, just arrived at by a different, longer route than a clean derivation would have taken.

The comparison did turn up one real, previously invisible bug: primitive cost is a declared property of every registered primitive, but "smallest wins" inside sbe_build_calls was actually counting call depth, not the declared cost — a cheap primitive and an expensive one competed on equal footing as long as they used the same number of calls. Fixed, and issue #71 closed with the full evidence trail rather than left open on a hunch.

Lesson: "are these two systems secretly the same algorithm" is answerable by building the alternative and racing it, not by reasoning about their descriptions — and a negative result (they're not secretly unified) can still surface a real, unrelated bug in the system you already trusted.

Act LIX: a heuristic that finally listened to "A*"

The direct prompt was pointed, and fair: "there is basically using a heuristic which is what A* does (and you will note, I keep mentioning A* even though you keep, basically, ignoring it) so lets do that." cond(test, a, b)'s own witness (see the synthesis page's own account of this for the full technical shape) had, until this point, been ordered by nothing more principled than partition-list order. A real admissible heuristic — derived from a relaxed breadth-first search over which primitive/type combinations can reach which other types at all, cheap and permissive rather than exact — turned the partition search into genuine A*, with provable early stopping once no remaining partition's lower bound could beat the best answer already found, and the same ambiguity-tie tracking the plain enumerator already relied on, carried over rather than dropped for the sake of speed.

Lesson: when someone keeps naming the specific algorithm they think applies, that's worth taking as a direct instruction, not a suggestion to keep tuning around.

Act LX: three background copies, thirty-five gigabytes, one reboot

Long-running synthesis searches got left running across a session interruption, and a relaunch afterward didn't check what was already alive first. Three separate copies of the same search ended up running in parallel, consuming roughly 35GB of RAM between them, and the machine went down hard enough — Chrome crashed, everything stopped responding — to need a full reboot. The three background shells had, as it turned out, been running since before the reboot, not spawned fresh afterward; they simply didn't survive it, which was the one piece of good news in an otherwise bad incident.

Fixed on two levels, not one. Immediately: a hard process-level habit, now standing practice, of checking tasklist for anything already running before ever relaunching a background search, and never trusting a kill command's own "success" report without independently re-checking the process list afterward (one stuck process this session needed a second, more forceful kill attempt after the first claimed success and hadn't actually worked). Durably: a memory watchdog built directly into the PatLang runtime itself (spawn_memory_watchdog, rust-runtime/src/main.rs) — a background thread polling the process's own memory usage every two seconds and exiting cleanly, with a clear message rather than silently corrupting anything, past a configurable cap (PATLANG_MAX_MEM_MB, default 8GB). Every long-running search from this point on in the session ran under that cap as the only real safety net, deliberately left unbounded on wall-clock time instead — the alternative habit this incident helped break for good, covered next.

Lesson: a background process surviving a session interruption is not something to assume away — check what's actually running before adding to it, and build the safety net into the tool itself rather than relying on remembering to check by hand every single time.

Act LXI: arbitrary deadlines aren't evidence, twice reminded

Wrapping a long search in timeout 300 and treating hitting that limit as proof of "this case genuinely can't finish" is a habit that had already been raised and corrected once before this session, and it recurred — caught twice, directly: "Are you putting arbitrary deadlines on things again? We've talked about that before..." A timeout tells you the process didn't finish inside an arbitrarily chosen window; it tells you nothing about whether it would have finished the next second, or crashed, or looped forever. Every case this session that mattered — the markdown scaling wall, the disambiguated 8-example transition case — got re-run properly afterward: unbounded wall-clock time, the memory watchdog from Act LX as the only actual safety net, run through to a genuine finish or a genuine crash rather than an assumed one.

Lesson: a self-imposed timeout produces a fact about the timeout, not a fact about the thing being timed — if a real answer matters, remove the artificial deadline and use a safety net that reacts to what's actually happening (memory, in this case) instead.

Act LXII: fixing the boolean-test search, then rethinking the branches themselves

Direct per-level candidate-count instrumentation on the newly-A*'d cond search found the real cost driver: the boolean test guarding each partition was itself recursing into a full, unrestricted nested cond search, at combinatorial cost, on every single partition tried. Excluding cond from that one specific sub-search's own primitive list (bidi_strip_cond) dropped a real 8-example case from over 80 minutes to 29 seconds — a genuinely large, genuinely earned speedup from a small, precisely targeted change, not a broad rewrite.

A second idea followed directly from the user's own description of a different way to think about the same search: "I still think that if we have a list of local world state which gets passed around (mutable) and each candidate has to permit that all the members of the list of local world state to be considered... we would be effectively trying to find a solution using the A* search approach but basically simulating it as we go." Tried as a pure triple-nested scan over test/branch pools directly — no partition enumeration, no recursive re-synthesis at all — and reported honestly once measured: cubic in pool size, it made things worse, not better, crashing at size 8 alone on a case the existing approach already solved. Combining the two ideas rather than choosing between them was the actual breakthrough: keep partition enumeration (cheap, and it correctly frames "which examples belong to which branch" as the real unknown), but replace each branch's expensive recursive re-synthesis with a cheap single-pass scan for an already-built node matching that branch's targets exactly, skipping the partition outright if no such node exists yet. Measured directly: roughly 160x faster on the simpler 5-example case (under two seconds, down from a run that hadn't finished in over two minutes), and the harder, correctly-disambiguated 8-example case — previously needing over 80 minutes and returning a wrong answer — came in at just over two minutes with the right one.

Lesson: a negative result from one idea (the pure scan) and a real fix from another (excluding cond from its own sub-search) don't have to compete — the actual improvement here came from combining the cheap half of one approach with the cheap half of the other, not from picking a single winner between them.

Act LXIII: wrong about WASM, corrected on the spot

Asked directly whether any of this synthesis work would run under WebAssembly, the first answer was confidently wrong: a claim that PatLang lacked WASM compilation, real threading, a virtual filesystem, and any signalling mechanism at all. The correction was equally direct and specific — named live URLs already running on this very site, patlang-robots.html and patlang-vfs-demo.html among them — and checking the actual source turned up all four claims wrong at once: a working cooperative-fiber module, a VFS explicitly gated for the exact case (wasm32 without shared-memory atomics) rather than absent, and a signals mechanism (self_hosting/lib/signals.patlang) already built on primitives the codebase already had. The honest accounting afterward went further than just admitting the error: a separate Rust-side progress-query mechanism built earlier in this same session, before this correction, turned out to duplicate that exact existing signals mechanism, less capable and less well integrated — left in place since it was already committed and working, but named plainly as redundant rather than quietly kept.

Lesson: a confident claim about what a codebase "doesn't do" is a claim about the code, not about memory of the code — when directly contradicted with specific evidence, check the actual source before either defending or accepting the correction, and say plainly when something already built turns out to duplicate something that already existed.

Act LXIV: the same engine, four more domains

With the cond witness now fast enough to use freely, four small demos in increasing order of structural complexity proved the same synthesis mechanism generalizes well beyond pure text/numeric functions: an Account object whose deposit/withdraw methods call derived logic directly (a genuine object wrapping a synthesized decision, not just a synthesized function called from a script); an inventory system driven entirely by real when/emit events, the pure logic derived and the event wiring the only hand-written code; the two combined, an Account.withdraw composing two independently-derived pieces — one for the balance update, a second, separate one deciding whether an insufficient_funds event should fire at all — verified at the exact boundary (a withdrawal of precisely the remaining balance correctly does not fire the event); and a three-state, two-action ticket state machine, needing a genuinely nested conditional (guard on state, then guard on action within that state) rather than one flat decision, verified across two independent instances and a terminal-state absorption case.

The state machine demo is also where the arc's closing question first became visible, in its rawest form: with all six possible (state, action) pairs given exhaustively, the derived formula compared state directly to action — correct, since there's no held-out input left to prove it wrong, but plainly not what a person modelling "pending, active, done" would have written by hand.

Lesson: proving a mechanism generalizes means testing it on domains it wasn't built for, in order — each of these four demos deliberately reused a shape from the one before it (the same clamp-on-insufficient conditional, the same event-wiring convention) in a new setting, rather than four unrelated one-off tests.

Act LXV: four ways of asking for a more intuitive answer, and what actually worked

The state machine's own coincidental formula from Act LXIV prompted a direct question: could the examples alone be shaped to force a more intuitive result? Four attempts, each genuinely tried rather than assumed: a larger exhaustive table (4 actions instead of 2) crashed before finishing; a disjoint integer range for actions (shifted well clear of any state value) also crashed; a 3x3 table with in-range integers found a different coincidental structure rather than the intended one; string-typed actions ("start"/"finish"/"pause", an idea raised directly — "Wondering if making actions alphanumeric might be a better general approach?") found yet another coincidence, differently shaped again. Four attempts, four failures to force intuition through the examples alone — a real, honestly-reported negative result, not a single unlucky case.

The next lever tried instead, following directly from another concrete suggestion — "defining... functions that return needed values with contract based constraints so they limit the search on them?" — was to rule out the specific bad pattern directly rather than hope a better one turned up on its own. The synthesis page covers the resulting mechanism and its result in full: a whole-candidate structural contract, generalizing the enumerator's existing per-argument contracts, that can ban a named bad shape (a direct state-vs-action comparison, specifically) while leaving a correct formula reachable. It worked exactly as asked — and the formula it found instead was, if anything, more convoluted than the coincidence it replaced, at the same size, for three times the search cost. A real, working, narrowly-scoped capability, landed honestly as exactly that rather than oversold as the general fix the arc had been looking for.

Lesson: when a search only optimizes for one measurable property (smallest AST), forcing a different unmeasured property (looking natural to a person) by varying the training data alone is not guaranteed to work, and repeatedly didn't here. Ruling out a specific, already-identified bad pattern by name is a real and useful capability precisely because it doesn't depend on hoping the search happens to prefer what you'd have written — but it's a targeted patch for one named shape, not a general theory of what makes a formula intuitive.

If you're building something similar: the short version

"Are two systems secretly the same algorithm" is answered by building the alternative and racing it against the original, not by comparing their descriptions on paper.
When someone names the specific algorithm they think applies, more than once, treat it as a direct instruction rather than something to keep circling.
A background process surviving a session interruption is a real risk, not an edge case — check what's already running before relaunching anything, and build an automatic safety net (a memory cap, here) into the tool itself rather than relying on remembering to check by hand.
An arbitrary timeout tells you about the timeout, not about the thing being timed. If a real answer matters, remove it and use a safety net that reacts to what's actually happening.
A negative result from one idea and a real fix from another don't have to compete — combining the cheap, correct half of two different approaches can outperform either one alone.
A confident claim about what a codebase can't do is a claim about the code, worth checking against the code directly the moment it's contradicted with specific evidence, rather than defended from memory.
Proving a mechanism generalizes means deliberately testing it outside the domain it was built for, reusing shapes from one test to the next rather than running unrelated one-offs.
Forcing a search to prefer an unmeasured property (looking natural to a person) by varying only its training data is not guaranteed to work — and when it doesn't, ruling out a specific named bad pattern directly is a real, narrower, more honest fix than hoping better data will do it.