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.
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.
bottom-up (vs top-down)
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, ...
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.
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).
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."
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:
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.
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 clearly 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 seemingly 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.
separation of concerns
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.
spider (one that crawls over the web)
symbol system hypothesis
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.
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".