X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=004f8dfb22ebb43233c2b15c038ad4a98a081494;hp=c8ff72c686f81d16d6147bd1fe78787631ff4de6;hb=a1a38a5cfaede25b7e6299cac3275e1ccfd9b2db;hpb=e98de4be4fb298c4d0cc27b5c2956c880d3649a5 diff --git a/assignment10.mdwn b/assignment10.mdwn index c8ff72c6..004f8dfb 100644 --- a/assignment10.mdwn +++ b/assignment10.mdwn @@ -1,3 +1,20 @@ +***Non-required but strongly suggested work***: Here are some +additional homework problems that will consolidate your understanding +of what we've covered in the last weeks of the seminar. Those who are +taking the class for credit: since we're so late to post these, and +they add up to a substantial chunk of thinking, we won't officially +require you to do them, since we don't want to get into a bureaucratic +bind if you've planned your next month in a way that would not permit +you to get the work done. But ***we strongly encourage*** you to work on +the problem set: solving these problems will produce a qualitatively +deeper understanding of continuations. If you plan to do some or all +of these problems, and would like us to take them into account in our +evaluation of your work for the course, please let us know when to +expect to see them. (Up to the start of next term, which begins on 24 +January 2011, would be viable.) + +Of course, if you need help or want us to review your efforts, we'll be glad to discuss with you at any later point as well. + 1. This problem is taken from _The Craft of Functional Programming_ by Simon Thompson, Addison-Wesley 1999 : @@ -9,6 +26,27 @@ > it with. + As Ken Shan points out, this is an instance of the algorithm + for converting name/year citations (like 'see Montague 1970') + to numerals corresponding to their position in the + bibliography ('see [24]'). Except that bibliographic numerals + don't start with zero. + + Give some thought to efficiency: there are straightforward + solutions that involve traversing the tree once (in order to, + say, construct a suitable mapping from leafs to ints), then + traversing it again to do the conversion. Can you find a + solution that traverses the tree exactly once, replacing each + leaf as soon as you see it? + + Consider a variation in which you must replace each leaf with + its number of occurrences in the tree. Is there any way to do + that with a single traversal? + + You can assume that the tree is binary, leaf-labeled (no + labels on the internal nodes), and that the leafs are, say, + chars. + Here is [a hint](/hints/assignment_10_hint). @@ -54,11 +92,11 @@ Now, go back to the GS&V assignment from [[assignment7]]. Does the monad you've now crafted enable you to code your implementation of that semantics more elegantly? You can begin by using a composite store of the same sort we used in the hints: a pair of an assignment function `r` and some `h` that associates pegs with entities. -Is the `h` really essential to your solution? Or could you do everything with a store consisting of a single mapping from variables to entities? (You'd still be working with a State monad, but without the pegs.) Explain why or why not. + Are the pegs and the `h` really essential to your solution? Or could you do everything with a store consisting of a single mapping from variables to entities? (You'd still be working with a State monad, but without the pegs.) Explain why or why not. 4. The next two exercises were taken from _The Little Schemer_ Chapter 8. - Suppose `lst` is a list of Scheme symbols (`'symbols 'are 'things 'written 'like 'this`; a list of them is `'(written like this)`). And that the behavior of `(remove 'sym lst)` is to remove every occurrence of `'sym` from `lst`. + Suppose `lst` is a list of Scheme symbols (`'symbols 'are 'things 'written 'like 'this`; a list of them is `'(written like this)`). And suppose that the behavior of `(remove 'sym lst)` is to remove every occurrence of `'sym` from `lst`. Now we define a function `remove-co` which has the following behavior. It accepts as arguments a symbol, a list, and a handler `k` (I wonder why we named it that). `remove-co` calls `k` with two arguments: first, a list of all the symbols in `lst` that aren't equal to `'sym`, and second, a list of all the symbols in `lst` that are equal to `'sym` (the handler might want to, for example, see what the length of the latter list is). @@ -93,7 +131,19 @@ Is the `h` really essential to your solution? Or could you do everything with a (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) ________)))))) -6. Go back to the "abSd" problem we presented in [[From List Zippers to Continuations]]. Consider the "tc" solution which uses explicitly passed continuations. Try to reimplement this using reset and shift instead of having an explicit `k` argument. This will likely be challenging but rewarding. The notes on [[CPS and Continuation Operators]], especially the examples at the end, should be helpful. We are of course also glad to help you out. +6. Go back to the "abSd" problem we presented in [[From List Zippers to Continuations]]. Consider the "tc" solution which uses +explicitly passed continuations. Try to reimplement this using reset +and shift instead of having an explicit `k` argument. This will likely +be challenging but rewarding. The notes on [[CPS and Continuation Operators]], especially the examples at the end, should be helpful. We +are of course also glad to help you out. + + Consider adding a special symbol `'#'` (pronounced 'prompt') to the + mini-language such that + + `"ab#cdSef"` ~~> `"abcdcdef"` + + That is, the rule for `'S'` is to copy the preceding string, but + only up to the closest enclosing `'#'` symbol. 7. Can you reimplement your solution to [[assignment9]] using reset and shift?