X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=exercises%2F_assignment8.mdwn;h=a05707ac7104d8b8449da3d336b7dfd51c60dfee;hb=edc0629a18ec26271ea8c738eb81bb14c31dadf9;hp=1c7fdfaf02252e0d721d32acd9de6a507667096e;hpb=908143f5f416416081b24715bfc567cbea0aeff4;p=lambda.git diff --git a/exercises/_assignment8.mdwn b/exercises/_assignment8.mdwn index 1c7fdfaf..a05707ac 100644 --- a/exercises/_assignment8.mdwn +++ b/exercises/_assignment8.mdwn @@ -1,84 +1,51 @@ - Binding more than one variable at a time ---------------------------------------- -It requires some cleverness to use the link monad to bind more than -one variable at a time. Whereas in the standard Reader monad a single -environment can record any number of variable assignments, because -Jacobson's monad only tracks a single dependency, binding more than -one pronoun requires layering the monad. (Jacobson provides some -special combinators, but we can make do with the ingredients already -defined.) - -Let's take the following sentence as our target, with the obvious -binding relationships: - -
- John believes Mary said he thinks she's cute. - | | | | - | |---------|---------| - | | - |-----------------------| -- -It will be convenient to -have a counterpart to the lift operation that combines a monadic -functor with a non-monadic argument: +1. Jacobson's reader monad only allows for establishing a single binding +relationship at a time. It requires considerable cleverness to deploy +her combinators in a way that establishes multiple binding +relationships, as in -
- let g f v = ap (unit f) v;; - let g2 u a = ap u (unit a);; -+ John_x thinks Mary_y said he_x likes her_y. -As a first step, we'll bind "she" by "Mary": +See her 1999 paper for details. -
-believes (z said (g2 (g thinks (g cute she)) she) mary) john +Here is [[code for the simple arithmetic reader monad discussed in the +lecture notes|code/arith1.ml]]. It computes +`\x. (+ 1 (* (/ 6 x) 4))`. Your task is to modify it to compute +`\x\y.(+ 1 (* (/ 6 x) y))`. You will need to modify five lines. +The first one is the type of a boxed int. Instead of `type num = int +-> int`, you'll need -~~> believes (said (thinks (cute mary) he) mary) john -+ type num = int -> int -> int -As usual, there is a trail of *g*'s leading from the pronoun up to the -*z*. Next, we build a trail from the other pronoun ("he") to its -binder ("John"). +The second and third are the definitions of mid and map2. The fourth +is the one that encodes the variable x, the line that begins `(Leaf +(Num (fun x -> ...`. The fifth line you need to modify is the one +that replaces "4" with "y". When you have these lines modified, +you should be able to execute the following expression: -
-believes - said - thinks (cute she) he - Mary - John + # match eval t2 with Leaf (Num f) -> f 2 4;; + - : int = 13 -believes - z said - (g2 ((g thinks) (g cute she))) he - Mary - John +2. Based on the evaluator code from the assignment from week 7, +enhance the code to handle an arbitrary set of free variables. +Return to the original code (before executing the modifications +required by exercise 1). -z believes - (g2 (g (z said) - (g (g2 ((g thinks) (g cute she))) - he)) - Mary) - John -+Start like this: -In the first interation, we build a chain of *g*'s and *g2*'s from the -pronoun to be bound ("she") out to the level of the first argument of -*said*. + type env = string -> int + type num = env -> int + let g = fun var -> match var with "x" -> 2 | "y" -> 4 | _ -> 0;; -In the second iteration, we treat the entire structure as ordinary -functions and arguments, without "seeing" the monadic region. Once -again, we build a chain of *g*'s and *g2*'s from the currently -targeted pronoun ("he") out to the level of the first argument of -*believes*. (The new *g*'s and *g2*'s are the three leftmost). +When you have it working, try -
-z believes (g2 (g (z said) (g (g2 ((g thinks) (g cute she))) he)) mary) john + # match eval t2 with Leaf (Num f) -> f g;; + - : int = 13 -~~> believes (said (thinks (cute mary) john) mary) john -+3. Add in the maybe monad. Start here: -Obviously, we can repeat this strategy for any configuration of pronouns -and binders. + type num = env -> int option + Show that your code handles division by zero gracefully.