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