From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: see@sig.below (Barb Knox) Newsgroups: gmane.emacs.help Subject: Re: Lambda calculus and it relation to LISP Date: Mon, 07 Oct 2002 20:37:40 +1300 Organization: I'm not unemployed; I'm a consultant 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 X-Trace: main.gmane.org 1033976666 8336 127.0.0.1 (7 Oct 2002 07:44:26 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 7 Oct 2002 07:44:26 +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 17ySYz-0002AK-00 for ; Mon, 07 Oct 2002 09:44:25 +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 17ySVx-0006eU-00; Mon, 07 Oct 2002 03:41:17 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news.mel.connect.com.au!news.xtra.co.nz!newsfeeds.ihug.co.nz!lust.ihug.co.nz!ihug.co.nz!see Original-Newsgroups: gnu.emacs.help,comp.lang.lisp,sci.math,sci.logic Original-Lines: 45 Original-NNTP-Posting-Host: 203-173-242-118.adsl.ihug.co.nz Original-X-Trace: lust.ihug.co.nz 1033976261 29508 203.173.242.118 (7 Oct 2002 07:37:41 GMT) Original-X-Complaints-To: abuse@ihug.co.nz Original-NNTP-Posting-Date: Mon, 7 Oct 2002 07:37:41 +0000 (UTC) X-Newsreader: MT-NewsWatcher 2.4.4 Original-Xref: shelby.stanford.edu gnu.emacs.help:105774 comp.lang.lisp:95831 sci.math:550033 sci.logic:61641 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:2320 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2320 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 example, here is a recursive factorial function in lambda calculus in Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-', and '1'). It takes one argument (which gets bound to 'n') and returns its factorial. ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y))))) (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) ) Intense, eh? If you can get your head around this then you're most of the way towards understanding lambda calculus. Try desk-checking a few examples (starting with n=0). If you want, post the trace of your desk-checks here and we'll double-check them. The first line computes the fixed-point of the second line (ound to 'f') and passes this fixed point to 'f' (as 'ff'). If you want to understand recursion in lambda calculus (as opposed to in Lisp) then you really do need learn about fixed-points; see a textbook on recursive function theory. Note that it is critical that evaluation be done in "normal order" (outermost first) rather than in Lisp's "applicative order" (innermost first); otherwise the Y combinator never terminates. [snip] -- --------------------------- | BBB b \ barbara minus knox at iname stop com | B B aa rrr b | | BBB a a r bbb | | B B a a r b b | | BBB aa a r bbb | -----------------------------