Abacus to Zuse:

A philosophical dictionary of computing

abacus We all take for granted the way we write numbers. To shake up this complacency, we are often asked to imagine doing arithmetic in Roman numerals, which certainly puts the point across. An unfortunate effect, however, is that people get the impression that the merchants of the Roman empire two thousand years ago were unduly handicapped in their arithmetic compared to, say, those of two hundred years ago.

That seems unlikely because of the abacus. The abacus was already ancient at the time of the Roman empire. Even in the mid twentieth century, adepts at the soroban, the Japanese version of the abacus, held their own in competition with expert operators of electro-mechanical calculators.







artificial intelligence

assertion In the verification methods of Floyd and of Hoare logical formulas are attached to selected points in program text. These formulas, called assertions, are to be chosen so that every time execution reaches one of these points, the associated assertion is true.

It is not necessary for assertions to be executable, as this property is to be ascertained independently of any execution on the basis of the definition of the programming language. Thus assertions are not to be confused with the "assert" construct of C, C++, or Java. Use of the construct is an example of audit code (q.v.).

audit code David Gries, in "The Science of Programming" (page 168) argues that a program consisting of a large number of modules has low probability of being correct unless each of its modules has a very high probability of being correct. He notes that his argument is not universally accepted, quoting

Doug McIlroy (Bell Laboratories) disagrees with this argument, claiming that correct programs are made from incorrect parts. Telephone control programs, for example, are more than half audit code, whose business is to recover from unintended states, and the audit code has been known to mask software as well as hardware errors. Also, an incorrect procedure may be called within our own program in a (unknowingly) restricted fashion so that the incorrectness never comes to light. Procedures that blow up for some input work perfectly well in programs that insulate them from these cases.
Before coming across this passage I had not heard of "audit code". Because it struck me as an important concept, I searched for an authoritative definition. As of June 15, 2018 nothing turned up except this particular passage in this particular book. This, of course, after skipping numerous other hits that turned up amusing other readings of "audit code".

banker's algorithm In the fall of 1964 E.W. Dijkstra wrote a note describing an algorithm to prevent deadlock among processes competing for scare resources in a computer system. It is described in terms of an idealized banker with clients with demands for loans. The banker is idealized in the sense that the algorithm makes deadlock impossible. In real life, however, bankers are only in the business because their position allows them to gamble with other people's money in such a way that the upside of a gamble accrues to the banker, while the downside ends up being paid by the bank's clients or the taxpayers via government bail-outs.

The banker's algorithm is one of several appealing metaphors created by Dijkstra for isolating and illustrating problems arising in the design of operating systems. Other ones are the Sleeping Barber (1965) and that of the Dining Philosophers (1965).

Barton Robert S. Barton (1925--2009) was the designer of the Burroughs B5000 and was an influential teacher at the University of Utah. The design of the B5000 took place in 1961. It included a set of innovations each of which were remarkable in their own right: virtual memory, a dialect of Algol 60 as system programming language, a stack architecture with instructions designed to simplify compilers for Algol.

In 1968 Barton joined David Evans, Thomas Stockham, and Ivan Sutherland at the University of Utah. Several of the students influenced by Barton went on to make notable contributions. For example Alan Kay acknowledges that Barton's view of computer architecture contributed to the birth of Smalltalk.

binding time

Boltzmann machine

bottom-up (vs top-down)


chief programmer

Chinese-room argument

code inspection

complexity In the normal world complexity is the opposite of simplicity; in computing it means the opposite of efficiency. In addition to this confusion, it is worth noting that theoretical computer science is almost entirely monopolized by the study of "complexity" of algorithms.

dead computists Not so long ago most famous computists were alive. At the time exceptions were: H. Aiken, J. Eckert, J. Mauchly, J. von Neumann, and A. Turing.

Now their ranks are swelling rapidly. Some of the more recent additions: J. Backus, E. Dijkstra, J. McCarthy, R. Milner, A.J. Perlis, M.V. Wilkes, ...

deadly embrace


design pattern

dining philosophers

display hack When one converts data generated for another purpose into graphical elements, surprising patterns may result. A useful application is to test random-number generators. In the 1960s an effective way of obtaining scrap paper was to get the line printer to sing the national anthem.

Egyptian multiplication Many introductions to programming feature "fast exponentiation", an algorithm that speeds up exponentiation by repeated multiplication. It does this by halving the exponent every time it is even, while squaring the base. In the same way one can speed up multiplication by repeated addition. In current technology, with hardware multiplication this is not important. It was different in Egypt around 1700 B.C., when the Rhind Papyrus was written. This document contains a description of fast multiplication by repeated addition optimally interspersed with doubling. In "From mathematics to generic programming" by A. Stepanov and D. Rose a generic version is discussed at length under the heading "Egyptian Multiplication".

elegance Boltzmann is reputed to have said: "Elegance is for tailors". Some in computing take the opposite view, claiming that "Elegance is not optional". Something to this effect may have been said by E.W. Dijkstra. It is certainly said in this form by Richard O'Keefe in "The Practice of Prolog". In computing, elegance is not optional because elegance is the only way we know to combat complexity and in computing much effort comes to naught and that is almost always due to excessive complexity.

elegant technologies

escape (character)


firing squad synchronization problem


formatting guidelines Formatting preferences raise strong emotions. Many programming groups and programming courses enforce the boss's preferences in this regard. At one extreme there is the "cash slip" school of thought, where long lines are taboo; ideally the code should fit on a cash slip. At the other extreme there is Bjarne Stroustrup, who wrote "code is easier to understand and manipulate if significant chunks fit on a screen" ("The Design and Evolution of C++", page 118.75).







language lawyer F. Brooks (in "The Mythical Man-Month") accepts the need for such a person on a chief programmer team. Brooks may have been the first to use this term. E. Dijkstra and C. Hoare probably regarded the need for a language lawyer to be an indication that the language has migrated from aid to solution to have become part of the problem.



LOGO Language introduced by Seymour Papert. Usually comes with turtle graphics. Papert's ambition was to use personal computers running LOGO as a tool to help young children to become mathematicians (rather than teaching them mathematics).



mixin According to Wikipedia at one time, a mixin is a class that contains methods for use by other classes without having to be the parent class of those other classes. How those other classes gain access to the mixin's methods depends on the language. Mixins are sometimes described as being "included" rather than "inherited".
According to Bjarne Stroustrup ("The Design and Evolution of C++", page 261, last sentence) "The origin of the term mixin is reliably reported to be the addition of nuts, raisins, gummy bears, cookies, etc. to ice cream in an ice cream shop somewhere near MIT."







pair programming

Perlism One of many aphorisms attributed to Alan J. Perlis. Several versions of a list of these circulated samizdat fashion for many years even before his death. Sample Perlisms:

The above Perlisms are attributed to Perlis himself. As is to be hoped, other people may occasionally discover a new one.

philosophical dictionary Voltaire wrote the first. The present one is inspired by "Aristotle to Zoos: a Philosophical Dictionary of Biology" by P.B. and J.S. Medawar. In between, a notable representative of the genre is "The Devil's Dictionary" by Ambrose Beirce.






race condition

recursion Among the general public there exists a dread of circular definitions. Recursion is interesting as the kind of circular definition that one can get away with.

Recursion is an elegant method of getting a computer to do a lot of work with little effort in programming. Iteration is sometimes an alternative and then it is less elegant and usually more efficient. At one time recursion was daring and advanced (or abstract nonsense, depending on one's temperament). In its early years at least, Fortran did not allow recursion. When Algol 60 was being defined, it seems that the committee was divided about whether recursion was to be allowed, as nobody knew how to implement it. Depending on one's temperament, this was, or was not, sufficient reason not to include it in the language. The more adventurous members decided the issue by subterfuge: that recursion is allowed is stated by the Report, but indirectly and so inconspicuously that some committee members did not notice. The recursionists were vindicated by Dijkstra's inventing an implementation scheme when he wrote the first compiler for Algol 60 soon after the definition was completed.

A preference for recursion or iteration is often deeply ingrained in the personality of a computer scientist; it is a temperament, an outlook, a political bias. Recursionists and iterationists tend to be divided on questions having nothing to do with computing.

Since the advent of the programming language C, the basis for the opposition between recursion and iteration has disappeared. Recursion is at home in C, yet that language is as practical as the most die-hard iterationist could wish.

re-entrant code


referential transparency


second system



separation of concerns

shopping-list language Frederick Brooks maintained that Conceptual Integrity is an important consideration in the design of programming languages and of systems generally. This is what E.W. Dijkstra had in mind when he said in his Turing Award lecture: "... PL/I, a programming language for which the defining documentation is of a frightening size and complexity. Using PL/I must be like flying a plane with 7000 buttons, switches and handles to manipulate in the cockpit."
Probably Bjarne Stroustrup ("The Design and Evolution of C++", page 44.7) had this language in mind when he writes of his efforts to prevent C++ to turn into a "shopping-list language".
See language lawyer.


simulated annealing

sleeping barber

software engineering

spider (one that crawls over the web)


sticky bit


structured programming

symbol system hypothesis

syntactic sugar




trapdoor function

turtle graphics




von Neumann

ZEBRA In the 1950s every country built a computer. In this case the country was the Netherlands and the computer was the ZEBRA (Zeer Eenvoudige Binaire RekenAutomaat), designed by W.L. van der Poel. Its design was sufficiently remarkable for it to be in that Hall of Fame of computer architecture which is "Computer Structures: Readings and Examples" by C. Gordon Bell and Allen Newell. When I entered Delft Institute of Technology as a first-year student in 1961 there was a computer rumoured to live in the attic of Julianalaan 132, where I attended classes. It later turned out to be a ZEBRA, the only computer in the university. It was there only because it had been born there.

zero-knowledge proof

Zuse Appropriate last word for a philosophical dictionary. I don't expect to add anything original here. But it will do no harm, if only as a tribute to that giant of computing, Konrad Zuse. Besides, "Abacus to Zuse" is a nice title, achieving a wider alphabetic span than the Medawars in their "Aristotle to Zoos".