amb: Ambiguous Operator
The amb library provides John McCarthy’s ambiguous operator for nondeterministic programming in direct style. A choice is an ordinary expression: (amb 1 2 3) returns one of its alternatives, and the rest of the computation runs once for each of them as the search demands it. A search reports the results of those runs.
> (for/list ([x (in-amb (let ([a (amb 1 2 3)] [b (amb 10 20)]) (when (odd? (+ a b)) (amb)) (list a b)))]) x) '((2 10) (2 20))
Choices, and the other effects, can only be used within the dynamic extent of a search. The library is organized in three layers:
amb (Choices, Observers, and Local Searches) provides the everyday choice forms (amb, for/amb, sequence->amb, amb-local) and observers (in-amb, in-amb/do), and re-exports amb/base. typed/amb (Typed Interface) gives the same interface Typed Racket types.
amb/base (The Core: Generators and Effects) is the core on which everything else is built. It defines the generator protocol and the primitive effects: (λ () (amb-generate* thk)) turns a search into a generator of events (reifying it), and make-amb turns a generator of alternatives into a choice (reflecting it), alongside amb-fail and amb-pause.
amb/merge (Mergers) provides the standard mergers, which decide the search strategy of each choice.
This is version 3 of the library. It is not compatible with version 2; Changes from Version 2 lists the differences.