[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Lambda calculus and it relation to LISP
From: |
David Kastrup |
Subject: |
Re: Lambda calculus and it relation to LISP |
Date: |
08 Oct 2002 05:05:23 +0200 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.3.50 |
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
- Re: Lambda calculus and it relation to LISP, (continued)
- Re: Lambda calculus and it relation to LISP, gnuist, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP, David Kastrup, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Christian Lemburg, 2002/10/07
- Re: Lambda calculus and it relation to LISP, ozan s yigit, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Barb Knox, 2002/10/07
- Re: Lambda calculus and it relation to LISP,
David Kastrup <=
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/07
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/07
- Re: Lambda calculus and it relation to LISP, William Elliot, 2002/10/08
- Re: Lambda calculus and it relation to LISP, Fred Gilham, 2002/10/05
- Re: Lambda calculus and it relation to LISP, Kaz Kylheku, 2002/10/05
- Re: Lambda calculus and it relation to LISP, Thaddeus L Olczyk, 2002/10/06
- Re: Lambda calculus and it relation to LISP, Alfred Einstead, 2002/10/11