From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.help Subject: Re: Lambda calculus and it relation to LISP Date: 08 Oct 2002 05:05:23 +0200 Organization: T-Online 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 1034046732 6622 127.0.0.1 (8 Oct 2002 03:12:12 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Tue, 8 Oct 2002 03:12:12 +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 17ykn4-0001ig-00 for ; Tue, 08 Oct 2002 05:12:10 +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 17ykm5-0006KX-00; Mon, 07 Oct 2002 23:11:09 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!lnewspeer00.lnd.ops.eu.uu.net!emea.uu.net!newsfeed01.sul.t-online.de!newsmm00.sul.t-online.com!t-online.de!news.t-online.com!not-for-mail Original-Newsgroups: comp.emacs,gnu.emacs.help,comp.lang.lisp,sci.math,sci.logic Original-Lines: 71 Original-X-Trace: news.t-online.com 1034046327 03 12268 qSQ2bsWTSvAg3X 021008 03:05:27 Original-X-Complaints-To: abuse@t-online.com X-Sender: 520018396234-0001@t-dialin.net X-Face: 2FEFf>]>q>2iw=B6,xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN;i";/yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3.50 Original-Xref: shelby.stanford.edu comp.emacs:75106 gnu.emacs.help:105812 comp.lang.lisp:95948 sci.math:550268 sci.logic:61707 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:2359 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2359 see@sig.below (Barb Knox) writes: > In article , David Kastrup > wrote: > > > see@sig.below (Barb Knox) writes: > > > > > 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. > > > So we can check it out: > > > 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. > > > 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. Lambda calculus is an abtract concept. An abstract concept with "currying"? Anyhow, here is how to do a factorial in Scheme: ((lambda (f n) (f f n)) (lambda (f n) (if (< n 1) 1 (* n (f f (- n 1))))) 5) If we want to start from a function that does not look self-referential (namely, does not have (f f ...) in its core definition from where we want to have it recurse), things get more intricate: ((lambda (f g n) (g (f f g) n)) (lambda (f g) (lambda (n) (g (f f g) n))) (lambda (f n) (if (< n 1) 1 (* n (f (- n 1))))) 5) No curry involved here, but still rather spicy. Don't get burned. Anybody see a simpler solution for cranking up recursion on the last lambda-line? Oh, since we are here also in the Emacs groups: the equivalents would be ((lambda (f n) (funcall f f n)) (lambda (f n) (if (zerop n) 1 (* n (funcall f f (1- n))))) 5) ((lambda (f g n) (funcall g (funcall f f g) n)) (lambda (f g) `(lambda (n) (,g (funcall ,f ,f ,g) n))) (lambda (f n) (if (zerop n) 1 (* n (funcall f (1- n))))) 5) -- David Kastrup, Kriemhildstr. 15, 44793 Bochum Email: David.Kastrup@t-online.de