On this page:
2.1 Choices
amb
for/  amb
for*/  amb
sequence->amb
current-amb-shuffler
2.2 Observing a Search
in-amb
in-amb*
in-amb/  do
in-amb*/  do
2.3 Local Searches and First Answers
amb-local
amb-local*
2.3.1 The First Answer of a Search
9.3

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 ...)

John McCarthy’s ambiguous operator: a choice among the exprs. Its value is the value of one of them, and the rest of the computation runs once for each alternative that the merger runs. Each expr is evaluated only when chosen.

Each expr is wrapped in a thunk, and the thunks are collected into a mutable vector, on which current-amb-shuffler is called once.

Examples:
> (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.

Example:
> (for/list ([(i j) (in-amb (amb (values 1 'x) (values 2 'y)))])
    (cons i j))

'((1 . x) (2 . y))

(amb) is the choice among no alternatives, so it fails. It is commonly used to discard the computations that do not satisfy a constraint.

Examples:
> (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
Variants of for and for* in which each iteration of the loop body is an alternative. The body runs where the choice was made, as part of the search: a choice in it is a choice of the same search. The second form of each pair accepts optional Typed Racket type annotations (Typed Interface).

Example:
> (for/list ([x (in-amb (for/amb ([x '(1 2)]) (amb x (- x))))]) x)

'(1 -1 2 -2)

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.

Examples:
> (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.

Examples:
> (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?
A choice among the elements of seq, which are produced as the search goes on. The sequence may be infinite.

Examples:
> (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) → (-> mutable-vector? void?)

(current-amb-shuffler shuffle!) → void?
  shuffle! : (-> mutable-vector? void?)
A parameter that holds a procedure to reorder the alternatives of a choice. It is called once, where the choice is made, on the vector of alternatives of every amb and of every for/amb with #:length; the vector may be empty. It is not called for the alternatives of a sequence. The default is void.

Examples:
> (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
Starts a search of expr and returns its answers as a lazy stream. Nothing of the search runs before the first element is requested, and the stream keeps its elements: reading them again does not run the search again.

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.

Examples:
> (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)

procedure

(in-amb* thk [handler]) → stream?

  thk : (-> any)
  handler : (or/c #f (-> any)) = #f
The procedure form of in-amb: the search of (thk). The pause handler is an optional argument. Like in-amb, in a for clause it expands directly to the single-pass sequence of in-amb*/do, without building a stream.

syntax

(in-amb/do expr maybe-handler)

 
maybe-handler = 
  | #:on-pause handler-expr
Like in-amb, but returns a single-pass sequence instead of a stream, so the answers are not kept. Creating the sequence runs nothing of the search. Iterating over it again continues where the previous iteration stopped, and once it has ended it stays empty.

procedure

(in-amb*/do thk [handler]) → sequence?

  thk : (-> any)
  handler : (or/c #f (-> any)) = #f
The procedure form of in-amb/do.

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)

Equivalent to (amb-local* (λ () expr)).

procedure

(amb-local* thk) → any

  thk : (-> any)
An answer of (thk), found by a search of its own: a local search. The inner mergers decide the order of its events. The local search runs on demand, supplying each answer as an alternative of one choice in the enclosing search. It is the composition of make-amb and amb-generate*:

(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.

Examples:
> (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.