exercises/_assignment8.mdwn

   1 Binding more than one variable at a time
   2 ----------------------------------------
   3
   4 1. Jacobson's reader monad only allows for establishing a single binding
   5 relationship at a time.  It requires considerable cleverness to deploy
   6 her combinators in a way that establishes multiple binding
   7 relationships, as in
   8
   9     John_x thinks Mary_y said he_x likes her_y.
  10
  11 See her 1999 paper for details.
  12
  13 Here is [[code for the simple arithmetic reader monad discussed in the
  14 lecture notes|code/arith1.ml]]. It computes
  15 `\x. (+ 1 (* (/ 6 x) 4))`.  Your task is to modify it to compute
  16 `\x\y.(+ 1 (* (/ 6 x) y))`.  You will need to modify five lines.
  17 The first one is the type of a boxed int.  Instead of `type num = int
  18 -> int`, you'll need
  19
  20     type num = int -> int -> int
  21
  22 The second and third are the definitions of mid and map2.  The fourth
  23 is the one that encodes the variable x, the line that begins `(Leaf
  24 (Num (fun x -> ...`.  The fifth line you need to modify is the one
  25 that replaces "4" with "y".  When you have these lines modified,
  26 you should be able to execute the following expression:
  27
  28     # match eval t2 with Leaf (Num f) -> f 2 4;;
  29     - : int = 13
  30
  31 2. Based on the evaluator code from the assignment from week 7,
  32 enhance the code to handle an arbitrary set of free variables.
  33 Return to the original code (before executing the modifications
  34 required by exercise 1).
  35
  36 Start like this:
  37
  38     type env = string -> int
  39     type num = env -> int
  40     let g = fun var -> match var with "x" -> 2 | "y" -> 4 | _ -> 0;;
  41
  42 When you have it working, try
  43
  44     # match eval t2 with Leaf (Num f) -> f g;;
  45     - : int = 13
  46
  47 3. Add in the maybe monad.  Start here:
  48
  49         type num = env -> int option
  50
  51    Show that your code handles division by zero gracefully.