I’ve got lots of collections of source code. I have compilers, the Digitek compilers from the 1960s were written in a very interesting way. They had their own language and they used identifiers that were 30 characters long but very descriptive, and their compilers ran circles around the competition at the time—this company made the state-of-the-art compilers of 1963 or ’64.
And I’ve got Dijkstra’s source code for the THE operating system. I haven’t read that. I’ve just skimmed it so far but I collected it because I’m sure it would be interesting to read if I had time.
One time I broke my arm—fell off a bike—and I had a month where I couldn’t do anything much, so I read source code that I had heard had some clever ideas in it that hadn’t been documented. I think those were all extremely important experiences for me.
Seibeclass="underline" How do you tackle reading source code? Even reading something in a programming language you already know is a tricky problem.
Knuth: But it’s really worth it for what it builds in your brain. So how do I do it? There was a machine called the Bunker Ramo 300 and somebody told me that the Fortran compiler for this machine was really amazingly fast, but nobody had any idea why it worked. I got a copy of the source-code listing for it. I didn’t have a manual for the machine, so I wasn’t even sure what the machine language was.
But I took it as an interesting challenge. I could figure out BEGIN and then I would start to decode. The operation codes had some two-letter mnemonics and so I could start to figure out “This probably was a load instruction, this probably was a branch.” And I knew it was a Fortran compiler, so at some point it looked at column seven of a card, and that was where it would tell if it was a comment or not.
After three hours I had figured out a little bit about the machine. Then I found these big, branching tables. So it was a puzzle and I kept just making little charts like I’m working at a security agency trying to decode a secret code. But I knew it worked and I knew it was a Fortran compiler—it wasn’t encrypted in the sense that it was intentionally obscure; it was only in code because I hadn’t gotten the manual for the machine.
Eventually I was able to figure out why this compiler was so fast. Unfortunately it wasn’t because the algorithms were brilliant; it was just because they had used unstructured programming and hand optimized the code to the hilt.
It was just basically the way you solve some kind of an unknown puzzle—make tables and charts and get a little more information here and make a hypothesis. In general when I’m reading a technical paper, it’s the same challenge. I’m trying to get into the author’s mind, trying to figure out what the concept is. The more you learn to read other people’s stuff, the more able you are to invent your own in the future, it seems to me.
We ought to publish code. The Lions Book is available. And Bill Atkinson’s programs are now publicly available thanks to Apple, and it won’t be too long before we’ll be able to read that. That’s well-documented code with lots of pioneering graphics algorithms in it.
Seibeclass="underline" Certainly with open source there’s a lot more code out there to read than there use to be.
Knuth: Yeah, that’s right. But the more varieties of different kinds of notations are still useful—don’t only read the people who code like you.
Bibliography
The Art of Computer Programming, Donald Knuth (Addison-Wesley, 1997)
Beautiful Code: Leading Programmers Explain How They Think, Andy Oram, Greg Wilson (eds.) (O’Reilly, 2007)
Byte, Vol. 6, No. 8, “Smalltalk issue,” August 1981
Code Complete, Steve McConnell (Microsoft Press, 1993)
Compiling with Continuations, Andrew W. Appel (Cambridge University Press, 1992)
The Design and Analysis of Computer Algorithms, Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman (Addison-Wesley, 1974)
Design Patterns: Elements of Reusable Object-Oriented Software, Eric Gamma, Richard Helf, Ralph Johnson, and John M. Vlissides (Addison- Wesley Professional, 1994)
A Discipline of Programming, Edsger W. Dijkstra (Prentice Hall, Inc., 1976)
Effective Java, Joshua Bloch (Prentice Hall, 2008)
The Elements of Programming Style, Brian Kernighan and P.J. Plauger (Computing McGraw-Hill, 1978)
Elements of Style, William Strunk and E.B. White (Longman, 1999)
Expert C Programming, Peter van der Linden (Prentice Hall PTR, 1994)
Founders at Work, Jessica Livingston (Apress, 2007)
Hacker’s Delight, Henry S. Warren (Addison-Wesley, 2002)
Higher-Order Perl, Mark Jason Dominus (Morgan Kaufmann, 2005)
Java Concurrency in Practice, Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug Lea (Addison-Wesley, 2006)
Java Puzzlers: Traps, Pitfalls, and Corner Cases, Joshua Bloch and Neil Gafter (Addison-Wesley, 2005)
The Lisp 1.5 Programmer’s Manual, John McCarthy (MIT Press, 1962)
Literate Programming, Donald Knuth (Center for the Study of Language and Information, 1992)
Machine Intelligence 1, N.L. Collins and Donald Michie (eds.) (Oliver and Boyd, 1967)
Machine Intelligence 2, Ella Dale and Donald Michie (eds.) (Oliver and Boyd, 1968)
Machine Intelligence 3, Donald Michie (ed.) (Edinburgh University Press, 1968)
Machine Intelligence 4, Bernard Meltzer and Donald Michie (eds.) (Edinburgh University Press, 1969)
Magic House of Numbers, Irving Adler (HarperCollins, 1974)
META II a Syntax-Oriented Compiler Writing Language, D.V. Schorre in Proceedings of the 1964 19th ACM national conference, (ACM, 1964)
Mindstorms: Children, Computers, and Powerful Ideas, Seymour A. Papert (Basic Books, 1993)
The Mythical Man-Month: Essays on Software Engineering, Frederick P. Brooks (Addison-Wesley Professional, 1995)
Principles of Compiler Design, Alfred Aho and Jeffrey Ullman (Addison- Wesley, 1977)
“Proof of a Program: FIND”, C.A.R. Hoare in Communications of the ACM, Vol. 14, Issue 1 (ACM, 1971)
Programming Pearls, Jon Bentley (ACM Press, 1999)
Purely Functional Data Structures, Chris Okasaki (Cambridge University Press, 2008)
A Retargetable C Compiler: Design and Implementation, David Hanson and Christopher Fraser (Addison-Wesley Professional, 1995)
Smalltalk-80: The Interactive Programming Environment, Adele Goldberg (Addison-Wesley, 1983)
Smalltalk-80: The Language & Its Implementation, David Robson and Adele Goldberg (Addison-Wesley, 1983)
Structure and Interpretation of Computer Programs, Harold Abelson and Gerald Jay Sussman (MIT Press, 1996)
TeX: The Program, Donald Knuth (Addison-Wesley, 1986)
The Programming Language LISP: Its Operation and Applications, Edmund Berkeley and Daniel Bobrow, eds. (MIT Press, 1966)
The Psychology of Computer Programming: Silver Anniversary Edition, Gerald Weinberg (Dorset House, 1998)
The TeXbook, Donald Knuth (Addison-Wesley Professional, 1986)
Writers at Work: The Paris Review Interviews, Malcolm Cowley (Penguin, 1977)
Zen and the Art of Motorcycle Maintenance: An Inquiry into Values, Robert Pirsig (Bantam, 1984)