From cd57e7c557d01f9d74e6849c6988b61d827d182a Mon Sep 17 00:00:00 2001 From: bnewbold Date: Mon, 20 Apr 2009 19:41:39 -0400 Subject: ps08 done --- ps08_conspiracies/bnewbold_ps08.txt | 59 +++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100644 ps08_conspiracies/bnewbold_ps08.txt (limited to 'ps08_conspiracies/bnewbold_ps08.txt') diff --git a/ps08_conspiracies/bnewbold_ps08.txt b/ps08_conspiracies/bnewbold_ps08.txt new file mode 100644 index 0000000..5a7c174 --- /dev/null +++ b/ps08_conspiracies/bnewbold_ps08.txt @@ -0,0 +1,59 @@ +;;; 6.945 Problem Set #8 Comments +;;; 04/18/2009 +;;; Bryan Newbold + +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] -- cgit v1.2.3