Chapter 4, Metalinguistic Abstraction
Exercise 4.35
Since, amb-evaluator is implemented later(as always in sicp), I first read the complete section.
I do like this approach of top down presentation of the concepts in SICP. It helps in designing systems from the perspective of how they will be used. Also, I feel it also helps in building abstractions. However, I generally get more confident of my understanding by reading till the bottom.
To do these exercises, we have to use the amb-evaluator. Thus I am using the mit scheme code for sicp from here.
Since this is a very different style of programming, Let me mention that as per my understanding the most fundemental change, which I had missed initially, is the following:
Every expression in the new evaluator can evaluate to many results, one at a time.
After running the evaluator, I evaluated the following code:
1
2
3
4
5
6
7
8
9
10
11
12
13
(define (require p)
(if (not p) (amb)))
(define (an-integer-between low high)
(require (> high low))
(amb (+ low 1) (an-integer-between (+ low 1) high)))
(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)))))
Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
;;; Amb-Eval input:
(a-pythagorean-triple-between 0 100)
;;; Starting a new problem
;;; Amb-Eval value:
(3 4 5)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(5 12 13)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(6 8 10)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(7 24 25)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 15 17)