4.3 - Variations on a Scheme — Nondeterministic Computing

Amb and Search

The new special form `amb` returns the value of one of the expressions passed to it "ambiguously".

```(define (require p)
(if (not p) (amb)))

(define (an-element-of items)
(require (not (null? items)))
(amb (car items) (an-element-of (cdr items))))

(define (an-integer-starting-from n)
(amb n (an-integer-starting-from (+ n 1))))
```

Exercise 4.35

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

```(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)))))
```

```(define (an-integer-between low high)
(let ((i (an-integer-starting-from (+ low 1))))
(require (< i high))
i))
```

Exercise 4.36

*Note Exercise 3-69:: 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' by `an-integer-starting-from' in the procedure in *Note Exercise 4-35:: is not an adequate way to generate arbitrary Pythagorean triples. Write a procedure that actually will accomplish this. (That is, write a procedure for which repeatedly typing `try-again' would in principle eventually generate all Pythagorean triples.)

Exercise 4.37

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

```(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))))))
```

Examples of Nondeterministic Programs

Exercise 4.41

Write an ordinary Scheme program to solve the multiple dwelling puzzle.

Nope.