What is computation? The word itself means different things to different people, but everyone can agree that when a computer reads a program, runs that program, reads some input, and eventually produces some output, then some kind of computation has definitely happened. That gives us a decent starting point: computation is a name for what a computer does.

To create an environment where this familiar sort of computation can occur, we need three basic ingredients:

So this part of the book is about machines, languages, and programs—what they are, how they behave, how we can model and study them, and how we can exploit them to get useful work done. By investigating these three ingredients, we can develop a better intuition for what computation is and how it happens.

In Chapter 2, we’ll design and implement a toy programming language by exploring several different ways to specify its meaning. Understanding the meaning of a language is what allows us to take a lifeless piece of source code and animate it as a dynamic, executing process; each specification technique gives us a particular strategy for running a program, and we’ll end up with several different ways of implementing the same language.

We’ll see that programming is the art of assembling a precisely defined structure that can be dismantled, analyzed, and ultimately interpreted by a machine to create a computation. And more important, we’ll discover that implementing programming languages is easy and fun: although parsing, interpretation, and compilation can seem intimidating, they’re actually quite simple and enjoyable to play around with.

Programs aren’t much use without machines to run them on, so in Chapter 3, we’ll design very simple machines capable of performing basic, hardcoded tasks. From that humble foundation, we’ll work our way up to more sophisticated machines in Chapter 4, and in Chapter 5, we’ll see how to design a general-purpose computing device that can be controlled with software.

By the time we reach Part II, we’ll have seen the full spectrum of computational power: some machines with very limited capabilities, others that are more useful but still frustratingly constrained, and finally, the most powerful machines that we know how to build.