Understanding Computation: a very short review

One of the books on my Summer Reading List for 2013 was Tom Stuart's Understanding Computation

As computer books go, Stuart's book is rather unusual.

Many computer books are tediously practical: Learn XXX in 21 Days; Advanced Programming With The YYY Platform; ZZZ Technology In Depth.

Snore.

Some computer books are insightful and educational, but hard to approach: filled with dense academic prose, written to be used as textbooks in a classroom setting, short on motivation and examples. In my day, for example, we learned from The Design and Analysis of Computer Algorithms, which is as great a computer textbook as was ever written, but is certainly not the sort of book you approach lightly.

Stuart's book fits into neither category. In a relatively short, lively, friendly-yet-rigorous 300 pages, Stuart manages to educate the reader on a surpisingly broad range of core theoretical concepts:

• By page 20, we're discussing the concepts of syntax and semantics and learning about how to use Small-Step Operational Semantics to describe the behavior of a programming language implementation for an abstract machine.
• By page 50, we've moved on to Denotational Semantics, and we're learning to implement a language parser
• By page 60, we're studying Deterministic Finite Automata, and by page 70 we're comparing them to Nondeterministic Finite Automata
• By page 100, we've learned to build machines that recognize Regular Expressions, and we're introducing the concept of the Pushdown Stack into our abstract machine.

Understanding Computation continues at the same pace throughout the book, covering

• Nondeterministic Pushdown Automata
• Parsing, Lexical Analysis, and Syntactic Analysis
• Turing Machines
• Lambda Calculus
• Partial Recursive Functions
• Tag Systems
• Self-referential statements
• Programs that can refer to themselves
• Decidability
• The Halting Problem
• Incompleteness and Uncomputability

Whew! All this, in a friendly, clear, lively, 300 page book!

The sections on the Lambda Calculus were particularly rewarding for me, as this is an area that I somehow never picked up in my studies, and although I've tried from time to time to comprehend it, this was the first time I really felt like I got a true understanding of what was going on, and why it has the power that it does.

This is not to say that Understanding Computation is easy. You have to be willing to read Stuart's writing carefully, and you have to stop and think about what he's saying.

But all the way through, Understanding Computation is fun to read, not heavy or dull. For example, here's Stuart talking about the practice of programming:

Programmers tend to be practical, pragmatic creatures. We often learn a new programming language by reading documentation, following tutorials, studying existing programs, and tinkering with simple programs of our own, without giving much thought to what those programs mean. Sometimes the learning process feels a lot like trial and error: we try to understand a piece of a language by looking at examples and documentation, then we try to write something in it, then everything blows up and we have to go back and try again until we manage to assemble something that mostly works. As computers and the systems they support become increasingly complex, it's tempting to think of programs as opaque incantations that represent only themselves and work only by chance.

But computer programming isn't really about programs, it's about ideas. A program is a frozen representation of an idea, a snapshot of a structure that once existed in a programmer's imagination. Programs are only worth writing because they have meaning. So what connects code to its meaning, and how can we be more concrete about the meaning of a program than saying "it just does whatever it does"? In this chapter, we're going to look at a few techniques for nailing down the meaning of computer programs and see how to bring those dead snapshots to life.

"Everything blows up and we have to go back and try again": how perfect of a description is that?!

Some programmers are just programmers: for them, programming is a job, and they are doing it to make a living. To be an industrial programmer, you don't necessarily need to Think Deep Thoughts. You acquire a certain level of competence with the widely-used technologies of the moment; you join a team; you take on certain projects; you crank out code.

There's absolutely nothing wrong with being an industrial programmer, but this book is not really for that person.

There's another sort of programmer who isn't just interested in what, but also in why, and how. Some programmers don't approach programming just as a mechanical process, but are more introspective. They think about alternatives; they wonder whether one approach is somehow better than another; they look for ways to refine and elevate practice to art. This is the person who wants to be able to explain (to themselves and to others) not just that their program works, but why it works. This is the sort of programmer that frets about abstractions, that looks for common concepts and opportunities to reuse and extend solutions that were built earlier, that speculates not just about the solution to the problem at hand, but about the solution to the problem not yet encountered.

Stuart's book will appeal to that person, to that programmer who's neither just a practical engineer nor an abstract theoretician, but is rather somewhere in between, a little bit of both, and looking always for the opportunity to combine the two approaches and demonstrate that the whole is greater than the sum of its parts.

Does that describe you? Well, if so, give Understanding Computation a try; you might well enjoy it!