[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Lambda calculus and it relation to LISP
From: |
Barb Knox |
Subject: |
Re: Lambda calculus and it relation to LISP |
Date: |
Mon, 07 Oct 2002 23:59:01 +1300 |
In article <x5bs66h9sx.fsf@tupik.goethe.zz>, David Kastrup
<David.Kastrup@t-online.de> wrote:
> see@sig.below (Barb Knox) writes:
>
> > In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
> > gnuist007@hotmail.com (gnuist) wrote:
> > [snip]
> >
> > > In the same way I ask for GRADED examples of use of lambda. I am sure many
> > > of you can just cut and paste from your collection. Examples to illustrate
> > > recursion, etc. And how will you do recursion without/with "LABEL"?
> >
> > Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE. Recursion
> > is done via the "Y combinator", which is a very interesting
> > self-referential hack (in the good sense).
> >
> > 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.
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.
> So we can check it out:
>
> guile> ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y
Y)))))(lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
> standard input:1:27: In expression (f (Y Y)):
> standard input:1:27: Wrong number of arguments to #<procedure (ff n)>
> ABORT: (wrong-number-of-args)
>
> Type "(backtrace)" to get more information.
> guile> (backtrace)
>
> Backtrace:
> 0* [#<procedure (f)> #<procedure (ff n)>]
> 1 [#<procedure (Y)> #<procedure (Y)>]
> 2 (f (Y Y))
>
> Type "(debug-enable 'backtrace)" if you would like a backtrace
> automatically if an error occurs in the future.
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.
--
---------------------------
| BBB b \ barbara minus knox at iname stop com
| B B aa rrr b |
| BBB a a r bbb |
| B B a a r b b |
| BBB aa a r bbb |
-----------------------------
- Re: Lambda calculus and it relation to LISP, (continued)
- Re: Lambda calculus and it relation to LISP, Gareth McCaughan, 2002/10/06
- 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 <=
- Re: Lambda calculus and it relation to LISP, David Kastrup, 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/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