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?"

Comments

Theory

[sameb]

While not strictly 'computer theory', the following books have definitely helped me to merge computer programming with philosophy...

"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, ...], Rousseau [Reveries of a Solitary Walker, ...], Seneca [Letters From a Stoic, ...]... it's the texts that dwell into abstraction, truth, human nature, etc...

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...

From another Phil major

[Snafoo]

Geez, I didn't realise that there was more than one of us. :)

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.

The Pragmatic Programmer: From Journeyman to Maste

[helixblue]

While not strictly "theory", but more good programming attitude & habits - I highly recommend picking up a copy of "The Pragmatic Programmer: From Journeyman to Master". I cannot recommend this book nearly enough. While it may not teach you a specific language, it teaches you general best practices in getting the job done in an effective manner. I'll rip off one of the quotes from the Amazon.com page:


This book is an excellent distillation of practical experience and advice covering all phases of software development. While it's written mainly for the software developer, project managers will get valuable insight from the book on effective software development practice. The strength of this book is that it draws heavily from the authors' experience. Rather that promote a methodology, it promotes attitudes, values, tools and proven practices that will help anyone become a better software developer and make the job of software development more creative and stimulating. It's especially good for new software developers as it contains many lessons that experienced developers only learn the hard way. The book is well organized in easily digestible segments, with a very good cross reference system that makes it handy for repeated use. The appendix presents many valuable resources that professional programmers will want to explore.

I actually got introduced to it because the same guys later went on to write a pretty decent Book on Ruby. However useful that book was to learning Ruby, The Pragmatic Programmer was useful to fostering a positive set of habits and attitude toward programming in General. At least do yourself a favor and read the rest of the comments on Amazon.com before dismissing this underrated classic!

basically, you want early analytic philosophy

[woggo]

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.