4.36 Exercise 4.36

Consider the proposed procedure for generating all Pythagorean triples:

(define (pythagorean-triples)

(let ((i (an-integer-starting-from 1))

(j (an-integer-starting-from i))

(k (an-integer-starting-from j)))

(require (= (+ (* i i) (* j j)) (* k k)))

(list i j k)))

Using an-integer-starting-from in place of an-integer-between in the given procedure for computing Pythagorean triples would not suffice because, like with the infinite streams seen earlier, we would only be able to produce Pythagorean triples starting from a fixed i and j. This is because an-integer-starting-from produces an infinite number of values, and our backtracking will always have us try again with the next value of k. Like before, we need to interleave these values.

However, the kind of interleaving we did in the streams chapter isn’t going to work here, because the only decision we can revisit is the last one we’ve made. We need to constrain the inner loops while allowing the outer loop to generate toward infinity.

Another way of thinking about this is that we need to find a global ordering for all Pythagorean triples that is parametized on a single value. A natural choice for this is the value of k – by definition, we know that the values of i and j have to be integers between 1 and k, and we can generate them sequentially as in the correct procedure for generating bounded Pythagorean triples. Since the nondeterministic expressions generating i and j values are guaranteed to fail, we know that all possible values of k will eventually be considered, and that all Pythagorean triples will eventually be found.

(define (pythagorean-triples)

(let ((k (an-integer-starting-from 1)))

(let ((i (an-integer-between 1 k)))

(let ((j (an-integer-between i k)))

(require (= (+ (* i i) (* j j)) (* k k)))

(list i j k)))))