clean up a bit

[lambda.git] / topics / week9_using_monad_library.mdwn

diff --git a/topics/week9_using_monad_library.mdwn b/topics/week9_using_monad_library.mdwn
index d9820ac..f3cb414 100644 (file)
--- a/topics/week9_using_monad_library.mdwn
+++ b/topics/week9_using_monad_library.mdwn
@@ -4,7 +4,11 @@
 
 If you want to see the "signature" of some OCaml library or "module" --- that is, a list of the types it exports, and also of the types of function values (and other values) that it exports, you can do this.
 
 
 If you want to see the "signature" of some OCaml library or "module" --- that is, a list of the types it exports, and also of the types of function values (and other values) that it exports, you can do this.
 

-First, if you know that the module uses a specific *named* module type, here's what to do. An example is that modules you create using `Monad.Reader(struct type env = ... end).M` --- really you have to do that in two steps, first say `module R_E = Monad.Reader(struct type env = ... end)`, next write `R_E.M`; but for brief reading I'll just write `Monad.Reader(struct type env = ... end).M` --- these modules will all have the module type `Monad.READER`. We can see an expansion of `Monad.READER` by writing:
+If you know the name of the module but not the name of its module type, or if its module type doesn't have a name, you can do this:
+
+    module type SOMETHING = sig include module type of ModuleYouAreInterestedIn end
+
+More commonly, though, you'll know that the module uses a specific *named* module type. In that case, here is what to do. An example is that modules you create using `Monad.Reader(struct type env = ... end).M` --- really you have to do that in two steps, first say `module R_E = Monad.Reader(struct type env = ... end)`, next write `R_E.M`; but for brief reading I'll just write `Monad.Reader(struct type env = ... end).M` --- these modules will all have the module type `Monad.READER`. We can see an expansion of `Monad.READER` by writing:

 
     module type SOMETHING = sig include Monad.READER end
 
 
     module type SOMETHING = sig include Monad.READER end
 


@@ -57,14 +61,14 @@ The next block of stuff in the `Monad.READER` module type are functions common t
 
         let letx xint body = shift (insert 'x' xint) body
 
 
         let letx xint body = shift (insert 'x' xint) body
 

-    will declare an operation that takes an `int` `xint` and a monadic value `body`, and evaluates `body` in the context <code>let x = <i>xint</i> in ...</code>. If we wanted instead to have a version which accepted not an `int` but rather an `int` in a Reader monad box, we could write instead:
+    will declare an operation that takes an `int` `xint` and a monadic value `body`, and evaluates `body` in the context <code>let x = <i>xint</i> in ...</code>. If we wanted instead to have a version which accepted not an `int`, but rather an `int` Reader, we could write instead:

 
         let letx xx body = xx >>= fun xint -> shift (insert 'x' xint) body
 
 
 ### Examples ###
 
 
         let letx xx body = xx >>= fun xint -> shift (insert 'x' xint) body
 
 
 ### Examples ###
 

-Here are some examples of using the Reader Monad modules to evaluate some simple expressions using bound variables. First, you could look at [[this Haskell code|/code/reader1.hs]]. It `import`s the `Control.Monad.Reader` library, which is where Haskell's Reader monad can be found. It declares an `Env` type that we'll implement as a simple *function* from `Char`s to `Int`s. Then it defines an "empty" environment `env0`, and a function `insert` for adding new bindings to an `env`. Next, we make a general function `getint` that can create monadic values like the `getx` illustrated above. We show how to use `getx` and `gety` to write monadic versions of `y + x` and `3 + x`. Next, we define a `letx` function as illustrated above (the second version, that takes a monadic value `xx` as its argument). We show how to use this to write a monadic version of `let x = 2 in y + x`. The final line of the file applies `runReader` to the monadic value we've built --- this is Haskell's way of doing what we do in OCaml with `run`, namely to remove the abstraction barrier and see what concrete type is really constituting our `Reader Env a`s --- and we supply it with the empty environment, which will be sufficient since the expression we're interpreting has no free variables. Haskell binds the variable `res` to the result. You can run this code inside `ghci` by typing `:load /path/to/reader1.hs`. (You could also say `:add ...` instead of `:load ...`.) Then type `res`, and Haskell will report back `5`.
+Here are some examples of using the Reader Monad modules to evaluate some simple expressions using bound variables. First, you could look at [[this Haskell code|/code/reader1.hs]]. It `import`s the `Control.Monad.Reader` library, which is where Haskell's Reader monad can be found. It declares an `Env` type that we'll implement as a simple *function* from `Char`s to `Int`s. Then it defines an "empty" environment `env0`, and a function `insert` for adding new bindings to an `env`. Next, we make a general function `getint` that can create monadic values like the `getx` illustrated above. We show how to use `getx` and `gety` to write monadic versions of `y + x` and `3 + x`. Next, we define a `letx` function as illustrated above (the second version, that takes a monadic value `xx` as its argument). We show how to use this to write a monadic version of `let x = 2 in y + x`. The final line of the file applies `runReader` to the monadic value we've built --- this is Haskell's way of doing what we do in OCaml with `run`, namely to remove the abstraction barrier and see what concrete type is really constituting our `Reader Env a`s --- and we supply it with the empty environment, which will be sufficient since the expression we're interpreting has no free variables. Haskell binds the variable `res` to the result. You can run this code inside `ghci` by typing `:load /path/to/reader1.hs`. (You may also be able to say `:add ...` instead of `:load ...`.) Then type `res`, and Haskell will report back `5`.

 
 [[This OCaml code|/code/reader1.ml]] does exactly the same thing only using our OCaml monad libraries instead. The biggest difference from the Haskell version is in the first few lines, where we have to generate a Reader monad module parameterized on the `env` type that we intend to work with.
 
 
 [[This OCaml code|/code/reader1.ml]] does exactly the same thing only using our OCaml monad libraries instead. The biggest difference from the Haskell version is in the first few lines, where we have to generate a Reader monad module parameterized on the `env` type that we intend to work with.
 


@@ -78,11 +82,11 @@ and like this in Haskell:
     data Bound = Int Int | Fun (Reader Env Int -> Reader Env Int)
     type Env = Char -> Bound
 
     data Bound = Int Int | Fun (Reader Env Int -> Reader Env Int)
     type Env = Char -> Bound
 

-There is a tricky issue in the OCaml case, though, in that when working with OCaml, we have to *generate* our R Reader monad module, parameterized on the type of the `env`, but here we see that we need access to the *type* `'a R.t` from the generated R module in order to declare the `env`. Fortunately, it is possible to do this, by having the module that declares the `env` and the module that has our Reader monad in it be mutually recursively defined. The first few lines of [[this OCaml code|/code/reader2.ml]] do the tricky work.
+There is a tricky issue in the OCaml case, though, in that when working with OCaml, we have to *generate* our `R` Reader monad module, parameterized on the type of the `env`, but here we see that we need access to the *type* `'a R.t` from the generated `R` module in order to declare the `env`. Fortunately, it is possible to do this, by having the module that declares the `env` and the module that has our Reader monad in it be mutually recursively defined. The first few lines of [[this OCaml code|/code/reader2.ml]] do the tricky work.

 
 

-After that, our [[Haskell code|/code/reader2.hs]] and [[OCaml code|/code/reader2.ml]] proceed basically the same, allowing for the difference in syntax and vocabulary between Haskell and OCaml. The `getint` function works like before, except now we have to pull the int out from behind the `Int` constructor of our disjoint sum type `bound`. We have a parallel `getfun` function. Then we interpret the variable `x` using the monadic value `getint 'x'`, and we interpret the variable `f` using the monadic value `getfun 'f'`. The `letx` operation is similarly adjusted, and we also have a parallel `letf`.
+After that, our [[Haskell code|/code/reader2.hs]] and [[OCaml code|/code/reader2.ml]] proceed basically the same, allowing for the difference in syntax and vocabulary between Haskell and OCaml. The `getint` function works like before, except now we have to pull the `int` out from behind the `Int` constructor of our disjoint sum type `bound`. We have a parallel `getfun` function. Then we interpret the variable `x` using the monadic value `getint 'x'`, and we interpret the variable `f` using the monadic value `getfun 'f'`. The `letx` operation is similarly adjusted, and we also have a parallel `letf`.

 
 

-The really new thing in this code, compared to the previous example, is our definition of a monadic value to interpret the lambda abstract `\y -> y + x`, that `f` gets bound to. And also our interpretation of the expression `f 3`, which looks up a function that the variable `f` is bound to, and then applies it to (a monadically-lifted version of) `3`. (We have the argument be monadically lifted so that we could also say, for example, `f y`.)
+The really new thing in this code, compared to the previous example, is our definition of a monadic value to interpret the lambda abstract `\y -> y + x`, that `f` gets bound to. And also our interpretation of the expression `f 3`, which looks up a function that the variable `f` is bound to, and then applies it to (a monadically-lifted version of) `3`. (We have the argument be monadically lifted so that we could also say, for example, `f y`.) You can examine the code to see how we do these things.

 
 
 ## OK, what else is in the OCaml Monad modules? ##
 
 
 ## OK, what else is in the OCaml Monad modules? ##


@@ -136,9 +140,9 @@ Writer is very similar to Reader: first, it is parameterized on something like a
         val shift : (env -> env) -> 'a t -> 'a t
       end
 
         val shift : (env -> env) -> 'a t -> 'a t
       end
 

-Whereas Writer's `sensor` and Reader's `shift` have isomorphic types, there is some extra complextity to Writer's `listen` and `listens`, compared to `ask` and `asks`. What this extra complexity means is that for `Writer`, listening happens only in a local context. You can't `listen` to what got written to the log before you installed your `listen`ing tap. But you can return payloads that are dependent on what you've heard in the local context.
+Whereas Writer's `censor` and Reader's `shift` have isomorphic types, there is some extra complextity to Writer's `listen` and `listens`, compared to `ask` and `asks`. What this extra complexity means is that for `Writer`, listening happens only in a local context. You can't `listen` to what got written to the log before you installed your `listen`ing tap. But you can return payloads that are dependent on what you've heard in the local context.

 
 

-Unlike Reader, Writer also has a `tell` operation, which is akin to the `put` operation in the State monad. The difference is that the `tell` function takes a `log` as argument and *appends* that to the existing `log`. You can't erase or overwrite elements already in the `log`; you can only append to it. However, if you like, you can `censor` the log in arbitrary ways and use that when interpreting other monadic values locally. After that local context, though, we return to the original log (
+Unlike Reader, Writer also has a `tell` operation, which is akin to the `put` operation in the State monad. The difference is that the `tell` function takes a `log` as argument and *appends* that to the existing `log`. You can't erase or overwrite elements already in the `log`; you can only append to it. However, if you like, you can `censor` the log generated by any local context. (Inside the local context, the log isn't yet censored; the censoring only affects what's seen downstream as the contributions made by that context to the log.)

 
 Here's a complex example that illustrates this. First we will use the helper function `String.upper` (from "juli8.ml") and a second helper function that we define like this:
 
 
 Here's a complex example that illustrates this. First we will use the helper function `String.upper` (from "juli8.ml") and a second helper function that we define like this:
 


@@ -157,17 +161,17 @@ Next, we construct some monadic values and reveal them at the end using `run`:
        let zz = tell "before" >> yy >>= fun y -> tell "after" >> mid y in
        ...);;
 
        let zz = tell "before" >> yy >>= fun y -> tell "after" >> mid y in
        ...);;
 

-The monadic value `xx` writes "one" to the log, then discards the resulting `()` payload (it continues `>> ...` rather than `>>= fun var -> ...`). Then we have a use of `listens`. This will evaluate its body `tell "two" >> mid 10` and return as payload a pair of the body's original payload and a bracketed copy of the local log. Thus the payload of `listens bracket (tell "two" >> mid 10)` will be `(10, "{two}")`. The `"one"` that got written to the log earlier isn't accessible to `listens`; however it does stay in the log. Hence the result of `run xx`, showing first the payload and then the log, would be:
+The monadic value `xx` writes `"one"` to the log, then discards the resulting `()` payload (it continues `>> ...` rather than `>>= fun var -> ...`). Then we have a use of `listens`. This will evaluate its body `tell "two" >> mid 10` and return as payload a pair of the body's original payload and a `bracket`ed copy of the local log. Thus the payload of `listens bracket (tell "two" >> mid 10)` will be `(10, "{two}")`. Its log will be `"two"`. The `"one"` that got written to the log earlier isn't accessible to `listens`; however it does stay in the overall log, to which the `listens ...` construction contributes. Hence the result of `run xx`, showing first the payload and then the log, would be:

 
     - : (int * string) W.result = ((10, "{two}"), "one two")
 
 Now `yy` uses that `xx` monadic value to illustrate the use of `censor`. Here we have `censor` apply `String.upper` to the log generated in the local context it's applied to, hence the result of  `run yy` would be:
 
 
     - : (int * string) W.result = ((10, "{two}"), "one two")
 
 Now `yy` uses that `xx` monadic value to illustrate the use of `censor`. Here we have `censor` apply `String.upper` to the log generated in the local context it's applied to, hence the result of  `run yy` would be:
 

-    - : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "ZERO ONE TWO three")
+    - : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "ZERO ONE TWO")

 
 The final value `zz` shows what happens to entries written to the log before and after the `censor`ing that occurs in `yy`, namely nothing. That is, `run zz` is:
 
 
 The final value `zz` shows what happens to entries written to the log before and after the `censor`ing that occurs in `yy`, namely nothing. That is, `run zz` is:
 

-- : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "before ZERO ONE TWO after")
+    - : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "before ZERO ONE TWO after")

 
 Let's look at some more familiar monad signatures. Here is one:
 
 
 Let's look at some more familiar monad signatures. Here is one:
 


@@ -188,7 +192,7 @@ This is what's exposed in the `Monad.Option.M` module (with `Option` and `List`,
 
 If `some_bool_expr` is true, then this will ignore its payload and go on to compute `more_monadic_stuff`; if it's false, then the whole chain gets ignored because of the distinctive behavior of `mzero`.
 
 
 If `some_bool_expr` is true, then this will ignore its payload and go on to compute `more_monadic_stuff`; if it's false, then the whole chain gets ignored because of the distinctive behavior of `mzero`.
 

-The third special operation in the Option monad is `test`. This lets you supply a function that takes an ordinary `'a option` type (that is, one where the "abstraction curtain" imposed by the `'a O.t` type is not in place) and returns a bool. Then you take an Option monadic value (one where the "abstraction curtain" *is* in place). OCaml will temporarily remove the abstraction curtain on the second argument and see how the function you supplied assesses it. If the result is `true`, then the result is identical to that Option monadic value, unaltered. If the result is `false`, then the result is `mzero`. (For those of you who know Frank Veltman's work on dynamic semantics for epistemic modals, this is a key component.)
+The third special operation in the Option monad is `test`. This lets you supply a function that takes an ordinary `'a option` type (that is, one where the "abstraction curtain" imposed by the `'a O.t` type is not in place) and returns a `bool`. Then you take an Option monadic value (one where the "abstraction curtain" *is* in place). OCaml will temporarily remove the abstraction curtain on the second argument and see how the function you supplied assesses it. If the result is `true`, then the result is identical to that Option monadic value, unaltered. If the result is `false`, then the result is `mzero`. (For those of you who know Frank Veltman's work on dynamic semantics for epistemic modals, this `test` (or the version of it for sets of worlds) is a key component.)

 
 Here is the List monadic interface:
 
 
 Here is the List monadic interface: