From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Gareth.McCaughan@pobox.com (Gareth McCaughan) Newsgroups: gmane.emacs.help Subject: Re: Lambda calculus and it relation to LISP Date: Sun, 6 Oct 2002 20:22:54 +0100 Organization: International Pedant Conspiracy Sender: help-gnu-emacs-admin@gnu.org Message-ID: References: <9e8ebeb2.0210041920.2e480123@posting.google.com> <20021006050255.A63895-100000@agora.rdrop.com> Reply-To: Gareth.McCaughan@pobox.com NNTP-Posting-Host: localhost.gmane.org X-Trace: main.gmane.org 1033932442 18750 127.0.0.1 (6 Oct 2002 19:27:22 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 6 Oct 2002 19:27:22 +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 17yH3f-0004s8-00 for ; Sun, 06 Oct 2002 21:27:20 +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 17yH3P-0007jd-00; Sun, 06 Oct 2002 15:27:04 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!skynet.be!skynet.be!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newspeer1-gui.server.ntli.net!ntli.net!newsfep1-win.server.ntli.net.POSTED!53ab2750!not-for-mail Original-Newsgroups: gnu.emacs.help,comp.lang.lisp,sci.math,sci.logic User-Agent: slrn/0.9.6.3 (FreeBSD) Original-Lines: 80 Original-NNTP-Posting-Host: 62.253.132.109 Original-X-Complaints-To: abuse@ntlworld.com Original-X-Trace: newsfep1-win.server.ntli.net 1033932230 62.253.132.109 (Sun, 06 Oct 2002 20:23:50 BST) Original-NNTP-Posting-Date: Sun, 06 Oct 2002 20:23:50 BST Original-Xref: shelby.stanford.edu gnu.emacs.help:105769 comp.lang.lisp:95781 sci.math:549891 sci.logic:61608 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:2315 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2315 William Elliot wrote: [I said:] > _ There are three transformations you're allowed to do, of which the > _ most important is one that takes (Lx.E)F into whatever you get by > _ substituting E for every (free) occurrence of x in F. > Provided no free variable of F falls within the scope of a > bound variable of E. What are the other two transformations? Alpha-conversion (rename a variable) and eta-reduction (turn \x.(f x) into f, when that's safe). The one I mentioned above is beta-reduction. Yes, the proviso you quote is correct. I was simplifying. > _ The point of all this is that that is, in some sense, > _ *all* you need; within this system you can model all > _ of mathematics, or at least all the mathematics > _ Alonzo Church cared about. You have to "encode" > _ everything as a function. For instance, here's a > _ famous way of representing the non-negative integers: > _ 0 "is" Lx.(Lf.(Ly.y)) > _ 1 "is" Lx.(Lf.(Ly.f y)) > _ 2 "is" Lx.(Lf.(Ly.f (f y))) > _ 3 "is" Lx.(Lf.(Ly.f (f (f y)))) > _ etc. > What?? Maybe this is add 0, add 1, etc. Argle. I'm not quite sure what I was thinking when I wrote those down. No, it's not add-0, add-1, etc; it's just a mangled version of what I actually meant. What I actually meant, coincidentally enough, is ... > 0 = (Lfx.x) > 1 = (Lfx.fx) > 2 = (Lfx.f(fx)) > 3 = (Lfx.f(f(fx))) ... what you wrote. > _ Important features of the lambda calculus > _ 1. In the lambda calculus, *everything* is a function. > _ 2. In so far as the lambda calculus has a preferred "order > _ of evaluation", it's "normal order", which amounts to > _ evaluating things as you need them. > What's this normal order? Always reduce the leftmost thing available. In particular, when you have an application "f x", you always prefer to reduce things in f before things in f. In particular, if it turns out that you don't need x then you'll never bother reducing any of its bits. > Other questions: > _ ((lambda (g n) (g g n)) > _ (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5) > > (Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5) > > What's the lambda formula for > = as in =0n > if as in if(=0n)1 > - as in -n1 ? I believe you know the answers to all these questions :-). > and finally, let as in > > (let ((f (lambda (f n) > (if (= 0 n) 1 (* n (f f (- n 1)))))) > (n 5)) > (f f n)) > > _ Recursion without a function actually calling itself! (let ((x y)) E) === ((lambda (x) E) y). -- Gareth McCaughan Gareth.McCaughan@pobox.com .sig under construc