From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Christian Lemburg Newsgroups: gmane.emacs.help Subject: Re: Lambda calculus and it relation to LISP Date: 07 Oct 2002 12:44:52 +0200 Organization: KPNQwest Germany GmbH, customer reader site Sender: help-gnu-emacs-admin@gnu.org Message-ID: References: <9e8ebeb2.0210041920.2e480123@posting.google.com> <20021006050255.A63895-100000@agora.rdrop.com> <9e8ebeb2.0210062058.5c7ab267@posting.google.com> NNTP-Posting-Host: localhost.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1033988632 6168 127.0.0.1 (7 Oct 2002 11:03:52 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 7 Oct 2002 11:03:52 +0000 (UTC) Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 17yVfz-0001bL-00 for ; Mon, 07 Oct 2002 13:03:51 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10) id 17yVaA-0004Wu-00; Mon, 07 Oct 2002 06:57:50 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news.ems.psu.edu!news.cis.ohio-state.edu!news.maxwell.syr.edu!newsfeed.vmunix.org!newsfeed01.sul.t-online.de!newsfeed00.sul.t-online.de!t-online.de!blackbush.xlink.net!blackbush.de.kpnqwest.net!scapa.de.kpnqwest.net!194.121.123.2!194.121.123.146 Original-Newsgroups: gnu.emacs.help,comp.lang.lisp Original-Lines: 89 Original-NNTP-Posting-Host: 194.121.123.2 Original-X-Trace: newsreader1.lb-lan.ka.de.kpnqwest.net 1033988059 6004 194.121.123.2 (7 Oct 2002 10:54:19 GMT) Original-X-Complaints-To: "abuse@de.kpnqwest.net" Original-NNTP-Posting-Date: Mon, 7 Oct 2002 10:54:19 +0000 (UTC) X-Face: "PlaRZ)@9[if~e#S1]D7|l`|7"C.kV+P^$.r!pL"NE^5Gh[Fwr?wR-@{Me)_Dfyec#Mi4M7 KWUn#dE$B3L3?WX:lR.vf-LI+w3OJL46>O2+HP#h$;.*K^Om]xOh8a>F1"6{%;k>=/;{Pn%sX2~'E? User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands) X-Original-NNTP-Posting-Host: 194.121.123.146 Original-Xref: shelby.stanford.edu gnu.emacs.help:105779 comp.lang.lisp:95847 Original-To: help-gnu-emacs@gnu.org Errors-To: help-gnu-emacs-admin@gnu.org X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.0.11 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: Xref: main.gmane.org gmane.emacs.help:2326 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2326 David Kastrup 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, , http://www.clemburg.com/ Money is the root of all evil, and man needs roots