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 23:59:01 +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 1033988489 5627 127.0.0.1 (7 Oct 2002 11:01:29 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 7 Oct 2002 11:01:29 +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 17yVde-0001SN-00 for ; Mon, 07 Oct 2002 13:01:26 +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 17yVdP-0006BJ-00; Mon, 07 Oct 2002 07:01:11 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!logbridge.uoregon.edu!xmission!news-hog.berkeley.edu!ucberkeley!nntp-relay.ihug.net!lust.ihug.co.nz!ihug.co.nz!see Original-Newsgroups: gnu.emacs.help,comp.lang.lisp,sci.math,sci.logic Original-Lines: 69 Original-NNTP-Posting-Host: 203-173-242-118.adsl.ihug.co.nz Original-X-Trace: lust.ihug.co.nz 1033988341 6860 203.173.242.118 (7 Oct 2002 10:59:01 GMT) Original-X-Complaints-To: abuse@ihug.co.nz Original-NNTP-Posting-Date: Mon, 7 Oct 2002 10:59:01 +0000 (UTC) X-Newsreader: MT-NewsWatcher 2.4.4 Original-Xref: shelby.stanford.edu gnu.emacs.help:105780 comp.lang.lisp:95848 sci.math:550064 sci.logic:61653 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:2325 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2325 In article , David Kastrup wrote: > 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 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? > > Also wrong. This is "Lispish Syntax", actually Scheme. No, not wrong. It's *lambda calculus* with a Lispish (or Schemish if you prefer) syntax. It is not Scheme. The original question was about lambda calculus. > So we can check it out: > > guile> ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))(lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) ) > standard input:1:27: In expression (f (Y Y)): > standard input:1:27: Wrong number of arguments to # > ABORT: (wrong-number-of-args) > > Type "(backtrace)" to get more information. > guile> (backtrace) > > Backtrace: > 0* [# #] > 1 [# #] > 2 (f (Y Y)) > > Type "(debug-enable 'backtrace)" if you would like a backtrace > automatically if an error occurs in the future. I never claimed it would run in Scheme. IIRC, Scheme does applicative-order evaluation, not normal-order. Also IIRC, Scheme does not do "currying", whereby, e.g., ((lambda (a b) (+ a b)) 3) --> (lambda (b) (+ 3 b)). You can get around the currying by changing the second line to: (lambda (ff) (lambda (n) ... )) ) but that doesn't help with the evaluation order. -- --------------------------- | 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 | -----------------------------