author Jim Pryor Mon, 13 Dec 2010 04:05:37 +0000 (23:05 -0500) committer Jim Pryor Mon, 13 Dec 2010 04:05:37 +0000 (23:05 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

index 609443f..7be7fd4 100644 (file)
@@ -391,8 +391,8 @@ natural language meaning.

**Quantification and default quantifier scope construal**.

-We saw in the copy-string example and in the same-fringe example that
-local properties of a tree (whether a character is `S` or not, which
+We saw in the copy-string example ("abSd") and in the same-fringe example that
+local properties of a structure (whether a character is `'S'` or not, which
integer occurs at some leaf position) can control global properties of
the computation (whether the preceeding string is copied or not,
whether the computation halts or proceeds).  Local control of
@@ -415,13 +415,13 @@ the following:
| "someone" -> Node (Leaf "exists y", k "y")
| _ -> k s;;

-       let sentence1 = Node (Leaf "John",
+Then we can crudely approximate quantification as follows:
+
+       # let sentence1 = Node (Leaf "John",
Node (Node (Leaf "saw",
Leaf "everyone"),
Leaf "yesterday"));;

-Then we can crudely approximate quantification as follows:
-
# tree_monadize lex sentence1 (fun x -> x);;
- : string tree =
Node
@@ -450,17 +450,17 @@ inverse scope:
Node (Leaf "forall x", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))

There are many crucially important details about quantification that
-are being simplified here, and the continuation treatment here is not
+are being simplified here, and the continuation treatment used here is not
scalable for a number of reasons.  Nevertheless, it will serve to give
an idea of how continuations can provide insight into the behavior of
-quantifiers.
+quantifiers.

----------------------
+==============

-Of course, by now you may have realized that we have discovered a new
+Of course, by now you may have realized that we are working with a new
so are trees.  Here is the type constructor, unit, and bind:

type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);;
@@ -478,20 +478,20 @@ To check the other two laws, we need to make the following
observation: it is easy to prove based on `tree_bind` by a simple
induction on the structure of the first argument that the tree
resulting from `bind u f` is a tree with the same strucure as `u`,
-except that each leaf `a` has been replaced with `f a`:
+except that each leaf `a` has been replaced with the tree returned by `f a`:

.                         .
__|__                     __|__
-                     |   |                     |   |
+                     |   |                    /\   |
a1  .                   f a1  .
_|__                     __|__
-                        |  |                     |   |
+                        |  |                     |   /\
.  a5                    .  f a5
bind         _|__       f   =        __|__
-                       |  |                    |   |
+                       |  |                    |   /\
.  a4                   .  f a4
__|__                   __|___
-                     |   |                   |    |
+                     |   |                  /\    /\
a2  a3                f a2  f a3

Given this equivalence, the right identity law
@@ -529,7 +529,7 @@ Now when we bind this tree to `g`, we get

At this point, it should be easy to convince yourself that
using the recipe on the right hand side of the associative law will
-built the exact same final tree.
+build the exact same final tree.

So binary trees are a monad.

@@ -542,37 +542,5 @@ that is intended to represent non-deterministic computations as a tree.
What's this have to do with tree\_monadize?
--------------------------------------------

-So we've defined a Tree monad:
-
-       type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);;
-       let tree_unit (a: 'a) : 'a tree = Leaf a;;
-       let rec tree_bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
-           match u with
-           | Leaf a -> f a
-           | Node (l, r) -> Node (tree_bind l f, tree_bind r f);;
-
-What's this have to do with the `tree_monadize` functions we defined earlier?
-
-       let rec tree_monadize (t : 'a tree) (f : 'a -> 'b reader) : 'b tree reader =
-           match t with
-           | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
-           | Node (l, r) -> reader_bind (tree_monadize l f) (fun l' ->
-
-... and so on for different monads?
-
-Well, notice that `tree\_monadizer` takes arguments whose types
-resemble that of a monadic `bind` function.  Here's a schematic bind