exercises/_assignment8.mdwn

   1
   2 Binding more than one variable at a time
   3 ----------------------------------------
   4
   5 It requires some cleverness to use the link monad to bind more than
   6 one variable at a time.  Whereas in the standard Reader monad a single
   7 environment can record any number of variable assignments, because
   8 Jacobson's monad only tracks a single dependency, binding more than
   9 one pronoun requires layering the monad.  (Jacobson provides some
  10 special combinators, but we can make do with the ingredients already
  11 defined.)
  12
  13 Let's take the following sentence as our target, with the obvious
  14 binding relationships:
  15
  16 <pre>
  17     John believes Mary said he thinks she's cute.
  18      |             |         |         |
  19      |             |---------|---------|
  20      |                       |
  21      |-----------------------|
  22 </pre>
  23
  24 It will be convenient to
  25 have a counterpart to the lift operation that combines a monadic
  26 functor with a non-monadic argument:
  27
  28 <pre>
  29     let g f v = ap (unit f) v;;
  30     let g2 u a = ap u (unit a);;
  31 </pre>
  32
  33 As a first step, we'll bind "she" by "Mary":
  34
  35 <pre>
  36 believes (z said (g2 (g thinks (g cute she)) she) mary) john
  37
  38 ~~> believes (said (thinks (cute mary) he) mary) john
  39 </pre>
  40
  41 As usual, there is a trail of *g*'s leading from the pronoun up to the
  42 *z*.  Next, we build a trail from the other pronoun ("he") to its
  43 binder ("John").
  44
  45 <pre>
  46 believes
  47   said
  48     thinks (cute she) he
  49     Mary
  50   John
  51
  52 believes
  53   z said
  54     (g2 ((g thinks) (g cute she))) he
  55     Mary
  56   John
  57
  58 z believes
  59   (g2 (g (z said)
  60          (g (g2 ((g thinks) (g cute she)))
  61             he))
  62       Mary)
  63   John
  64 </pre>
  65
  66 In the first interation, we build a chain of *g*'s and *g2*'s from the
  67 pronoun to be bound ("she") out to the level of the first argument of
  68 *said*.
  69
  70 In the second iteration, we treat the entire structure as ordinary
  71 functions and arguments, without "seeing" the monadic region.  Once
  72 again, we build a chain of *g*'s and *g2*'s from the currently
  73 targeted pronoun ("he") out to the level of the first argument of
  74 *believes*.  (The new *g*'s and *g2*'s are the three leftmost).
  75
  76 <pre>
  77 z believes (g2 (g (z said) (g (g2 ((g thinks) (g cute she))) he)) mary) john
  78
  79 ~~> believes (said (thinks (cute mary) john) mary) john
  80 </pre>
  81
  82 Obviously, we can repeat this strategy for any configuration of pronouns
  83 and binders.
  84