(This document is unfinished.)
So I’ve been reading John Backus’s Turing Award paper from 1977 [Backus 1977], and a lot of the assertions he makes therein seem dubious to me. Perhaps this is a little unfair, since von Neumann computers are now 60 years old, and were only 30 years old when Backus wrote; and much of the interesting stuff in the intervening 30 years has been elaboration on Backus’s ideas. And I’m just some wanker, while Backus was a Turing Award winner, so probably whatever I can say here is pretty obvious now; but quite a bit of it was anticipated by Dijkstra’s EWD-692 response immediately afterwards.
According to Eliezer Yudkowsky, Max Gluckman once said: “A science is any discipline in which the fool of this generation can go beyond the point reached by the genius of the last generation.”
So maybe this article is a demonstration that computer programming is a science.
Still, I thought it would be useful to collect 30 years of perspective on the very influential ideas he expresses in this paper.
Backus’s initial complaint about the obesity of von Neumann languages was myopic, coming as it did on the heels of five years of remarkable innovation in the invention of small von Neumann languages. Although he correctly identifies “word-at-a-time thinking” as a serious obstacle to good programming, its cure is garbage collection, not the removal of the assignment statement.
The point-free style he advocates could have been adopted a decade or more before he wrote his paper, but it wasn’t, apparently because programs in that style are fucking hard to read. Many languages available today reduce the problems he identified with von Neumann languages of the time, as illustrated by his inner product example, but without using that point-free style; some of those languages were already available when he wrote, but were not in the mainstream.
Most people who have commented on the paper don’t seem to have read most of the meat of the paper, probably because it’s badly presented. I suggest another order of presentation that I think makes them easier.
Backus’s pessimism that formal semantics would make von Neumann languages more tractable was wrong, although this is in part because those languages have been redesigned over the years to be analytically tractable. Similarly, his assertion that the word-at-a-time nature of von Neumann languages makes them non-extensible is both unsupported and simply mistaken, as illustrated by ample counterexamples from his time and our own.
Backus: “Each successive language incorporates, with a little cleaning up, all the features of its predecessors plus a few more. Some languages have manuals exceeding 500 pages; others cram a complex description into shorter manuals by using dense formalisms. . . . For twenty years programming languages have been steadily progressing toward their present condition of obesity; as a result, the study and invention of programming languages has lost much of its excitement.”
The C programming language was already in use at Bell Labs and a few universities when he wrote this, although Kernighan and Ritchie’s manual (120 pages, I think?) didn’t come out until, I think, the next year. C is not a minimal language, but as K&R says, it demonstrates that a language that doesn’t have everything can be easier to use than those that do. Other smallish languages in use in 1977 — almost all substantially created during the previous five years — included BLISS-10 and BLISS-11, Scheme [Sussman 1975], Prolog, Smalltalk, and, of course, Forth, which is perhaps the ultimate in simplicity of mechanism among high-level languages.
Backus does say, in the next paragraph, “Since large increases in size bring only small increases in power, smaller, more elegant languages such as Pascal continue to be popular.” But I think this dramatically understates the reality of 1977, as seen from 2007; there had been a renaissance in small, elegant languages over the several years immediately preceding Backus’s paper, languages whose simplicity, elegance, and power has kept many of them in use until the present day. Some of them were not widely known at the time, but perhaps Backus’s disgust owes more to overexposure to PL/1, which had been standardized the previous year after 13 years of drafts, and to Algol 68, than to a paucity of alternatives.
Dijkstra makes a similar comment in EWD-692:
He writes that “smaller, more elegant languages than Pascal continue to be popular”, where in the case of Pascal “rapidly gaining in popularity” would be more accurate.
Backus says, “Not only is the tube [between the processor and memory] a literal bottleneck for the data traffic of a problem, but, more importantly, it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand.”
This is necessarily true of programs for the Altair 8800, which shipped with 256 bytes of memory and could run Altair BASIC in 4096 bytes, or an un-upgraded Apple ][, which I think had shipped around the time of Backus’s talk. But, as demonstrated by APL, the various FP and FL systems that came after this paper, and the “Lambda: The Ultimate” series of papers around the same time, the limitation is not really imposed by the hardware architecture; it takes some cleverness but not a huge amount of code to allow those single words to represent the larger conceptual units in question.
In a sense, McCarthy’s 1960 Lisp article that Backus cites also showed this — or rather, the Lisp implementation that followed it in the next few months. That Lisp (modulo its bugs and its dynamic scoping, which had to be papered over with the FUNARGS (XXX?) form) was capable of more or less directly implementing all of the primitive functions and functional forms that Backus presents in this paper.
His sample program from section 5.2 is:
Def Innerproduct = (Insert +)o(ApplyToAll ×)o Transpose
or
Def IP = (/+)o(α ×)o Trans.
where “o” is the function composition operator, “×” multiplication, and “α” the alpha he uses for ApplyToAll. We can define the operations needed to write this quite concisely in modern Scheme, with lists for vectors, as follows. (Remember that Backus’s functions are to be applied to a single argument which is a vector of its arguments.)
(define (plus args) (apply + args))
(define (x args) (apply * args))
(define (o f g) (lambda (x) (f (g x))))
; Note that this implementation doesn't discover whether its
; argument has a unit so that it can do the right thing in the
; case of an empty vector.
(define (insert fn)
(lambda (args) (if (null? (cdr args)) (car args)
(fn `(,(car args)
,((insert fn) (cdr args)))))))
(define (alpha fn)
(lambda (args) (if (null? args) '()
`(,(fn (car args)) .
,((alpha fn) (cdr args))))))
(define (transpose1 heads tails)
(if (null? tails) '()
(cons (cons (car heads) (car tails))
(transpose1 (cdr heads) (cdr tails)))))
(define (transpose0 lst)
(if (null? lst) '() (cons '() (transpose0 (cdr lst)))))
(define (transpose lst)
(transpose1 (car lst) (if (null? (cdr lst)) (transpose0 (car lst))
(transpose (cdr lst)))))
(define ip (o (o (insert plus) (alpha x)) transpose))
(begin (display (ip '((1 2 3) (6 5 4)))) (newline)) ; outputs "28"
You will notice that the definition of “ip” here is identical to the one from Backus’s paper, except for being in prefix order with parentheses. This code makes heavy use of closures, but with some cost in readability could use the Lisp 1.5 FUNARGS (XXX?) form instead, and similarly quasiquotation could be replaced with explicit calls to “cons”. Maybe it would be 30 lines of code instead of 22. (I don’t have a Lisp 1.5 implementation handy to test on, so I can’t say for sure.)
So, however tied we may have been to “word-at-a-time thinking” in the first 30 years of von Neumann computers, there had been systems in use since 1964 or so that could express Backus’s functional forms in a few lines of code each.
And APL had already shown some of the way from the mid-1960s on. While APL expressions’ values were internally represented as pointers, they were presented to the user in a very non-word-at-a-time fashion; and indeed, in many cases, they represented finite maps with domains of integers less than some limit, or integer pairs, and so on.
And, of course, Church’s SK-combinators (which Backus mentions in his paper) are straightforward to implement even in ancient Lisp, sufficient to express any computable function, support the writing of higher-order functions, and don’t name their arguments. (But I think the first efficient implementations of SK-combinators on computers, using graph reduction instead of tree reduction, either did not precede Backus’s paper by much, or actually followed it.) XXX find out, asshole
So why had programming with higher-order functions that don’t name their arguments — what we now call “point-free style” — not taken off in the 1960s? Was it really because programmers were too tied to “word-at-a-time thinking”? That doesn’t seem plausible to me.
The alternative I suggest — after 40 years of our collective experience with “point-free style” in Forth, as well as 30 years in languages inspired by this very paper, languages such as Miranda, Haskell, and ML, plus more than 50 years of APL one-liners that are nearly point-free — is that while point-free programs are indeed much easier to “refactor” (i.e. perform semantics-preserving transformations on), they are fucking hard to read, maybe because they’re too abstract.
This is based not only on my own limited experience, but the experiences of other hackers who have spent years programming in point-free style. Even the HaskellWiki Pointfree page [HaskellWiki Pointfree] admits that it can sometimes be hard to read:
Point-free style can (clearly) lead to Obfuscation when used unwisely. As higher-order functions are chained together, it can become harder to mentally infer the types of expressions. The mental cues to an expression’s type (explicit function arguments, and the number of arguments) go missing.
Point-free style often times leads to code which is difficult to modify. A function written in a pointfree style may have to be radically changed to make minor changes in functionality. This is because the function becomes more complicated than a composition of lambdas and other functions, and compositions must be changed to application for a pointful function.
Perhaps these are why pointfree style is sometimes (often?) referred to as pointless style.
(However, other parts of the same page advocate point-free style as “clearer”, “cleaner”, and “good discipline”.)
So today, the state of the art (due largely to work in languages inspired by Backus’s paper) is something like this Python program:
def innerproduct(a, b): return sum(ai * bi for ai, bi in zip(a, b))
Which compares favorably to Backus’s 1977 “von Neumann program for Inner Product”:
c := 0
for i := 1 step 1 until n do
c := c + a[i] × b[i]
(This could be translated to C as follows, gaining a bit of clarity but not changing in any substantial way:)
c = 0;
for (i = 0; i < n; i++) c += a[i] * b[i];
Backus lists seven undesirable properties of this program:
a) Its statements operate on an invisible “state” according to complex rules.
This is not really true of the Python program above. Although it is a
user-visible feature that the expression (ai*bi for ai, bi in zip(a,
b)) results in a stateful iterator that eventually runs out of values,
this program does not make use of that property.
The rules that govern the evaluation of the program are more complex than those of Backus’s FP, though.
b) It is not hierarchical. Except for the right side of the assignment statement, it does not construct complex entities from simpler ones.
Actually, the assignment statement contains four nested compound
expressions, made out of five atomic variables and one another. The
Python program contains zip(a, b), ai * bi, the generator
expression, and the sum expression — exactly the same number; but
perhaps zip(a, b) and the generator expression would be more to
Backus’s liking, since they express exactly the return values of the
Trans and (α ×) operations in his functional IP program.
c) It is dynamic and repetitive. One must mentally execute it to understand it.
This is not true of this Python program, although it is true of many
Python programs. Incidentally, this is exactly Guido van Rossum’s
reason for wanting to remove Backus’s “insert”, called reduce, from
Python [van Rossum XXX] — he finds he has to mentally execute the
reduction process to understand it.
d) It computes word-at-a-time by repetition (of the assignment) and by modification (of variable i).
This is true of the actual execution of the Python program, as it is of the execution of Backus’s FP programs or any other programs on a von Neumann machine; but if you try to interpret it as a statement about the user-level semantics of the code, it reduces to criticism (c).
e) Part of the data,
n, is in the program; thus it lacks generality and works only for vectors of lengthn.
Not true of the Python program.
f) It names its arguments; it can only be used for vectors
aandb. To become general, it requires a procedure declaration. These involve complex issues (e.g. call-by-name versus call-by-value.)
Almost as true of the Python program as of the C version; in fact, the procedure declaration constitutes fully half of my program as written.
“Call-by-name” here refers to evaluating procedure parameters when their values are needed, rather than before entering the procedure; it’s like lazy evaluation, but may evaluate the procedure parameter more than once. In effect, this allows you to construct any arbitrary zero-argument closure, called a “thunk”, subject to the limitations of what you can express in an expression in the language in question.
In the cases where the parameter will always evaluate to the same value, it is therefore just a gratuitously inefficient version of lazy evaluation; in the cases where it can evaluate to different values, its value therefore depends on some information that could be thought of as a parameter to the thunk, but which generally needs to be passed in by mutating some apparently-unrelated variable, and so in those cases, it is just a gratuitously bug-prone version of a general closure facility (limited to passing the closures downward through the stack).
“Call-by-name” was therefore replaced by a combination of call-by-reference and a general closure facility, albeit one limited to “downward funargs”, in Pascal (XXX did Algol-60 have downward funargs? I think so); and C and most languages designed since then have simply stuck to call-by-value. So, although call-by-name does indeed involve complex issues, it should have been an irrelevancy long before 1977, and merely adding procedure declarations to your language does not imply that your semantics will suffer the slings and arrows of outrageous call-by-name.
XXX sometimes people say “call-by-name” when they mean “lazy evaluation”; maybe that’s what Backus meant?
(Of the other languages I’ve used or mentioned in this note, C, Scheme, Python, Smalltalk-80, APL, OCaml, 1960 Lisp, Miranda, Haskell, ML, and Forth just use call-by-value; Perl 5 just uses call-by-reference; C++ has both call-by-value and call-by-reference; Algol 60 has both call-by-value and call-by-name; Prolog uses something else entirely; Altair BASIC didn’t have procedures; I’m not sure about BLISS-10 and BLISS-11; Lisp 1.5 had call-by-value and, I think, also FEXPRs; I think Smalltalk-72 did something vaguely FEXPR-like; and PL/1 and (I think) Algol 68, consistent with the rest of the language design, have every horrifying deformed argument-passing convention you can imagine.)
However, the distinction between call-by-value and call-by-name includes another complexity — strictness. A function “f” is strict in some parameter if it can’t compute its return value without getting the value of that parameter. Backus calls this property “bottom-preserving”, and not having procedure declarations has not saved him from strictness; throughout the paper there are a number of minor logical errors having to do with this particular extra complexity.
Backus implies that procedure declarations import some other complexities that he hasn’t mentioned; the ones I can think of are variable scoping (lexical vs. dynamic vs. broken) and the creation of closures (downward-only or generalized; interchangeability with non-closure function pointers; etc.).
This absence of variables is the central difference, as I read it, between Backus’s proposed programming system and most of the purely applicative systems that preceded it: unlike them, it doesn’t have lambda substitution. It is interesting to note that nearly all of the systems inspired by Backus’s paper over the ensuing 30 years have acquired lambda substitution rather quickly.
g) Its “housekeeping” operations are represented by symbols in scattered places (in the for statement and the subscripts in the assignment). This makes it impossible to consolidate housekeeping operations, the most common of all, into single, powerful, widely used operators.
This is still somewhat true of the generator expression (... for
... in ...) but not the sum and zip operations. Backus never
defines “housekeeping” anywhere in his paper, but as additional
examples, he gives function composition, matrix transposition,
apply-to-all, and “insert”, more commonly known as “reduce” or “fold”.
A modern C++ program, using the STL, is somewhat similar in structure,
although dramatically wordier. C++ is probably the poster child for
obese von Neumann languages; here I have included the entire file with
a main() function, because that turned out to be a little tricky for
me to write concisely with my limited knowledge of C++, and I would
hate for anyone else to have to suffer the same way. It’s only the 4
lines inside innerproduct that correspond to the 2-3 lines of C
given at the top of this section or the half-line of Python.
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
template<typename T>
T innerproduct(vector<T> a, vector<T> b) {
vector<T> result;
transform(a.begin(), a.end(), b.begin(),
back_insert_iterator<vector<T> >(result), multiplies<T>());
return accumulate(result.begin() + 1, result.end(), result[0], plus<T>());
}
#define arrayend(array) ((array)+sizeof(array)/sizeof((array)[0]))
int main(int argc, char **argv) {
int aa[] = {1, 2, 3};
int bb[] = {6, 5, 4};
vector<int> a(aa, arrayend(aa)), b(bb, arrayend(bb));
cout << innerproduct(a, b) << endl;
return 0;
}
(I think that’s purely standard C++. I tested it with g++ 4.1.2.
There’s no particular reason transform() couldn’t have been defined
to produce an InputIterator instead of consuming an
OutputIterator, but it wasn’t. Oh, and the STL contains an
inner_product() template function that does this already, but you have
to give it a starting value, as with accumulate(), so it’s hard to
make a call to it generic across element types.)
(A note about performance: the above program compiles to 3632 bytes of machine code, on the order of 750 instructions, containing obvious inefficiencies; the inner-product function itself, instantiated for vectors of integers, is 86 instructions, and on my laptop, it takes 3300 nanoseconds on Backus’s example vectors. By comparison, the analogous non-generic C function, with the code at the top of this section, is 23 instructions, contains no calls to other functions, and consequently executes in 54 nanoseconds. So much for the STL’s vaunted “absolute efficiency”. The C++ version also requires four dynamic libraries at run-time.)
In “A Short History of STL” [Stepanov 2007], Stepanov writes about how his work was inspired by Backus’s FP work.
In OCaml, which is very much inspired by Backus’s paper, we could write:
List.fold_left2 (fun a b c -> a + b * c) 0
Although that’s not generic across numeric types the way the Python and C++ versions are.
In Squeak Smalltalk, it looks like this, as a method on
SequenceableCollection:
innerProduct: aCollection
^ (self with: aCollection collect: [:a :b | a * b ]) sum.
I don’t know if with:collect: and sum existed in Smalltalk-80, let
alone the Smalltalk that existed in 1977; the oldest version in Squeak
was in 1999 by “di”, which is presumably Dan Ingalls, but older
versions may exist.
In R5RS Scheme, if I don’t restrict myself to trying to reproduce the structure of Backus’s program exactly using facilities that I’m sure were present in early Lisp, I can write it quite concisely as well:
(define (innerproduct a b) (apply + (map * a b)))
I don’t know when Scheme’s map acquired the ability to apply to an arbitrary number of arguments, but I suspect it was a bit later than Backus’s paper.
The Smalltalk and Scheme versions, too, are generic across all numeric types; although the Scheme version, unlike the Python, C++, and Smalltalk versions, doesn’t support user-defined numeric types.
These programs are improvements over the C version along Backus’s criteria in the following ways: Python: abceg; C++: beg; OCaml: abceg; Squeak: abceg; Scheme: aceg.
So, in sum, von Neumann programming languages — the avant-garde, if not yet the mainstream — have adopted features that provide most of Backus’s desiderata, but without requiring the point-free style he considers crucial. Some of them, I think, had those features before his paper.
In section 4, Backus writes, “The assignment statement is the von Neumann bottleneck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does. Consider a typical program; at its center are a number of assignment statements containing some subscripted variables. Each assignment statement produces a one-word result.”
But actually, even years before Backus wrote his paper, PL/1 supported
assignment statements that copied entire arrays, and C eventually
acquired the ability to copy structs in simple assignment statements
as well. But you can’t write the functional forms used in Backus’s
“InnerProduct” program in those languages, the way you can in Python,
OCaml, Smalltalk, or Scheme. The key is that, even though assignment
statements in Python or Scheme only copy single words (unlike those in
C and PL/1!) those single words can effectively stand for much larger
data structures that they point to.
In C, a single word can point to a much larger data structure, but you must constantly be aware of the difference between the pointer and the thing it points to, because you must be careful to free the thing it points to before overwriting the last copy of the pointer, or letting it go out of scope. C++ can do better here because its destructors and copy-constructors allow you to automate that work.
So, even though C’s assignment statements and parameter-passing can
copy entire structs (say, complex numbers, or begin-end pointer
pairs), they can’t copy structures of irregular and unpredictable
size, such as the transposed list of pairs in the inner-product
function. Garbage-collected languages can universally pass structures
of irregular and unpredictable size without worrying about who
deallocates them, and so you can toss around a list, or a parse tree,
or an arbitrary-precision number, or an arbitrary-size matrix, or a
drawing, as easily if it were a single byte.
(As long as you don’t mutate it. Once you start mutating it, you have to worry about aliasing. But most of the time, that doesn’t impose a large practical complexity penalty on your programs — just your proofs.)
In sum, Backus misidentified the source of word-at-a-time thinking; it is not the assignment statement and its ability to transfer only a word at a time, but rather the hassle of manual memory management.
This is perhaps somewhat surprising; garbage collection had been invented for Lisp in 1958 or 1959, and Algol-68 implementations were required to provide it. But it seems that in 1977, Backus didn’t have much experience programming in garbage-collection languages. Perhaps this is because, despite Algol-68’s mandate, garbage-collected programming environments weren’t in wide use by 1977, largely because garbage collection was grossly inefficient until the invention of generational garbage collection (in 1982? XXX).
However, this myopia about garbage collection was not limited to Backus; Dijkstra comments in EWD692, about this very paper: