added jsMath files
[lambda.git] / assignment10.mdwn
1 ***Non-required but strongly suggested work***: Here are some
2 additional homework problems that will consolidate your understanding
3 of what we've covered in the last weeks of the seminar. Those who are
4 taking the class for credit: since we're so late to post these, and
5 they add up to a substantial chunk of thinking, we won't officially
6 require you to do them, since we don't want to get into a bureaucratic
7 bind if you've planned your next month in a way that would not permit
8 you to get the work done.  But ***we strongly encourage*** you to work on
9 the problem set: solving these problems will produce a qualitatively
10 deeper understanding of continuations.  If you plan to do some or all
11 of these problems, and would like us to take them into account in our
12 evaluation of your work for the course, please let us know when to
13 expect to see them.  (Up to the start of next term, which begins on 24
14 January 2011, would be viable.)
15
16 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.
17
18
19 1.      This problem is taken from _The Craft of Functional Programming_ by Simon Thompson, Addison-Wesley 1999 <http://www.cs.kent.ac.uk/people/staff/sjt/>:
20
21         >       Given an arbitrary tree, transform it to a
22         >       tree of integers in which the original elements are replaced by
23         >       natural numbers, starting from 0.  The same element has to be
24         >       replaced by the same number at every occurrence, and when we meet
25         >       an as-yet-unvisited element we have to find a "new" number to match
26         >       it with.
27
28
29         As Ken Shan points out, this is an instance of the algorithm
30         for converting name/year citations (like 'see Montague 1970')
31         to numerals corresponding to their position in the
32         bibliography ('see [24]').  Except that bibliographic numerals
33         don't start with zero.
34
35         Give some thought to efficiency: there are straightforward
36         solutions that involve traversing the tree once (in order to,
37         say, construct a suitable mapping from leafs to ints), then
38         traversing it again to do the conversion.  Can you find a
39         solution that traverses the tree exactly once, replacing each
40         leaf as soon as you see it?
41
42         You can assume that the tree is binary, leaf-labeled (no
43         labels on the internal nodes), and that the leafs are, say,
44         chars.
45
46         Here is [a hint](/hints/assignment_10_hint_1).
47
48         Consider a variation in which you must replace each leaf with
49         its number of occurrences in the tree.  Is there any way to do
50         that with a single traversal? (Here is [a hint](/hints/assignment_10_hint_2).)
51
52
53
54 2.      Armed with your solution to problem 1, try this: you have as input a leaf-labeled, binary tree whose labels are strings. You also have as input an interpretation function from strings to meanings. Let the meanings of your strings be primitive elements, for instance:
55
56                 type meaning = John | Bill | Sally | Zachariah | Swam | Likes | ...
57
58         If you want to get fancy and have different strings be interpreted to meanings of different types, go ahead. But that won't be essential to this problem. What is essential is that sometimes different strings might map onto the same meaning. For instance, both `"John"` and `"Hannes"` might map to `John`.
59
60         Your task is to return a tree with the same structure as the original tree, but with all string labels replaced with a pair of a meaning and an int. The meaning should be the meaning your interpretation function assigns to the string. Two leaves that get the same meaning should get the same int as well iff the leaves originally were labelled with the same string. So if `"John"` is replaced with `(John, 1)`, then `"Hannes"` should be replaced with `(John, j)` where `j` is an `int` other than `1`. We don't care whether you ever use the same `int`s for leafs with different associated meanings.
61
62         If you solve this, congratulations! You're most of the way to implementing a hyper-evaluative semantics, of the sort Jim discussed around Week 10.
63
64 3.      Our notes on [[monad transformers]] give you most of the pieces you need to implement a StateT monad transformer. The only crucial piece that's missing is a definition for StateT's `elevate` function. Here are the earlier pieces repeated, together with that missing piece:
65
66                 type 'a stateT(M) =
67                   store -> ('a * store) M;;
68                 
69                 let unit (a : 'a) : 'a stateT(M) =
70                   fun s -> M.unit (a, s);;
71                   (* can in general be defined as `fun a -> elevate (M.unit a)` *)
72                 
73                 let bind (u : 'a stateT(M)) (f : 'a -> 'b stateT(M)) : 'b stateT(M) =
74                   fun s -> M.bind (u s) (fun (a, s') -> f a s');;
75                 
76                 let elevate (m : 'a M) : 'a stateT(M) =
77                   fun s -> M.bind w (fun a -> M.unit (a, s));;
78
79         That won't compile in OCaml because we use the `M`s in a way that's intuitive but unrecognized by OCaml. What OCaml will recognize is more complex. Don't worry; you won't need to code a general implementation of StateT.
80
81         What we do want you to do is to implement StateT(List). That is, plug in the implementations of the List monad's type, unit, and bind into the preceding definitions. That will be a monad, consisting of an inner List monad with StateT packaging around it. Choose sensible names for the type, and unit, bind, and elevate functions of your StateT(List) monad.
82
83         You may want to write some operations for your List monad, such as:
84
85                 either (u : 'a list) (v : 'a list) : 'a list
86                 (* appends list v to list u *)
87                 
88                 foreach (u : 'a list) (v : 'a list) : 'a list
89                 (* returns a list of lists, each member of which consists of u followed
90                   by a single member of v; there is one for each member of v *)
91
92         and so on. These are just suggestions; you decide which List operations you'll need. For each of these, use your StateT(List)'s `elevate` function to convert them into operations in your combined, State-around-List monad.
93
94         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.
95
96         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.
97
98 4.      The next two exercises were taken from _The Little Schemer_ Chapter 8.
99
100         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`.
101
102         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).
103
104         Here is a partial implementation. You should fill in the blanks. If you get stuck, you can consult the walkthough in _The Little Schemer_, or talk to us.
105
106                 (define remove-co
107                   (lambda (a lst k)
108                     (cond
109                       ((null? lst)
110                        (k ___  ___))
111                       ((eq? (car lst) a)
112                        (remove-co a (cdr lst) (lambda (left right) ________)))
113                       (else
114                        (remove-co a (cdr lst) (lambda (left right) ________))))))
115
116         What would be a helper function you could supply as a `k` that would report `#t` iff the original `lst` contained more instances of some symbol than non-instances?
117
118         <!--
119                 (define remove-co
120                   (lambda (a lst k)
121                     (cond
122                       ((null? lst)
123                        (k '() '()))
124                       ((eq? (car lst) a)
125                        (remove-co a (cdr lst) (lambda (left right) (k left (cons (car lst) right)))))
126                       (else
127                        (remove-co a (cdr lst) (lambda (left right) (k (cons (car lst) left) right)))))))
128         -->
129
130 5.      Now we define a function `insert-co` which has the following behavior. It accepts as arguments three symbols, a list, and a handler. The first symbol is inserted before (to the left of) any occurrences in the list of the second symbol, and after (to the right of) any occurrences of the third symbol. The handler is then called with three arguments: the new list (with the insertions made), the number of "to-the-left" insertions that were made, and the number of "to-the-right" insertions that were made.
131
132         Here is a partial implementation. You should fill in the blanks. If you get stuck, you can consult the walkthough in _The Little Schemer_, or talk to us.
133
134                 (define insert-co
135                   (lambda (new before after lst k)
136                     (cond
137                       ((null? lst)
138                        (k ___  ___ ___))
139                       ((eq? (car lst) before)
140                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) ________)))
141                       ((eq? (car lst) after)
142                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) ________)))
143                       (else
144                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) ________))))))
145
146         <!--
147                 (define insert-co
148                   (lambda (new before after lst k)
149                     (cond
150                       ((null? lst)
151                        (k '() 0 0))
152                       ((eq? (car lst) before)
153                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons new (cons before new-lst)) (succ lefts) rights))))
154                       ((eq? (car lst) after)
155                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons after (cons new new-lst)) lefts (succ rights)))))
156                       (else
157                        (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (car lst) new-lst) lefts rights)))))))
158         -->
159
160
161 6.      Go back to the "abSd" problem we presented in [[From List Zippers to Continuations]]. Consider the "tc" solution which uses
162 explicitly passed continuations. Try to reimplement this using reset
163 and shift instead of having an explicit `k` argument. This will likely
164 be challenging but rewarding. The notes on [[CPS and Continuation Operators]], especially the examples at the end, should be helpful. We
165 are of course also glad to help you out.
166
167     Consider adding a special symbol `'#'` (pronounced 'prompt') to the
168     mini-language such that
169
170     `"ab#cdSef"` ~~> `"abcdcdef"`
171
172     That is, the rule for `'S'` is to copy the preceding string, but
173     only up to the closest enclosing `'#'` symbol.
174
175 7.      Can you reimplement your solution to [[assignment9]] using reset and shift?
176
177 These are challenging questions, don't get frustrated if you get stuck, seek help.
178
179