XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek8_reader_monad.mdwn;h=93e2086851d3aa8d435825e1e8d456942a7e9633;hp=4dc0da64fe6cea3a6a223e85f588f872323094f3;hb=HEAD;hpb=9fa2ebb32617d76b9dde81b4d6adfada2f15d48d;ds=inline
diff git a/topics/week8_reader_monad.mdwn b/topics/week8_reader_monad.mdwn
index 4dc0da64..93e20868 100644
 a/topics/week8_reader_monad.mdwn
+++ b/topics/week8_reader_monad.mdwn
@@ 1,34 +1,32 @@

+
[[!toc levels=2]]
The Reader Monad
================
+[[!toc levels=2]]
The goal for this part is to introduce the Reader Monad, and present
two linguistics applications: binding and intensionality. Along the
+The goal for these notes is to introduce the Reader Monad, and present
+two linguistic applications: binding and intensionality. Along the
way, we'll continue to think through issues related to order, and a
related notion of flow of information.
At this point, we've seen monads in general, and three examples of
monads: the identity monad (invisible boxes), the Maybe monad (option
types), and the List monad.
+monads: the Identity monad (invisible boxes), the Option/Maybe monad (option
+types), and the List monad.
We've also seen an application of the Maybe monad to safe division.
The starting point was to allow the division function to return an int
option instead of an int. If we divide 6 by 2, we get the answer Just
3. But if we divide 6 by 0, we get the answer Nothing.
+We've also seen an application of the Option/Maybe monad to safe division.
+The starting point was to allow the division function to return an `int
+option` instead of an `int`. If we divide `6` by `2`, we get the answer `Some
+3`. But if we divide `6` by `0`, we get the answer `None`.
The next step was to adjust the other arithmetic functions to teach
them what to do if they received Nothing instead of a boxed integer.
This meant changing the type of their input from ints to int options.
+them what to do if they received `None` instead of a boxed integer.
+This meant changing the type of their input from `int`s to `int option`s.
But we didn't need to do this piecemeal; rather, we "lift"ed the
ordinary arithmetic operations into the monad using the various tools
provided by the monad.
+provided by the monad.
We'll go over this lifting operation in detail in the next section.
## Tracing the effect of safediv on a larger computation
+## Tracing the effect of `safe_div` on a larger computation
So let's see how this works in terms of a specific computation.
@@ 51,38 +49,39 @@ ___ ______
/ 6
No matter which arithmetic operation we begin with, this computation
should eventually reduce to 13. Given a specific reduction strategy,
we can watch the order in which the computation proceeds. Following
on the lambda evaluator developed during the previous homework, let's
+No matter what order we evaluate it in, this computation
+should eventually reduce to `13`. Given a specific reduction strategy,
+we can watch the order in which the computation proceeds. Following
+on the evaluator developed during the previous homework, let's
adopt the following reduction strategy:
 In order to reduce an expression of the form (head arg), do the following in order:
 1. Reduce head to h'
 2. Reduce arg to a'.
 3. If (h' a') is a redex, reduce it.
+> In order to reduce an expression of the form (head arg), do the following in order:
+
+> 1. Reduce `head` to `head'`
+> 2. Reduce `arg` to `arg'`.
+> 3. If `(head' arg')` is a redex, reduce it.
There are many details left unspecified here, but this will be enough
for today. The order in which the computation unfolds will be

 1. Reduce head (+ 1) to itself
 2. Reduce arg ((* ((/ 6) 2)) 3)
 1. Reduce head (* ((/ 6) 2))
 1. Reduce head *
 2. Reduce arg ((/ 6) 2)
 1. Reduce head (/ 6) to itself
 2. Reduce arg 2 to itself
 3. Reduce ((/ 6) 2) to 3
 3. Reduce (* 3) to itself
 2. Reduce arg 4 to itself
 3. Reduce ((* 3) 4) to 12
 3. Reduce ((+ 1) 12) to 13
+for today. The order in which the computation unfolds will be
+
+> 1. Reduce head `(+ 1)` to itself
+> 2. Reduce arg `((* ((/ 6) 2)) 4)`
+> 1. Reduce head `(* ((/ 6) 2))`
+> 1. Reduce head `*` to itself
+> 2. Reduce arg `((/ 6) 2)`
+> 1. Reduce head `(/ 6)` to itself
+> 2. Reduce arg `2` to itself
+> 3. Reduce `((/ 6) 2)` to `3`
+> 3. Reduce `(* 3)` to itself
+> 2. Reduce arg `4` to itself
+> 3. Reduce `((* 3) 4)` to `12`
+> 3. Reduce `((+ 1) 12)` to `13`
This reduction pattern follows the structure of the original
expression exactly, at each node moving first to the left branch,
processing the left branch, then moving to the right branch, and
finally processing the results of the two subcomputation. (This is
called depthfirst postorder traversal of the tree.)
+finally processing the results of the two subcomputation. (This is
+called a depthfirst postorder traversal of the tree.)
[diagram with arrows traversing the tree]
@@ 93,13 +92,13 @@ It will be helpful to see how the types change as we make adjustments.
type tree = Leaf of contents  Branch of tree * tree
Never mind that these types will allow us to construct silly
arithmetric trees such as `+ *` or `2 3`. Note that during the
+arithmetric trees such as `+ *` or `2 3`. Note that during the
reduction sequence, the result of reduction was in every case a
wellformed subtree. So the process of reduction could be animated by
replacing subtrees with the result of reduction on that subtree, till
the entire tree is replaced by a single integer (namely, 13).
+wellformed subtree. So the process of reduction could be animated by
+replacing subtrees with the result of reduction on that subtree, until
+the entire tree is replaced by a single integer (namely, `13`).
Now we replace the number 2 with 0:
+Now we replace the number `2` with `0`: