1 This is the assignment for weeks 8-9, on Reader and State monads.
4 1. When discussing safe division, we worked with operators like `map2 (+)` which just did their ordinary thing, only now lifted up into working on "boxed" or monadic values. Also there was a special division operator, which interacted with the new possibilities presented by the Option/Maybe monad. Instead of this special division operator and the Option monad, show us how to write expressions in the Reader monad with special `getx` operators. That is, instead of representing computations like `(2+3)/0/1`, now you will represent computations like `(2+x)+1`. To keep things simple, suppose that your language only allows three variables `x`, `y`, and `z`, and you can represent the `env` as a triple of `int`s. For this problem you don't need to demonstrate how to implement binding expressions like `let x = 3 in ...`. You just need to compute the value of possibly open expressions, relative to a supplied `env` that gives values for `x` and `y` and `z`.
6 2. Okay, now what changes do you need to make to add in expressions like `let x = 3 in ...`
10 1. Jacobson's reader monad only allows for establishing a single binding
11 relationship at a time. It requires considerable cleverness to deploy
12 her combinators in a way that establishes multiple binding
15 John_x thinks Mary_y said he_x likes her_y.
17 See her 1999 paper for details.
19 Here is [[code for the arithmetic tree Chris presented in week 8|code/arith1.ml]]. It computes
20 `\x. (+ 1 (* (/ 6 x) 4))`. Your task is to modify it to compute
21 `\x y. (+ 1 (* (/ 6 x) y))`. You will need to modify five lines.
22 The first one is the type of a boxed int. Instead of `type num = int
25 type num = int -> int -> int
27 The second and third are the definitions of `mid` and `map2`. The fourth
28 is the one that encodes the variable `x`, the line that begins `(Leaf
29 (Num (fun x -> ...`. The fifth line you need to modify is the one
30 that replaces "4" with "y". When you have these lines modified,
31 you should be able to execute the following expression:
33 # match eval t2 with Leaf (Num f) -> f 2 4;;
36 2. Based on the evaluator code from the assignment from week 7, and what you've learned about the Reader monad,
37 enhance the arithmetic tree code to handle an arbitrary set of free variables. Don't use Juli8 libraries for this; just do it by hand.
38 Return to the original code (that is, before the modifications required by the previous problem).
42 type env = string -> int
44 let my_env = fun var -> match var with "x" -> 2 | "y" -> 4 | _ -> 0;;
46 When you have it working, try
48 # match eval t2 with Leaf (Num f) -> f my_env;;
51 For this problem you don't need to demonstrate how to implement binding expressions like `let x = 3 in ...`. You just need to compute the value of possibly open expressions, relative to the supplied `env`.
53 3. Okay, now what changes do you need to make to add in expressions like `let x = 3 in ...`
55 4. Add in the Option/Maybe monad. Start here:
57 type num = env -> int option
59 Show that your code handles division by zero gracefully.
61 5. Consider the following code which uses the Juli8 libraries for OCaml.
63 module S = Monad.State(struct type store = int end);;
64 let xx = S.(mid 1 >>= fun x -> put 20 >> modify succ >> get >>= fun y -> mid [x;y]) in
67 Recall that `xx >> yy` is short for `xx >>= fun _ -> yy`. The equivalent Haskell code is:
69 import Control.Monad.State
70 let { xx :: State Int [Int];
71 xx = return 1 >>= \x -> put 20 >> modify succ >> get >>= \y -> return [x,y] } in
76 import Control.Monad.State
77 let { xx :: State Int [Int];
78 xx = do { x <- return 1;
85 Don't try running the code yet. Instead, get yourself into a position to predict what it will do, by reading the past few discussions about the State monad. After you've made a prediction, then run the code and see if you got it right.
87 6. Here's another one:
89 (* start with module S = ... as before *)
90 let yy = S.(let xx = modify succ >> get in
91 xx >>= fun x1 -> xx >>= fun x2 -> xx >>= fun x3 -> mid [x1;x2;x3]) in
94 The equivalent Haskell code is:
96 import Control.Monad.State
97 let { xx :: State Int Int;
98 xx = modify succ >> get;
99 yy = xx >>= \x1 -> xx >>= \x2 -> xx >>= \x3 -> return [x1,x2,x3] } in
102 What is your prediction? What did OCaml or Haskell actually evaluate this to?
104 7. Suppose you're trying to use the State monad to keep a running tally of how often certain arithmetic operations have been used in computing a complex expression. You've come upon the design plan of using the same State monad module `S` from the previous problems, and defining a function like this:
106 let counting_plus xx yy = S.(tick >> map2 (+) xx yy)
108 How should you define the operation `tick` to make this work? The intended behavior is that after running:
110 let zz = counting_plus (S.mid 1) (counting_plus (S.mid 2) (S.mid 3)) in
113 you should get a payload of `6` (`1+(2+3)`) and a final `store` of `2` (because `+` was used twice).
115 8. Instead of the design in the previous problem, suppose you had instead chosen to do things this way:
117 let counting_plus xx yy = S.(map2 (+) xx yy >>= tock)
119 How should you define the operation `tock` to make this work, with the same behavior as before?
121 <!-- How would you expand your strategy, if you also wanted to be safe from division by zero? This is a deep question. How should you combine two monads into a single system? If you don't arrive at working code, you can still discuss the issues and design choices. -->
123 9. Here is how to create a monadic stack of a Reader monad transformer wrapped around an underlying Option monad:
125 module O = Monad.Option (* not really necessary *)
126 module R = Monad.Reader(struct type env = (* whatever *) end)
127 module RO = R.T(O) (* wrap R's Transformer around O *)
129 You can inspect the types that result by saying `#show RO.result` (in OCaml version >= 4.02), or by running:
131 let env0 = (* some appropriate env, depending on how you defined R *) in
132 let xx = RO.(mid 1) in RO.run xx env0
134 and inspecting the type of the result. In Haskell:
136 import Control.Monad.Reader
137 -- substitute your own choices for the type Env and value env0
138 let { xx :: ReaderT Env Maybe Int; xx = return 1 } in runReaderT xx env0
140 Okay, here are some questions about various monad transformers. Use OCaml to help you answer them. Which combined monad has the type of an optional list (that is, either `None` or `Some [...]`): an Option transformer wrapped around an underlying List monad, or a List transformer wrapped around an underlying Option monad? Which combined monad has the type of a function from `store`s to a pair `('a list, store)`: a List transformer wrapped around an underlying State monad or a State transformer wrapped around an underlying List monad?
142 The last two problems are non-monadic.
144 10. This is a question about native mutation mechanisms in languages that have them, like OCaml or Scheme. What an expression like this:
147 let incr c = (let old = !cell in let () = cell := old + 1 in ()) in
148 (incr cell, !cell, incr cell, incr cell)
150 will evaluate to will be `((), n, (), ())` for some number `n` between `0` and `3`. But what number is sensitive to the details of OCaml's evaluation strategy for evaluating tuple expressions. How can you avoid that dependence? That is, how can you rewrite such code to force it that the values in the 4-tuple have been evaluated left-to-right? Show us a strategy that works no matter what the expressions in the tuple are, not just these particular ones. (But you can assume that the expressions all terminate.)
152 11. In the evaluator code for [[Week 7 homework|/exercises/assignment7]], we left the `LetRec` portions unimplemented. How might we implement these for the second, `env`-using interpreter? One strategy would be to interpret expressions like:
154 letrec f = \x. BODY in
157 as though they really read:
159 let f = FIX (\f x. BODY) in
162 for some fixed-point combinator `FIX`. And that would work, supposing you use some fixed point combinator like the "primed" ones we showed you earlier that work with eager/call-by-value evaluation strategies. But for this problem, we want you to approach the task a different way.
164 Begin by deleting all the `module VA = ...` code that implements the substitute-and-repeat interpreter. Next, change the type of `env` to be an `(identifier * bound) list`. Add a line after the definition of that type that says `and bound = Plain of result | Recursive of identifier * identifier * term * env`. The idea here is that some variables will be bound to ordinary `result`s, and others will be bound to special structures we've made to keep track of the recursive definitions. These special structures are akin to the `Closure of identifier * term * env` we already added to the `term` (or really more properly `result`) datatype. For `Closure`s, the single `identifier` is the bound variable, the `term` is the body of the lambda abstract, and the `env` is the environment that is in place when some variable is bound to this lambda abstract. Those same parameters make up the last three arguments of our `Recursive` structure. The first argument in the `Recursive` structure is to hold the variable that our `letrec` construction binds to the lambda abstract. That is, in:
166 letrec f = \x. BODY in
169 both of the variables `f` and `x` need to be interpreted specially when we evaluate `BODY`, and this is how we keep track of which variable is `f`.
171 Just making those changes will require you to change some other parts of the interpreter to make it still work. Before trying to do anything further with `letrec`, try finding what parts of the code need to be changed to accommodate these modifications to our types. See if you can get the interpreter working again as well as it was before.
173 OK, once you've done that, then add an extra line:
175 | LetRec of identifier * term * term
177 to the definition of the `term` datatype. (For `letrec IDENT1 = TERM1 in TERM2`. You can assume that `TERM1` is always a `Lambda` term.) Now what will you need to add to the `eval` function to get it to interpret these terms properly? This will take some thought, and a good understanding of how the other clauses in the `eval` function are working.
179 Here's a conceptual question: why did we point you in the direction of complicating the type that environments associate variables with, rather than just adding a new clause to the `result` type, as we did with Closures?