3 The Core: Generators and Effects
| (require amb/base) | package: amb |
amb/base exports the seven bindings that the rest of the library is built on: make-amb, amb-generate*, amb-fail, amb-pause, current-amb-merger, with-amb-mark and call-with-amb-mark. amb re-exports all of them.
The design centers on the duality between direct-style searches and generators: (λ () (amb-generate* thk)) reifies a search into a generator of events, and make-amb reflects a generator of alternatives back into a choice in direct style. A library that builds its own language on searches, such as a miniKanren, needs nothing more: a disjunction is make-amb, a failure is amb-fail, a relation pauses with amb-pause, and running a goal is amb-generate*. The surface forms of amb (Choices, Observers, and Local Searches) are written for uniformity rather than speed; a library that cares about the cost of each step can use these bindings directly.
3.1 The Generator Protocol
A search is represented by a generator: a thunk that returns two values—a result for the next step and a generator for the rest of the search.
| generator | = | (-> (values result generator)) | ||
| result | = | list? | ||
| | | #f | |||
| | | exact-positive-integer? |
A list is an answer holding its return values. The empty list '() represents a zero-valued answer, not the end.
#f signals the end of the search. The returned generator must not be called.
A positive integer n reports a batch of n logical pauses, followed by the returned generator.
Expanding each batch into individual pauses yields a generator’s sequence of logical events (for instance, a batch of 3 produces the same three pauses as batches of 1 and 2). Throughout this manual, two generators are considered equivalent when they produce the same logical events and diverge in the same places, regardless of how pauses are batched.
0 is not a valid result: every batch must account for at least one pause so that each step makes progress—otherwise a generator could return empty batches forever without reaching the next logical event. If a generator returns an invalid first value (not a list, #f, or a positive integer), the consumer raises exn:fail:contract; the returned generator is not checked unless it is called.
Generators are single-pass: every generator—and each generator it returns—must be called at most once. The behavior of calling a generator more than once is unspecified (for example, the library’s vector-backed choice generators raise exn:fail:contract).
Because sequence-generate* already returns an answer list or #f along with the next step, (λ () (sequence-generate* seq)) is a pause-free generator for any sequence.
Generators appear in three places: make-amb consumes a generator of alternatives, amb-generate* exposes a search as a generator, and a merger combines two generators into one.
3.2 Core Primitives
procedure
(amb-generate* thk) →
(or/c list? #f exact-positive-integer?) (-> any) thk : (-> any)
amb-generate* is eager: it runs the search up to its first event when it is called. (λ () (amb-generate* thk)) is the generator of the whole search; it is what in-amb*/do reads.
> (define-values (v next) (amb-generate* (λ () (amb 1 (begin (amb-pause) 2))))) > v '(1)
> (define-values (v2 next2) (next)) > v2 1
> (define-values (v3 next3) (next2)) > v3 '(2)
Together with make-amb, it builds searches inside a search: amb-local (Local Searches and First Answers), and others that the library does not provide, such as the first answer of a search.
For example, (sequence->amb seq) is (make-amb (λ () (sequence-generate* seq))).
> (define (countdown n) (λ () (if (zero? n) (values #f void) (values (list n) (countdown (sub1 n)))))) > (stream->list (in-amb (make-amb (countdown 3)))) '(3 2 1)
For two alternatives m, n supplied without pauses, the choice merges them from the right by the merger μ that is current where the choice is made, merging the last one with the end of the supply:
(μ kₘ (μ kₙ end))
where kₘ is the generator of the rest of the computation with the alternative m. The inner merge is not made before the outer one turns to it, so next is not asked for an alternative before its turn. make-amb keeps the merge with the end whatever the merger is; for a merger that has the end as a right unit, such as those of amb/merge, it makes no difference.
next is code that supplies alternatives: it must not choose, fail or pause in the search that it supplies (Code That Supplies Alternatives). It pauses by returning a number.
> (stream->list (in-amb (amb 1 (amb-fail) 2))) '(1 2)
Since nothing of the computation will be resumed, amb-fail does not capture its continuation. A continuation barrier between it and its search, such as the barrier around an exception handler that raise calls, does not stop it. A choice or a pause captures its continuation, and a barrier stops it. This holds for a choice among no alternatives too, such as (amb), an empty for/amb, or (sequence->amb '()): it fails, but it is still a choice.
A merger may pass the turn to another alternative at every logical pause, including between pauses in the same batch; the default merger, amb-append, lets the paused branch keep the turn (Fairness Needs Pauses). Observers skip pauses by default, or call their #:on-pause handler once per logical pause.
> (stream->list (in-amb (begin (amb-pause) 'x))) '(x)
> (stream->list (in-amb (begin (amb-pause 3) 'x) #:on-pause (λ () 'pause))) '(pause pause pause x)
> (stream->list (in-amb (begin (amb-pause 0) 'x) #:on-pause (λ () 'pause))) '(x)
The merger is read where a choice is made, so different choices of one search can use different mergers.
> (require amb/merge)
> (for/list ([x (in-amb (list (parameterize ([current-amb-merger amb-alternate]) (amb 1 2)) (amb 'a 'b)))]) x) '((1 a) (2 a) (1 b) (2 b))
See Mergers for the mergers of amb/merge, and for the requirements on a merger of one’s own.
3.3 Code That Supplies Alternatives
Some code runs for a choice without being part of the search:
On-demand supply: the generator given to make-amb, the sequence given to sequence->amb, and the for-clauses and break-clauses of for/amb and for*/amb without #:length.
Eager pre-collection and shuffling: the #:length expression and clauses/guards of for/amb and for*/amb with #:length, and the procedure of current-amb-shuffler.
On-demand supply runs after make-amb leaves the search, when the merger turns to the next alternative—which may be long after the choice was made, and in another dynamic context. Eager pre-collection and shuffling run at the choice point before make-amb is called, under a supply mark (see Where Host Code Runs). In both cases, an effect of the enclosing search has no meaning here and raises an error.
> (stream->list (in-amb (for/amb ([x '(1 2 3)] #:when (amb #t #f)) x))) make-amb: not allowed while the alternatives of a choice are
supplied;
code that supplies alternatives must not choose, fail or
pause in its search;
for example, the generator of make-amb, a clause of
for/amb, or the shuffler
The body of for/amb, and the expressions of amb, are part of the search.
An independent search started inside supply code is unaffected.
With #:length, clauses up to the length limit or the end of the loop run where the choice is made. An effect in those clauses raises an error there, even if only the first answer is requested. Without #:length, the error is raised when the search reaches the iteration that has the effect.
syntax
(with-amb-mark expr)
procedure
(call-with-amb-mark thk) → any
thk : (-> any)
make-amb already marks its generator automatically. You need with-amb-mark when writing a custom choice form that gathers its alternatives before calling make-amb—for example, collecting thunks into a list or vector, just as for/amb with #:length does. Without the mark, a stray amb inside that collection loop would run as part of the enclosing search and silently duplicate the rest of the collection for each branch instead of failing fast.
The mark only blocks effects targeting the enclosing search: it does not start a search of its own, and an independent nested search started inside expr (via in-amb or amb-generate*) runs normally. In the example below, with-amb-mark catches the (amb #t #f) inside the for/list that builds the thunk list for choose-among.
> (define (choose-among . thunks) ((sequence->amb thunks)))
> (stream->list (in-amb (apply choose-among (with-amb-mark (for/list ([i 3] #:when (amb #t #f)) (λ () i)))))) make-amb: not allowed while the alternatives of a choice are
supplied;
code that supplies alternatives must not choose, fail or
pause in its search;
for example, the generator of make-amb, a clause of
for/amb, or the shuffler
See Where Host Code Runs for the full rules on where host code runs relative to search boundaries.