From: William Elliot <mars@xx.com>
Subject: Re: Lambda calculus and it relation to LISP
Date: Sun, 6 Oct 2002 05:03:09 -0700 [thread overview]
Message-ID: <20021006050255.A63895-100000@agora.rdrop.com> (raw)
In-Reply-To: <slrnapt79s.8dr.Gareth.McCaughan@g.local>
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! =-----
next prev parent reply other threads:[~2002-10-06 12:03 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-10-05 3:20 Lambda calculus and it relation to LISP gnuist
2002-10-05 7:51 ` Luke A. Olbrish
2002-10-05 10:46 ` William Elliot
2002-10-12 0:28 ` Alfred Einstead
2002-10-12 4:02 ` William Elliot
2002-10-05 11:44 ` David Kastrup
2002-10-09 4:38 ` James Wong
2002-10-09 4:48 ` William Elliot
2002-10-05 7:58 ` Charles Matthews
2002-10-05 8:05 ` Gareth McCaughan
2002-10-06 12:03 ` William Elliot [this message]
2002-10-06 19:22 ` Gareth McCaughan
2002-10-07 4:58 ` gnuist
2002-10-07 7:14 ` William Elliot
2002-10-07 7:37 ` Barb Knox
2002-10-07 9:34 ` David Kastrup
2002-10-07 9:59 ` William Elliot
2002-10-07 11:10 ` Barb Knox
2002-10-07 14:34 ` William Elliot
2002-10-07 10:44 ` Christian Lemburg
2002-10-08 1:02 ` ozan s yigit
2002-10-07 10:59 ` Barb Knox
2002-10-08 3:05 ` David Kastrup
2002-10-07 23:12 ` Gareth McCaughan
2002-10-07 9:54 ` William Elliot
2002-10-07 22:48 ` Gareth McCaughan
2002-10-08 8:42 ` William Elliot
2002-10-05 14:46 ` Fred Gilham
2002-10-05 16:15 ` Kaz Kylheku
2002-10-06 12:22 ` Thaddeus L Olczyk
2002-10-06 13:46 ` Joona I Palaste
2002-10-12 0:36 ` Alfred Einstead
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20021006050255.A63895-100000@agora.rdrop.com \
--to=mars@xx.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.