Sunday, August 15, 2021

What are the most important 46 papers in Computer Science? Harry Lewis has a book about them!

 (Disclosure:  Harry Lewis was my PhD advisor. For a blog post on  disclosures and bias see my post on that topic here.)

Harry Lewis has a book out: Ideas that Created the Future: Classic Papers in Computer Science

He picked out the 46 (why 46? Why not 46?) classic papers in computer science and, for each one, has a short article saying why its important, and then has the paper itself, though perhaps shortened (leave out the boring parts) or in some cases he has an excerpt of a book (e.g., The Mythical Man Month which is why I blogged about that book recently here).

Harry Lewis has blogged about his book here where he points to my review which is in SIGACT News. 

OR you an use my link to my review here

The list of 46 papers had some constraints, so if you wonder why isn't X there it might have hit one of those constraints.

1) No paper past 1980 (he had to stop somewhere).

2) He preferred short readable papers to long or unreadable ones (don't we all!). Before thinking `Gee why isn't paper X in the book' go read paper X. 

3) Some papers cost to much to get permission to reprint. My review points to one such paper that I found 5 links to on the web. 

4) We don't need X papers on topic Y.

Of more interest is some papers that you had not heard of but we can now see are important.

For more thought, read my review!

For even more information, buy the book!


  1. Why 46? Because 50 is boring and used too much, 42 is already taken and used too much, so he took the average.

    So what are the four that got left out because 50 was so boring? My proposals:
    (1) One of the Steele and Sussman lambda papers
    (2) What is a number that a man may know it and a man that he may know a number*.
    (3) Artificial Intelligence Meets Natural Stupidity. (This is badly dated criticism of 1970s MIT AI Lab work, but the points behind the criticism remain valid and important.)
    (4) Hackmem (MIT AI Lab report #239)

    (Yes, you can tell I had a part-time gig next door to the MIT AI Lab around 1975...)

    *: The sexism in the title is painfully dated, but it's still a kewl paper. An inverse problem is the recent translation of a Japanese novel, which in English became "Convenience Store Woman" but in Japanese was "Convenience Store Human", which I would have translated as "Homo Conveniensus". (Although written by a woman, the phenomenon (ASD) appears in males as well.)

  2. Interesting papers and Harry R. Lewis is keeping busy these days!
    I'll have to order that one. It's usually nice to have these papers printed on good quality paper, and binded in one piece.

    I must admit what did annoy me, and yes it poked my eyes -- sometimes, Lewis would print the full names, like Alan Mathison Turing, but for Shannon, he didn't ... it's Claude Elwood Shannon, neither for other prominent figures like Maurice Wilkes. So, at least from this angle, the book is missing some bits of information -- consistency ... But since it's Harry Lewis, I'll let it slide.

    Paper 35 did surprise me though, substantially.
    What intrigued me most though is the influence that Ivan Sutherland's had on Harry Lewis ... and the many people that
    he himself influenced -- some of them I regard v highly :)

    @DJL, perhaps you knew an older friend of mine, the creator of the HHKB who happened to have an office at the lab around that time.

  3. A quick reply to both comments.

    46 was the result of a 500+/- page limit. My editor was indulgent, but at some point she said “no more!”

    I have my own list of papers I wish I had included. It doesn’t overlap with yours, but yours relates to another project I had in mind: What are your favorite CS polemics? Shouldn’t everyone read the GNU Manifesto, for example? That would be a different kind of collection from this one, but would be a lot of fun.

    Another interesting question is which papers should have been left out, and why. I have my own answer (not #35!), but am curious what others think.

    As for names, I started by using whatever name the author used. But I didn’t stick with that, because I wanted the reader to know who these people are, and “A. M. Turing” just did not seem a fair way of naming God, for example. But neither did it seem right to identify Knuth as Donald Ervin Knuth, a name nobody knows him by. So it was hard to stay consistent, and it seemed more important to be educational. Hoare is Tony if he is not C.A.R.; nobody would recognize the full name.

    A related detail on names. Some authors used different versions of their names on different papers. But if you use those variants, then BibTeX treats them as different people, blocking together chronologically all papers by one version of the name, then following it with a chronological listing of the next version, etc. Some of my BibTeX entries were generated by the Harvard library catalog system, which seems to draw on Library of Congress data, yielding the fullest name. That’s how Knuth wound up with the full name in the bibliography.

    1. What papers to leave out? First off, they are all great papers. Even so, with that i mind here are my thoughts on what could have been left out.

      The paper by Menabara and Lovelace about the work of Babbage and Lovelace. B & L were impressive, but its not clear they wer influential.

      Mathematical Problems by Hilbert- the connection to computation is tenous- it goes through Godel and Turing, so it is perhaps further removed from computing.

      Dij has two papers tabout Prog Verif:
      Solution of a problem in conc. prog. cont
      The Structure of THE...

      One would have sufficed.

      And- this is prob just me, but I dont know if you need
      all both of the following:

      A protocol for Packet Network...
      Ethernet: Dist packet switching

      How to share a secret- a paper I think is awesome- but I wonder
      if what it shows is actually used. I've heard rumors but
      when trying to track it down I couldn't find anyone REALLY
      using it.

  4. Well! I disagree with pretty much every suggestion you make here. The last one is the most defensible, but the paper did stimulate a lot of work. But rather than defending those other papers (except to say that the two Dijkstra papers are NOT program verification papers -- the important thing is the clear statement of the problem, and the algorithms and P/V apparatus, not the proofs) -- I'll give you my choice: Engelbart. His work was super important, but the important manifestation of it was his 1968 demo, not his rather tedious writing about it. I'm sorry I didn't just include a link to the video of the demo and use the pages for something else.

  5. Wonderful commentary.

    I think, for a practitioner, the THE paper was stunning, not just for P/V but for the desperate desire to have a dependable way to have confidence in his work. A Discipline reflects that also, with an adaptable methodology, and one does not have to choose theory vs. practice sides in order to appreciate the purpose without polemic.