Nondeterministic computing

Lesson 16 changed one evaluator rule — when arguments evaluate — and laziness fell out. But a lazy program still computes one answer per expression. Now we change a different rule and let an expression compute many. We add a single operator, amb ("ambiguous"), that means "pick one of these values, and if a later constraint rejects it, automatically back up and pick another." With it the evaluator gains backtracking search as a built-in. The mechanism that makes this work — and the deep idea of the lesson — is that the evaluator stops returning a value and instead threads two continuations: what to do on success, and what to do on failure.

1 · amb and require — what they mean

amb(a, b, c, …) is an expression that nondeterministically returns one of its arguments. Operationally: it returns the first one, but it remembers the others as untried alternatives. If, later, the surrounding computation fails — declares "this can't be right" — control rewinds back to this amb and it returns the next alternative, re-running everything downstream. An amb with no arguments, amb(), has nothing to return: it is immediate failure, "this path is dead."

require(p) is the filter that triggers backtracking. Like amb it is special syntax the evaluator recognizes (not an ordinary function that returns a value), but it reads as if defined in terms of amb:

// require: if the predicate fails, this branch is dead -> backtrack.
function require(p) { if (!p) return amb(); }   // amb() = no choices = fail

// A number that is nondeterministically one of a list:
function anElementOf(xs) {
  require(!isEmpty(xs));
  return amb(head(xs), anElementOf(tail(xs)));   // this OR the rest
}

The programming model is a reversal. Instead of writing a loop that tries combinations and tests each, you declare the choices with amb and declare the constraints with require, and the evaluator does the trying and the backing-up. You describe the shape of the answer; the search is the runtime's job. That is a step toward "say what, not how" — which Lesson 18 takes all the way.

2 · A continuation, concretely

To implement automatic backtracking the evaluator needs to be able to resume the rest of the computation from a chosen point, and to abandon the current path and resume a different one. Both require a first-class handle on "what happens next." That handle is a continuation.

  the continuation of  f(x)  in  2 + f(x)   is   (v) => deliver (2 + v) onward

The nondeterministic evaluator carries two continuations at every step:

3 · The evaluator rebuilt around two continuations

This is the same eval/apply cycle from Lesson 14, but evaluate no longer returns a value. It takes the expression, the environment, and the two continuations, and it calls one of them. Most expression types are mechanical — evaluate a subexpression, and in its success continuation continue with the rest. The interesting case is amb.

// Ordinary expression: succeed with the value, passing failure through unchanged.
function evalSelf(expr, env, succeed, fail) {
  succeed(expr.value, fail);          // "here is the value; here is how to back up"
}

// amb: try each choice in turn. If a choice's downstream fails, try the next.
function evalAmb(expr, env, succeed, fail) {
  const choices = expr.choices;       // the argument expressions
  function tryNext(i) {
    if (i >= choices.length) {
      fail();                         // out of choices -> tell the PRIOR amb to back up
    } else {
      evaluate(choices[i], env,
        succeed,                      // a choice succeeded: carry it forward...
        () => tryNext(i + 1));         // ...but if downstream fails, RE-ENTER here at i+1
    }
  }
  tryNext(0);
}

Read the failure continuation of choice i: it is () => tryNext(i+1). So when some require deep downstream calls its failure continuation, the chain of failure continuations leads control right back to this amb, which advances to choice i+1 and re-runs everything after it with the new value. Backtracking is just: invoke the failure continuation that the last open amb installed. No undo log, no explicit stack of states — the continuation closures are the saved search state.

// The driver: ask for one answer; print it; on "try-again", call the saved fail.
function ambEval(expr, env) {
  evaluate(expr, env,
    (value, fail) => { report(value); /* keep `fail` to ask for the NEXT answer */ },
    () => report("no more values"));     // top-level failure = search exhausted
}

4 · Worked puzzle — Pythagorean triples by choice + filter

Find integers i ≤ j ≤ k in 1..n with i*i + j*j === k*k. The imperative version is three nested loops and a test. The nondeterministic version declares the same thing:

function pythagoreanTriple(n) {
  const k = anIntegerBetween(1, n);
  const j = anIntegerBetween(1, k);          // enforce j <= k by construction
  const i = anIntegerBetween(1, j);          // enforce i <= j by construction
  require(i * i + j * j === k * k);          // the only real constraint
  return [i, j, k];
}

k=1 -> j=1 -> i=1 : 1+1 == 1?  no  -> require fails -> backtrack
   no more i (i<=j=1) -> backtrack to j
   no more j (j<=k=1) -> backtrack to k
k=2 -> j=1 -> i=1 : 1+1 == 4?  no  -> backtrack
       j=2 -> i=1 : 1+4 == 4?  no  -> backtrack
              i=2 : 4+4 == 4?  no  -> backtrack out of k=2
k=3, k=4 : every (i,j) fails the require -> exhausted, backtrack each time
k=5 -> j=1,2,3 : all fail
       j=4 -> i=1 : 1+16 == 25? no
              i=2 : 4+16 == 25? no
              i=3 : 9+16 == 25? YES -> require passes -> succeed([3,4,5])

5 · Search vs sequence — the contrast with Lesson 13 streams

Both streams and amb deal with "many values," so it is worth being precise about the difference.

You can simulate one with the other — a stream of all solutions, or a depth-first search expressed as nested stream filters — but the natural fit differs. Streams shine when you want the values in order, lazily; amb shines when you want one satisfier of a constraint and don't care how the engine finds it. Crucially, amb made the backtracking control a language primitive, whereas streams only made the data lazy. That is the larger trajectory: each evaluator variant promotes something previously hand-coded (delay, then search) into the language itself.

Common mistakes / failure modes

Checkpoint exercise

function pairSummingTo(xs, target) {
  const a = anElementOf(xs);
  const b = anElementOf(xs);
  require(a !== b);
  require(a + b === target);
  return [a, b];
}

Where this points next

With amb you say what the answer must satisfy and let the engine search — but you still write a procedure: generate this, then that, then require this. The choices and constraints are tangled with an implicit control order (depth-first, left-to-right). Lesson 18 pushes declarativeness all the way: a logic / query language where you state facts and rules about relations and pose queries, with no procedural order at all. The engine that makes this work generalizes amb's search with a deeper idea — unification, two-directional pattern matching — so the same rule can run "forwards" and "backwards." It is the same evaluator-owns-semantics move once more, taken to its declarative limit.

Interview prompts

• What does amb mean, and how is require defined from it? (§1 — amb(a,b,…) returns one choice and saves the rest for backtracking; amb() is failure; require(p) = if(!p) amb(), a filter that kills the branch.)
• Explain a continuation concretely. (§2 — the rest of the computation reified as a function of the pending value; the call stack is the implicit chain of continuations, made explicit here so it can be saved or abandoned.)
• Why does the nondeterministic evaluator need two continuations? (§2–3 — success carries a value forward plus how to undo; failure resumes the last open amb at its next choice — calling it is exactly what backtracking is.)
• How does backtracking actually happen mechanically? (§3 — each amb choice's failure continuation is () => tryNext(i+1); a downstream require failure calls up the failure chain, re-entering that amb at the next choice and re-running downstream.)
• Trace the search for Pythagorean triples up to the first hit. (§4 — depth-first over k,j,i smallest-first; each failed require calls a saved failure continuation; for n=5 it lands on [3,4,5].)
• How does amb differ from Lesson 13 streams? (§5 — streams = lazy sequence of values, linear pull, filter skips; amb = search tree with backtracking, control is a primitive, require abandons a branch.)
• Why does ordering of choices and requires matter? (§4, mistakes — it is deterministic depth-first; early constraints/structural bounds prune the tree before it grows, so placement is the performance story.)