index ea387b9..e9cf823 100644 (file)
@@ -42,8 +42,13 @@ Instead, we're going to give you almost the complete program, with a few gaps
in it that you have to complete. You have to understand enough to
add the last pieces to make the program function.

in it that you have to complete. You have to understand enough to
add the last pieces to make the program function.

-We're still writing up the (substantial) exposition of this, and will post a link
-to it here soon.
+You can find the skeleton code [[here|/code/untyped_evaluator.ml]].
+
+We've also prepared a much fuller version, that has user-friendly input
+and printing of results. We'll provide a link to that shortly. It
+will be easiest for you to understand that code if you've
+completed the gaps in the simplified skeleton linked above.
+

## Evaluation in the untyped lambda calculus: environments

## Evaluation in the untyped lambda calculus: environments

@@ -61,8 +66,8 @@ since it amounts to evaluating terms relative to an assignment
function. The difference between the substitute-and-repeat approach
above, and this approach, is one huge step towards monads.

function. The difference between the substitute-and-repeat approach
above, and this approach, is one huge step towards monads.

-We're still writing up the exposition of this, too, and will post a link
-to it here soon.
+The skeleton code for this is at the [[same link as before|/code/untyped_evaluator.ml]].
+This part of the exercise is the "V2" part of that code.

@@ -70,18 +75,18 @@ to it here soon.
Mappables (functors), MapNables (applicative functors), and Monads
(composables) are ways of lifting computations from unboxed types into
boxed types.  Here, a "boxed type" is a type function with one unsaturated
Mappables (functors), MapNables (applicative functors), and Monads
(composables) are ways of lifting computations from unboxed types into
boxed types.  Here, a "boxed type" is a type function with one unsaturated
-hole (which may have several occurrences). We can think of the box type
-as a function from a type to a type. Call this type function M, and let P, Q, R, and S be schematic variables over types.
+hole (which may have several occurrences, as in `(α,α) tree`). We can think of the box type
+as a function from a type to a type.

-Recall that a monad requires a singleton function `mid : P-> MP`, and a
-composition operator like `>=> : (P-><u>Q</u>) -> (Q-><u>R</u>) -> (P-><u>R</u>)`.
+Recall that a monad requires a singleton function <code>mid : P-> <u>P</u></code>, and a
+composition operator like <code>&gt;=&gt; : (P-><u>Q</u>) -> (Q-><u>R</u>) -> (P-><u>R</u>)</code>.

As we said in the notes, we'll move freely back and forth between using `>=>` and using `<=<` (aka `mcomp`), which
is just `>=>` with its arguments flipped. `<=<` has the virtue that it corresponds more
closely to the ordinary mathematical symbol `○`. But `>=>` has the virtue
that its types flow more naturally from left to right.

As we said in the notes, we'll move freely back and forth between using `>=>` and using `<=<` (aka `mcomp`), which
is just `>=>` with its arguments flipped. `<=<` has the virtue that it corresponds more
closely to the ordinary mathematical symbol `○`. But `>=>` has the virtue
that its types flow more naturally from left to right.

-Anyway, `mid` and (let's say) `<=<` have to obey the following Monad Laws:
+Anyway, `mid` and (let's say) `<=<` have to obey the Monad Laws:

mid <=< k = k
k <=< mid = k

mid <=< k = k
k <=< mid = k
@@ -102,7 +107,7 @@ suitable for `mid` and `<=<`:
conceptual world neat and tidy (for instance, think of [[our discussion
of Kaplan's Plexy|topics/week6_plexy]]).  As we learned in class, there is a natural monad
for the Option type. Using the vocabulary of OCaml, let's say that
conceptual world neat and tidy (for instance, think of [[our discussion
of Kaplan's Plexy|topics/week6_plexy]]).  As we learned in class, there is a natural monad
for the Option type. Using the vocabulary of OCaml, let's say that
-"`'a option`" is the type of a boxed `'a`, whatever type `'a` is.
+`'a option` is the type of a boxed `'a`, whatever type `'a` is.
More specifically,

type 'a option = None | Some 'a
More specifically,

type 'a option = None | Some 'a
@@ -114,8 +119,8 @@ More specifically,
Show that your composition operator obeys the Monad Laws.

2.  Do the same with lists.  That is, given an arbitrary type
Show that your composition operator obeys the Monad Laws.

2.  Do the same with lists.  That is, given an arbitrary type
-`'a`, let the boxed type be `['a]` or `'a list`, that is, lists of objects of type `'a`.  The singleton
-is `\p. [p]`, and the composition operator is:
+`'a`, let the boxed type be `['a]` or `'a list`, that is, lists of values of type `'a`.  The `mid`
+is the singleton function `\p. [p]`, and the composition operator is:

let (>=>) (j : 'a -> 'b list) (k : 'b -> 'c list) : 'a -> 'c list =
fun a -> List.flatten (List.map k (j a))

let (>=>) (j : 'a -> 'b list) (k : 'b -> 'c list) : 'a -> 'c list =
fun a -> List.flatten (List.map k (j a))