help-gnu-emacs
[Top][All Lists]
Advanced

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

Re: Lambda calculus and it relation to LISP


From: Christian Lemburg
Subject: Re: Lambda calculus and it relation to LISP
Date: 07 Oct 2002 12:44:52 +0200
User-agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)

David Kastrup <address@hidden> writes:

> address@hidden (Barb Knox) writes:
> 
> > In article <address@hidden>,
> > address@hidden (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, <address@hidden>, http://www.clemburg.com/


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


reply via email to

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