X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week3.mdwn;h=39e472bf9a644c1bdac774790ed134f26ab7cf31;hp=27bdc53e3c718c3c3db7230d0fd4aadc98470e79;hb=372c27cbb4d670940cfc22c427e3b12d87d3b9df;hpb=3046bff4d37b7a7424f414633706ac6f7cfc3d59 diff --git a/week3.mdwn b/week3.mdwn index 27bdc53e..39e472bf 100644 --- a/week3.mdwn +++ b/week3.mdwn @@ -1,3 +1,12 @@ +[[!toc]] + +##More on evaluation strategies## + +Here are notes on [[evaluation order]] that make the choice of which +lambda to reduce next the selection of a route through a network of +links. + + ##Computing the length of a list## How could we compute the length of a list? Without worrying yet about what lambda-calculus implementation we're using for the list, the basic idea would be to define this recursively: @@ -211,7 +220,8 @@ Instead of writing out a long formula twice, we could write: and the initial `(\x. x x)` is just what we earlier called the `ω` combinator (lower-case omega, not the non-terminating `Ω`). So the self-application of `H` can be written: -
``ω (\h \lst. (isempty lst) zero (add one ((h h) (extract-tail lst))))``
+
``````ω (\h \lst. (isempty lst) zero (add one ((h h) (extract-tail lst))))
+``````
and this will indeed implement the recursive function we couldn't earlier figure out how to define. @@ -414,7 +424,7 @@ to *the tail* of the list we were evaluating its application to at the previous ##Fixed-point Combinators Are a Bit Intoxicating## -![tatoo](/y-combinator.jpg) +![tatoo](/y-combinator-fixed.jpg) There's a tendency for people to say "Y-combinator" to refer to fixed-point combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Y-combinator is only one of many fixed-point combinators. @@ -493,16 +503,16 @@ As any functional programmer quickly learns, writing a recursive function divides into two tasks: figuring out how to handle the recursive case, and remembering to insert a base case. The interesting and enjoyable part is figuring out the recursive pattern, -but leaving out the base case creates a program that runs forever. -For instance, consider computing a factorial: `n!` is `n * (n-1) * -(n-2) * ... * 1`. The recursive case says that the factorial of a -number `n` is `n` times the factorial of `n-1`. But if we leave out -the base case, we get +but the base case cannot be ignored, since leaving out the base case +creates a program that runs forever. For instance, consider computing +a factorial: `n!` is `n * (n-1) * (n-2) * ... * 1`. The recursive +case says that the factorial of a number `n` is `n` times the +factorial of `n-1`. But if we leave out the base case, we get 3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 0 * -1! ... -That's why it's crucial to declare that 0! = 1, and the recursive rule -does not apply. In our terms, +That's why it's crucial to declare that 0! = 1, in which case the +recursive rule does not apply. In our terms, fac = Y (\fac n. iszero n 1 (fac (predecessor n))) @@ -514,12 +524,12 @@ case: the truth-teller paradox (and related paradoxes). (1) This sentence is true. -If we assume that "this sentence" can refer to (1), then the -proposition expressed by (1) will be true just in case the thing -referred to by "this sentence is true". Thus (1) will be true just in -case (1) is true, and (1) is true just in case (1) is true, and so on. -If (1) is true, then (1) is true; but if (1) is not true, then (1) is -not true. +If we assume that the complex demonstrative "this sentence" can refer +to (1), then the proposition expressed by (1) will be true just in +case the thing referred to by *this sentence* is true. Thus (1) will +be true just in case (1) is true, and (1) is true just in case (1) is +true, and so on. If (1) is true, then (1) is true; but if (1) is not +true, then (1) is not true. Without pretending to give a serious analysis of the paradox, let's assume that sentences can have for their meaning boolean functions @@ -529,29 +539,32 @@ is John* might denote the function `\x y. x`, our `true`. Then (1) denotes a function from whatever the referent of *this sentence* is to a boolean. So (1) denotes `\f. f true false`, where the argument `f` is the referent of *this sentence*. Of course, if -`f` is a boolean, `f true false <~~> f`, (1) denotes the identity -function `I`. +`f` is a boolean, `f true false <~~> f`, so for our purposes, we can +assume that (1) denotes the identity function `I`. If we use (1) in a context in which *this sentence* refers to the sentence in which the demonstrative occurs, then we must find a meaning `m` such that `I m = I`. But since in this context `m` is the -same as the meaning `I`, we have `m = I m`, so `m` is a fixed point -for the denotation of the sentence (when used in the appropriate context). +same as the meaning `I`, so we have `m = I m`. In other words, `m` is +a fixed point for the denotation of the sentence (when used in the +appropriate context). That means that in a context in which *this sentence* refers to the sentence in which it occurs, the sentence denotes a fixed point for -the identity function, `Y I`. - - Y I - (\f. (\h. f (h h)) (\h. f (h h))) I - (\h. I (h h)) (\h. I (h h))) - (\h. (h h)) (\h. (h h))) - ω ω - &Omega - -Oh. Well. That feels right! The meaning of *This sentence is true* +the identity function. Here's a fixed point for the identity +function: + +
``````Y I
+(\f. (\h. f (h h)) (\h. f (h h))) I
+(\h. I (h h)) (\h. I (h h)))
+(\h. (h h)) (\h. (h h)))
+ω ω
+&Omega
+``````
+ +Oh. Well! That feels right. The meaning of *This sentence is true* in a context in which *this sentence* refers to the sentence in which -it occurs is Ω, our prototypical infinite loop... +it occurs is `Ω`, our prototypical infinite loop... What about the liar paradox? @@ -578,3 +591,50 @@ See Barwise and Etchemendy's 1987 OUP book, [The Liar: an essay on truth and circularity](http://tinyurl.com/2db62bk) for an approach that is similar, but expressed in terms of non-well-founded sets rather than recursive functions. + +##However...## + +You should be cautious about feeling too comfortable with +these results. Thinking again of the truth-teller paradox, yes, +`Ω` is *a* fixed point for `I`, and perhaps it has +some a privileged status among all the fixed points for `I`, being the +one delivered by Y and all (though it is not obvious why Y should have +any special status). + +But one could ask: look, literally every formula is a fixed point for +`I`, since + + X <~~> I X + +for any choice of X whatsoever. + +So the Y combinator is only guaranteed to give us one fixed point out +of infinitely many---and not always the intuitively most useful +one. (For instance, the squaring function has zero as a fixed point, +since 0 * 0 = 0, and 1 as a fixed point, since 1 * 1 = 1, but `Y +(\x. mul x x)` doesn't give us 0 or 1.) So with respect to the +truth-teller paradox, why in the reasoning we've +just gone through should we be reaching for just this fixed point at +just this juncture? + +One obstacle to thinking this through is the fact that a sentence +normally has only two truth values. We might consider instead a noun +phrase such as + +(3) the entity that this noun phrase refers to + +The reference of (3) depends on the reference of the embedded noun +phrase *this noun phrase*. It's easy to see that any object is a +fixed point for this referential function: if this pen cap is the +referent of *this noun phrase*, then it is the referent of (3), and so +for any object. + +The chameleon nature of (3), by the way (a description that is equally +good at describing any object), makes it particularly well suited as a +gloss on pronouns such as *it*. In the system of +[Jacobson 1999](http://www.springerlink.com/content/j706674r4w217jj5/), +pronouns denote (you guessed it!) identity functions... + +Ultimately, in the context of this course, these paradoxes are more +useful as a way of gaining leverage on the concepts of fixed points +and recursion, rather than the other way around.