[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Lambda calculus and it relation to LISP

From: Barb Knox
Subject: Re: Lambda calculus and it relation to LISP
Date: Mon, 07 Oct 2002 20:37:40 +1300

In article <>, (gnuist) wrote:

> 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

    ((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

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.


|  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   |   

reply via email to

[Prev in Thread] Current Thread [Next in Thread]