From: jim Date: Wed, 18 Feb 2015 17:28:43 +0000 (-0500) Subject: finish X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=1c616d1aeb687348c467d78b8149d5b415be2328 finish --- diff --git a/topics/week3_unit.mdwn b/topics/week3_unit.mdwn index c0b26090..54f0a83f 100644 --- a/topics/week3_unit.mdwn +++ b/topics/week3_unit.mdwn @@ -295,3 +295,81 @@ But sometimes the more general data structure you're working with will be well-d (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 a function 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 function 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 ω ω, 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 ⊥, 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: + +K I (ω ω) + +--- 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 ω ω. Since `K I (...)` discards its second argument, the non-terminating computation of ω ω (that is, the result of self-applying self-application) is never demanded. +