amb: Ambiguous Operator

8.16.0.1

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

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:

> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (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)
> (parameterize ([current-amb-shuffler void]
                 [current-amb-tasks    ((current-amb-maker))]
                 [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)

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

The backend of 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 ...+)

The syntax of for/amb and for*/amb resembles that of for/vector and for*/vector, but instead of evaluating the loop body, they wrap each iteration as a thunk to create alternatives.

Examples:

> (parameterize ([current-amb-shuffler void]
                 [current-amb-tasks    ((current-amb-maker))]
                 [current-amb-pusher   enqueue!])
    (define x (let next ([i 0]) (amb (next (add1 i)) i)))
    (define y (for/amb #:length 3 ([i 3]) i))
    (unless (< x 2) (amb))
    (displayln (cons x y))
    (unless (= (+ x y) 3) (amb)))
(0 . 0)
(0 . 1)
(0 . 2)
(1 . 0)
(1 . 1)
(1 . 2)
> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (define-values (x y)
      (for/amb ([v '([2 . 9] [9 . 2])])
        (values (car v) (cdr v))))
    (unless (> x y) (amb))
    (displayln (cons x y)))
(9 . 2)
> (let/cc break
    (parameterize ([current-amb-tasks ((current-amb-maker))]
                   [current-amb-empty-handler break])
      (define-values (x y)
        (for*/amb #:length 3 #:fill (values -1 -1) ([i 3] [j 3])
          (values i j)))
      (unless (> x y) (amb))
      (displayln (cons x y))
      (amb)))
> (let/cc k
    (define a* '())
    (define b* '())
    (define (return) (k a* (list->bytes b*)))
    (parameterize ([current-amb-tasks ((current-amb-maker))]
                   [current-amb-empty-handler return])
      (define x (for/amb ([i 10]) i))
      (when (even? x)
        (set! a* (cons x a*))
        (set! b* (cons (+ x 48) b*)))
      (amb)))
'(8 6 4 2 0)
#"86420"

2 Stream Constructor🔗ℹ

syntax
(in-amb expr)

Constructs a stream from the results of evaluating the ambiguous expression expr, allowing for lazy evaluation of results.

The in-amb form automatically creates a new amb sequence and records all relevant parameters at the time expr is evaluated, so there is no need to worry about affecting calls to other amb expressions.

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

Example:

> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (define (next i j) (amb (values i j) (next (add1 i) (sub1 j))))
    (amb 1 2 3)
    (displayln (= 2 ((current-amb-length) (current-amb-tasks))))
    (time
     (displayln
      (for/and ([i (in-range 1000000)]
                [(j k) (in-amb (next 0 0))])
        (= i j (- k)))))
    (displayln (= 2 ((current-amb-length) (current-amb-tasks)))))
#t
#t
cpu time: 2450 real time: 2451 gc time: 79
#t

A good practice is to wrap amb expressions in a procedure, then use in-amb or 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 ([m (in-amb (f 2))])
    (displayln m))
3
4

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

The backend of in-amb.

Examples:

> (define (thk)
    (define x (for/amb ([i 10]) i))
    (unless (even? x) (amb))
    x)
> (for/list ([x (in-amb* thk)]) x)
'(0 2 4 6 8)

3 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:

> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (amb))
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (amb*))
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (for/amb ([i '()]) i))
amb: empty amb tasks;
expected at least one amb task
  in: (amb)
> (parameterize ([current-amb-tasks ((current-amb-maker))])
    (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)

4 Parameter🔗ℹ

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 vector-reverse!.

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 thunk that, when invoked, uses call-in-continuation to call an alternative. 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? (-> none/c) void?)
(current-amb-pusher push!) → void?
push! : (-> sequence? (-> none/c) 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? (-> none/c))
(current-amb-popper pop!) → void?
pop! : (-> sequence? (-> none/c))

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	Stream Constructor
3	Exception Type
4	Parameter