-
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:
-
-<pre>
- John believes Mary said he thinks she's cute.
- | | | |
- | |---------|---------|
- | |
- |-----------------------|
-</pre>
-
-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
-<pre>
- let g f v = ap (unit f) v;;
- let g2 u a = ap u (unit a);;
-</pre>
+ 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.
-<pre>
-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
-</pre>
+ 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:
-<pre>
-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
-</pre>
+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
-<pre>
-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
-</pre>
+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.