Re: Lisp history: IF, etc.

Paul Rubin <no.email@nospam.invalid> writes:

   Alan Bawden <alan@csail.mit.edu> writes:
   > But when McCarthy was inventing Lisp, nobody thought that pure Lambda
   > Calculus was anything like a programming language.

   Ah ok, that was before my time.  I had been under the impression that
   Lisp had started as lambda calculus with some concessions to
   practicality added.

   https://en.wikipedia.org/wiki/Lisp_(programming_language)#History

   gives that impression too.

It's a common misconception that McCarthy was trying to turn Lambda
Calculus into a programming language.  But if you read what he was
writing at the time you will find that he was actually trying to turn
First Order Predicate Calculus (FOPC, i.e. Mathematical Logic) into a
programming language.  He added LAMBDA (and LABEL) because he needed
LAMBDA in order to define recursive functions, but as he himself often
admitted, he didn't really understand Lambda Calculus, he just needed
the notation.  He _did_ understand FOPC.

Once you understand his true goal, a lot of history becomes more clear.
For example, it explains why McCarthy often talked about conditional
expressions as such an important idea, while he devoted much less ink to
lambda expressions.  From our point of view it's clear that adding
LAMBDA to a programming language was more significant then adding COND,
but that's not how he saw things at the time.

It also explains how Common Lisp wound up being a Lisp-2.  We have
separate namespaces for functions and values because that's how FOPC
works, so that's how Lisp 1.5 was supposed to work.  (It doesn't
_actually_ work that way, but it's clear from the manual that that's how
you're supposed to think about it!)  Most Lisps followed Lisp 1.5 down
that path.

   > It's only since then that we've done the work to make that practical.

   Does Scheme not count?  I think lazy evaluation is not needed since the
   input to the Church boolean (I hope I have the jargon right) is two
   lambda abstractions.  The boolean selects one of them, and the result is
   applied to whatever the next thing is.

When I wrote "make that practical" I was referring to using Lambda
Calculus _directly_ as a practical programming language.  And no, I
don't think that Scheme lets you do that.  Even ignoring how
inconvenient it would be to wrap lambdas around both arms of all your
conditionals, the big problem is what do you do about side effects like
I/O?  You really need Monads (or something like them) in order to make
that work, and it wasn't until sometime in the 1980s that anybody
figured that out.  And I'm not even sure that Haskel (for example)
counts as using Lambda Calculus directly as a programming language.  It
seems like there are a lot of ideas knocking around in Haskel that are
well beyond what Church invented!

But all this happened well after McCarthy developed Lisp.  If you had
told anyone in 1960 that they should look to Lambda Calculus for useful
insights into how to design a programming language, they probably would
have thought it was just about as relevant as Turing Machines are to
designing actual computing hardware -- perhaps not completely
irrelevant, but not a very practical.

- Alan