Chapter 4, Metalinguistic Abstraction

Exercise 4.73


For infinite streams, flatten-stream goes into infinite recursion without printing anything!

There’s a subtle difference between this infinite streams and in ex-4.71. When we combine the stream of streams using flatten-stream, then it might be the case we have infinite stream of finite(or infinite) streams. For such infinite stream of streams, we should be delaying else recursion with scheme’s applicative order evaluation will cause it to keep computing the infinite stream of streams!

It took me some time to come up with an example to demonstrate the situation for infinite stream of infinite stream. The example turned out to be quite simple.

Using the same rules which i used in ex-4.72:

1
2
3
4
5
(assert! (ones ()))
(assert! (rule (ones (1 . ?x)) (ones ?x)))

(assert! (twos ()))
(assert! (rule (twos (2 . ?x)) (twos ?x)))

Unlike the previous exercise, now i used and query instead of or query:

1
(and (ones ?x) (twos ?y))

Why and?

Because and passes the stream of resulting frames from each clause to the next clause! or does not do so. So, if first clause can generate infinite frames, then we can produce the context required to demonstrate flatten-stream getting infinite stream of stream!

With the change suggested in book:

1
2
3
4
5
;;; Query input:
(and (ones ?x) (twos ?y))

;;; Query results:
;Aborting!: maximum recursion depth exceeded

With the original version

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
;;; Query input:

(and (ones ?x) (twos ?y))

;;; Query results:
(and (ones ()) (twos ()))
(and (ones (1)) (twos ()))
(and (ones ()) (twos (2)))
(and (ones (1 1)) (twos ()))
(and (ones ()) (twos (2 2)))
(and (ones (1)) (twos (2)))
(and (ones ()) (twos (2 2 2)))
(and (ones (1 1 1)) (twos ()))
(and (ones ()) (twos (2 2 2 2)))
(and (ones (1)) (twos (2 2)))
(and (ones ()) (twos (2 2 2 2 2)))
(and (ones (1 1)) (twos (2)))
(and (ones ()) (twos (2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2)))
(and (ones (1 1 1 1)) (twos ()))
(and (ones ()) (twos (2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2)))
(and (ones (1 1)) (twos (2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1 1)) (twos (2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1)) (twos (2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1 1 1 1)) (twos ()))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1)) (twos (2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1 1)) (twos (2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1)) (twos (2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1 1 1)) (twos (2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1)) (twos (2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1 1 1)) (twos (2 2 2)))
(and (ones ()) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
(and (ones (1)) (twos (2 2 2 2 2 2 2 2 2 2 2 2 2 2)))
....