blob: 5a7c174cc070cf0584485d0abd60c5f4d5a5b777 (
plain)
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
|
;;; 6.945 Problem Set #8 Comments
;;; 04/18/2009
;;; Bryan Newbold <bnewbold@mit.edu>
Problem 8.1:
--------------------------------
The algorithm is of O(n^2) in the number of list elements including empty lists
and and the implicit empty list which terminates every list. The total number
of elements is thus larger than the resulting fringe by a factor of the depth
(plus whatever extra non-implicit empty lists).
Problem 8.2:
--------------------------------
A)
If it wasn't thunk-ified, the expression (lazy-fringe (cdr subtree)) passed as
a parameter to stream-append would be recursively evaluated when first passed;
delaying this evaluation is the entire point. The way to go forward with
stream-append would be to turn the reference to (cdr subtree) into a lazy
stream itself; thunkifying does effectively the same thing.
B)
[see code in bnewbold_ps08_work.scm]
Problem 8.3:
--------------------------------
The side effects from use of set! ruin any lambda-calculus rules. Here the
lambda wrapper preserves the context of resume-thunk; the procedure associated
with resume-thunk can get set! to something new, but the version wrapped up in
a lambda and returned will be the original procedure defined a couple
expressions earlier.
Problem 8.4:
--------------------------------
Running with pretty print gives the following output:
(a a)
(b b)
(c c)
(d d)
(e e)
(f f)
(g g)
(h h)
((*done*) a)
;Value: #f
Without passing *done* to return, *done* thunks through out of all the built
up continuations, dragging the evaluation context back to the point when it
was acs-coroutine-fringe-generator was first defined. This causes f2 to be
redefined starting at the begining of the tree ('a) so that the two
coroutines never return *done* together.
Problem 8.5:
--------------------------------
[see code in bnewbold_ps08_work.scm]
Problem 8.6:
--------------------------------
[see code in bnewbold_ps08_work.scm]
|
