To extend Scheme JavaScript to support nondeterminism, we introduce a new special form syntactic form called amb.[1] The expression (amb $e_1\ e_2\ldots e_n$) amb($e_1,\ e_2,\ldots, e_n$) returns the value of one of the $n$ expressions $e_i$ ambiguously. For example, the expression

Original	JavaScript
(list (amb 1 2 3) (amb 'a 'b))	list(amb(1, 2, 3), amb("a", "b"));

can have six possible values:

Original	JavaScript
(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)	list(1, "a") list(1, "b") list(2, "a") list(2, "b") list(3, "a") list(3, "b")

Amb An amb expression with a single choice produces an ordinary (single) value.

Amb An amb expression with no choices—the expression (amb)—is amb()—is an expression with no acceptable values. Operationally, we can think of (amb) amb() as an expression that when evaluated causes the computation to fail: The computation aborts and no value is produced. Using this idea, we can express the requirement that a particular predicate expression p must be true as follows:

Original	JavaScript
(define (require p) (if (not p) (amb)))	function require(p) { if (! p) { amb(); } else {} }

With amb and require, we can implement the an-element-of procedure an_element_of function used above:

Original	JavaScript
(define (an-element-of items) (require (not (null? items))) (amb (car items) (an-element-of (cdr items))))	function an_element_of(items) { require(! is_null(items)); return amb(head(items), an_element_of(tail(items))); }

An-element-of An application of an_element_of fails if the list is empty. Otherwise it ambiguously returns either the first element of the list or an element chosen from the rest of the list.

We can also express infinite ranges of choices. The following procedure function potentially returns any integer greater than or equal to some given $n$:

Original	JavaScript
(define (an-integer-starting-from n) (amb n (an-integer-starting-from (+ n 1))))	function an_integer_starting_from(n) { return amb(n, an_integer_starting_from(n + 1)); }

This is like the stream procedure integers-starting-from function integers_starting_from described in section 3.5.2, but with an important difference: The stream procedure function returns an object that represents the sequence of all integers beginning with $n$, whereas the amb procedure function returns a single integer.[2]

Abstractly, we can imagine that evaluating an amb expression causes time to split into branches, where the computation continues on each branch with one of the possible values of the expression. We say that amb represents a nondeterministic choice point. If we had a machine with a sufficient number of processors that could be dynamically allocated, we could implement the search in a straightforward way. Execution would proceed as in a sequential machine, until an amb expression is encountered. At this point, more processors would be allocated and initialized to continue all of the parallel executions implied by the choice. Each processor would proceed sequentially as if it were the only choice, until it either terminates by encountering a failure, or it further subdivides, or it finishes.[3]

On the other hand, if we have a machine that can execute only one process (or a few concurrent processes), we must consider the alternatives sequentially. One could imagine modifying an evaluator to pick at random a branch to follow whenever it encounters a choice point. Random choice, however, can easily lead to failing values. We might try running the evaluator over and over, making random choices and hoping to find a non-failing value, but it is better to systematically search all possible execution paths. The amb evaluator that we will develop and work with in this section implements a systematic search as follows: When the evaluator encounters an application of amb, it initially selects the first alternative. This selection may itself lead to a further choice. The evaluator will always initially choose the first alternative at each choice point. If a choice results in a failure, then the evaluator automagically[4] backtracks to the most recent choice point and tries the next alternative. If it runs out of alternatives at any choice point, the evaluator will back up to the previous choice point and resume from there. This process leads to a search strategy known as depth-first search or chronological backtracking.[5]

Driver loop

The driver loop for the amb evaluator has some unusual properties. It reads an expression a program and prints the value of the first non-failing execution, as in the prime-sum-pair prime_sum_pair example shown above. If we want to see the value of the next successful execution, we can ask the interpreter to backtrack and attempt to generate a second non-failing execution.

Original		JavaScript
This is signaled by typing the symbol try-again. If any expression except try-again is given, the interpreter will start a new problem, discarding the unexplored alternatives in the previous problem.		This is signaled by typing retry. If any other input except retry is given, the interpreter will start a new problem, discarding the unexplored alternatives in the previous problem.

Here is a sample interaction:

Original	JavaScript
;;; Amb-Eval input: (prime-sum-pair '(1 3 5 8) '(20 35 110)) ;;; Starting a new problem ;;; Amb-Eval value: (3 20)	amb-evaluate input: prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110)); Starting a new problem amb-evaluate value: [3, [20, null]]

Original	JavaScript
;;; Amb-Eval input: try-again ;;; Amb-Eval value: (3 110)	amb-evaluate input: retry amb-evaluate value: [3, [110, null]]

Original	JavaScript
;;; Amb-Eval input: try-again ;;; Amb-Eval value: (8 35) ;;; Amb-Eval input:	amb-evaluate input: retry amb-evaluate value: [8, [35, null]]

Original	JavaScript
try-again ;;; There are no more values of (prime-sum-pair (quote (1 3 5 8)) (quote (20 35 110)))	amb-evaluate input: retry There are no more values of prime_sum_pair([1, [3, [5, [8, null]]]], [20, [35, [110, null]]])

Original	JavaScript
;;; Amb-Eval input: (prime-sum-pair '(19 27 30) '(11 36 58)) ;;; Starting a new problem ;;; Amb-Eval value: (30 11)	amb-evaluate input: prime_sum_pair(list(19, 27, 30), list(11, 36, 58)); Starting a new problem amb-evaluate value: [30, [11, null]]

Exercise 4.44 Write a procedure an-integer-between function an_integer_between that returns an integer between two given bounds. This can be used to implement a procedure function that finds Pythagorean triples, i.e., triples of integers $(i,j,k)$ between the given bounds such that $i \leq j$ and $i^2 + j^2 =k^2$, as follows:

Original	JavaScript
(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high))) (let ((j (an-integer-between i high))) (let ((k (an-integer-between j high))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k)))))	function a_pythogorean_triple_between(low, high) { const i = an_integer_between(low, high); const j = an_integer_between(i, high); const k = an_integer_between(j, high); require(i * i + j * j === k * k); return list(i, j, k); }

Solution

// solution by GitHub user jonathantorres function an_integer_between(low, high) { require(low <= high); return amb(low, an_integer_between(low+1, high)); }

Exercise 4.45 Exercise 3.72 discussed how to generate the stream of all Pythagorean triples, with no upper bound on the size of the integers to be searched. Explain why simply replacing an-integer-between an_integer_between by an-integer-starting-from an_integer_starting_from in the procedure function in exercise 4.44 is not an adequate way to generate arbitrary Pythagorean triples. Write a procedure function that actually will accomplish this. (That is, write a procedure function for which repeatedly typing try-again retry would in principle eventually generate all Pythagorean triples.)

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.46 Ben Bitdiddle claims that the following method for generating Pythagorean triples is more efficient than the one in exercise 4.44. Is he correct? (Hint: Consider the number of possibilities that must be explored.)

Original	JavaScript
(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high)) (hsq (* high high))) (let ((j (an-integer-between i high))) (let ((ksq (+ (* i i) (* j j)))) (require (>= hsq ksq)) (let ((k (sqrt ksq))) (require (integer? k)) (list i j k))))))	function a_pythagorean_triple_between(low, high) { const i = an_integer_between(low, high); const hsq = high * high; const j = an_integer_between(i, high); const ksq = i * i + j * j; require(hsq >= ksq); const k = math_sqrt(ksq); require(is_integer(k)); return list(i, j, k); }

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.