Re: Lambda calculus and it relation to LISP

[Barb Knox]

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   |   
-----------------------------