Racket

amb: Ambiguous Operator🔗ℹ

Noah Ma <noahstorym@gmail.com>

(require amb)

package: amb

(require typed/amb)

package: typed-amb

1 Ambiguous Operator🔗ℹ

syntax
(amb expr ...)

John McCarthy’s ambiguous operator.

The form (amb expr ...) expands to (amb* (λ () expr) ...).

Examples:

> (amb 1 (values 2 3) 4)
1
> (amb)
2
3
> (amb)
4
> (amb)
amb: empty amb tasks;
expected at least one amb task
in: (amb)

Wrapping amb expressions with a new amb sequence is recommended. This ensures that each instance of non-deterministic computation starts with a fresh sequence, avoiding unintended interactions between different amb expressions.

Examples:

> (define make-amb-tasks (current-amb-maker))
> (amb 1 (values 2 3) 4)
1
> (parameterize ([current-amb-tasks (make-amb-tasks)])
    (let ([x (amb 1 2)])
      (displayln (list x))
      (let ([y (amb 3 4)])
        (displayln (list x y))
        (let ([z (amb 5 6)])
          (displayln (list x y z))
          (amb)))))
(1)
(1 3)
(1 3 5)
(1 3 6)
(1 4)
(1 4 5)
(1 4 6)
(2)
(2 3)
(2 3 5)
(2 3 6)
(2 4)
(2 4 5)
(2 4 6)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (amb)
2
3
> (parameterize ([current-amb-tasks (make-amb-tasks)]
                 [current-amb-pusher enqueue!])
    (let ([x (amb 1 2)])
      (displayln (list x))
      (let ([y (amb 3 4)])
        (displayln (list x y))
        (let ([z (amb 5 6)])
          (displayln (list x y z))
          (amb)))))
(1)
(2)
(1 3)
(1 4)
(2 3)
(2 4)
(1 3 5)
(1 3 6)
(1 4 5)
(1 4 6)
(2 3 5)
(2 3 6)
(2 4 5)
(2 4 6)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (amb)
4
> (amb)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)

For most use cases, we recommend using in-amb to construct a stream from ambiguous computations. A good practice is to wrap amb expressions in a procedure, then use in-amb to create a lazy stream that produces as many results as needed.

Examples:

> (define (f n)
    (define m (amb 0 1 2 3 4))
    (unless (> m n) (amb))
    m)
> (for/list ([m (in-amb (f 2))]) m)
'(3 4)

procedure
(amb* alt ...) → any
alt : (-> any)

The backend of amb.

If an alt is the amb* procedure itself, it is skipped, and evaluation proceeds to the next alt.

Examples:

> (define (zero) 0)
> (define (one) 1)
> (current-amb-shuffler displayln)
> (amb* amb* zero amb* one amb*)
#(#<procedure:amb*> #<procedure:zero> #<procedure:amb*> #<procedure:one> #<procedure:amb*>)
0
> (amb)
#()
1
> (amb)
#()
amb: empty amb tasks;
expected at least one amb task
in: (amb)
> (define (amb+) (amb))
> (amb* amb+ zero amb+ one amb+)
#(#<procedure:amb+> #<procedure:zero> #<procedure:amb+> #<procedure:one> #<procedure:amb+>)
#()
0
> (amb)
#()
#()
1
> (amb)
#()
#()
amb: empty amb tasks;
expected at least one amb task
in: (amb)

syntax
(for/amb maybe-length (for-clause ...) break-clause ... body ...+)
(for/amb type-ann-maybe maybe-length (for-clause ...) type-ann-maybe expr ...+)
syntax
(for*/amb maybe-length (for-clause ...) break-clause ... body ...+)
(for*/amb type-ann-maybe maybe-length (for-clause ...) type-ann-maybe expr ...+)

Variants of for that treat each iteration of the loop body as an ambiguous choice.

When the #:length clause is specified, the syntax resembles for/vector and for*/vector. The loop body for each iteration is wrapped in a thunk to create a fixed number of alternatives.

Examples:

> (for/amb #:length 4 ([i #(1 2)] [j #(x y)]) (values i j))
1
'x
> (amb)
2
'y
> (amb)
amb: empty amb tasks;
expected at least one amb task
in: (amb)
> (for/amb #:length 4 #:fill 0 ([i #(1 2)] [j #(x y)]) (values i j))
1
'x
> (amb)
2
'y
> (amb)
0
> (amb)
0
> (amb)
amb: empty amb tasks;
expected at least one amb task
in: (amb)

If the #:length clause is omitted, a choice point is created for each iteration. After the body of one iteration is evaluated, backtracking via (amb) proceeds to the next iteration. This allows for iterating over sequences of any size, including infinite ones.

Examples:

> (for/amb ([i (in-naturals)]) i)
0
> (amb)
1
> (amb)
2
> (amb)
3

2 Prompt Tag🔗ℹ

value
amb-prompt-tag : continuation-prompt-tag?

A continuation prompt tag used by in-amb operations to delimit backtracking.

3 Stream Constructor🔗ℹ

syntax
(in-amb expr)

Constructs a stream from the results of evaluating the ambiguous expression expr, allowing results to be produced lazily.

The form (in-amb expr) expands to (in-amb* (λ () expr)).

Example:

> (for/list ([i (in-amb (amb 1 (amb 2 3) (amb 4 5 6) 7 8))]) i)
'(1 2 3 4 5 6 7 8)

in-amb acts as a one-step lookahead sequence generator. To determine if the sequence continues, it must compute the next valid path.

Examples:

> (for/list ([i (in-amb (begin0 (amb 1 (amb 2 3) 4) (displayln 'data)))] [_ 2]) i)
data
data
data
'(1 2)
> (for/list ([_ 2] [i (in-amb (begin0 (amb 1 (amb 2 3) 4) (displayln 'data)))]) i)
data
data
'(1 2)

The ambiguous computation is executed in the dynamic context where in-amb is called. In particular, dynamic bindings such as those introduced by parameterize are preserved from the stream’s creation site rather than from the site where the stream is consumed.

Examples:

> (define p (make-parameter 0))
> (define s (parameterize ([p 1]) (in-amb (amb 0 (p) 2))))
> (for/list ([i (parameterize ([p 2]) s)]) i)
'(0 1 2)

Internally, in-amb installs the parameters required to run an ambiguous computation, including current-amb-prompt-tag, current-amb-tasks, and current-amb-empty-handler. Other parameters retain the values they had when in-amb was invoked.

Examples:

> (amb 1 2 3)
1
> (for/list ([(i j) (in-amb (amb (values 1 'x) (values 2 'y)))]) (cons i j))
'((1 . x) (2 . y))
> (amb)
2
> (define (rotate-queue! q)
    (when (non-empty-queue? q)
      (enqueue! q (dequeue! q))))
> (parameterize ([current-amb-rotator rotate-queue!])
    (for/list ([i (in-amb (amb (amb 1 2 3) (amb 'a 'b 'c)))]) i))
'(1 a 2 b 3 c)
> (amb)
3
> (amb)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)

procedure
(in-amb* thk) → stream?
thk : (-> any)

The backend of in-amb.

Examples:

> (define (make)
(parameterize ([current-amb-pusher enqueue!])
(let g () (amb 0 1 (cons (g) (g))))))
> (for/list ([x (in-amb* make)] [_ 10]) x)
'(0 1 (0 . 0) (0 . 1) (1 . 0) (1 . 1) (0 0 . 0) (0 0 . 1) (0 1 . 0) (0 1 . 1))

syntax
(in-amb/do expr)

Similar to in-amb, except that a sequence is returned instead of a stream.

procedure
(in-amb*/do thk) → sequence?
thk : (-> any)

The backend of in-amb/do.

4 Exception Type🔗ℹ

struct
(struct exn:fail:contract:amb exn:fail:contract ()
#:extra-constructor-name make-exn:fail:contract:amb
#:transparent)

Raised when evaluating (amb) with an empty amb sequence.

Examples:

> (amb)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (amb*)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (for/amb ([i '()]) i)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (for*/amb ([i '()]) i)
amb: empty amb tasks;
expected at least one amb task
  in: (amb)

procedure
(raise-amb-error) → none/c

Creates an exn:fail:contract:amb value and raises it as an exception.

Example:

> (raise-amb-error)
amb: empty amb tasks;
expected at least one amb task
in: (amb)

5 Parameter🔗ℹ

The behavior of the amb search engine can be customized through a set of parameters. These parameters control how amb tasks are stored, scheduled, and executed, as well as the continuation prompt used to delimit ambiguous computations.

parameter
(current-amb-prompt-tag) → continuation-prompt-tag?
(current-amb-prompt-tag prompt-tag) → void?
prompt-tag : continuation-prompt-tag?

A parameter that specifies the continuation prompt tag used to delimit ambiguous computations. The default value is (default-continuation-prompt-tag).

parameter
(current-amb-empty-handler) → (-> none/c)
(current-amb-empty-handler empty-handler) → void?
empty-handler : (-> none/c)

A parameter that specifies the procedure to be called when the amb sequence is empty and (amb) is evaluated. The default value is raise-amb-error.

parameter
(current-amb-shuffler) → (-> mutable-vector? void?)
(current-amb-shuffler shuffle!) → void?
shuffle! : (-> mutable-vector? void?)

A parameter that specifies how to shuffle alternatives before scheduling new amb tasks into the current amb sequence. The default value is void.

parameter
(current-amb-rotator) → (-> sequence? void?)
(current-amb-rotator rotate!) → void?
rotate! : (-> sequence? void?)

A parameter that specifies how to rotate amb tasks before running an alternative. The default value is void.

parameter
(current-amb-maker) → (-> sequence?)
(current-amb-maker make) → void?
make : (-> sequence?)

A parameter that specifies the method for creating a new amb sequence. This allows users to define the data structure used to store amb tasks. The default value is make-queue.

parameter
(current-amb-tasks) → sequence?
(current-amb-tasks tasks) → void?
tasks : sequence?

A parameter that holds the sequence of amb tasks to be evaluated. Each amb task is a continuation created by current-continuation. The default value is (make-queue).

parameter
(current-amb-length)
→ (-> sequence? exact-nonnegative-integer?)
(current-amb-length length) → void?
length : (-> sequence? exact-nonnegative-integer?)

A parameter that specifies the method for retrieving the number of amb tasks in the current amb sequence. The default value is queue-length.

parameter
(current-amb-pusher) → (-> sequence? continuation? void?)
(current-amb-pusher push!) → void?
push! : (-> sequence? continuation? void?)

A parameter that defines the method for pushing an amb task into the current amb sequence. The default value is enqueue-front!.

parameter
(current-amb-popper) → (-> sequence? continuation?)
(current-amb-popper pop!) → void?
pop! : (-> sequence? continuation?)

A parameter that defines the method for popping an amb task from the current amb sequence. The default value is dequeue!.

1	Ambiguous Operator
2	Prompt Tag
3	Stream Constructor
4	Exception Type
5	Parameter