Rating: 8.8/10
Anthology of famous and influential computer science papers from the beginning of the field until 1980, in chronological order. Each one is abridged to the most important sections, with a short introduction about its context and influence, but is otherwise relatively sparse in annotations or explanations. Reading the papers in chronological order, we can see how the idea of computing developed from early versions into bulky mainframes that can process computations, and gradually into interactive devices that are more and more ubiquitous.
The linguistic difficulty is front-loaded in the earliest chapters, where the authors were lacking in pre-modern conventions, with philosophical ramblings by early authors like Leibniz and George Boole, then in the 20th century the writing stabilizes into something more scientific. The papers fall into several categories like theoretical algorithms or models of computation, engineering works, visions and calls to action, and systems. The modern reader will likely find the textbook relatively easy, as many of them map to things taught in standard computer science courses, but often the original presentation is more cumbersome than the modern, and details are often different, but the overall idea is recognizable.
The most difficult are the non-technical vision papers, eg, imagining computers being interactive and powering the work of professionals requires reverse engineering what computers were at the time and why the idea was not obvious, and decoding what an author meant when the terminology had not yet been invented. Finally, the last section presents several papers from the 70s on cryptography, which is quite a modern breakthrough.
Chapters 1/2: short sections from works by Aristotle and Leibniz, obviously from before any concept of computers, but both have some form of abstract terms and predicates and rules and manipulate them to stand for real things, which is a precursor of many of the theoretical ideas to come.
Chapter 3. Ada Lovelace’s notes on Charles Babbage’s Difference Engine and Analytical Engine. The Difference Engine computes tables of algebraic expressions, and in the notes A-G, Ada switches to the Analytical Engine, which is more general-purpose, has cards for operations and variables, and walks through some sample computations of formulas on the machine (although neither machine was actually built).
Chapter 4. The Laws of Thought by George Boole (~1850), which lays a foundation of Boolean algebra using variables like X being 0 or 1 to represent statements, algebraic properties like commutation and distribution, although the text is quite wordy with Victorian language and reads more like philosophy than mathematics.
Chapter 5. Hilbert’s list of 23 mathematical problems that he posed in 1900, notably on the solvability of Diophantine equations, where he believed that all problems were solvable either by proof or counterexamples, since incompleteness or uncomputability results did not exist yet.
Chapter 6. Turing (1936) proposed a Turing machine with an infinitely long tape and used serialization and diagonalization arguments to show undecidability of the decision problem of whether the machine will eventually emit a given symbol, and argued the equivalence of machine and human computer capabilities.
Chapter 7. Mark I – early designs for a programmable computer built from IBM plugboard parts, mainly to compute tables of functions reliably, and used the Harvard architecture which kept a strict separation between code and data.
Chapter 8. Shannon (1938) showed equivalence between propositional logic and electrical circuits, where circuits wired in series or parallel correspond to the AND or OR operations, and a circuit can be minimized by converting to an algebraic expression, applying a rule, and converting it back.
Chapter 9. McCulloch and Pitts (1943) proposed feedforward neural networks with fixed thresholds and a clock mechanism to model the brain, and proved the equivalence of propositional logic with these networks, as well as further capabilities like memory and Turing equivalence of networks with recurrence and loops (although the notation was confusing and error prone).
Chapter 10. EDVAC design (von Neumann, 1945), which lays out an architecture for a computer with an arithmetic unit, control unit, and memory, and is most famous for encoding its own instructions in binary and loading them from memory in the same way as data. He discusses trade-offs of mechanical relays versus vacuum tubes, which are several orders of magnitude faster, so you don’t need more complex parallel schemas to multiply numbers faster because they were already very fast.
Chapter 11. Vision and call to action by Vannevar Bush in 1945, imagining a future where computers can be mass produced and available for quick and easy business operations, have information searchable and retrievable for scientists, with voice and brain technology for easy communication with operators, and using it to organize personal and field-wide knowledge.
Chapter 12. Shannon (1948) defines an abstract information channel capable of transmitting discrete symbols, entropy as the uncertainty of information and properties of entropy, and demonstrates modeling English text as a Markov process and measuring the entropy of various n-gram models.
Chapter 13. Hamming (1950) proposed a clever parity system for correcting any single bit error using some check bits, and the general theory of error detection and correction within dimensional hypercubes, and proves the optimality of the proposed construction.
Chapter 14. Turing (1950), which proposes to address the question of “can a machine think?” with a more operational imitation game where a computer pretends to be a human and an interrogator tries to guess which is which, and the setup has messages relayed via text so that the physical form of a computer is not a factor. He lists various arguments for why computers cannot “think”, from theological to Gödel’s incompleteness and discrete versus continuous inability to originate new ideas, etc., and refutes each one of them. Finally, he describes a learning machine that is taught through examples rather than hand programmed, which anticipates machine learning.
Chapter 15. Wilkes (1951) proposed decomposing operations in a processor into microcodes that are simpler and can be composed, rather than engineering ad-hoc wiring for each operation in a processor.
Chapter 16. Grace Hopper (1952), who proposed building a library of useful subroutines that can be invoked with general conventions on the meaning of input arguments, common constants, where to store the output, etc., and a compilation procedure to produce a single program out of subroutines.
Chapter 17. Kruskal (1956), an algorithm for the minimal spanning tree, and while there is no runtime analysis, a correctness proof is given.
Chapter 18. Rosenblatt (1958), who presents the perceptron as an object that can learn patterns from stimuli, in statistical patterns rather than propositional logic as in McCulloch and Pitts, anticipating the symbolic versus statistical split for AI.
Chapter 19. Wiener (1960), who warns of machines that can execute faster than operators can understand them, going out of control and giving you what you said but not what you intended, with an example of a checkers machine that can beat its creators after a few hours.
Chapter 20. Licklider (1960), “Man-Computer Symbiosis,” where instead of submitting fixed jobs, the computer is a tool that collaborates with humans in real time, where the human sets the evaluation criteria and hypotheses and the computer executes the tedious parts, and the shared language must be easy to upgrade collaboratively, like on an electric whiteboard or with speech recognition.
Chapter 21. McCarthy (1960), who defines S-expressions as a vehicle for functional programming, pattern matching, and recursion to express algorithms in terms of functions, “apply” as a first-class concept that treats code as data to be interpreted, and higher-order functions, and the Lisp programming language that implements S-expressions and has garbage collection.
Chapter 22. Engelbart (1962), with a vision of the computer as augmenting human intelligence with workflows where the information that the human needs is available and the expert uses the computer in real time as a jointly defined workflow, where the human operates a computer while performing a task in real time.
Chapter 23. An experimental timesharing system from 1962 to rapidly divide computer time between multiple users so that each one can debug interactively, defining the technical requirements like memory isolation, interrupts, and cost tracking. They implement a scheduling algorithm that ensures graceful degradation, and find that once users are used to interactive computers, delays start to feel slow.
Chapter 24. Sketchpad (1963) is the first computer-aided drawing program. An operator could draw using a light pen to input abstract shape definitions like line, circle, and constraint lines to be equal length, etc. It is easy to define sub-figures that can be copied and reused.
Chapter 25. Moore (1965) observation of miniaturization of components: the number of components on a chip is doubling every year. Also comments on issues of yield during manufacturing and heat as they scale, and components that cannot be miniaturized like capacitors.
Chapter 26. Dijkstra (1965) algorithm for mutex so that concurrent programs are protected in a critical section, using a flag and loop mechanism to prevent deadlocks.
Chapter 27. ELIZA (1966) is the first chatbot, which works by mechanical translation of user input sentences with some precedence and memory, etc. It is designed to simulate a psychiatrist so that the program can repeat back what the user said, the user supplies all the information, and the program doesn’t need to know much about the world.
Chapter 28. Dijkstra (1968) report on engineering a multiprocessing system that decomposes the problem into layers and argues it is best to define the invariants and prove correctness, thoroughly testing each level before moving to the next, since bugs in a lower level are hard to tell from machine malfunction, and correctness of threading priorities must not depend on the relative speed of processors, eg, so that any process may be interrupted without breaking correctness. The appendix defines various synchronization primitives like semaphores and mutual exclusion.
Chapter 29. Dijkstra (1968) opinion piece that the go-to statement is considered harmful, arguing that go-to makes programs hard to reason about, specifically that it makes it impossible to characterize program progress with an index.
Chapter 30. Strassen (1969) algorithm for matrix multiplication faster than cubic time, by generalizing the fact that a 2×2 matrix multiplication can be done in 7 multiplications instead of 8 and recursing, and the paper applies it to matrix inversion as well.
Chapter 31. Hoare (1969) on formal methods to prove program correctness, starting with axioms of computer arithmetic where operations may overflow, and defining semantics of program execution, eg, of the assignment operator by precondition and postcondition, where the postcondition is defined to be satisfied after some statement executes, and the semantics of multiple statements, loops, etc. Recognizes the difficulty of proving program correctness formally, but advises it for programming language specification to be unambiguous to implementers.
Chapter 32. Codd (1970) defines relational databases, where instead of the program needing to manage indexes to data, you define relations where rows are unordered, columns are given names, and they can be converted to normal form and queried with relational operators, turning structures into flat tables.
Chapter 33. Royce’s 1970 paper on what came to be known as the waterfall method, where software can be broken down into stages of requirement gathering, documentation, design, coding, testing, and operations, and advocated for a large amount of documentation before coding. It came to be a sort of caricature, but the actual paper warned against the dangers of strict waterfall procedure and advocated for the importance of iterations and some feedback as well.
Chapter 34. Cook (1971) showed that any problem that’s verifiable in polynomial time can be oracle reduced to 3-SAT by encoding the turing machine as a Boolean satisfiability problem, so then solving it will lead to any polynomial time algorithm for the original problem (later known as the NP class). He conjectured that graph isomorphism and primality are also in this class, but was unable to prove it.
Chapter 35. TF-IDF paper (1972), which proposed that terms that are more specific, appearing in fewer documents, are more useful for keyword matching, so weighting by inverse document frequency works better than simply counting term overlaps.
Chapter 36. Karp (1972) identifies a large number of problems that reduce to Boolean satisfiability, thereby defining a class of NP-complete problems, where a solution to one means a polynomial solution to all the others.
Chapter 37. Description of the Unix system (1974) that had a number of elegant innovations: everything was a file, meaning I/O devices communicate through the file system rather than a special API, and a file is raw bytes with a basic permission system; the shell allowed pipes, which encouraged small utilities that are composed instead of many options in programs; and the fork-exec system of spawning processes was simple and elegant.
Chapter 38. TCP/IP protocol (1974), proposing a protocol for packet-switching networks, a universally understood addressing scheme and ports that map to processes, TCP that allows reconstruction of packets in order and error recovery through sequence numbers, splitting up packets into smaller ones and reconstructing by bytes but not at the packet level in this version, and proposing TCP as a monolithic system and not the TCP/IP split.
Chapter 39. Abstract data types (1974), as a way of abstracting a problem by defining a type and operations available on that type so that the user is not concerned with the internals, and gives an example of how a Polish notation parser can be implemented clearly.
Chapter 40. The famous Mythical Man-Month essay, arguing that software estimates tend to be optimistic and that breaking down a project into man-months is a fallacy, as adding more people to a late project makes it more delayed after factoring in training time and additional coordination complexity.
Chapter 41. The Ethernet (1976) design, where packets are sent to the ether and heard by all receivers, with a protocol to detect interference and exponentially back off; the header contains an address and the listener is supposed to only look at those addressed to it and acknowledge a response. It is more similar to modern Wi-Fi than Ethernet in its need for collision detection.
Chapter 42. Diffie and Hellman (1976) on public key cryptography, generating a key pair where the public key is useful for encryption and the private key for decryption, and this solves the key exchange problem where two parties need to agree on a secret. (Although the original scheme posits the idea of a trapdoor function needed for public key cryptography, the math only worked for key exchange). The system should be based on the computational infeasibility of finding the key either when the attacker knows the past plain text or chooses a plain text to encrypt and knows the workings of the system. They propose a discrete logarithm as a function that is hard to reverse, and they note that the same system can be used to prove the authenticity of a message.
Chapter 43. Knuth (1976), proposing a consistent definition for Big O, Omega, and Theta notations for upper and lower bounds, where Big O was previously used inconsistently, and argues why this is better than relational notation.
Chapter 44. An essay on the flaws of software verification, which on the surface seems similar to mathematical proof, but proofs are supposed to be simple and appreciated and shared by human mathematicians, understood and extended organically, whereas program verifications are long and cumbersome, give little insight, and don’t increase confidence that it works in practice, even if it agrees with specifications, as neither is independently derived.
Chapter 45. The RSA algorithm (1978), implementing public key cryptography using the difficulty of factoring as the foundation, and shows that the math of why the method works, as well as an algorithm to generate primes efficiently and how to use it to sign messages.
Chapter 46. The book ends with Shamir (1979), a method to share a secret such that any k of n keys are sufficient to recover it, based on polynomial interpolation.
