Elements of programming

For learners new to computer science or to languages from the Lisp family. After this lesson you can read and write small Scheme programs, explain how the interpreter evaluates an expression, and name the three mechanisms every general-purpose language gives you for building complex ideas from simple ones.

Why start here

Programming is not, fundamentally, about typing instructions for a machine. It is about expressing computational processes in a language a human can read and a machine can run. In SICP §1.1, Abelson and Sussman argue that every powerful programming language must give us three things to combine ideas:

1. Primitive expressions — the simplest entities the language deals with.
2. Means of combination — ways to build compound things from simpler ones.
3. Means of abstraction — ways to name those compounds so they can be used as if they were primitives.

This three-part frame is the spine of the whole course. Every chapter of SICP — and arguably every advance in programming languages from FORTRAN to Haskell — is about extending one of those three categories.

Alan Perlis put it more bluntly in the foreword to SICP: "I think that it's extraordinarily important that we in computer science keep fun in computing… we wish to disturb the lives of as many people as possible."

Expressions, evaluation, and the REPL

Lisp programs are made of expressions. You type one at the read–eval–print loop (REPL), the interpreter returns its value, and the loop repeats. The simplest expressions are numbers:

486
;; => 486

Combinations are written as parenthesised lists with the operator first:

(+ 137 349)   ;; => 486
(* 5 99)      ;; => 495
(/ 10 5)      ;; => 2

This prefix notation — operator first — has two virtues SICP §1.1.1 calls out: operators can take arbitrarily many arguments (no precedence rules), and combinations nest without ambiguity:

(+ (* 3 5) (- 10 6))   ;; => 19

Naming and the environment

A define form binds a name to a value:

(define size 2)
(* 5 size)   ;; => 10

The pair (name, value) is stored in an environment. Every evaluation happens with respect to some environment, and define is how we extend it. We will rebuild this idea formally in 03-higher-order-procedures and again, from scratch, when we write a metacircular evaluator in 07-metalinguistic-abstraction.

The general rule for evaluating combinations, from SICP §1.1.3:

To evaluate a combination: (1) evaluate the subexpressions; (2) apply the procedure that is the value of the leftmost subexpression to the arguments that are the values of the other subexpressions.

This is recursive — sub-expressions are themselves evaluated by the same rule — bottoming out at primitives (numbers, built-in operators, names looked up in the environment). That recursion is your first encounter with the substitution model.

Compound procedures

A procedure definition is the second means of abstraction:

(define (square x) (* x x))
(square 21)              ;; => 441
(square (+ 2 5))         ;; => 49
(square (square 3))      ;; => 81

square is now a black box: anywhere a number is expected, (square …) works. You can build sum-of-squares from it:

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares 3 4)     ;; => 25

Notice the layering. sum-of-squares uses square, which uses *. Each layer hides the one below. SICP calls this a procedural abstraction: the user of square does not care how squaring is implemented, only that it squares.

The substitution model

To reason about what a procedure call returns, SICP §1.1.5 gives us the substitution model:

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

So (sum-of-squares 3 4) reduces step by step:

(sum-of-squares 3 4)
(+ (square 3) (square 4))
(+ (* 3 3)   (* 4 4))
(+ 9 16)
25

The substitution model is a fiction — real interpreters use environments and pointers — but it is correct for the purely functional subset of Scheme we use in this module. We hold on to it until Module 01 Lesson 06, where assignment breaks it and we need the environment model instead.

Applicative vs. normal order

The model above evaluates arguments before substituting (this is called applicative order). An alternative — normal order — substitutes unevaluated argument expressions into the body and evaluates only when a value is finally needed. Both produce the same answer for well-behaved programs, but applicative order is more efficient because it never evaluates the same expression twice. Scheme uses applicative order. (SICP §1.1.5)

This distinction matters later — Haskell uses a form of normal order called lazy evaluation, and we'll see streams (Module 01 Lesson 05) that simulate it inside Scheme.

Conditionals and case analysis

Real programs branch. Scheme has two forms:

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

;; equivalent using if
(define (abs x)
  (if (< x 0) (- x) x))

cond walks a list of (predicate value) clauses; the first true predicate wins. if is the special case for two branches. Both are special forms — unlike + or square, they cannot be ordinary procedures because they must not evaluate every sub-expression (you don't want (- x) evaluated when x is positive). The reason cond and if are special forms is the same reason short-circuit && and || exist in C: control flow has to be lazier than function application. (SICP §1.1.6)

Square roots by Newton's method — abstraction in action

The capstone of §1.1 is a worked example: computing sqrt by Newton's method of successive approximations.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y) (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x) (sqrt-iter 1.0 x))

(sqrt 9)        ;; => 3.00009155...
(sqrt 2)        ;; => 1.41421568...

Two things matter here. First, sqrt is recursive: it calls itself on a refined guess. The substitution model still applies — each call substitutes a better guess. Second, the program is built as a small tower of named ideas (good-enough?, improve, average) each of which could stand on its own. The reader of sqrt-iter does not need to know how good-enough? decides; the reader of good-enough? does not need to know what sqrt-iter will do with the answer. SICP calls each of these a procedural abstraction, and the whole arrangement a black-box abstraction.

Internal definitions and block structure

There is one obvious problem with the sqrt program above: good-enough? and improve are global, so the rest of the world can call them too — even though they only make sense inside sqrt. Scheme's fix is block structure — definitions nested inside another definition:

(define (sqrt x)
  (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001))
  (define (improve guess) (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess) guess (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

Notice x no longer needs to be passed down — it is captured by the lexical scope of the inner procedures. This is the same scoping rule as JavaScript closures, Python nested functions, Rust closures, and almost every modern language. It is also the foundation of Lesson 03's higher-order procedures. (SICP §1.1.8)

What "abstraction" actually means

A theme to carry into the next lesson, from Abelson's first OCW lecture: computer science is not really about computers any more than geometry is about surveying instruments. The interesting subject is the language of process — how to describe what something does in a way that another mind (or another procedure) can use without re-deriving everything from first principles.

Every subsequent module — algorithms, OS, databases, distributed systems — is at some level about choosing the right abstractions and not paying for the wrong ones.

Sources

• Abelson, Sussman & Sussman — Structure and Interpretation of Computer Programs §1.1 (MIT Press, 2e, 1996) — https://sarabander.github.io/sicp/html/1_002e1.xhtml
• MIT OCW 6.001 — Spring 2005 — Lecture 1: Overview and Introduction to Lisp (Hal Abelson) — https://ocw.mit.edu/courses/6-001-structure-and-interpretation-of-computer-programs-spring-2005/resources/lecture-1-overview-and-introduction-to-lisp/
• Alan Perlis — Foreword to SICP — https://sarabander.github.io/sicp/html/Foreword.xhtml

Practice

Install MIT/GNU Scheme or Racket (use #lang sicp in DrRacket for SICP compatibility).

1. SICP Exercises 1.1–1.8. Exercise 1.6 in particular is the killer one — it forces you to confront why if cannot be defined as an ordinary procedure.
2. Modify good-enough? to use a relative tolerance instead of an absolute one (Exercise 1.7), then test it on very small (1e-10) and very large (1e10) inputs and observe what changes.

<!-- py-runnable-demo -->

Try it yourself — Python

This runs real Python (CPython compiled to WebAssembly) right in your browser. Hit Run — the first run downloads the runtime (a few seconds), then it's cached.

Edit the code, add a print, or trigger an error to see how Python tracebacks render.