XGitUrl: 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 lambdacalculus 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 (lowercase omega, not the nonterminating Ω
). So the selfapplication of `H` can be written:
ω (\h \lst. (isempty lst) zero (add one ((h h) (extracttail lst))))
+ω (\h \lst. (isempty lst) zero (add one ((h h) (extracttail 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
##Fixedpoint Combinators Are a Bit Intoxicating##
![tatoo](/ycombinator.jpg)
+![tatoo](/ycombinatorfixed.jpg)
There's a tendency for people to say "Ycombinator" to refer to fixedpoint combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Ycombinator is only one of many fixedpoint 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 * (n1) *
(n2) * ... * 1`. The recursive case says that the factorial of a
number `n` is `n` times the factorial of `n1`. 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 * (n1) * (n2) * ... * 1`. The recursive
+case says that the factorial of a number `n` is `n` times the
+factorial of `n1`. 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 truthteller 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 nonwellfounded sets
rather than recursive functions.
+
+##However...##
+
+You should be cautious about feeling too comfortable with
+these results. Thinking again of the truthteller 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 manyand 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
+truthteller 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.