Slashdot Mirror
Books on Programming Theory?
subversionfactor asks: "I am a philosophy student with an intense interest in mathematics and programming. However, while I've always been able to find books about various experimental areas of mathematics, I've never seen (m)any on the subject of programming theory. Most bookstores' "Tech" sections only include how-to books and books about why dot-coms failed. Does anyone in the Slashdot community have any recommendations for books dealing with any aspect of programming theory?"
Knuth's The Art of Computer Programming. Duh.
Structure and Interpretation of Computer Programming, Abelson & Sussman
Art of Computer Programming, v1-4, Knuth (ok, so this is three titles)
Although "theory of programming" is rather weakly defined:
"The Art of Computer Programming" by Knuth
"Programming Pearls" by Bentley
"Godel, Escher, Bach: An Eternal Golden Braid" by Hofstadter
"The Tao of Programming"
Jargon File
While not strictly 'computer theory', the following books have definitely helped me to merge computer programming with philosophy...
...], Rousseau [Reveries of a Solitary Walker, ...], Seneca [Letters From a Stoic, ...]... it's the texts that dwell into abstraction, truth, human nature, etc...
"The Elegant Universe" - Greene
"Hyperspace" - Kaku
"The Bit and the Pendulum" - Siegfried
"The Structure of Scientific Revolutions" - Kuhn
"The Advent of the Aglorithm" - Berlinksi
"Orality & Literacy" - Ong
"Genome" - Ridley
"Philosophy of Mind" - Kim
Scientific American - Every issue
"Artificial Intelligence [A Modern Approach]" - Russel & Norvig
"Computer Organization & Design [The Hardware/Software Interface]" - Hennessey
And then of course Plato [The Republic, Timaeus & Critias, Phaedrus, etc..], Descarte [Meditations,
While non of these books will make you a better programmer persay, they all will make you understand how things relate, how to approach topics, and what people will get out of things...
I'm going to (a) give you a fish and (b) teach you how to catch more.
(a) Introduction to the Theory of Computation (Sipser, Michael; 1997, PWS Publishing Company; ISBN 0-534-94728-X; QA267.S56 1996b 511.3 --dc20; amazon page here) is a fantastic volume. We used it in a comp sci course I took, and is probably the only book from my dint in c.s. that I won't sell. This, however, brings us to the bit about fishing:
(b) Find out what courses at your university offer comp. sci theory, and then either (i) take the course (possibly pass/fail), or (ii) borrow their reading list. Contrary to your experiences in phil, virtually all (comp?) sci lectures are simple verbalisations of some gigantic glossy textbook. Those guys in the faculty of Science have far less interest in primary sources than we do; class time is not spent carefully teasing apart inscrutable two thousand year old sentences when a big glossy manual with colour diagrams are available.
- undoware.ca
"Introduction to Algorithms" by Cormen, Leisersen, Rivest, and Stein provides a much more readable, but, as always, not as in-depth alternative to Knuth.
* And remember, it's spelled N-e-t-s-c-a-p-e, but it's pronounced "Mozilla."
... Just a few more things to throw in. If you're interested in Philsophy of Language and Phil. of Mathematics, you're also likely to be interested in formal semantics and other programming language areas, which are not neccessarily linked to "Theory of Computation". These fields delve much more into meaning of programming languages, rather than merely the computational or algorithmic side.
h tml
For semantics, I don't have any good sources to refer you to, as I've only got lecture notes explaining the basics, but you want to look for discussion of "denotational semantics" These are discussed most in the functional language community. The Scheme spec (r5rs) has a denotational semantics for the language. "Monads" are also an area of some interest... but monads and category theory may be leaning more towards the mathematical side.
Another related article:
Rayside, Derick, Gerard T. Campbell
"An Aristotelian Understanding of Object-Oriented Programming"
OOPSLA '00 10/00 Minneapolis, MN USA
[conference procedings]
http://citeseer.nj.nec.com/rayside00aristotelian.
Here are two cites ripped from a course web page somewhere:
J.C.Reynolds, Theories of Programming Languages, Cambridge University Press 1998, ISBN 0-521-59414-6
D.A.Schmidt, Denotational Semantics: A Methodology for Language Development, WCB Publishers, Dubuque, Iowa 1988, ISBN 0-697-06849-8
A few other things that may or may not be of interest in object oriented areas:
Black, Andrew, Jens Palsberg. Foundations of Object-Oriented Languages ACM SIGPLAN Notices. Volume 29, No. 3, March 1994.
Cook, William R., Walter L. Hill, and Peter S. Canning. Inheritance Is Not Subtyping. in Theoretical Aspects of Object-Oriented Design. ed. Carl A. Gunter and John C. Mitchel. MIT Press, Cambridge, Mass.: 1994.
Danforth, Scott, Chris Tomlinson. Type Theories and Object-Oriented Programming. ACM Comput-ing Surveys, Vol. 20, No. 1, March 1988, p. 29
You can learn a lot about CS by looking at pre-1930 math and philosophy.
You'll see a lot of the genesis of proto-computer-science in Frege and Wittgenstein. Of course, it comes out full bore in Church and Turing. Any graduate-level logic text should cover combinatory logic (basically, with the lambda-calculus, the basis of functional programming). One such text (that I can recommend) is _Computability and Logic_, by Boolos.
Of course, SICP (as recommended elsewhere) is excellent, and the Sipser book (likewise) is a readable introduction to theory of computation.
What are you interested in? If you're interested in models for computation, check out the logic books. If you're interested in types (a la Russell), contrast logical types with PL types by reading Luca Cardelli's "Type Systems" (available online free from citeseer, use google). If you're interested in algorithms, Sedgewick or the massive MIT Press algorithms book is good.
You can't be hurt by reading the fundamentals, either: Church, Turing, Rosser, anything by Burstall or Hoare, and (if you're in for some fun), PL semantics (the seminal work in this area is Strachey/Scott). There is a good book available online called "Semantics with Applications" or something similar; I believe that the authors are named Nielsen.
Be careful, though. I was an undergrad philosophy major, and now I'm a grad student in programming languages.
I am a philosophy student with an intense interest in mathematics and programming...Does anyone...have any recommendations for books dealing with any aspect of programming theory?
It sounds like you are looking for Edsger Dijkstra's A Discipline of Programming, which is great fun if you can juggle math, logic, philosophy, and programming (in a non-deterministic language he made up for the book) without getting fixated on any one to the exclusion of the others. He starts with an interesting angle on why we have computers at all, and builds up from there.
-- MarkusQ
You're not a CS major, I take it.
Compare the work done by a bubble-sort to that of a quick-sort. This is independant of OS, compiler, library, and language. Good algorithms are above such details. When you're dealing with basic tasks like sorting, hashing, indexing, graph theory, list manipulation, etc., there are many fundamental theorms that transcend the particulars of the compiler or operating system. And many complex problems can be broken down into these sort of basic primitives.
I'm not implying that programming is all about these theoretical details, because it's not. But understanding the theory is an essential tool for being able to optimize a loop, write a library, or fix code in any case where time and space (i.e. code length) is of any concern.