Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

`sqrt`

is our first example of a process defined by a set of mutually
defined functions. Notice that the definition of `sqrt-iter`

is
*recursive* (the function is defined in terms of itself). The idea of
being able to define a function in terms of itself may be disturbing;
it may seem unclear how such a “circular” definition could make sense
at all, much less specify a well-defined process to be carried out by
a computer.

Observe that the problem of computing square roots breaks up naturally into a number of subproblems: how to tell whether a guess is good enough, how to improve a guess, and so on. Each of these tasks is accomplished by a separate function.

The importance of this decomposition strategy is not simply that one is dividing the program into parts, rather, it is crucial that each function accomplishesan identifiable task that can be used as a module in defining other functions.

For example, when we define the `good-enough?`

function in terms of
square , we are able to regard `square`

as a “black box.” We are not
at that moment concerned with how the function computes its
result. The details of how the square is computed can be suppressed,
to be considered at a later time. Indeed, as far as the `good-enough?`

function is concerned, `square`

is not quite a function but rather an
abstraction of a function, a so-called procedural abstraction. At this
level of abstraction, any function that computes the square is equally
good.

Thus, considering only the values they return, the following two functions for squaring a number should be indistinguishable. Each takes a numerical argument and produces the square of that number as the value.

```
(defn square [x]
(* x x))
```

```
(defn (square x)
(exp (double (log x))))
(defn double [x]
(+ x x))
```

So a function definition should be able to suppress detail. The users of the function may not have written the function themselves, but may have obtained it from another programmer. A user should not need to know how the function is implemented in order to use it.

It is not even clear which of these functions is a more efficient implementation. This depends upon the hardware available. There are machines for which the “obvious” implementation is the less efficient one. Consider a machine that has extensive tables of logarithms and antilogarithms stored in a very efficient manner.

One detail of a function’s implementation that should not matter to the user of the function is the implementer’s choice of names for the function’s formal parameters.

Thus, the following functions should not be distinguishable:

```
(defn square [x]
(* x x))
```

```
(defn square [y]
(* y y))
```

This principle, that the meaning of a function should be independent
of the parameter names used by its author, seems on the surface to be
self-evident, but its consequences are profound. The simplest
consequence is that the parameter names of a function must be local to
the body of the function. For example, we used square in the
definition of `good-enough?`

in our square-root function:

```
(defn good-enough? [guess x]
(< (abs (- (square guess) x)) 0.001))
```

The intention of the author of `good-enough?`

is to determine if the
square of the first argument is within a given tolerance of the second
argument. We see that the author of `good-enough?`

used the name
`guess`

to refer to the first argument and `x`

to refer to the second
argument. The argument of `square`

is `guess`

. If the author of
`square`

used `x`

(as above) to refer to that argument, we see that
the `x`

in good-enough? must be a different `x`

than the one in square
. Running the function square must not affect the value of `x`

that
is used by `good-enough?`

, because that value of `x`

may be needed by
`good-enough?`

after `square`

is done computing.

If the parameters were not local to the bodies of their respective
functions, then the parameter `x`

in square could be confused with the
parameter `x`

in `good-enough?`

, and the behavior of `good-enough?`

would depend upon which version of square we used. Thus, `square`

would not be the black box we desired.

A formal parameter of a function has a very special role in the
function definition, in that it doesn’t matter what name the formal
parameter has. Such a name is called a *bound variable*, and we say
that the function definition binds its formal parameters. The meaning
of a function definition is unchanged if a bound variable is
consistently renamed throughout the definition.

If a variable is not bound, we say that it is *free*. The set of
expressions for which a binding defines a name is called the *scope*
of that name.

In a function definition, the bound variables declared as the formal parameters of the function have the body of the function as their scope.

In the definition of `good-enough?`

above, `guess`

and `x`

are bound
variables but `<`

, `-`

, `abs`

, and `square`

are free. The meaning
of `good-enough?`

should be independent of the names we choose for
`guess`

and `x`

so long as they are distinct and different from `<`

,
`-`

, `abs`

, and `square`

. (If we renamed `guess`

to `abs`

we would
have introduced a bug by capturing the variable `abs`

. It would have
changed from free to bound.)

The meaning of `good-enough?`

is not independent of the names of its
free variables, however. It surely depends upon the fact (external to
this definition) that the symbol `abs`

names a function for computing
the absolute value of a number. `good-enough?`

will compute a
different function if we substitute `cos`

for `abs`

in its definition.

maybe namespaces, block structure and lexical scoping?