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.
We had lots of great classes in college on programming theory. You really want to look at a book on compiler theory or a book on language theory -- a great one would cover the differences between the major paradigms, and give examples of each.
6 782669/qid=1034821624/sr=8-2/ref=sr_8_2/103-561245 0-3349406?v=glance&n=507846
Our programming languages class had us learn a crapload (scientific term) of languages in one semester, and while I don't remember them all, or even how to code in them, I learned a lot about the underlying theory behind coding and the different paradigms.
I wish I could find the book we used in the class, but amazon has the following which looks interesting: http://www.amazon.com/exec/obidos/tg/detail/-/071
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
"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."
Brian Cantwell Smith
On the Origin of Objects
MIT Press
ISBN: 0-262-19363-9 (HB) 0-262-69209-0 (PB)
An exploration of object oriented programming turned philosophic inquiry. I've only read the first half; as a double major in Philosophy and CS I had to stop reading it so that my senior CS project did not devlove into a philosophy paper.
In my opinion, it strikes the perfect balance for a book of its kind between readability and technical detail. And, based on who wrote it, you can be sure that the tecnical detail is correct. Depending on what you mean by "programming theory", I'm not sure if this is exactly what you are looking for. But based on your stated background, I'm sure you'll love it.
Move on. There's nothing to see here.
... 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
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
by Bertrand Myer
Eiffel is used for the examples, but it is a comprehensive work on OO Design applicable to any OO language.
Definitely worth reading.
The Practice of Programming
by Brian W. Kernighan and Rob Pike
David Gries, The Science of Programming, Springer.
"This is the very first book to discuss the theory and principles of computer programming on the basis of the idea that a proof of correctness and a program should be developed hand in hand. It is built around the method first proposed by Dijkstra in his monograph The Discipline of Programming (1976), involving a "calculus for the derivation of programs." Directing his materials to the computer programmer with at least one year of experience, Gries presents explicit principles behind program development, and then leads the reader through example programs using those principles. Propositions and predicate calculus are presented as a took for the programmer, rather than simply an object of study. The reader should come away with a fresh outlook on programming theory and practice, and the assurance to develop correct programs effectively."
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.
Algorithms+Data Structures=Programs is classic CS material.
this site was mentioned here about a year ago. theres's a good list of books there. others might like to contribute the titles they've mentioned.