amb: Ambiguous Operator🔗ℹ

1 Evaluation Model🔗ℹ

An amb-tree is a leaf-labeled tree: internal nodes are pure branching points with no values of their own; only leaves carry the results of complete computations. Structurally, a tree is either a leaf value or a stream of subtrees. Categorically, this is the free monad over the stream functor.

Each amb expression creates an amb-tree with one branch per alternative. A branch that calls (amb) is a dead end: it is pruned and the search backtracks.

Internally, in-amb maintains an amb-frontier—an immutable deque of pending amb-trees. Each step pops a tree, runs one branch, and, depending on the outcome, either yields a leaf and suspends, enqueues a child tree and continues, discards the tree and continues (dead end), or just continues.

The alternatives in amb are mutually exclusive—each is lazily evaluated only when that branch is selected.

Corresponding amb-tree:

Nested amb expressions are implicitly flattened: their alternatives are inserted into the parent’s choice list. Under unfair depth-first order, (amb (amb 1 2) (amb) (amb 'a 'b)) therefore produces the same sequence of leaves as (amb 1 2 'a 'b).

By contrast, when amb expressions appear in order (e.g., via let*), each subsequent amb is in the continuation of the previous one. The amb-tree becomes a Cartesian product of all choices.

Corresponding amb-tree:

Since this is the free monad over the stream functor, it can be expressed purely with streams. The correspondence is direct: amb is stream, in-amb is stream-flatten, and sequential amb in let* corresponds to for*/stream composed with stream-flatten. This is the interpretation without an empty handler, in which an empty choice contributes nothing; it does not model the handler, whose leaf ends the whole branch. The examples above, rewritten in this style:

(define (stream-flatten s*)

(stream*

(if (stream-empty? s*)

s*

(call-with-values

(λ () (stream-first s*))

(λ (v . v*)

(define s (stream-rest s*))

(if (and (null? v*) (stream? v))

(if (stream-empty? v)

(stream-flatten s)

(stream-flatten (stream* (stream-first v) (stream-rest v) s)))

(stream-cons (apply values v v*) (stream-flatten s))))))))

The translation extends to realistic programs. Whereas in-amb and nested amb expressions both flatten implicitly, the stream encoding requires explicit stream-flatten at each level. Intermediate bindings use #:do, and (amb) (dead end) becomes #:when or #:unless.

The difference is in the traversal mechanism. stream-flatten relies on the implicit program stack as its frontier, yielding unfair depth-first order (LIFO). in-amb replaces the stack with an amb-frontier to make the traversal order configurable (see Parameters).

Despite the continuation capture and deque management, the overhead is negligible in practice—on the Pythagorean triple example above, the amb version runs at roughly the same speed as the stream version.

The stream-flatten wrappers in the stream version serve a specific purpose: they mirror amb’s implicit flattening of nested amb-trees, so that each loop variable can traverse a leaf-labeled tree rather than just a flat stream. When the iteration source is already flat—as it is for in-range or in-stream over a plain stream—wrapping it in stream-flatten adds significant overhead. In those cases, omit stream-flatten and iterate directly:

2 Ambiguous Operator🔗ℹ

Each expr is implicitly wrapped in a thunk and collected into a mutable vector.

When called with no arguments, (amb) is a choice among no alternatives: the computation ends there. What it ends with is decided by the innermost search. By default it ends with nothing, so (amb) signals failure, causing the search to backtrack; this is commonly used as a pruning mechanism to discard branches that do not satisfy a constraint. A search started with a handler (#:empty-handler for in-amb and in-amb/do) instead calls the handler at the point of (amb) and produces its results as one leaf.

A dead-end (amb) nested among alternatives prunes only that branch—the others proceed normally:

A productive nested amb creates a child amb-tree. When the inner tree is exhausted, the search backtracks and continues with the next sibling in the parent:

Alternatives producing multiple values are supported:

If the optional #:length clause is specified, the syntax resembles for/vector and for*/vector. Each loop body is implicitly wrapped in a thunk and collected into a mutable vector, mirroring how amb itself works.

If the optional #:length clause is omitted, the number of iterations is unknown, so each loop body is deferred to a thunk and produced one at a time by driving the for loop as a coroutine: a captured continuation resumes the loop to yield the next alternative on demand. Because the body is evaluated lazily, this works with sequences of any size, including infinite ones.

A for/amb that provides no alternative at all is (amb): without #:length, a loop with no iterations; with #:length, a length of 0, or no iterations and no #:fill. Slots filled by default are not alternatives, but with #:fill every slot is one. The clauses are evaluated once either way.

3 Stream Constructor🔗ℹ

The form (in-amb expr) expands to (in-amb* (λ () expr)), and (in-amb expr #:empty-handler handler-expr) to (in-amb* (λ () expr) handler-expr).

The empty handler answers (amb). When the computation reaches (amb), the handler is called there, in the dynamic context of (amb), and the values it returns are produced as one leaf; the rest of that branch is abandoned, as with failure. The default handler is amb-fail, which makes (amb) a failure. The handler may also call amb-fail itself, make choices of its own, or raise an exception; if it reaches (amb) of the same search, exn:fail:contract is raised. It should return as many values as expr does: Typed Racket checks this, and otherwise the mismatch is reported only where the leaf is received.

Since the search is lazy, the dynamic context of (amb) is the one in which the search is resumed, that is, the consumer’s, as for any other code in expr:

The handler belongs to the search that was given it, not to the dynamic extent of in-amb: a search started inside the computation, without a handler of its own, still fails at its own (amb). Together with a choice point, a handler makes a pause observable: (when (amb #t #f) (amb)) produces the handler’s leaf and then continues the computation after it.

in-amb acts as a one-step lookahead stream constructor. To determine whether the stream is non-empty, it eagerly evaluates the next leaf.

4 Parameters🔗ℹ

The behavior of the amb search engine is governed by two orthogonal parameters: current-amb-depth-first? controls traversal order and current-amb-fair? controls fairness. Together, they make the amb-frontier pluggable in ways impossible to achieve with the implicit stack alone.

As described in Evaluation Model, the search driver maintains an amb-frontier. Each step pops an amb-tree from the front and runs it. The result determines what happens next:

• Dead end: the tree is exhausted and is discarded (not returned to the amb-frontier). The search continues.

• Nothing: the tree produced nothing on this resumption. The parent tree is put back for its remaining alternatives. current-amb-fair? controls whether the parent tree goes to the front or the back. The search continues.

• Leaf: a result is produced, by the computation or by the empty handler at (amb). The parent tree is put back (as in the nothing case). The search suspends.

• Branch: a new amb-tree was created. The parent tree is put back (as in the nothing case), and the new child tree is also inserted. current-amb-depth-first? controls whether the child tree goes to the front or the back. The search continues.

Both parameters are captured per-tree at the point where amb or for/amb is evaluated. This means different parts of a computation can use different strategies via parameterize. As a result, different subtrees may coexist in the same search with different traversal strategies.

When #t (the default), child trees are pushed to the front of the amb-frontier, yielding depth-first search (DFS). When #f, child trees are pushed to the back, yielding breadth-first search (BFS).

When #f (the default), the parent tree is placed back at the front. When #t, the parent tree is placed at the back, giving other pending trees a chance to run first. This prevents any single branch from starving its siblings.

The default value is void (no shuffling).