Re: Lambda calculus and it relation to LISP

[see@sig.below (Barb Knox)]

In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
gnuist007@hotmail.com (gnuist) wrote:
[snip]

> In the same way I ask for GRADED examples of use of lambda. I am sure many
> of you can just cut and paste from your collection. Examples to illustrate
> recursion, etc. And how will you do recursion without/with "LABEL"?

Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE.  Recursion
is done via the "Y combinator", which is a very interesting
self-referential hack (in the good sense).

For example, here is a recursive factorial function in lambda calculus in
Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
and '1').  It takes one argument (which gets bound to 'n') and returns its
factorial.

    ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
     (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )

Intense, eh?  If you can get your head around this then you're most of the
way towards understanding lambda calculus.  Try desk-checking a few
examples (starting with n=0).  If you want, post the trace of your
desk-checks here and we'll double-check them.

The first line computes the fixed-point of the second line (ound to 'f')
and passes this fixed point to 'f' (as 'ff').  If you want to understand
recursion in lambda calculus (as opposed to in Lisp) then you really do
need learn about fixed-points; see a textbook on recursive function
theory.

Note that it is critical that evaluation be done in "normal order"
(outermost first) rather than in Lisp's "applicative order" (innermost
first); otherwise the Y combinator never terminates.

[snip]

-- 
---------------------------
|  BBB                b    \    barbara minus knox at iname stop com
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   
|  B  B  a  a   r     b  b  |   
|  BBB    aa a  r     bbb   |   
-----------------------------