From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: William Elliot Newsgroups: gmane.emacs.help Subject: Re: Lambda calculus and it relation to LISP Date: Sun, 6 Oct 2002 05:03:09 -0700 Organization: Newsfeeds.com http://www.newsfeeds.com 80,000+ UNCENSORED Newsgroups. Sender: help-gnu-emacs-admin@gnu.org Message-ID: <20021006050255.A63895-100000@agora.rdrop.com> References: <9e8ebeb2.0210041920.2e480123@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 1033906102 18529 127.0.0.1 (6 Oct 2002 12:08:22 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 6 Oct 2002 12:08: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 17yACp-0004oe-00 for ; Sun, 06 Oct 2002 14:08:19 +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 17yAAi-0002sl-00; Sun, 06 Oct 2002 08:06:08 -0400 Original-Newsgroups: gnu.emacs.help,comp.lang.lisp,sci.math,sci.logic X-X-Sender: In-Reply-To: Original-NNTP-Posting-Host: 199.26.172.34 Original-X-Trace: corp.newsgroups.com 1033904715 199.26.172.34 (6 Oct 2002 06:45:15 -0500) Original-Lines: 95 X-Comments: This message was posted through Newsfeeds.com X-Comments2: IMPORTANT: Newsfeeds.com does not condone, nor support, spam or any illegal or copyrighted postings. X-Comments3: IMPORTANT: Under NO circumstances will postings containing illegal or copyrighted material through this service be tolerated!! X-Report: Please report illegal or inappropriate use to X-Abuse-Info: Please be sure to forward a copy of ALL headers, INCLUDING the body (DO NOT SEND ATTACHMENTS) Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!l-out.nntp.be!corp.newsgroups.com!agora.rdrop.com!mars Original-Xref: shelby.stanford.edu gnu.emacs.help:105763 comp.lang.lisp:95730 sci.math:549820 sci.logic:61593 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:2309 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:2309 Gareth.McCaughan@pobox.com Using L for lambda and convention (Lxy.M) for (Lx.(Ly.M)) and = for transform or converts to. wwf: variables wwf N,M ==> wwf (Lx.N), (NM) _ 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? _ 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. 0 = (Lfx.x) 1 = (Lfx.fx) 2 = (Lfx.f(fx)) 3 = (Lfx.f(f(fx))) ... 0f = I 0fx = x 1f = (Lx.fx) 1fx = fx 2f = (Lx.f(f(x)) 2fx = f(f(x)) 3f = (Lx.f(f(f(x))) 3fx = f(f(f(x))) ... _ So, we represent n by something that takes a function f _ and returns a new function that just applies f n times _ to its argument. Then addition is _ Lm.Ln.Lf.Ly.(m f) ((n f) y) Ok. By my definition for 1. +11 = Lf.Ly.(1f)(1fy) = Lf.Ly.f(f(y)) = 2 By your definition Lx.(Lf.(Ly.f y)) +11 = Lf.Ly.(1f)(1fy) = something complicated _ and multiplication is _ Lm.Ln.Lf.m (n f) Ok Lnfx.nf(fx) successor function. Lmn.nm exponetation m^n _ 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? _ 3. The lambda calculus is purely syntactic; two _ expressions are "equal" if you can transform one to _ the other by the standard transformations. _ 4. Evaluation in the lambda calculus works by repeated textual _ substitution. 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 ? 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! ---- -----= Posted via Newsfeeds.Com, Uncensored Usenet News =----- http://www.newsfeeds.com - The #1 Newsgroup Service in the World! -----== Over 80,000 Newsgroups - 16 Different Servers! =-----