2 Choices, Observers, and Local Searches
The amb module provides the surface choice forms, search observers, and local search combinators, and re-exports the core primitives of amb/base (The Core: Generators and Effects).
2.1 Choices
syntax
(amb expr ...)
Each expr is wrapped in a thunk, and the thunks are collected into a mutable vector, on which current-amb-shuffler is called once.
> (stream->list (in-amb (amb 1 2 3))) '(1 2 3)
> (stream->list (in-amb (amb (amb 1 2 3) (amb 'a 'b 'c)))) '(1 2 3 a b c)
An alternative may return multiple values.
(amb) is the choice among no alternatives, so it fails. It is commonly used to discard the computations that do not satisfy a constraint.
> (stream->list (in-amb (amb))) '()
> (stream->list (in-amb (amb 1 2 (amb) 3 4))) '(1 2 3 4)
(amb) is a choice like any other: the shuffler is called on the empty vector, and the choice captures the continuation. Its events are those of (amb-fail), but amb-fail does less work; use it where the cost of a failure matters, or where a continuation barrier may be in the way.
syntax
(for/amb maybe-length (for-clause ...) break-clause ... body ...+)
(for/amb type-ann-maybe maybe-length (for-clause ...) type-ann-maybe break-clause ... body ...+)
syntax
(for*/amb maybe-length (for-clause ...) break-clause ... body ...+)
(for*/amb type-ann-maybe maybe-length (for-clause ...) type-ann-maybe break-clause ... body ...+)
maybe-length =
| #:length length-expr | #:length length-expr #:fill fill-expr break-clause = #:break guard-expr | #:final guard-expr type-ann-maybe =
| : type
With #:length, the forms work like amb combined with for/vector and for*/vector. Where the choice is made, length-expr is evaluated and the clauses run until the loop finishes or reaches that length. Each loop body is wrapped in a thunk, and at most length thunks are collected into a mutable vector, on which current-amb-shuffler is called once.
The slots that no iteration fills are not alternatives, unless #:fill is given: then fill-expr is wrapped in a thunk and each empty slot becomes an alternative that evaluates fill-expr when chosen (unlike for/vector, fill-expr is evaluated lazily per chosen slot, not once up front). A length of zero skips the clauses and calls the shuffler on an empty vector.
> (for/list ([(a b) (in-amb (for/amb #:length 4 #:fill (values 0 'w) ([i #(1 2)] [j #(x y)]) (values i j)))]) (cons a b)) '((1 . x) (2 . y) (0 . w) (0 . w))
> (for/list ([(a b) (in-amb (for/amb #:length 4 ([i #(1 2)] [j #(x y)]) (values i j)))]) (cons a b)) '((1 . x) (2 . y))
Without #:length, the loop does not collect its alternatives up front; instead, it advances lazily as the search does, taking a step through the clauses when the merger of the choice turns to the next alternative. This works with sequences of any size, infinite ones included. The shuffler is not called.
> (for/list ([x (in-amb (for/amb ([i (in-naturals)]) i))] [_ 5]) x) '(0 1 2 3 4)
> (for/list ([x (in-amb (for/amb ([c "hello"]) c))]) x) '(#\h #\e #\l #\l #\o)
With no iterations, for/amb fails unless a positive length and #:fill supply alternatives.
The for-clauses and break-clauses are not part of the search; see Code That Supplies Alternatives.
procedure
(sequence->amb seq) → any
seq : sequence?
> (define (roll-doubles) (define a (sequence->amb (in-range 1 7))) (define b (sequence->amb (in-range 1 7))) (unless (= a b) (amb)) (list a b)) > (stream->list (in-amb (roll-doubles))) '((1 1) (2 2) (3 3) (4 4) (5 5) (6 6))
parameter
(current-amb-shuffler shuffle!) → void? shuffle! : (-> mutable-vector? void?)
> (require (only-in srfi/43 vector-reverse!))
> (parameterize ([current-amb-shuffler vector-reverse!]) (stream->list (in-amb (amb 1 2 3 4)))) '(4 3 2 1)
The shuffler permutes the alternatives of one choice. (amb a b c) with a uniform shuffler chooses its first alternative uniformly; the nested (amb (amb a b) c) does not.
When the shuffler returns, the vector belongs to the choice. The choice does not keep a thunk once it has been taken: its slot is cleared, and a long vector is replaced by a shorter copy of the rest once half of it has been taken. A shuffler should therefore not keep the vector or look at it later. It is also code that supplies alternatives (Code That Supplies Alternatives).
2.2 Observing a Search
syntax
(in-amb expr maybe-handler)
maybe-handler =
| #:on-pause handler-expr
In a for clause, in-amb is used directly as the single-pass sequence of in-amb/do, without building the stream.
The pauses of the search are skipped, unless handler-expr is given. It must produce a thunk (or #f to skip pauses), which is called once for each pause (n times for a batch of n). The values that it returns become one element of the stream, in place of the pause; they do not go back into the search. The handler is called by whoever reads the stream, outside the search.
> (define (p) 'pause) > (for/list ([x (in-amb (begin (amb-pause) (amb 1 2)) #:on-pause p)]) x) '(pause 1 2)
> (for/list ([x (in-amb (amb 1 (begin (amb-pause) 2) 3))]) x) '(1 2 3)
syntax
(in-amb/do expr maybe-handler)
maybe-handler =
| #:on-pause handler-expr
See After an Exception for how in-amb and in-amb/do behave after an exception or a reentrant read.
2.3 Local Searches and First Answers
syntax
(amb-local expr)
procedure
(amb-local* thk) → any
thk : (-> any)
(make-amb (λ () (amb-generate* thk)))
The pauses of the local search are pauses of the search around it.
Within the search-event model (fixing the same inner computation and mergers, and assuming the computation does not observe host dynamic environment differences such as parameters across the search boundary; see Where Host Code Runs):
At the end of a computation, (amb-local expr) has the same logical events as expr when the enclosing choice uses one of the mergers of amb/merge.
When the computation goes on after it, the order can change: the enclosing merger schedules the rest of the computation from the local search’s answers. If amb-append is used throughout, both forms have the same logical events for any continuation.
> (require amb/merge) > (define (pause-then x) (amb-pause) x)
> (parameterize ([current-amb-merger amb-level]) (list (stream->list (in-amb (list (amb (pause-then 1) 2) (amb 'x (pause-then 'y))))) (stream->list (in-amb (list (amb-local (amb (pause-then 1) 2)) (amb 'x (pause-then 'y))))))) '(((2 x) (1 x) (2 y) (1 y)) ((2 x) (2 y) (1 x) (1 y)))
2.3.1 The First Answer of a Search
The library does not provide the first answer of a search, because there are two ways to write it, and they differ in what happens to the pauses of that search.
(define (first-answer thk) (for/first ([v (in-amb* thk)]) v))
Here the pauses stay inside the search of (thk). For the search around it, finding the answer is a single step, and no merger gets a turn before it is done. If (thk) pauses forever, so does the search around it, whatever its merger. If there is no answer, the result is #f, not a failure.
(define (amb-once thk) (let loop ([gen (λ () (amb-generate* thk))]) (define-values (v next) (gen)) (cond [(list? v) (apply values v)] [(not v) (amb-fail)] [else (amb-pause v) (loop next)])))
Here every pause of the search of (thk) is passed on as a pause of the search around it, which therefore stays fair, and no answer is a failure. This is the version that the committed choice of a miniKanren needs.