Re: Lambda calculus and it relation to LISP

[Barb Knox]

In article <20021007025544.G57236-100000@agora.rdrop.com>, William Elliot
<mars@xx.com> wrote:

> On 7 Oct 2002, David Kastrup 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))))) )
[snip]

> What's lambda calculus expressions for -, <, if, = ?

'-' and '<' are a bit tricky, as is most LC arithmetic using Church
numerals -- see a textbook that covers LC.

'if' is usually
  (lambda (test) (lambda (ifTrue) (lambda (ifFalse) ((test ifTrue) ifFalse))))
or
  (lambda (test ifTrue ifFalse) (test ifTrue ifFalse))

where the value for TRUE is
  (lambda (ifTrue ifFalse) ifTrue)
and the value for FALSE is
  (lambda (ifTrue ifFalse) ifFalse)

As you can see, raw LC makes a pretty horrible programming language, which
is why useable functional languages (1) are strongly typed, and (2) have
primitives for numbers, strings, etc. so that one does not have to deal
with Church numerals, etc.

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