The elements of programming

We start from nothing. The whole 22-lesson arc rests on one sentence — programming is the control of complexity through abstraction — and on one question: what does a powerful language have to give you so you can build abstractions at all? The answer is three things, and only three: primitives (built-in atoms), means of combination (ways to build compound things from simpler ones), and means of abstraction (ways to name a compound thing and use it as a unit). This lesson defines those three, then introduces the substitution model — the first and simplest theory of how a program runs, the one every later evaluation model will be measured against and, eventually, forced to replace.

1 · Expressions, values, and the three means

You interact with a language by typing expressions; the interpreter evaluates each one and reports the value it denotes. The simplest expressions are primitive: the numeral 486 evaluates to the number 486; the name Math.PI to a number near 3.14159. You combine expressions with operators, which are themselves a means of combination: 137 + 349 is a compound expression whose subexpressions are evaluated and then combined by +.

137 + 349         // => 486   — combine two primitives
1000 - 334        // => 666
(3 * 5) + (10 - 6) // => 19   — combinations nest arbitrarily

That nesting is the first glimpse of the whole game. Three capabilities recur in every powerful language, and SICP names them once so we can spot them forever after:

2 · Names and bindings — the first abstraction

The means of abstraction begins with the ability to name things. A constant declaration associates a name with the value of an expression:

const size = 2;
size * 5;          // => 10  — the name stands for its value
const pi = 3.14159;
const radius = 10;
pi * radius * radius;   // => 314.159

The name size is now bound to 2. The interpreter keeps these name→value associations in an environment — for now, think of it as a single global table. To evaluate a name, look it up in the environment and return what it is bound to. Naming is genuine abstraction: pi lets us refer to a computed value without recomputing or even understanding it. We have hidden a detail behind a name — the smallest possible version of the move the entire series is about.

3 · Function definition, application, and the substitution model

Naming a value is the start; naming a process is the leap. A function declaration abstracts a compound operation under a name and gives it parameters:

function square(x) { return x * x; }
function sumOfSquares(a, b) { return square(a) + square(b); }

square(21);            // => 441
sumOfSquares(3, 4);    // => 25

How does sumOfSquares(3, 4) actually produce 25? Our first theory of evaluation — the substitution model — answers this. The rule for applying a function to arguments is:

"Replaced by" is literal: substitute the argument into the body, then keep reducing. Trace it fully — every step is just substitution and primitive arithmetic:

sumOfSquares(3, 4)
  -- substitute 3 for a, 4 for b in the body:
square(3) + square(4)
  -- apply square to 3: substitute 3 for x in (x * x):
(3 * 3) + square(4)
  -- apply square to 4:
(3 * 3) + (4 * 4)
  -- reduce primitive operators:
9 + 16
25

One subtlety the model leaves open: do we evaluate the arguments before substituting (called applicative order — what JavaScript actually does), or substitute the unevaluated argument expressions and only reduce when forced (normal order)? For pure arithmetic the final value is identical, so we defer the distinction. Note that it exists — lesson 16 will deliberately switch orders and watch the meaning of programs change.

4 · Predicates and conditionals — letting a process branch

A process that always does the same thing is weak. Predicates (expressions returning a boolean) plus conditionals let a function choose:

function abs(x) {
  return x >= 0 ? x : -x;        // conditional expression: test ? then : else
}
function clamp(x, lo, hi) {
  if (x < lo) { return lo; }
  else if (x > hi) { return hi; }
  else { return x; }
}

The substitution model extends cleanly: to evaluate a conditional, evaluate the predicate; if it is true, evaluate the consequent, otherwise the alternative. Crucially, only the chosen branch is evaluated — a fact we will lean on when we build evaluators ourselves. Logical operators && and || compose predicates: x > 0 && x < 10.

5 · Block structure — hiding internal names

As functions grow, they need helper functions and intermediate names that callers should never see. A block (a function body) can contain its own local declarations, invisible outside it. This is block structure, and it is the means of abstraction applied to a function's own internals:

function sqrt(x) {
  // helpers and locals live INSIDE sqrt; the outside sees only sqrt(x)
  function isGoodEnough(guess) { return Math.abs(guess * guess - x) < 0.001; }
  function improve(guess)      { return (guess + x / guess) / 2; }
  function iter(guess) {
    return isGoodEnough(guess) ? guess : iter(improve(guess));
  }
  return iter(1.0);
}

Notice x is visible to every inner function without being passed — the inner functions are nested in the scope where x is bound. This is lexical scoping: a name refers to the binding in the textually enclosing block. The substitution model handles it informally (substitute x everywhere it appears), but you should already sense a crack: substitution into nested scopes gets delicate, and lesson 10's environment model exists partly to make scoping exact.

6 · Newton's square root — a process behind a boundary

The sqrt above is a real algorithm: Newton's method of successive approximation. Start with a guess; if the guess squared is close enough to x, accept it; otherwise improve the guess by averaging it with x/guess and repeat. The averaging step provably drives the guess toward the true root.

guess      guess*guess    improve -> (guess + 2/guess)/2
1.0000     1.0000         1.5000
1.5000     2.2500         1.4167
1.4167     2.0069         1.41422
1.41422    2.00000...     good enough -> return 1.41422

That last sentence is the whole point and the deepest idea in the lesson. sqrt is a black box: to use it you need to know only its contract — "give me a non-negative number, get back its approximate square root" — not its implementation. An abstraction is a contract, not an implementation. We could swap Newton's method for any other algorithm and no caller would notice or need to change. This procedural abstraction — sealing a process behind a name and a contract — is the lesson's payoff, and the template for every abstraction in the series.

Common mistakes / failure modes

Checkpoint exercise

function cube(x) { return x * x * x; }
function sumCubes(a, b, c) { return cube(a) + cube(b) + cube(c); }

Where this points next

We can now name a process and seal it behind a contract — sqrt(x) is a black box. But the instant you can name a process, an unavoidable question appears that the substitution model answers only by accident: what does running it cost? Our two sqrt helpers, recursion in iter, the redundant calls in the checkpoint — these have wildly different time and space behavior, and "it returns the right value" says nothing about whether it returns in a millisecond or a millennium. The substitution trace already hints at it: the shape of the reduction (how long the chain of pending operations grows) is a property of the process, separate from the function's definition. Lesson 02 makes that separation precise — definition versus the process a definition generates — and gives us orders of growth to predict cost. Naming a process forces us to ask its price.

Interview prompts

• Name the three means a powerful language provides and give an example of each. (§1 — primitives (numbers, operators); means of combination (nested operator/function application); means of abstraction (const names a value, function names a process).)
• State the substitution model's rule for applying a function. (§3 — evaluate the argument expressions, then evaluate the function body with each parameter replaced by its argument value; reduce until only a value remains.)
• What is the difference between applicative and normal order, and does it matter here? (§3 — applicative evaluates arguments before substituting (JavaScript); normal substitutes unevaluated expressions; identical final value for pure arithmetic, but lesson 16 shows termination can differ.)
• Why is a function a "black box," and what is the cost of leaking its internals? (§6 — users depend only on its contract, so the implementation can change freely; if callers depend on internals (tolerance, guess sequence) the abstraction barrier breaks and you lose that freedom.)
• How does block structure relate to abstraction and scope? (§5 — a function body may declare local helpers/names invisible outside it (lexical scope), abstracting the function's own internals so callers see only its contract.)
• When is the substitution model valid, and what threatens it? (§3, mistakes — it is a human reasoning tool valid while functions are pure (a call denotes one value); assignment/state (lesson 09) make a call's result depend on history, breaking it.)
• Explain how Newton's method computes a square root and why the caller need not know it. (§6 — iteratively improve a guess by averaging it with x/guess until guess² is close enough; the caller relies only on the contract "non-negative in, approximate root out.")