# 1.4 Summary and roadmap

Computer scientists think about problems differently. When confronted with a problem, a computer scientist does not just attempt to solve it. Instead, computer scientists think about a problem as a mapping between its inputs and desired outputs, develop a systematic sequence of steps for solving the problem for any possible input, and consider how the number of steps required to solve the problem scales as the input size increases.

The rest of this book presents a whirlwind introduction to computer science. We do not cover any topics in great depth, but rather provide a broad picture of what computer science is, how to think like a computer scientist, and how to solve problems.

**Part I: Defining Procedures.** Part I focuses on how to define
procedures that perform desired computations. The nature of the computer
forces solutions to be expressed precisely in a language the computer
can interpret. This means a computer scientist needs to understand how
languages work and exactly what phrases in a language mean. Natural
languages like English are too complex and inexact for this, so we need
to invent and use new languages that are simpler, more structured, and
less ambiguously defined than natural
languages.Chapter 2 focuses on language, and during
the course of this book we will use language to precisely describe
processes and languages are interpreted.

The computer frees humans from having to actually carry out the steps needed to solve the problem. Without complaint, boredom, or rebellion, it dutifully executes the exact steps the program specifies. And it executes them at a remarkable rate — billions of simple steps in each second on a typical laptop. This changes not just the time it takes to solve a problem, but qualitatively changes the kinds of problems we can solve, and the kinds of solutions worth considering. Problems like sequencing the human genome, simulating the global climate, and making a photomosaic not only could not have been solved without computing, but perhaps could not have even been envisioned.Chapter 3 introduces programming, and Chapter 4 develops some techniques for constructing programs that solve problems. To represent more interesting problems, we need ways to manage more complex data.Chapter 5 concludes Part I by exploring ways to represent data and define procedures that operate on complex data.

**Part II: Analyzing Procedures.** Part II considers the problem of
estimating the cost required to execute a procedure. This requires
understanding how machines can compute (Chapter 6),
and mathematical tools for reasoning about how cost grows with the size
of the inputs to a procedure (Chapter 7).Chapter 8 provides
some extended examples that apply these techniques.

**Part III: Improving Expressiveness.** The techniques from Part I and
II are sufficient for describing all computations. Our goal, however, it
to be able to define concise, elegant, and efficient procedures for
performing desired computations. Part III presents techniques that
enable more expressive procedures.

**Part IV: The Limits of Computing.** We hope that by the end of Part
III, readers will feel confident that they could program a computer to
do just about anything. In Part IV, we consider the question of what can
and cannot be done by a mechanical computer. A large class of
interesting problems cannot be solved by any computer, even with
unlimited time and space.

**Themes.** Much of the book will revolve around three very powerful
ideas that are prevalent throughout computing:

*Recursive definitions.* A recursive definition
define a thing in terms of smaller instances of itself. A simple example
is defining your ancestors as (1) your parents, and (2) the ancestors of
your ancestors. Recursive definitions can define an infinitely large set
with a small description. They also provide a powerful technique for
solving problems by breaking a problem into solving a simple instance of
the problem and showing how to solve a larger instance of the problem by
using a solution to a smaller instance. We use recursive definitions to
define infinite languages in Chapter 2, to solve
problems in Chapter 4, to build complex data
structures in Chapter 5. In later chapters, we see how
language interpreters themselves can be defined recursively.

*Universality.* Computers are distinguished from other machines in that
their behavior can be changed by a program. Procedures themselves can be
described using just bits, so we can write procedures that process
procedures as inputs and that generate procedures as outputs.
Considering procedures as data is both a powerful problem solving tool,
and a useful way of thinking about the power and fundamental limits of
computing. We introduce the use of procedures as inputs and outputs in Chapter 4, see how generated procedures can be
packaged with state to model objects in Chapter 10.
One of the most fundamental results in computing is that any machine
that can perform a few simple operations is powerful enough to perform
any computation, and in this deep sense, all mechanical computers are
equivalent. We introduce a model of computation in Chapter 6, and reason about the limits of computation in Chapter 12.

*Abstraction.* Abstraction is a way of hiding details by giving things
names. We use abstraction to manage complexity. Good abstractions hide
unnecessary details so they can be used to build complex systems without
needing to understand all the details of the abstraction at once. We
introduce procedural abstraction in Chapter 4,
data abstraction in Chapter 5, abstraction using objects
in Chapter 10, and many other examples of abstraction
throughout this book.

Throughout this book, these three themes will recur recursively, universally, and abstractly as we explore the art and science of how to instruct computing machines to perform useful tasks, reason about the resources needed to execute a particular procedure, and understand the fundamental and practical limits on what computers can do.