Theoretical Introduction to Programming

by Bruce Mills

Including easily digested information about fundamental techniques and concepts in software construction, this book is distinct in unifying pure theory with pragmatic details. Driven by generic problems and concepts, with brief and complete illustrations from languages including C, Prolog, Java, Scheme, Haskell and HTML. This book is intended to be both a how-to handbook and easy reference guide. Discussions of principle, worked examples and exercises are presented. All concepts outside introductory programming are explained with clear demarcation and dependencies so the experienced programmer can quickly locate material. Readable in a linear manner, with short mono-thematic to encourage dipping and reference. Also included are sections on open problems in software theory and practice. While little other than a novice programmer's knowledge is explicitly assumed, a certain conceptual maturity, either through commercial programming or academic training is required – each language is introduced and explained briefly as needed.

Genres: Programming

369 pages, Paperback

First published September 14, 2005

About the author

Bruce Mills has published scholarly books and articles on 19th-century American writings and co-edited a collection of essays by siblings of those on the autism spectrum. His creative nonfiction has appeared in The Georgia Review and New England Review. Etruscan will publish his memoir, An Archaeology of Yearning, in 2013. Mills teaches at Kalamazoo College.

Reviews

[John C · Rating 5 out of 5]

(First, despite what it says on the sidebar, this book's author is likely not the same Bruce Mills who's part of the English faculty at Kalamazoo.)

There's a nice quote from this book that jumps out at me regularly, and which dovetails with Joel Spolsky's view that a good programmer be able to "view a problem at several levels of abstraction simultaneously:"

But to say that int is integer arithmetic with bounds and overflow conditions is to say that it is not integer arithmetic.

Abstractions leak, in other words.

The book, besides containing philosophical wisdom like the bit above, covers topics like Turing machines, state machines (and everything in between), Von Neumann architecture, the lambda calculus, pre- and post-conditions, the Y-combinator, Gödel's theorem, P-vs-NP, the various language paradigms, sorting, Conway's game of life, and more.

It's not a tutorial on how to program specific things in a specific language, and that is to its credit. Instead, the book is a survey of many of the other things one learns (or hopefully learns) during the course of an undergraduate CS degree. The focus is on theory of computation and programming language theory (as opposed to say, databases, AI, or operating systems). Each topic gets an overview of usually a few pages.

I greatly recommend it, especially to those who've already learned to program, but don't have formal schooling. Or to those who are currently learning, or to those who could benefit from a collection of short refreshers.

The writing is clear and I've yet to see another book that covers so much of the foundations of the craft so concisely.