Understanding Computation

Part I. Programs and Machines

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:

• A machine capable of performing the computation

• A language for writing instructions that the machine can understand

• A program written in that language, describing the exact computation that the machine should perform

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