[Top][All Lists]
[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
- Re: Lambda calculus and it relation to LISP, (continued)
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/05
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/06
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/06
- Re: Lambda calculus and it relation to LISP, gnuist, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP, David Kastrup, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP,
Christian Lemburg <=
- Re: Lambda calculus and it relation to LISP, ozan s yigit, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP, David Kastrup, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/08
- Re: Lambda calculus and it relation to LISP, Fred Gilham, 2002/10/05
- Re: Lambda calculus and it relation to LISP, Kaz Kylheku, 2002/10/05
- Re: Lambda calculus and it relation to LISP, Thaddeus L Olczyk, 2002/10/06