A Computer Science Canon

“The classics are those books about which you usually hear people saying: ‘I’m rereading...’, never ‘I’m reading...’” — Italo Calvino, Why read the classics? Italian publishing 1991, translated 1999.

       These writings comprise my list of the classics in computer science. In recognition of the inevitable for all efforts of this nature, the list below is biased and subjective. While I have included several historical works, many of the contemporary works have been selected on the basis of personal interest. For a more comprehensive look at the historical works, I strongly recommend "Creating a computer science canon: A course of classic readings in computer science" by Michael Eisenberg at the University of Colorado. My purpose of creating such a list is twofold; to enumerate those works that have profoundly shaped the computer science community, and to list those works that have influenced my own research and education. The list below strikes a balance of these two interests. Suggestions, criticisms, or comments are always appreciated.

    ? - 1969

  • "An unsolvable problem of elementary number theory." Alonzo Church, American Journal of Mathematics, volume 58, 1936.
  • "On computable numbers, with an application to the Entscheidungsproblem." Alan Turing, Proceedings of the London Mathematical Society, series 2, volume 42, 1937.
  • Theory of games and economic behavior. John Von Neumann and Oskar Morgenstern, Princeton University Press, 1944. 60th anniversary edition published in 2004.
  • "A mathematical theory of communication." Claude Shannon, Bell System Technical Journal, volume 27, July and October, 1948.
  • "Computing machinery and intelligence." Alan Turing, Mind, volume 49, 1950.
  • "A proof of the queuing formula L =λW." John Little, Operations Research, volume 9, May-June 1961.
  • "Go to statement considered harmful." Edsger Dijkstra, Communications of the ACM, volume 11, number 3, March 1968.
  • "Semantics of context-free languages." Donald E. Knuth, Theory of Computing Systems, volume 2, number 2, June 1968.
  • The sciences of the artificial. Herbert Simon, MIT Press, 1969. Third edition published in 1996.
  • 1970 - 1979

  • "The UNIX timesharing system." Dennis Ritchie and Ken Thompson, Communications of the ACM, volume 17, number 7, July 1974.
  • "Computer programming as an art." Don Knuth, Communications of the ACM, volume 17, number 12, December 1974. ACM Turing award lecture 1974.
  • "Debunking the 'Expensive Procedure Call' myth, or, procedure call implementations Considered Harmful, or, Lambda: The Ultimate GOTO." Guy Lewis Steele, Jr. MIT AI Lab Memo, AIM-443, October 1977.
  • "Time, clocks, and the ordering of events in a distributed system." Leslie Lamport, Communications of the ACM, volume 21, number 7, July 1978.
  • "Can programming be liberated from the Von Neumann style? A functional style and its algebra of programs." John Backus, Communications of the ACM, volume 21, number 8, August 1978. ACM Turing award lecture 1977.
  • "Communicating sequential processes." Tony Hoare (C.A.R. Hoare), Communications of the ACM, volume 21, number 8, August 1978.
  • "Social processes and proofs of theorems and programs." Richard De Millo, Richard Lipton, and Alan Perlis, Communications of the ACM, volume 22, number 5, May 1979.
  • Computers and intractability: A guide to the theory of NP-completeness. Michael Garey and David Johnson, W. H. Freeman Publishers, 1979.
  • Gödel, Escher, Bach: An eternal golden braid. Douglas Hofstadter, Basic Books Publishers, 1979. 20th anniversary edition published 1999.

    1980 - 1989

  • "Specifying software requirements for complex systems: New techniques and their application." Kathryn Heninger, IEEE Transactions on Software Engineering, volume SE-6, number 1, January 1980.
  • "An improved illumination model for shaded display." Turner Whitted, Communications of the ACM, volume 23, number 6, June 1980.
  • "The Byzantine generals problem." Leslie Lamport, Robert Shostak, and Marshall Pease, ACM Transactions on Programming Languages and Systems, volume 4, issue 3, July 1982.
  • "Epigrams on programming." Alan J. Perlis, ACM SIGPLAN Notices, volume 17, issue 9, September 1982.
  • "Maintaining knowledge about temporal intervals." James F. Allen, Communications of the ACM, volume 26, issue 11, November 1983.
  • "Reflections on trusting trust." Ken Thompson, Communications of the ACM, volume 27, number 8, August 1984. ACM Turing award lecture 1983.
  • "An experimental evaluation of the assumption of independence in multiversion programming." John C. Knight and Nancy G. Leveson, IEEE Transactions on Software Engineering, volume SE-12, number 1, January 1986.
  • "A case for redundant arrays of inexpensive disks (RAID)." David A Patterson, Garth Gibson, and Randy H. Katz, Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, June 1988.
  • "Program verification: the very idea." James H. Fetzer, Communications of the ACM, volume 31, issue 9, September 1988.
  • "Fast, cheap and out of control: a robot invasion of the solar system." Rodney Brooks and Anita Flynn, Journal of the British Interplanetary Society, volume 42, 1989.
  • 1990 - 1999

  • "Evaluation of safety-critical software." David Parnas, A. John van Schouwen, and Shu Po Kwan, Communications of the ACM, volume 33, number 6, June 1990.
  • "A bridging model for parallel computation." Leslie G. Valiant, Communications of the ACM, volume 33, number 8, August 1990.
  • "A data locality optimizing algorithm." Michael E. Wolf and Monica S. Lam, Proceedings of the ACM Conference on Programming Language Design and Implementation, June 1991.
  • "An approach to the synthesis of life." Thomas Ray, appearing in Artificial Life II, Santa Fe Institute studies in the sciences of complexity, volume 11, 1991.
  • "Symbolic boolean manipulation with ordered binary-decision diagrams." Randal E. Bryant, ACM Computing Surveys, volume 24, issue 3, September 1992.
  • "A behavioral notion of subtyping." Barbara H. Liskov and Jeannette M. Wing, ACM Transactions on Programming Languages and Systems, volume 16, issue 6, November 1994.
  • "Molecular computation of solutions to combinatorial problems." Leonard M. Adleman, Science, volume 266, number 5187, November 1994.
  • "Hitting the memory wall: implications of the obvious." William A. Wulf and Sally A. McKee, ACM SIGARCH Computer Architecture News, volume 23, issue 1, March 1995.
  • "Cilk: An efficient multithreaded runtime system." Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. ACM SIGPLAN Notices, volume 30, issue 8, August 1995.
  • "The cathedral and the bazaar." Eric S. Raymond, first presented by the author at the Linux Kongress, May 1997. Published as a part of a book with the same title in 1999.
  • 2000 - present

  • "The evolutionary origin of complex features." Richard E. Lenski, Charles Ofria, Robert T. Pennock, and Christoph Adami. Nature, volume 423, May 8 2003.
  • "The Google file system." Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, 19th ACM Symposium on Operating Systems Principles, October 2003.
  • "Is computer science science?" by Peter J. Denning. From the 'Profession of IT' column of the Communications of the ACM, volume 48, number 4, April 2005.
  • "The rise and fall of High Performance Fortran: an historical object lesson." Ken Kennedy, Charles Koelbel, and Hans Zima. Proceedings of the third ACM SIGPLAN conference on History of programming languages. 2007.
  • On Teaching:

  • "Software engineering programs are not computer science programs." David Parnas, IEEE Software, volume 16, issue 6, 1999.
  • "The undergraduate language course: what to do?" Joe Bergin, SIGPLAN Notices, volume 36, number 6, 2001.
  • "A 2007 model curriculum for a liberal arts degree in computer science." Liberal Arts Computer Science Consortium (LACS). ACM Journal on Educational Resources in Computing, volume 17, number 2, 2007.
  • "Computer science and the liberal arts: A philosophical examination." Henry M. Walker and Charles Kelemen, ACM Transactions on Computing Education, volume 10, number 1, 2010.

See also Creating a computer science canon: A course of classic readings in computer science, Michael Eisenberg. University of Colorado.