Re: Lambda calculus and it relation to LISP

[David Kastrup]

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