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

## 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 <David.Kastrup@t-online.de> writes:

> see@sig.below (Barb Knox) writes:
>
> > 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

```