Re: Lambda calculus and it relation to LISP

[Christian Lemburg]

David Kastrup <David.Kastrup@t-online.de> writes:

> see@sig.below (Barb Knox) writes:
> 
> > 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 a good introduction to this very topic, read Essentials of
Programming Languages, Daniel P. Friedman, Mitchell Wand, and
Christopher T. Haynes, MIT Press, 1992.  An in-depth study of
programming language structure and features. Discusses fundamental
concepts by means of a series of interpreters that are developed in
Scheme, using a formal approach that derives the interpreters from a
formal specification of the language and its features. In-depth
discussion of parameter-passing techniques, continuations,
object-oriented languages, and derivation of a compiler from an
interpreter. This is one of a trio I heartily recommend to any
programmer: SICP, Essentials of Programming Languages, Paradigms of
Artificial Intelligence Programming: Case Studies in Common Lisp.

I think Lambda calculus is covered in Chapter 4 of EOPL.

For those who may understand Perl, but not Lisp, here is the
applicative Y combinator in Perl, maybe it helps.


sub Y {
    my $f = shift;
    sub {
        my $x = shift;
        $f->(sub { my $y = shift; return ($x->($x))->($y)});
    }->(
        sub {
            my $x = shift;
            $f->(sub { my $y = shift; return ($x->($x))->($y)});
        });
}

sub countdown {
    my $x = shift;
    return Y(sub { 
                 my $f = shift; 
                 return sub {
                     my $x = shift;
                     if ($x) {
                         print "$x\n";
                         $f->($x - 1);
                     } else {
                         print "yeah!\n";
                     }
                 }})->($x);
}


sub fact {
    my $x = shift;
    return Y(sub { 
                 my $f = shift; 
                 return sub {
                     my $x = shift;
                     if ($x < 2) {
                         return 1;
                     } else {
                         return $x * $f->($x - 1);
                     }
                 }})->($x);
}



countdown(10);
print "fact(5) = ", fact(5), "\n";



-- 
Christian Lemburg, <lemburg@aixonix.de>, http://www.clemburg.com/


 Money is the root of all evil, and man needs roots