add sentence about Identity Monad
[lambda.git] / topics / week3_unit.mdwn
index e722e8f..548a58d 100644 (file)
@@ -1,48 +1,50 @@
-What is `()`?
-=============
+[[!toc]]
 
-Recall the notion of "data structures" discussed at the end of this week's [[further notes on lists|week3 lists#v5-lists]]. Our (first model of) "cmyg-colors" included four variants, three of which had no parameters and the last of which had two number parameters (one for *brightness* and another for *glossiness*). (Subsequently, we altered this to replace one of those parameters with another cmyg-color; but for present purposes let's stick with the first model.)
+What is *unit*?
+===============
 
-In the other notes, we discussed how to encode such data structures in the Lambda Calculus. Now let's consider another notation that's sometimes used to talk about them. We might express the data structure just described like this:
+Recall the notion of **data structures** discussed at the end of this week's [[further notes on lists|week3 lists#v5-lists]]. Our (first model of) "cmyg-colors" included four **variants**, three of which had no **parameters** and the last of which had two number parameters (one for *brightness* and another for *glossiness*). (Subsequently, we altered this to replace one of those parameters with another cmyg-color; but for present purposes let's stick with the first model.)
+
+In the other notes, we discussed how to encode such data structures in the Lambda Calculus. Now let's consider another notation that's sometimes used to talk about them. We might describe such data structures like this:
 
     CMYG_color = Cyan () | Magenta () | Yellow () | Gray (Number, Number)
 
-The component `Cyan ()` says this is one variant, that we will associate with the *tag* `Cyan`, and this variant has no parameters. Here we write that as `()`, for better consistency with the final case where the variant has multiple parameters, but different notational conventions, such as omitting the `()`, would also be possible. The final component `Gray (Number, Number)` says the last variant is associated with the tag `Gray`, and also specifies that this variant has two parameters, and that we expect each of them to be a number. The vertical bar `|` is just a syntactic separator, like a comma.
+The component `Cyan ()` says here is one variant, that we will associate with the *tag* `Cyan`, and this variant has no parameters. Here we write that as `()`, for better consistency with the final case where the variant has multiple parameters, but different notational conventions, such as omitting the `()`, would also be possible. The final component `Gray (Number, Number)` says the last variant is associated with the tag `Gray`, and also specifies that this variant has two parameters, and that we expect each of them to be a number. The vertical bar `|` is just a syntactic separator, like a comma.
 
-These "tags" are also called "constructors", or more specifically "data constructors". (Later we will encounter other kinds of constructors. But "constructor" without any modifiers or special context can be assumed to mean these things.) The reason they are called that is that the way to specify some *instance* of this data structure is to write things like:
+These "tags" are also called **constructors**, or more specifically "data constructors". (Later we will encounter other kinds of constructors. But "constructor" without any modifiers or special context can be assumed to mean these things.) The reason they are called that is that the way to specify *some instance* of this data structure is to write:
 
     Cyan ()
     Gray (5, 0)
 
-These may look like function applications, but they're not. They're canonical "constructions" of those instances of the data structure. Notice that in the `Gray` case, we construct an instance using specific numbers; whereas in the specification of the data structure itself, we used not specific numbers but instead the general type `Number`.
+These may look like function applications, but they're not. They're canonical *constructions* of those instances of the data structure. Notice that in the `Gray` case, we construct an instance using specific numbers; whereas in the description of the data structure itself, we used not specific numbers but instead the general type `Number`.
 
-(Here too other conventions would be possible, such as, again, omitting the `()` after the `Cyan`. Here we follow the general conventions of Haskell and OCaml in capitalizing the alphabetic names of constructors; whereas, on the other hand, variables bound to functions begin with lowercase letters. In fact, in both languages there are also some constructors written outside this convention. Our friends that we express in Kapulet as `[]` and `&` can be thought of as constructors, too. Haskell expresses those as `[]` and `:` and OCaml as `[]` and `::`. Also, as we said in the other notes, we might think of the boolean truth-values as variants in a data structure. Following the conventions here, the most consistent nomenclature would then be to designate them `True ()` and `False ()`. Haskell sort-of does that, but omits the `()`. OCaml also omits the `()` and in this unique case has the variants be expressed all lower-case rather than capitalized.)
+(Here too other conventions would be possible, such as, again, omitting the `()` after the `Cyan`. Here we also follow the general convention of Haskell and OCaml in capitalizing the alphabetic names of constructors; whereas, on the other hand, variables bound to functions begin with lowercase letters. In fact, in both languages there are also some constructors written outside this convention. Our friends that we express in Kapulet as `[]` and `&` can be thought of as constructors, too. Haskell expresses those as `[]` and `:` and OCaml as `[]` and `::`. Also, as we said in the other notes, we might think of the *boolean truth-values* as variants in a data structure. Following the conventions here, the most consistent nomenclature would then be to designate them `True ()` and `False ()`. Haskell sort-of does that, but omits the `()`. OCaml also omits the `()` and in this unique case expresses the variants all lower-case rather than capitalized.)
 
 We will be working with all these ideas more in later weeks.
 
-We said that it is also possible to think of triples as a data structure, that has only one variant with three parameters. We could express that in Kapulet like this:
+We said that it is possible to think of *triples* as a data structure, too, that has only one variant with three parameters. We could describe that in Kapulet like this:
 
     ... = Triple (Number, Number, Boolean)
 
-Here I just chose specific types for the three parameters. In later weeks we'll see ways to describe triples more generally, without pre-committing to such specific types. We could also write this in Kapulet:
+Here I just chose specific types for the three parameters. In later weeks we'll see ways to describe triples more generally, without pre-committing to such specific types. We could also write the following in Kapulet:
 
     ... = Trio (Number, Number, Boolean)
 
-and if we had both of these, these two data structures would be regarded as distinct, even though they are exactly isomorphic. I mention this only so that you have some idea of why we're choosing the names we are for the variants. The answer is: No reason, it's arbitrary. Different names for the variants would give us distinct but completely isomorphic structures. Let's move on.
+and if we had both of those, they'd be two distinct data structures, even though they are exactly isomorphic. I mention this only so that you have some idea of why we're choosing the names we are for the variants. The answer is: No reason, it's arbitrary. Different names for the variants would give us distinct but completely isomorphic structures.
 
-Now what about a data structure that has only one variant, that takes *no* parameters. We could express that like this:
+Now what about a data structure that has only one variant, that takes *no* parameters. We could describe that like this:
 
     ... = Unit ()
 
-"Unit" is a standard name for this data structure, for the reason that there can be only one instance of the whole structure. In the case of the Boolean structure, there are two possibilities, and in the case of triples, there are as many possibilities as there are choices of the three parameters. But here there is only one possibility. It may be hard to conceive in advance how or why such a data structure could be useful. But we will see that it is.
+"Unit" is a standard name for this data structure, for the reason that there can be only one instance of the whole structure. In the case of the Boolean structure, there are two possibilities, and in the case of Triples, there are as many possibilities as there are choices of the three parameters. But here there is only one possibility. It may be hard to conceive in advance how or why such a data structure could be useful. But we will see that it is.
 
-In various programming contexts, the word `void` is sometimes used, with varying meanings. A fair portion of those meanings overlap with the notion we're here calling *unit*. (Though the correspondence isn't perfect or complete.)
+In various programming contexts, the word "void" is sometimes used, with varying meanings. Some of those meanings overlap with the notion we're here calling *unit*. (Though the correspondence isn't perfect or complete.)
 
-So those are two notions in Kapulet: triples, instances of which we specify as `Triple (5, 0, 'false)` (or maybe it should be `Triple (5, 0, False ())`), and unit(s), instance(s) of which can only be specified as `Unit ()`.
+So, there are two notions in Kapulet: triples, instances of which we specify as `Triple (5, 0, 'false)` (or maybe it should be `Triple (5, 0, False ())`), and unit(s), instance(s) of which can only be specified as `Unit ()`.
 
-As we've mentioned before, though, Kapulet also has parallel, lighter-weight versions of these. In the length-three case there is just the syntax for supplying three arguments at once to an uncurried function, as in `f (5, 0, 'false)`. In the length-zero case we might have instead just `f ()`. (Again, it may be hard to conceive in advance how or why we'd apply a function to no arguments; but read on.) Indeed, it looks like something of the same sort is also going on in our notation `Triple (5, 0, 'false)` and so on.
+As we've observed before, though, Kapulet also has parallel, *lighter*-weight notion of a tuple or multi-value. In the length-three case, we have the syntax for supplying three arguments at once to an uncurried function, as in `f (5, 0, 'false)`. In the length-zero case we might say instead just `g ()`. (Again, it may be hard to conceive in advance how or why we'd apply a function to no arguments; but read on.) Indeed, it looks like something of the same sort is also going on in our notation `Triple (5, 0, 'false)` and so on.
 
-It is conceptually helpful to separate some different ideas here, which is why Kapulet has these different notions. One difference is that only the "heavier-weight" triple is a single value that can be bound to a single value. So you can do this:
+It's conceptually helpful to separate some different ideas here, which is why Kapulet has these different notions. One difference is that only the heavier-weight triple is a single value that can be bound to a single variable. So you can do this:
 
     let
       x match Triple (5, 0, 'false)
@@ -64,7 +66,7 @@ A second, related difference comes up when we consider how these different thing
 
     Pair (Triple (5, 0, 'false), 12)
 
-that Triple is just another value that occupies the first position in the Pair, in the same that the number `12` occupies the second position. You could also have sequences or sets of these Triples.
+that Triple is just another value that occupies the first position in the Pair, in the same that the Number `12` occupies the second position. You can also have sequences or sets of such Triples.
 
 On the other hand, you can't say:
 
@@ -84,27 +86,25 @@ and those would mean the same as:
 
     Quadruple (5, 0, 'false, 12)
 
-Similarly, `Quadruple (5, 0, 'false, (), 12)` would also mean the same; though again you may not be able to imagine cases where it's useful to write it in that longer form. On the other hand, you could not say `Quadruple (5, 0, 'false, Unit (), 12)`, because that would be trying to construct a quadruple out of *five* values.
+Similarly, `Quadruple (5, 0, 'false, (), 12)` would also mean the same; though again you may not be able to imagine cases where it's useful to write it in that longer form. On the other hand, you could not say `Quadruple (5, 0, 'false, Unit (), 12)`, because that would be trying to construct a *quad*ruple out of *five* values.
 
-As I said, there is some conceptual benefit to having both the heavy-weight and the light-weight notion of a triple, and the notions of `Unit ()` versus `()` are the corresponding, limiting cases of these. What we will discuss below about the ways in which `()` could be useful really applies to *both* of Kapulet's `Unit ()` and Kapulet's `()`. It's just that which of these notions you focus on will affect how you conceptualize what's going on. If I say:
+As I said, there is some conceptual benefit to having both the heavyweight and the lightweight notion of a triple, and the notions of `Unit ()` versus `()` are the corresponding, limiting cases of these. Our discussion below of the ways in which *unit* could be useful really applies to *both* of Kapulet's `Unit ()` and Kapulet's `()`. It's just that which of these notions you focus on will affect how you conceptualize what's going on. If I say:
 
-    f ()
+    g ()
 
-in Kaupulet, we should think of that as *applying* the function `f` somehow, but to no arguments. That's an odd idea; how is it different from just the function `f` unapplied? We'll discuss this below. On the other hand, if I say:
+in Kapulet, we should think of that as *applying* the function `g` somehow, but to no arguments. That's an odd idea; how is it different from just the function `g` unapplied? We'll discuss this below. On the other hand, if I say:
 
-    g (Unit ())
+    h (Unit ())
 
-we should think of that as applying the function `g` to a single argument, only here it is an argument that is the only possible instance of its data structure. This might seem more comprehensible than `f ()`, but if we can assume that `g` only accepts arguments from the data structure to which `Unit ()` belongs, it really ought to be just as puzzling. If there's only possible argument that `g` accepts, then again, how or why should applying `g` to that argument be different from just the function `g` unapplied. Indeed, in logic settings this is sometimes how we model *constants*: as functors from singleton domains.
+we should think of that as applying the function `h` to a single argument, only here it is an argument that is the only possible instance of its data structure. This might seem more comprehensible than `g ()`, but if we can assume that `h` only accepts arguments from the data structure to which `Unit ()` belongs, it really ought to be just as puzzling. If there's only possible argument that `h` accepts, then again, how or why should applying `h` to that argument be different from just the function `h` unapplied. Indeed, in logic settings this is sometimes how we model *constants*: as functors from singleton domains.
 
 So we have yet to get a good sense of the usefulness of *unit*. But in Kapulet at least we're getting some handle on how to manipulate and talk about it/them.
 
 
-() in Other Languages
-=====================
-
-Other programming languages make the picture messier.
+Other programming languages make the picture messier
+====================================================
 
-Haskell isn't so bad. In Haskell the story is simple: there Kapulet's `()` and `(5, 0, 'false)` are not part of the language; only Kapulet's `Unit ()` and `Triple (5, 0, 'false)` are. Awkwardly, though, the way Haskell *expresses* the latter two notions is like this:
+Haskell isn't so bad. In Haskell the story is simple: Kapulet's `()` and `(5, 0, 'false)` are not part of the language; only Kapulet's `Unit ()` and `Triple (5, 0, 'false)` are. Awkwardly, though, the way Haskell *expresses* the latter two notions is like this:
 
     -- Haskell
     ()
@@ -112,7 +112,7 @@ Haskell isn't so bad. In Haskell the story is simple: there Kapulet's `()` and `
 
 Still, it is just using the same notions Kapulet expresses more verbosely.
 
-In OCaml, things are somewhat like they are in Haskell. The primary notions are Kapulet's heavier-weight tuples, and they are expressed using sparer syntax:
+In OCaml, things are somewhat as in Haskell. The primary notions are Kapulet's heavier-weight tuples, and they are expressed using sparer syntax:
 
     (* OCaml *)
     ()
@@ -120,7 +120,7 @@ In OCaml, things are somewhat like they are in Haskell. The primary notions are
 
 But there are a few odd quirks in OCaml that only make sense if you posit a tacit distinction between these tuples and a notion like Kapulet's lighter-weight tuples (for which OCaml has no explicit syntax). I don't want to detail those quirks now; I'm just saying they are there.
 
-Scheme is the most complicated.
+Scheme is much more complicated.
 
 Firstly, Scheme does have notions that systematically parallel Kapulet's lighter-weight tuples. What Kapulet writes as:
 
@@ -140,17 +140,17 @@ most closely corresponds in Scheme to:
 
     (lambda (x) (values x 0 #f))
 
-Following this pattern, Kapulet's `()` most closely corresponds to Scheme's `(values)`. Scheme's `(values 5)` evaluates the same as just the simple `5` (as does Kapulet's `(5)`).
+Following this pattern, Kapulet's `()` most closely corresponds to Scheme's `(values)`. Scheme's `(values 5)` evaluates the same as just bare `5` (as does Kapulet's `(5)`).
 
-Scheme's handling of these multiple-value returns is not completely and smoothly integrated into the language though. In later versions of the Scheme standard, they are better-integrated, and there are common extensions to make things even smoother, but it's still not perfect. You can't write things like this:
+Scheme's handling of these multi-value returns is not completely and smoothly integrated into the language though. In later versions of the Scheme standard, they are better-integrated, and there are common extensions to make things even smoother, but it's still not perfect. You can't write things like this:
 
     (f (values 5 0) #f)
 
-and expect it to work the same as `(f 5 0 #f)`. Chicken will just use the first value, `5`, and discard any subsequent values. Racket will instead complain, that you have it two values in a place where it was expecting only one. So although these light-weight multi-values exist in Scheme, they are only occasionally used.
+and expect it to work the same as `(f 5 0 #f)`. Chicken will just use the first value, `5`, and discard any subsequent values. Racket will instead complain, that you gave it two values in a place where it was expecting only one. So although these lightweight multi-values exist in Scheme, they are only occasionally used.
 
-Instead, Scheme generally works with heavier-weight collections. But which ones? Let's focus on triples first (or really any *n*-tuple, for *n* at least two), where the answer is already complex. It becomes even moreso in the case of unit(s).
+Instead, Scheme generally works with heavier-weight collections. But which ones? Let's focus on triples first (or really any *n*-tuple, for *n* at least two), where the answer is already complex. It will become even more so in the case of unit(s).
 
-Scheme has two parallel notions for expressing longer *n*-tuples. The more straightforward one is called a *vector*. You can build a vector in Scheme like this:
+Scheme has two parallel notions for expressing longer *n*-tuples. The more straightforward one is called a **vector**. You can build a vector in Scheme like this:
 
     (vector 5 0 #f)
 
@@ -158,13 +158,14 @@ and Scheme will display the result like this:
 
     #(5 0 #f)
 
---- perhaps with a further single-quote prefix, depending on your configuration. It's also possible to specify a vector using that latter syntax. Vectors are like tuples in Kapulet, Haskell, and OCaml, in that their different elements can be of heterogenous types. They are like Kapulet's heavy-weigh tuples in that they can be assigned to single variables, can be discrete elements in other structures, including other vectors, and so on. Scheme vectors are *unlike* the tuple structures in the other languages in that they are usually *mutable*: one and numerically the same vector container can contain different elements at different stages in the program's evaluation. But some Scheme implementations also have immutable vectors.
+--- perhaps with a further single-quote prefix, depending on your configuration. It's also possible to specify a vector using that latter syntax. Vectors are like tuples in Kapulet, Haskell, and OCaml, in that their different elements can be of heterogenous types. They are like Kapulet's heavyweight tuples in that they can be assigned to single variables, can be discrete elements in other structures, including other vectors, and so on. Scheme vectors are *unlike* the tuple structures in the other languages in that they are usually *mutable*: one and numerically the same vector container can contain different elements at different stages in the program's evaluation. But some Scheme implementations also have immutable vectors.
 
-The other notion in Scheme for expressing longer *n*-tuples is what I'll call the possibly-improper list, or *imp*. (This isn't standard Scheme terminology; I think it's conceptually cleaner to start here and work your way forward to the standard Scheme ways of talking.) I won't say yet how you tell Scheme to construct an imp, but they are displayed like this:
+<a id=imp></a>
+The other notion in Scheme for expressing longer *n*-tuples is what I'll call the possibly-improper list, or **imp**. (This isn't standard Scheme terminology. I think it's conceptually cleaner to start here and work your way toward the standard Scheme ways of talking.) I won't say yet how you tell Scheme to construct an imp, but they are displayed like this:
 
     (5 0 . #f)
 
-Again, perhaps with a further single-quote prefix, depending on your configuration. In the special case where the imp is of length 2, these are called "dotted pairs":
+--- or perhaps with a further single-quote prefix, depending on your configuration. In the special case where the imp is of length two, these are called **dotted pairs**:
 
     (0 . #f)
 
@@ -177,13 +178,13 @@ specifies the same length-three imp displayed above. However, if you try this:
     (let* ((x 5))
           '(x 0 . #f))
 
-you won't get the same thing. Instead, you'll get a triple whose first element is the *symbol* `'x`. Similarly, if you try this:
+you won't get the same thing. Instead, you'll get a length-three imp whose first element is the *symbol* `'x`. Similarly, if you try this:
 
     '(5 (- 3 y) . #f)
 
-you won't get an imp whose second element is `0`, even when the variable `y` is bound to the value `3`. Instead, you'll get an imp whose second element is *another imp*, that begins with the symbol `'-` and continues with the number 3.
+you won't get an imp whose second element is `0`, even when the variable `y` is bound to the value `3`. Instead, you'll get an imp whose second element is *another imp*, that begins with the symbol `'-` and continues with the number `3`.
 
-(By the way, in all of these languages the initial position in a sequence is called position 0, the next position 1, and so on. Some languages start counting from 0, others start counting from 1. Nowadays, most do the former. When we use English ordinals, though, we will always use "first" to mean the initial position.)
+(By the way, in all of these languages the initial position in a sequence is called position 0, the next position 1, and so on. Some languages start counting from 0, others start counting from 1. Nowadays, most do the former. When we use English ordinals in these web pages, though, we will always use "first" to mean the initial position.)
 
 If you try to write simply:
 
@@ -195,21 +196,23 @@ There are important semantic generalities about how Scheme works that underwrite
 
     '(- 3 y)
 
-might be, depending on your configuration, displayed as:
+might, depending on your configuration, be displayed as:
 
     (- 3 y)
 
-But if you submit that expression to Scheme, it gets evaluated to the result of applying the subtraction function (or whatever function `-` is bound to, you can rebind it) to the arguments `3` and whatever value the variable `y` is then bound to. What is going on here is that the Scheme expression most recently displayed is itself an imp. Scheme doesn't think of its programs as flat strings of characters. It thinks of them as already parsed into imps that contain numbers, symbols, and other imps. (You can think of these possibly deeply-embedded imps as representing syntax trees.) Asking Scheme to *evaluate* such an imp means for it to apply the function value it gets by evaluating the imp's head, if there be such, to the values it gets by evaluating the other elements in the imp. When you instead specify to Scheme the *quoted* form:
+But if you submit *that, unquoted* expression to Scheme, it gets *evaluated* to the result of *applying* the subtraction function (or whatever function `-` is bound to, you can rebind it) to the arguments `3` and whatever value the variable `y` is then bound to. What is going on here is that the Scheme expression being evaluated is *itself* an imp. Scheme doesn't think of its programs as flat strings of characters. It thinks of them as already parsed into imps that contain numbers, symbols, and other imps. (You can think of these possibly deeply-embedded imps as constituting syntax trees.) Asking Scheme to *evaluate* such an imp means for it to apply the function value it gets by evaluating the imp's head, if there be such, to the values it gets by evaluating the other elements in the imp. When you instead specify to Scheme the *quoted* form:
 
     '(- 3 y)
 
 that refers to *the imp itself*, rather than to the result of evaluating it in the way just described. Now you see why we call this "quotation", and use the symbol we do for it. You might also see the relation between the *symbol* `'y` (or just `y` when it occurs embedded in the quoted imp above, or even more deeply embedded, as in `'(5 (- 3 y) . #f)`) and the *variable* `y`. For Scheme, symbols just *are* variables, only not yet evaluated. That's why we write the symbol with an initial single-quote.
 
-The major difference in Scheme between vectors and imps is that imps have this special relation to Scheme's own syntax. Scheme treats its code as itself being a complex imp, not as being a complex vector. Another difference is that under the hood, the computer implements vectors and imps differently. Vectors store all of their elements in a contiguous block of memory (an "array"), whereas imps may store them scattered all over the place (as a "linked list"). On early computing hardware, the latter was oftentimes more useful; on contemporary hardware, it's much less so. But neither vectors nor imps are closer models of (heavy-weight) tuples in Kapulet, OCaml, and Haskell than the other. They can both contain type-heterogenous elements, including other vectors and/or imps. Like vectors, but unlike the structures in other languages, imps in Scheme are by default mutable. But many implementations also offer immutable imps.
+<!-- TODO Explain that `(let* ((x 1) (y 'x)) y)` evaluates to the symbol/unevaluated variable `'x` (it might also be displayed as `x`: different Schemes have different display conventions), not to the number value `1`. But you can explicitly request that Scheme evaluate that symbol, as in `(let* ((x 1) (y 'x)) (eval y))` which will evaluate to `1`. -->
 
-Okay, that's the story about longer Scheme containers you should first get your head around. We'll talk about shorter containers, including unit(s), in a moment. I've used idiosyncratic language in talking about these "imp"s, though, and I've suppressed some complications that we should now consider.
+The major difference in Scheme between vectors and imps is that imps have this special relation to Scheme's own syntax. Scheme treats its code as itself being complex imps, not as being complex vectors. Another difference is that under the hood, the computer implements vectors and imps differently. Vectors store all of their elements in a contiguous block of memory (an "array"), whereas imps may store them scattered all over the place (as a "linked list"). On early computing hardware, the latter was often-times more useful; on contemporary hardware, it's much less so. But neither vectors nor imps are closer models of (heavyweight) tuples in Kapulet, OCaml, and Haskell than the other. They can both contain type-heterogenous elements, including other vectors and/or imps. Like vectors, but unlike the structures in other languages, imps in Scheme are by default mutable. But many implementations also offer immutable imps.
 
-One complication is that in the special case where the final element in an imp is Scheme's empty list --- that we can specify as `(list)` or `'()` or in some implementations as `null` (with no surrounding parentheses) --- in that case Scheme calls the imp a *(proper) list*. (Hence my term *possibly improper* list for the general notion.) And in that case the list can be written, not only as:
+Okay, that's the story you should first get your head around about longer Scheme containers. We'll talk about shorter containers, including unit(s), in a moment. But I've used idiosyncratic language in talking about these "imp"s, and I've suppressed some complications, which we should now consider.
+
+One complication is that in the special case where the final element in an imp is Scheme's empty list --- that we can specify as `(list)` or `'()` or in some implementations as `null` (with no surrounding parentheses) --- in that case Scheme calls the imp a *(proper) list*. (Hence my term *possibly-improper* list for the general notion.) And in that case the list can be written, not only as:
 
     '(- 3 y . ())
 
@@ -219,38 +222,36 @@ but also as:
 
 with no `.` and final element. The lack of a `.` and final element means that the imp's final element is the empty list, and that this *possibly* improper list is in fact proper. So what Scheme calls its "lists" are in fact a special case of one of its equally-good candidates (vectors and imps) to be identified with Kapulet's, OCaml's, and Haskell's tuples. Scheme doesn't make the sharp distinction between tuples and lists that the other languages do.
 
-A second complication is that FIXME embedded pairs, `cons`.
-
-We asked before how you specify an imp. We've seen one notation, using an initial single-quote. That works if you're ready to construct the imp without the help of any variables. But if you want to use variables, what should you do? (There is in fact a variation on quotation, called *quasi-quotation* and using the initial prefix <code>`</code> rather than `'` that you could use; but I'm not going to explain that.) If you want to build a *proper* imp, that is, a Scheme list, you can instead use the function/constructor `list`:
+We asked before how you specify an imp. We've seen one notation, using an initial single-quote. That works if you're ready to construct the imp without the help of any variables. But if you want to use variables, what should you do? (There is in fact a variation on quotation, called *quasi-quotation* and using the initial prefix <code>\`</code> rather than `'` that you could use; but I'm not going to explain that.) If you want to build a *proper* imp, that is, a Scheme list, you can instead use the function/constructor `list`:
 
     (list '- 3 y)
 
 returns the imp whose first member is the symbol `'-` (if you left the quote off, you would instead get the function that this symbol is bound to), whose second member is the number 3, whose third value is whatever value the symbol/variable `y` is bound to, and whose final value is the empty list.
 
-What if you want to instead build an *improper* imp, such as `(5 0 . y)`, again using the value `y` is bound to rather than the quoted symbol? There is no form in standard Scheme to do this *directly*. But many Scheme implementations do have a special function for doing this. Racket calls it `list*`, so if you write in Racket:
+What if you want to instead build an *improper* imp, such as `(5 0 . y)`, again using the value `y` is bound to rather than the quoted symbol? There is no function in *standard* Scheme to do this *directly*. But many Scheme *implementations* do have a special function for it. Racket calls it `list*`, so if you write in Racket:
 
     (let* ((y #f))
-          (cons* 5 0 y))
+          (list* 5 0 y))
 
 You will get the imp whose first member is `5`, whose second member is `0`, and whose final member is `#f` (*not* the symbol `'y`).
 
 Other Scheme implementations that provide this function call it `cons*`, for reasons that will become clearer in a moment.
 
-I said there was no form in *standard* Scheme to do this *directly*. You can however do it indirectly, and the reason why brings us to our last complication about Scheme imps. This is that in fact, Scheme imps of length greater than two are really all built up out of embedded "dotted pairs" (that is, imps of length two). The length-three imp `'(5 0 . #f)` is really implemented in Scheme as a length-two imp, whose first member is `5`, and whose second member is *another* length-two imp, whose first member is `0` and whose second member is `#f`. It could also be written as `'(5 . (0 . #f))`. (This is *not* the same as the imp `'((5 . 0) . #f)`.) Moreover, standard Scheme *does* have a function/constructor to build the simplest, dotted-pair case of imps. And what it calls this operation is `cons`. Yes, the same name we were using to pronounce our list constructor in the other languages. `cons` does play that role in Scheme, too, given the way that Scheme in fact implements (what it calls) lists. If `ys` is bound to one proper list, of any finite length, and `y` is bound to any value, then `(cons y ys)` will build a new dotted-pair that has these values as elements, and given how Scheme implements proper lists, that just is the longer list whose head is `y`'s value and whose tail is `ys`'s value.
+I said there was no form in *standard* Scheme to do this *directly*. You can however do it indirectly, and the reason why brings us to our last complication about Scheme imps. This is that in fact, Scheme imps of length greater than two are really all built up out of embedded "dotted pairs" (that is, imps of length two). The length-three imp `'(5 0 . #f)` is really implemented in Scheme as a length-two imp, whose first member is `5`, and whose second member is *another* length-two imp, whose first member is `0` and whose second member is `#f`. It could also be written as `'(5 . (0 . #f))`. (This is *not* the same as the imp `'((5 . 0) . #f)`.) Moreover, standard Scheme *does* have a function/constructor to build the simplest, "dotted pair" case of imps. And what it calls this operation is `cons`. Yes, the same name we were using to pronounce our list constructor in the other languages. `cons` does play the list constructor role in Scheme, too, given the way that Scheme in fact implements (what it calls) lists. If `ys` is bound to one proper list, of any finite length, and `y` is bound to any value, then `(cons y ys)` will build a new dotted pair that has those values as elements, and given how Scheme implements proper lists, that *just is* the longer list whose head is `y`'s value and whose tail is `ys`'s value.
 
-The function that Scheme uses to extract the first element of a dotted-pair (and so also to extract the head of a proper or improper list) is `car`; the function it uses to extract the second element of a dotted-pair (and so also the tail of a proper list) is `cdr`. The reasons for these funny names are historical.
+The function that Scheme uses to extract the first element of a dotted pair (and so also to extract the head of a proper or improper list) is `car`; the function it uses to extract the second element of a dotted pair (and so also the tail of a proper list) is `cdr`. The reasons for these funny names are historical.
 
-If you grew up learning functional programming and list manipulation from Scheme, all these complexities might seem natural to you, and might shape the way you think about notions like *list* and *ordered pair*. Scheme is a great language, but that would be unfortunate. Conceptually, these quirks about scheme are something of a hack. I think you get a better understanding of the conceptual terrain from the other functional programming languages, and by beginning to think about Scheme's lists and dotted-pairs by starting with the notion of a possibly-improper list, rather than the other way around. Most texts teaching Scheme will go in the other direction, though.
+If you grew up learning functional programming and list manipulation from Scheme, all these complexities might seem natural to you, and might shape the way you think about notions like *list* and *ordered pair*. Scheme is a great language, but that would be unfortunate. Conceptually, these quirks about Scheme are something of a hack. I think you get a better understanding of the conceptual terrain from the other functional programming languages, and by beginning to think about Scheme's lists and dotted pairs by starting with the notion of a *possibly-improper* list, rather than the other way around. Most texts teaching Scheme will go in the other direction, though.
 
 Okay, all of that was just us getting clear about Scheme's *longer* containers, of length at least two. What about the shorter containers?
 
-Scheme does have vectors of length one: you can write `(vector 5)` or `#(5)`. And that will be distinct from the number `5`. Kapulet is similar: we could have a heavy-weight one-tuple, perhaps `Single 5` (or `Single (5)`, the parentheses make no difference when they contain exactly one syntactic atom), that would be distinct from the number `5`. But there is no difference among light-weight tuples. In Kapulet, `(5)` and `5` would just be notational variants for the number. Although OCaml and Haskell for the most part have tuples corresponding to Kapulet's heavy-weight tuples, in this case they do not. Some subtleties aside, they don't have any one-tuple `(5)` that's distinct from mere `5`.
+Scheme does have vectors of length one: you can write `(vector 5)` or `#(5)`. And that will be distinct from the number `5`. Kapulet is similar: we could have a heavyweight one-tuple, perhaps `Single 5` (or `Single (5)`, the parentheses make no difference when they contain exactly one syntactic atom), that would be distinct from the number `5`. But there is no difference among lightweight tuples. In Kapulet, `(5)` and `5` would just be notational variants for the number. Although OCaml and Haskell for the most part have tuples corresponding to Kapulet's heavyweight tuples, in this case they do not. Some subtleties about their type systems aside, they don't have any native one-tuple `(5)` that's distinct from mere `5`.
 
-Scheme doesn't have any *imps* of length one, because it builds its imps out of dotted-pairs, so they can't get any smaller than length two.
+Scheme doesn't have any *imps* of length one, because it builds its imps out of dotted pairs, so they can't get any smaller than length two. (Some Schemes do have a separate notion of a *box*, which is isomorphic to vectors of length one.)
 
-Now how about unit(s)? Here again, Scheme has vectors of that length: you can write `(vector)` or `#()`. And that will in many ways correspond to the heavy-weight Kapulet length-zero tuple `Unit ()`. And here too, there can be no imps that are this short.
+Now how about unit(s)? Here again, Scheme has vectors of that length: you can write `(vector)` or `#()`. And that will in many ways correspond to the heavyweight Kapulet length-zero tuple `Unit ()`. Here too, there can be no imps that are this short.
 
-But at this point Scheme has *yet another* special value, that in Scheme documentation is usually called *void*. And in many Scheme implementations, there is a special function that generates this value, expressed as `void`. You can call this function with zero or more arguments; they will all be ignored and you will get the special *void* value as a result. Generally Scheme doesn't display this value, if you say:
+But at this point Scheme has *yet another* special value, that in Scheme documentation is usually called *void*. And in many Scheme implementations, there is a special function that generates this value, expressed as `void`. You can apply this function to zero or more arguments; they will all be ignored and you will get the special *void* value as a result. Generally Scheme doesn't display this value. If you say:
 
     (void)
 
@@ -259,18 +260,18 @@ or:
     (let* ((x (void)))
           x)
 
-your Scheme interpreter will probably just not display anything, not even a blank line. If you say this, however:
+your Scheme interpreter will probably just not show any result, not even a blank line. If you wrote this, however:
 
     (display x)
 
-it might say `#<void>` or `#<unspecified>`.
+it might have shown `#<void>` or `#<unspecified>`.
 
-Even if your Scheme implementation lacks the `void` function, though --- as the official standard permits it to do --- you can still generate these special values in some ways. One example is if a `cond` expression has no `else` clause, but none of the clauses that are supplied fail. So this will also generate the special *void* value:
+Even if your Scheme implementation lacks the `void` function, though --- as the official standard permits it to do --- you can still generate the special *void* value in other ways. One example is if a `cond` expression has no `else` clause, but none of the clauses that *are* supplied succeed. So this will also generate the special *void* value:
 
     (cond
       (#f 'impossible))
 
-Pulling this all together, finally: Scheme has two heavy-weight values corresponding to Kapulet's `Unit ()`, namely its length-one vector (expressible as `(vector)` or `#()`) and its special *void* value (expressible in various ways). It has two heavy-weight values corresponding to Kapulet's `Triple (0, 5, #f)`, namely a length-three vector and a length-three imp. Corresponding to the *light-weight* Kapulet tuples or multi-values are the Scheme idioms:
+Ok. Let's pull this all together. Scheme has two heavyweight values corresponding to Kapulet's `Unit ()`, namely its length-zero vector (expressible as `(vector)` or `#()`) and its special *void* value (expressible in various ways). It has two heavyweight values corresponding to Kapulet's `Triple (0, 5, #f)`, namely a length-three vector and a length-three imp. Corresponding to the *lightweight* Kapulet tuples or multi-values are the Scheme idioms:
 
     ; when calling Scheme functions
     (f 0 5 #f)
@@ -285,3 +286,93 @@ and:
 I told you the correspondences between all these languages was complex. But now, finally, you should have some handle on how to manipulate and talk about unit(s) in languages besides Kapulet. We still have to figure out what these are good for.
 
 
+Using *unit* as a parameter in a data structure
+===============================================
+
+As I mentioned in class, you might sometimes want to use *unit* as a parameter to some existing data structure. For instance, sequences or lists are data structures that have one variant `[]` with no parameters, and a second variant with both a head parameter and a tail parameter that has to be another list. What is the head parameter? Well, in some cases it might be a Number, or a Boolean, or another atomic symbol. Or even a function. But in some cases we might not care about the specific identity of the head. We might only care about the list structure. (For lists, all there is to their structure is their *length*. For other structures, their structure might be more complex and encode more information.) We *could* just make a list of Numbers, and ignore the identity of the particular Numbers used. But it's ugly to make arbitrary choices about which Numbers to use, when we really don't care. It can also mislead readers of our code about how the code works. If we want to specify clearly that we don't care about the identity of the head element, we could instead make it a list of *Units*, where there is only ever one choice for which instance of that type to use.
+
+If the notion so expressed is important enough, we might give it its *own*, dedicated data structure, that just left out the head parameter. Informationally, it's all the same whether you omit some parameter or include it but offer only one choice for what it can be. Indeed I suggested that this is a helpful way to think of Numbers as compared to Lists. (In Chapter 6 of *The Little Schemer*, they also briefly explore representing the number `4` as the list `'(() () () ())`.)
+
+But sometimes the more general data structure you're working with will be well-developed, and have lots of code already built up around it, prepared to handle parameters of many types. And the special case where you don't care about the identity of the parameter might be more limited purpose, that's easier to just piggy-back on the more general notion than to write separate code for. In these cases *Units* can be a useful choice for the type of some parameter, precisely because they are uninformative.
+
+(For these purposes you'd want to use heavyweight units, like Kapulet's `Unit ()` or Haskell and OCaml's `()`. For the remaining jobs to be discussed below, however, arguably *either* of Kapulet's heavyweight or lightweight units could be deployed.)
+
+
+Returning *unit* as a result
+============================
+
+Some functions return *Units* as their results. How could that ever be useful? Since there's only ever one result, it seems like the function would have to be a constant function, from whatever arguments it was willing to accept, to that result. Now sometimes constant functions might be useful; for example, you might have an operation that expected some predicate to apply to numbers, and in a particular case you might want every number to count as passing, so you could supply the constant predicate from numbers to truth. But here the constant function's usefulness depends on the possibility of your choosing it rather than some other function with the same result type. Even if you limited yourself only to *constant* functions to Boolean results, you still have two to choose from, and that choice can encode some information. When we turn to constant functions from some arguments into the *Unit* type, on the other hand, there is only one result that any such function could constantly return. What would be the point?
+
+The point emerges when we have functions that do more than merely *evaluate* other functions and relations on their arguments. Some functions additionally perform *side*-effects, like vocalizing (or printing) their arguments, or changing what the first element in some mutable list value is, or so on. A function can perform side-effects and *also* return a useful value. For example, we might have a "noisy-successor" function that vocalizes the value of its number argument, and evaluates to that argument's successor. So if I ask the computer to evaluate:
+
+    [noisy_succ 3, 5]
+
+or:
+
+    [noisy_succ (1 + 2), 5]
+
+The computer will vocalize the word "three", but return the value `4`, to be used in building up a potentially more complex value --- in these cases the length-two sequence `[4, 5]`.
+
+For some functions, on the other hand, *all we care about* is the side-effect. There may be no informative result to return. Then we're in a situation like we were in the previous section. We *could* return, say, a Number result, chosen arbitrarily. Or a random Boolean. But this is ugly and can mislead readers about what's going on. The cleanest thing to do is to signal explicitly that the result value is not informative. For this *Units* are perfect.
+
+We haven't yet started to work with any functions with side-effects, but we will later. You may also be familiar with some of these ideas from other contexts, or other programming languages.
+
+
+Supplying *unit* as an argument
+===============================
+
+Finally, in some cases we have functions that are applied to *Units* as arguments. How can that be useful? What's the difference between applying a function to an uninformative argument and just the original, unapplied function?
+
+As Chris observed in seminar, we do make such distinctions in natural language. We distinguish between the English *predicate* "is raining" and the *sentence* "*It* is raining." Only the latter can have a truth-value (in a particular context of utterance, that supplies a time and a place). Only the former still has syntactic positions left unsaturated, and can be coordinated with other, similar predicates ("is raining *and won't get warmer*"). Yet that initial "It" is semantically uninformative. It doesn't refer to anything. All it does is provide empty filler. It seems like its sole function is to mark the difference between the predicate and the sentence.
+
+This is indeed the role *unit* has when it's the argument a function expects or receives. Now, you ask: why would it be *useful* to distinguish between the unapplied and the applied function. If one Kapulet programmer writes:
+
+    let
+      g match lambda (). 1 + 3;
+      f match lambda (thunk, y). thunk () * y
+    in f (g, 5)
+
+and another writes merely:
+
+    let
+      g' match 1 + 3;
+      f' match lambda (x, y). x * y
+    in f' (g', 5)
+
+what advantage can the first have possibly achieved? Why bind `g` to such a *function* --- these functions that take `()` arguments are known as **thunks** --- which later gets applied, but to an uninformative argument, rather than just calculating the function's result in the first place, and binding a variable that *that*?
+
+The main usefulness of this is again when we're dealing with functions that have side-effects. If `g` were bound instead to `lambda (). noisy_succ 3`, we might want to control when the body of that function gets computed. We might be in a position to build the function at one point in the program, but only want it to be computed at some distant point, related to where we are now by a complex path. Also, we might want to control *how often* the body gets computed. If for example, we say:
+
+    let
+      g match lambda (). noisy_succ 3;
+      f match lambda (thunk, y). thunk () * thunk () * thunk () * y
+    in f (g, 5)
+
+that will result in the computer vocalizing "three" three times, and returning `320`. Whereas if we say:
+
+    let
+      g' match noisy_succ 3;
+      f' match lambda (x, y). x * x * x * y
+    in f' (g', 5)
+
+that will result in the computer vocalizing "three" only once, and returning the same result. (I assume here our language has what we called "strict" or "eager" evaluation order, where a function's arguments are evaluated *before* being substituted into the body of the function. Most programming languages work like this; but Haskell does not do so by default. With the Lambda Calculus, it may or may not; you have to decide.)
+
+Here again, we haven't started to work with any functions with side-effects, so you have to imagine ahead ways in which this could be useful.
+
+But in this case, we *have* also encountered this very week *another* way in which delaying the evaluation of a function in this way could be useful. Some expressions just won't evaluate to any value. In the Lambda Calculus, we had the example of <code>&omega; &omega;</code>, that is, `(\x. x x) (\x. x x)`. And also some even scarier terms. We can write these in Kapulet, or we can write other scary terms using `letrec`:
+
+    letrec
+      blackhole match lambda (). blackhole ();
+      fst match lambda (x, y). x
+    in fst (5, blackhole)
+
+If `blackhole` ever gets applied to its `()` argument, computing the result will require re-applying `blackhole` to that same argument, which will require ... and the reduction or computation will never terminate. Some of the vocabulary people use for such expressions is that they involve "infinite loops" or "non-termination" or that they "diverge" or that their "meaning is bottom" (written <code>&bot;</code>, as we sometimes use in logic to represent a constant formula that is always false). "Bottom" is a meaning we might assign these terms, but don't say that this is their *value*. Such terms don't have any value. (Sometimes people talk sloppily, and we might even do it ourselves. But the best way to talk here is to say that expressions like `blackhole ()` *don't have any values*, or in other words *don't evaluate to anything*, though our semantics may assign them a *meaning* or denotation. Interestingly, you can't in general assign all non-terminating expressions the same meaning. See ___ for discussion.)
+
+But in the complex expression above, we never do apply `blackhole` to an argument, so no harm comes about. It makes no difference that we were evaluating `fst (5, blackhole)` rather than `snd (blackhole, 5)` (or even `snd (5, blackhole)`). In none of the cases do we ever request the result of computing `blackhole`'s body. So everything is ok.
+
+This is like how in the Lambda Calculus it can be alright to say:
+
+<code>K I (&omega; &omega;)</code>
+
+--- that is, assuming the lambda term is being evaluated in "normal" or "lazy" order, so that we reduce the leftmost, outermost redex `K I (...)` before we reduce the argument redex <code>&omega; &omega;</code>. Since `K I (...)` discards its second argument, the non-terminating computation of <code>&omega; &omega;</code> (that is, the result of self-applying self-application) is never demanded.
+