Prev Up Next

An accessible description of amb and many example uses are found in the premier Scheme textbook SICP. Informally, amb takes zero or more expressions and nondeterministically returns the value of one of them. Thus,

(amb 1 2)

may evaluate to 1 or 2.

amb called with no expressions has no value to return, and is considered to fail. Thus,

(amb)
-->ERROR!!! amb tree exhausted

(We will examine the wording of the error message later.)

In particular, amb is required to return a value if at least one its subexpressions converges, ie, doesn't fail. Thus,

(amb 1 (amb))

and

(amb (amb) 1)

both return 1.

Clearly, amb cannot simply be equated to its first subexpression, since it has to return a non-failing value, if this is at all possible. However, this is not all: The bias for convergence is more stringent than a merely local choice of amb's subexpressions. amb should furthermore return that convergent value that makes the entire program converge. In denotational parlance, amb is an angelic operator.

For example,

(amb #t #f)

may return either #t or #f, but in the program

(if (amb #t #f)
    1
    (amb))

the first amb-expression must return #t. If it returned #f, the if's ``else'' branch would be chosen, which causes the entire program to fail.

Prev Up Next

Log in or register to write something here or to contact authors.