From: David Kastrup <David.Kastrup@t-online.de>
Subject: Re: Lambda calculus and it relation to LISP
Date: 08 Oct 2002 05:05:23 +0200 [thread overview]
Message-ID: <x5y9998wb0.fsf@tupik.goethe.zz> (raw)
In-Reply-To: see-0710022359020001@192.168.1.2
see@sig.below (Barb Knox) writes:
> In article <x5bs66h9sx.fsf@tupik.goethe.zz>, David Kastrup
> <David.Kastrup@t-online.de> 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
next prev parent reply other threads:[~2002-10-08 3:05 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
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 [this message]
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
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=x5y9998wb0.fsf@tupik.goethe.zz \
--to=david.kastrup@t-online.de \
/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.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).