Re: Lambda calculus and it relation to LISP

[Christian Lemburg <lemburg@aixonix.de>]

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