Papers

Eric Brewer and Daniel Abadi expand our notions of what the real trade-offs are in the CAP theorem. Flexible positioning between C and A Eric Brewer discusses the range of options available under CAP in “CAP Twelve Years Later: How the “Rules” Have Changed”. In particular, he notes that designers don’t have to pick exclusively between AP or CP, but can choose a range of flexible options between the two, including limiting operations during a partition to just certain, inviolable operations that will maintain invariants. ...

A scientist’s idea of literary criticism is different from most people’s. It involves math. Prof. Alan Kaminsky graphs and predicts the size of Harry Potter books in “Harry Potter Book Sizes” . He notes that the books were initially growing exponentially. (I thought they were growing in Fibonacci scale, just by eyeballing the heights of each hardcover.) If his prediction had held, the last book should have been just over 7000 pages. Which would not qualify it as the longest book ever. In fact, it would only be number four. ...

Chuck Jones inspires UI designers in this classic paper from Ungar and Chang. Another paper about the SELF programming language, this time on its interface, “Animation: From Cartoon to the User Interface” by Bay-Wei Chang and David Ungar. Chang and Ungar take lessons from traditional animation to inform the design of their own GUI. It opens with the observation that animators work with 24 frames per second, and the audience is never confused from frame to frame, but even the simplest GUI can trip users up when things change unexpectedly. The solution, of course, is to buy the ACME Web Development Framework. No, wait… The solution is to steal a few simple lessons from hand-drawn animation to make a GUI more intuitive. Everything from bouncing at the end of a move, to motion blur when an object moves more than its size in a single frame, to using non-linear easing. ...

In 1991 Ungar and Smith wrote about the experimental programming language SELF, and in it described duck typing, calling it behaviorism. I found an early example of Duck Typing in “SELF: The Power of Simplicity” by David Ungar and Randall B. Smith. It’s from 1991. Is this the earliest example of duck typing? Behaviorism. In many object languages, objects are passive; an object is what it is. In SELF, an object is what it does. Since variable access is the same as message passing, ordinary passive objects can be regarded merely as methods that always return themselves. For example, consider the number 17. In Smalltalk, the number 17 represents a particular (immutable) state. In SELF, the number 17 is just an object that returns itself and behaves a certain way with respect to arithmetic. The only way to know an object is by its actions. ...

This paper is considered seminal in Object Oriented Design, but Parnas never mentions objects, and his example program is described in procedural programming terms. The lessons in this paper are applicable to all programming methodologies. It’s just about smart design decisions. Good programming design grew a major root in 1972 with “On the Criteria To Be Used in Decomposing Systems into Modules” by David Parnas. How do you build a big program? You have to break it down into smaller programs, obviously, but that leaves the also-obvious question how do you choose those smaller programs? David Parnas looks at a silly little program called The KWIC Index Production System to demonstrate two different answers to this question. ...

You can’t trust Ken Thompson. He’ll prove it. Reflections on Trusting Trust Ken Thompson created the modern world. When he was given the Turning award in 1984 for that small accomplishment he gave a small speech that proves that you can’t trust him. At all. It’s a simple three step proof. If a compiler has a backdoor that infects programs, we’ll only find the hack by reading the source code of the compiler. Compilers are compiled by a programming language, just like any other program. If the compiler has a backdoor that infects a compiler, we cannot find hack by reading the source code, not after it has been bootstrapped. It’s a beautiful little paper that will make you question the whole notion of security. ...