4.3 - Variations on a Scheme — Nondeterministic Computing
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))))
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))
*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.)
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))))))
Write an ordinary Scheme program to solve the multiple dwelling puzzle.
The following is a set of semi-relevant links that came up during the discussion:
- http://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf Continuation, functions and jumps
- http://double.co.nz/pdf/continuations.pdf Web programming with continuations