Re: Help with Lambda Calculus



kunjaan <kunjaan@xxxxxxxxx> wrote:
+---------------
| But what I am confused is that if a function gets another function and
| an argument and just returns the argument, how can that be 0? It still
| has something in it, right?
+---------------

Others have discussed Church numerals at length, so I won't comment
further about that except to point you here, especially to the section
on "Translation with other representations":

http://en.wikipedia.org/wiki/Church_numerals

+---------------
| It is just so counter intuitive.
+---------------

Well, yes. There nothing particularly "intuitive" (or useful!) about
pure lambda calculus. It's just a formalism (a "calculus") that permits
certain axioms to be stated and certain theorems to be proved, especially
about computability or recursion theory, see:

http://en.wikipedia.org/wiki/Lambda_calculus
http://en.wikipedia.org/wiki/Kleene%E2%80%93Rosser_paradox

Note that despite their claims to being "based on" the lambda calculus,
Lisp & Scheme are actually quite far from the original untyped lambda
calculus that inspired them, using as they do quite traditionally encoded
dynamically-typed values, and allowing mutation. [The earliest Lisps
even used only dynamic scope for variables, which is *definitely* not
the case in the lambda calculus!! Fortunately, Scheme & CL fixed that.]

So if you're studying lambda calculus for a course in computability
theory, my advice would be to just put aside your questions about
why Church numerals are used there -- they just are, because it's
traditional to do so. That's what your professor will expect you
to use in the proofs you turn in.

On the other hand, if you're studying lambda calculus in order to
learn something about programming in Scheme or Common Lisp or ML
or Haskell, etc., then I'd say to put aside your curiosity about
the precise details of formal lambda calculus and just study the
syntax/semantics of the particular language in which you plan to
be coding, since the lambda calculus has very little to do with
the day-to-day practicalities of programming.

On the third hand, a cursory overview of lambda calculus *is* a
useful thing to have in the intellectual arsenal of *any* programmer
[e.g., the notions of closures & currying & combinators and when
and when not to use them], if you don't take it too far. ;-}


-Rob

-----
Rob Warnock <rpw3@xxxxxxxx>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

.