From: Chris Barker Date: Mon, 27 Sep 2010 00:09:56 +0000 (-0400) Subject: edits X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=3046bff4d37b7a7424f414633706ac6f7cfc3d59 edits --- diff --git a/week3.mdwn b/week3.mdwn index c1804879..27bdc53e 100644 --- a/week3.mdwn +++ b/week3.mdwn @@ -485,3 +485,96 @@ the behavior of `sink` is sensitive to the nature of the input: if the input is the magic function `false`, the self-regeneration machinery will be discarded, and the recursion will stop. +That's about as simple as recursion gets. + +##Base cases, and their lack## + +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 + + 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, + + fac = Y (\fac n. iszero n 1 (fac (predecessor n))) + +If `n` is 0, `fac` reduces to 1, without computing the recursive case. + +There is a well-known problem in philosophy and natural language +semantics that has the flavor of a recursive function without a base +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. + +Without pretending to give a serious analysis of the paradox, let's +assume that sentences can have for their meaning boolean functions +like the ones we have been working with here. Then the sentence *John +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`. + +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). + +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* +in a context in which *this sentence* refers to the sentence in which +it occurs is Ω, our prototypical infinite loop... + +What about the liar paradox? + +(2) This sentence is false. + +Used in a context in which *this sentence* refers to the utterance of +(2) in which it occurs, (2) will denote a fixed point for `\f.neg f`, +or `\f l r. f r l`, which is the `C` combinator. So in such a +context, (2) might denote + + Y C + (\f. (\h. f (h h)) (\h. f (h h))) I + (\h. C (h h)) (\h. C (h h))) + C ((\h. C (h h)) (\h. C (h h))) + C (C ((\h. C (h h))(\h. C (h h)))) + C (C (C ((\h. C (h h))(\h. C (h h))))) + ... + +And infinite sequence of `C`s, each one negating the remainder of the +sequence. Yep, that feels like a reasonable representation of the +liar paradox. + +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.