# 5.7 Summary of Part I

To conclude Part I, we revisit the three main themes introduced in Section 1.4.

*Recursive definitions.*recursive definition We have seen many types of
recursive definitions and used them to solve problems, including the
pegboard puzzle. Recursive grammars provide a compact way to define a
language; recursive procedure definitions enable us to solve problems by
optimistically assuming a smaller problem instance can be solved and
using that solution to solve the problem; recursive data structures such
as the list type allow us to define and manipulate complex data built
from simple components. All recursive definitions involve a base case.
For grammars, the base case provides a way to stop the recursive
replacements by produce a terminal (or empty output) directly; for
procedures, the base case provides a direct solution to a small problem
instance; for data structures, the base case provides a small instance
of the data type (e.g., |null|). We will see many more examples of
recursive definitions in the rest of this book.

*Universality.* All of the programs we have can be created
from the simple subset of Scheme introduced in
Chapter 3. This subset is a *universal programming
language*: it is powerful enough to describe all possible computations.
We can generate all the programs using the simple Scheme grammar, and
interpret their meaning by systematically following the evaluation
rules. We have also seen the universality of code and data. Procedures
can take procedures as inputs, and produce procedures as outputs.

*Abstraction.*abstraction Abstraction hides details by giving things
names. Procedural abstraction defines a procedure; by using inputs, a
short procedure definition can abstract infinitely many different
information processes. Data abstraction hides the details of how data is
represented by providing procedures that abstractly create and
manipulate that data. As we develop programs to solve more complex
problems, it is increasingly important to use abstraction well to manage
complexity. We need to break problems down into smaller parts that can
be solved separately. Solutions to complex problems can be developed by
thinking about what objects need to be modeled, and designing data
abstractions the implement those models. Most of the work in solving the
problem is defining the right datatypes; once we have the datatypes we
need to model the problem well, we are usually well along the path to a
solution.

With the tools from Part I, you can define a procedure to do any possible computation. In Part II, we examine the costs of executing procedures.