Jacobson as a monad

[lambda.git] / week8.mdwn

diff --git a/week8.mdwn b/week8.mdwn
index e99e223..7f42092 100644 (file)
--- a/week8.mdwn
+++ b/week8.mdwn
@@ -11,24 +11,28 @@ positions.  The system does not make use of assignment functions or
 variables.  We'll see that from the point of view of our discussion of
 monads, Jacobson's system is essentially a reader monad in which the
 assignment function threaded through the computation is limited to at
 variables.  We'll see that from the point of view of our discussion of
 monads, Jacobson's system is essentially a reader monad in which the
 assignment function threaded through the computation is limited to at

-most one assignment.
+most one assignment.  More specifically, Jacobson's geach combinator
+*g* is exactly our `lift` operator, and her binding combinator *z* is
+exactly our `bind` with the arguments reversed!

 
 Jacobson's system contains two main combinators, *g* and *z*.  She
 calls *g* the Geach rule, and *z* effects binding.  (There is a third
 
 Jacobson's system contains two main combinators, *g* and *z*.  She
 calls *g* the Geach rule, and *z* effects binding.  (There is a third

-combinator, *l*, which we'll make use of to adjust function/argument
-order to better match English word order; N.B., though, that
-Jacobson's name for this combinator is "lift", but it is different
-from the monadic lift discussed in some detail below.)  Here is a
-typical computation (based closely on email from Simon Charlow, with
-beta reduction as performed by the on-line evaluator):
+combinator which following Curry and Steedman, I'll call *T*, which
+we'll make use of to adjust function/argument order to better match
+English word order; N.B., though, that Jacobson's name for this
+combinator is "lift", but it is different from the monadic lift
+discussed in some detail below.)  Here is a typical computation (based
+closely on email from Simon Charlow, with beta reduction as performed
+by the on-line evaluator):

 
 <pre>
 ; Analysis of "Everyone_i thinks he_i left"
 let g = \f g x. f (g x) in
 let z = \f g x. f (g x) x in
 
 <pre>
 ; Analysis of "Everyone_i thinks he_i left"
 let g = \f g x. f (g x) in
 let z = \f g x. f (g x) x in

-let everyone = \P. FORALL x (P x) in

 let he = \x. x in
 let he = \x. x in

-everyone ((z thinks) (g left he))
+let everyone = \P. FORALL x (P x) in
+
+everyone (z thinks (g left he))

 
 ~~>  FORALL x (thinks (left x) x)
 </pre>
 
 ~~>  FORALL x (thinks (left x) x)
 </pre>


@@ -44,8 +48,8 @@ Second, *g* plays the role of transmitting a binding dependency for an
 embedded constituent to a containing constituent.  If the sentence had
 been *Everyone_i thinks Bill said he_i left*, there would be an
 occurrence of *g* in the most deeply embedded clause (*he left*), and
 embedded constituent to a containing constituent.  If the sentence had
 been *Everyone_i thinks Bill said he_i left*, there would be an
 occurrence of *g* in the most deeply embedded clause (*he left*), and

-another occurrence of (a variant of) *g* in the next most deeply
-embedded clause (*Bill said he left*).
+another occurrence of *g* in the next most deeply
+embedded constituent (*said he left*), and so on (see below).

 
 Third, binding is accomplished by applying *z* not to the element that
 will (in some pre-theoretic sense) bind the pronoun, here, *everyone*,
 
 Third, binding is accomplished by applying *z* not to the element that
 will (in some pre-theoretic sense) bind the pronoun, here, *everyone*,


@@ -136,14 +140,14 @@ the parallel with the reader monad even more by writing a `shift`
 operator that used `unit` to produce a monadic result, if we wanted to.
 
 The monad version of *Everyone_i thinks he_i left*, then (remembering
 operator that used `unit` to produce a monadic result, if we wanted to.
 
 The monad version of *Everyone_i thinks he_i left*, then (remembering

-that `he = fun x -> x`, and that `l a f = f a`) is
+that `he = fun x -> x`, and letting `t a f = f a`) is

 
 <pre>
 everyone (z thinks (g left he))
 
 ~~> forall w (thinks (left w) w)
 
 
 <pre>
 everyone (z thinks (g left he))
 
 ~~> forall w (thinks (left w) w)
 

-everyone (z thinks (g (l bill) (g said (g left he))))
+everyone (z thinks (g (t bill) (g said (g left he))))

 
 ~~> forall w (thinks (said (left w) bill) w)
 </pre>
 
 ~~> forall w (thinks (said (left w) bill) w)
 </pre>


@@ -154,3 +158,15 @@ Jacobson's variable-free semantics is essentially a reader monad.
 
 One of Jacobson's main points survives: restricting the reader monad
 to a single-value environment eliminates the need for variable names.
 
 One of Jacobson's main points survives: restricting the reader monad
 to a single-value environment eliminates the need for variable names.

+
+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, so that intermediate regions
+of the computation will be functors inside of a link monad box inside
+another link monad box, and so on.  
+
+[Give details of the readings of *Everyone said someone thinks that he
+likes her*.  Jacobson needs to add a variant of g; is it necessary to 
+write a link swap that reverses the nesting of the monad boxes?]