McCarthy’s recipe for a programming language

On October 23, 2011 John McCarthy died. He is remembered as the inventor of Lisp, for contributions to the theory of computation, and for contributions to artificial intelligence. In this essay I argue that he did more than inventing Lisp; even more than originating the concept of high-level programming: he showed to those willing to see it a recipe for designing high-level languages. I support my argument by turning the clock back to 1950 and imagining how McCarthy’s recipe could have been followed at that point in time. By taking this unusual point of view I hope to bring out more clearly McCarthy’s contribution to programming languages.

Scruffies and Neats in Artificial Intelligence

In a previous essay [0] I traced the Lighthill Affair to the tension between the scruffies and the neats in Artificial Intelligence. As a reminder the official [1] definition of these terms:

” … the neats — those who think that AI theories should be grounded in mathematical rigor — versus the scruffies — those who would rather try out lots of ideas, write some programs, and then assess what seems to be working.”

For a few lines this is a pretty good characterization. But I think it only scratches the surface. In this essay I will explore the contrast in temperament and attitude that exists along several dimensions and is found elsewhere in science.

The MIT style in Artificial Intelligence 1958 – 1985

The MIT style in Artificial Intelligence 1958 – 1985

In a previous article I illustrated the tension in Artificial Intelligence (AI) between two mentalities, generally referred to as “scruffy” and “neat”. I started by accepting the characterization by Norvig and Russell [1].

“… the neats — those who think that AI theories should be grounded in mathematical rigor — versus the scruffies — those who would rather try out lots of ideas, write some programs, and then assess what seems to be working.”

Critics of my article have opened up so many dimensions of scruffy versus neat that it is hard to know where to start. From my disorganized thoughts one recurrent theme emerged: the distinctive MIT style during the formative years of AI.

From the Chronicles of Scruffy Versus Neat: the Lighthill Affair

The 1973 Lighthill Affair was an Affair in the sense of the Dreyfus and Profumo Affairs. And although it was scaled down to teacup size, it was big enough to make it into a textbook published twenty years later:

… the Lighthill Report, which formed the basis for the decision by the British government to end support of AI research in all but two universities. (Oral tradition paints a somewhat different and more colorful picture, with political ambitions and personal animosities that cannot be put into print.) [1]

In this article I will put in print some of the things hinted at here, and elaborate on the issues that have remained topical.

Another Scoop by Dijkstra?

Edsger W. Dijkstra (1930–2002) is known and remembered for many things in programming and in computing. But it seems that the problem of efficiently generating the sequence of prime numbers (2, 3, 5, 7, …) is not among them. I recently re-read his 1972 Notes on Structured Programming [5] and noticed for the first time, tucked away in a few lines, a remarkable insight that resolves the stand-off between the Sieve of Eratosthenes (efficient in terms of time, but not memory) and the method of Trial Division (efficient in terms of memory, but not time).

Unprotected Numerical Computation and Its Safe Alternatives

Conventional numerical computation is marvelously cheap, and it seems to work most of the time. The computing profession has long neglected to develop methods appropriate for those situations where cheapness is not an overriding concern and where “seems to work most of the time” is not good enough.

Many textbooks in numerical analysis start by showing that in certain situations the small errors caused by the use of floating-point arithmetic can rapidly grow and render the result of the computation meaningless. Such textbooks describe conditions under which mathematical algorithms can safely be transplanted to floating-point hardware: that the problem be well-conditioned and that the algorithm be stable. In the early days computing centres employed numerical analysts to make sure that none of the scarce processor cycles got wasted on meaningless results caused by ill-conditioned problems or unstable algorithms.

Much has changed since then. Thousands of scientists and engineers have on their desks gigaflops of computing power, and there is not a numerical analyst in sight. Although an even larger part of problem-solving is entrusted to the computer, the same fragile methodology is followed. And still the only justification is that conventional numerical computation seems to work most of the time.

A Standard of Excellence

When an industry-wide standard gets established, it is often lamented as a regression to the mediocre, if not outright bad. VHS vs Sony Beta comes to mind. This time, however, I come to praise a standard, not to bury one. I am going to talk about a success from that era: IEEE standard 754 for binary floating-point arithmetic.

From Formulas to Algorithms

Before computers, computation went like this: a scientist invented a formula; the user plugged in suitable values and evaluated the resulting variable-free expression. The user typically did not have the expertise to judge the correctness of the formula. Though the compilers of formula books tried to cover all important cases, it was common that a user failed to find one for the situation at hand. In such compilations one can find formulas for Annuity Whose Present Value Is One, Return on Investment, Moment of Inertia (for circular sheet, hollow circular cylinder, and dozens of other shapes), Curved Surface of Cone, Net Present Value, and many others (but maybe not the one you need right now).

Initially, computers reflected the age of the formula: FORTRAN comes from FORmula TRANslator. But FORTRAN was found more useful for writing algorithms in which formulas played a minor role.  Used in the right way, an algorithm can be self-explanatory in a way that the old-style formulas were not. The formulaic paradigm was authoritarian in the sense that the user did not get an explanation of the formula found in the book. Thus the algorithmic paradigm is less authoritarian: access to the source code implies access to an explanation, not of a formula, but of the number you are getting. Yet relics from the age of formulas linger. In this article I discuss two of these and use them to illustrate the power of the algorithmic approach.

An Interview with Paul McJones

In my quest for pioneer programmers I was fortunate to get in touch with one who has a possibly unrivalled record of participation in projects that are important in the development of computing over the decades. I am speaking of Paul McJones, who was part of the team assembled by Butler Lampson to develop Cal TSS, one of the first operating system designs to tackle the problems of protected and even mutually-suspicious subsystems. At IBM San Jose Research he worked with John Backus on his RED languages and with the System R group on the first relational database system. At Xerox he participated in the development of the Star office automation system (based on PARC’s Alto personal computer). Via Tandem Computer he went to do research at DEC SRC in Palo Alto. After various Silicon Valley start-ups he went to work at Adobe. This included a collaboration with Alexander Stepanov. A spin-off of this research is Elements of Programming (by A. Stepanov and P. McJones, Addison-Wesley, 2009), which presents a novel methodology that spans the gap between abstract mathematics and efficient algorithms.

In the following interview we try to cover at least a little bit of this wide and varied terrain.

In Defense of “Beautiful Code”

In my May 2008 APP article “Beauty Is Our Business?” I argued that neither in mathematics nor in programming the concept of Beauty is a useful one. But the B-word is hard to suppress. A kind reader of APP directed my attention to “Beautiful Code: Leading Programmers Explain How They Think”, a collection edited by Andy Oram and Greg Wilson. This book already existed when I wrote my article, so I could have known about it. It’s good that I didn’t, because we now have the benefit of Jeff Atwood’s comments [seen Sept. 30, 2010]. His critique is that an idea can be beautiful, or an algorithm. But the code embodying them is not beautiful, Atwood maintains, and code stands in the way of the appreciation of the beauty of the underlying idea or algorithm. In this article I argue that handwaving is not enough, that such abstract thing as an idea or an algorithm needs embodiment to be appreciated, and that for an algorithm the natural embodiment is in the form of code.