Exercise 4.36.  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 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.)

————————————————————————————————————————————————————————————————————————

Simply using an-integer-starting-from will fail because only triples of 
the form (low, low+1, _) will ever be tested, since there are an 
infinite number of such triples to try.

Instead we can generate all triples i < j < k in such a way that any 
given triple will eventually be reached.

Similarly to the stream example, the trick is to ensure that the last 
choice point introduced by amb will be one which will choose from the 
available infinite streams of options in a round-robin fashion.  At any 
point at which two infinite sequences of choices must be joined, we must 
introduce an additional amb call to alternate between them.

We define an ambiguous function (any-increasing-triple-from low) which 
generates all possible triples (i,j,k) above some lower bound low such 
that low ≤ i < j < k.

This set can be divided into two infinite subsets, those with i = low 
and those with i > low.

The latter set is then equal to (any-increasing-triple-from (+ low 1)).

The former subset includes (cons low increasing-pair), for any pair 
(j,k) where low < j < k.

A separate function generates these pairs.

We could almost write this as follows:

(define (any-increasing-triple-from low)
  (let ((any-in-this-plane (cons low (any-increasing-pair-from (+ low 1)))))
    (let ((any-not-in-this-plane (any-increasing-triple-from (+ low 1))))
      (amb any-in-this-plane any-not-in-this-plane))))

(define (any-increasing-pair-from low)
  (let ((any-in-this-row (list low (an-integer-starting-from (+ low 1)))))
    (let ((any-not-in-this-row (any-increasing-pair-from (+ low 1))))
      (amb any-in-this-row any-not-in-this-row))))

However, assuming the interpreter is strict, 
(any-increasing-triple-from 1) will not terminate, since it will call 
(any-increasing-triple-from 2) before returning a value, and each 
call will generate a new call to any-increasing-triple-from.

If the interpreter is lazy, this will terminate, but will not produce 
all triples, as the calls to amb will come in the wrong order, and only 
the triples (1 2 _) will be produced.

This is similar to the problem Louis Reasoner had in Chapter 3 combining 
infinite streams, and can be solved in the same way.

(define (any-increasing-triple-from low)
  (define (a-pair j)
    ; we want only pairs having j+1 < k, since the j+1 = k case is handled explicitly
    (list j (an-integer-starting-from (+ j 2))))
  (amb (list low (+ low 1) (+ low 2))
       (let ((in-this-plane (cons low (a-pair (+ low 1)))))
         (let ((higher-plane (any-increasing-triple-from (+ low 1))))
           (amb in-this-plane higher-plane)))))

(define all-pythagorean-triples
  (let ((triple (any-increasing-triple-from 1)))
    (require (= (+ (square (car triple)) (square (cadr triple)))
                (square (caddr triple))))
    triple))

If there was a way to control the generation of values and the ordering 
of choice points separately, then the more direct solution could be made 
to work, perhaps using some kind of annotations on amb to influence the 
order in which choice points are returned to.

(define (any-increasing-triple-from low)
  ; introduce a layer of laziness using procedures
  (define this-plane (lambda () (amb-level 1) (cons low (any-increasing-pair-from (+ low 1)))))
  (define other-plane (lambda () (amb-level 1) (any-increasing-triple-from (+ low 1))))
  (amb-level 2)
  (amb (this-plane) (other-plane)))

In this case (amb-level) is taken to set the 'level' at which choice 
points are created.  Rather than simply backtracking chronologically, 
the interpreter for this language will backtrack to the choice point at 
the highest level first.

The first run of (any-increasing-triple-from 1) will first make a 
level-2 choice to evaluate this-plane instead of other-plane.  The 
evaluation of this-plane first sets the level to 1, which affects the 
choice points generated by (any-increasing-pair-from).

On the next try, the level-2 choice point will be switched first even 
though it came chronologically earlier, and (other-plane) will be 
entered.  On the third try, the interpreter will need to go back to 
the first choice at level 2, since this branch was not yet exhausted. 
Essentially the interpreter here does the interleaving for us.

Unlike the simpler chronological backtracking, this requires the choices 
made at level 1 in any-increasing-pair-from to be stored even while the 
level 2 amb is on a new branch, to avoid trying the same possibilities 
repeatedly.

--

As discussed in the meeting, the above solution does not quite work, and 
there is a more elegant solution as aamar showed.