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: Tue, 08 Oct 2002 00:10:14 +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> <20021007025544.G57236-100000@agora.rdrop.com> NNTP-Posting-Host: localhost.gmane.org X-Trace: main.gmane.org 1033989371 8090 127.0.0.1 (7 Oct 2002 11:16:11 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 7 Oct 2002 11:16:11 +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 17yVrt-00026D-01 for ; Mon, 07 Oct 2002 13:16:09 +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 17yVrw-0007bn-00; Mon, 07 Oct 2002 07:16:12 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!newsfeed.berkeley.edu!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: 42 Original-NNTP-Posting-Host: 203-173-242-118.adsl.ihug.co.nz Original-X-Trace: lust.ihug.co.nz 1033989014 8117 203.173.242.118 (7 Oct 2002 11:10:14 GMT) Original-X-Complaints-To: abuse@ihug.co.nz Original-NNTP-Posting-Date: Mon, 7 Oct 2002 11:10:14 +0000 (UTC) X-Newsreader: MT-NewsWatcher 2.4.4 Original-Xref: shelby.stanford.edu gnu.emacs.help:105781 comp.lang.lisp:95850 sci.math:550068 sci.logic:61655 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:2327 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2327 In article <20021007025544.G57236-100000@agora.rdrop.com>, William Elliot wrote: > On 7 Oct 2002, 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))))) ) [snip] > What's lambda calculus expressions for -, <, if, = ? '-' and '<' are a bit tricky, as is most LC arithmetic using Church numerals -- see a textbook that covers LC. 'if' is usually (lambda (test) (lambda (ifTrue) (lambda (ifFalse) ((test ifTrue) ifFalse)))) or (lambda (test ifTrue ifFalse) (test ifTrue ifFalse)) where the value for TRUE is (lambda (ifTrue ifFalse) ifTrue) and the value for FALSE is (lambda (ifTrue ifFalse) ifFalse) As you can see, raw LC makes a pretty horrible programming language, which is why useable functional languages (1) are strongly typed, and (2) have primitives for numbers, strings, etc. so that one does not have to deal with Church numerals, etc. -- --------------------------- | 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 | -----------------------------