X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week8.mdwn;h=e285451add14ef6b1fb8d0d9900e93a2a9ed1d28;hp=d3b5c1b7b283f1133ffd9c603210a5fc4627acc1;hb=0514157d311eae9ec04606dc4b3e6a68038f3186;hpb=0c9310c3707526f77e7d72c0ae932b1d6290e773;ds=sidebyside diff --git a/week8.mdwn b/week8.mdwn index d3b5c1b7..e285451a 100644 --- a/week8.mdwn +++ b/week8.mdwn @@ -9,7 +9,7 @@ Semantics](http://www.springerlink.com/content/j706674r4w217jj5/)) uses combinators to impose binding relationships between argument 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 +monads, Jacobson's system is essentially a Reader monad in which the assignment function threaded through the computation is limited to at most one variable. It will turn out that Jacobson's geach combinator *g* is exactly our `lift` operator, and her binding combinator *z* is @@ -53,7 +53,7 @@ dependence of a pronoun upwards through the tree using *g* until just before you are about to combine with the binder, when you finish off with *z*. (There are examples with longer chains of *g*'s below.) -Last week we saw a reader monad for tracking variable assignments: +Last week we saw a Reader monad for tracking variable assignments:
type env = (char * int) list;; @@ -74,7 +74,7 @@ an assignemnt function was implemented as a list of `char * int`. The idea is that a list like `[('a', 2); ('b',5)]` associates the variable `'a'` with the value 2, and the variable `'b'` with the value 5. -Combining this reader monad with ideas from Jacobson's approach, we +Combining this Reader monad with ideas from Jacobson's approach, we can consider the following monad:@@ -89,7 +89,7 @@ let z (f: 'a -> e -> 'b) (u: 'a link) : e -> 'b = fun (x:e) -> f (u x) x;;I've called this the *link* monad, because it links (exactly one) -pronoun with a binder, but it's a kind of reader monad. (Prove that +pronoun with a binder, but it's a kind of Reader monad. (Prove that `ap`, the combinator for applying a linked functor to a linked object, can be equivalently defined in terms of `bind` and `unit`.) @@ -98,7 +98,7 @@ kind of value that can be linked into a structure is an individual of type `e`. It is easy to make the monad polymorphic in the type of the linked value, which will be necessary to handle, e.g., paycheck pronouns. -In the standard reader monad, the environment is an assignment +In the standard Reader monad, the environment is an assignment function. Here, instead this monad provides a single value. The idea is that this is the value that will be used to replace the pronoun linked to it by the monad. @@ -122,7 +122,7 @@ link`, and returns a `'b link`, i.e., the result is in the link monad. order), but returns something that is not in the monad. Rather, it will be a function from individuals to a computation in which the pronoun in question is bound to that individual. We could emphasize -the parallel with the reader monad even more by writing a `shift` +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 @@ -140,16 +140,16 @@ everyone (z thinks (g (t bill) (g said (g left he)))) So *g* is exactly `lift` (a combination of `bind` and `unit`), and *z* is exactly `bind` with the arguments reversed. It appears that -Jacobson's variable-free semantics is essentially a reader monad. +Jacobson's variable-free semantics is essentially a Reader monad. -One of Jacobson's main points survives: restricting the reader monad +One of Jacobson's main points survives: restricting the Reader monad to a single-value environment eliminates the need for variable names. 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 +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