Re: Lisp history: IF, etc.

Alan Bawden <alan@csail.mit.edu> writes:

Kaz Kylheku <643-408-1753@kylheku.com> writes:
>
   On 2024-04-03, Alan Bawden <alan@csail.mit.edu> wrote:
   > Lisp doesn't really have statements _because_ McCarthy invented the
   > conditional expression.  That's kind of the point.  Other programming
   > languages at the time (e.g. FORTRAN and ALGOL) only had conditional
   > statements.  McCarthy invented the conditional expression and thus
   > created the first expression-only programming language.
>
   However, conditional expressions ultimately come from math. E.g for
   specifying a discontinuous function:
>
      f(x) = { x, if x >= 0
             { 0, if x < 0
>
   If you think about it, it's actually kind of ignorant to invent a
   programming language with imperative if statements, but in which where
   the math conditional is missing.
>
If you think like a historian, you don't describe this as "ignorant".
It's just not something that was above the horizon in the mind set of
the time.  After all, that mathematical notation you are referring to
isn't something that mathematicians get very formal about.

So true.

It has a status that's midway between being able to define something
using a simple equation, and having to resort to a definition in the
form of a paragraph of words.  Realizing that you could tighten that
notation up and use it in a programming language _as a kind of
expression_ is actually a bit of a leap.

There's a paper from 1961--1963 in which he defines the conditional
expression with the intention of being able to define functions
recursively.

--8<---------------cut here---------------start------------->8---
  A BASIS FOR A MATHEMATICAL THEORY OF COMPUTATION
  JOHN McCARTHY
  1961--1963

  [This 1963 paper was included in Computer Programming and Formal Sys-
  tems, edited by P. Braffort and D. Hirshberg and published by
  North-Holland.  An earlier version was published in 1961 in the
  Proceedings of the Western Joint Computer Conference.]

  [...]

  The present paper is an attempt to create a basis for a mathematical
  theory of computation.  [...]

  [...]

  2.1 Functions Computable in Terms of Given Base Functions

  Suppose we are given a base collection F of functions (including
  predicates) having certain domains and ranges. [...] Our object is to
  define a class of functions C{F} which we shall call the class of
  functions computable in terms of F.  Before developing C{F} formally,
  we wish to give an example, and in order to give the example, we first
  need the concept of conditional expression. In our notation a
  conditional expression has the form

                  (p1 → e1, p2 → e2, . . . , pn → en)

  which corresponds to the ALGOL 60 reference language (12) expression

       if p1 then e1 else if p2 then e2 . . . else if pn then en.

  [...]

  Some examples of the conditional expressions for well known functions
  are |x| = (x < 0 → -x, x >= 0 → x) [...]

  Now we are ready to use conditional expressions to define functions
  recursively. For example, we have

                 n! = (n = 0 → 1, n =/= 0 → n · (n − 1)!)

  [...]
--8<---------------cut here---------------end--------------->8---