Structure and Interpretation of Computer Programs

Second Edition by Harold Abelson and Gerald Jay Sussman with Juile Sussman

My notes from this book

  1. Computational Process - an abstract being that inhabit computers. As they evolve, processes manipulate other abstract things called data.
  2. Program - evolution of a process is directed by a pattern of ruels called a program
  3. Lisp - invented in the late 1950s as a formalism for reasoning about the use of certain kinds of logical expressions, called recursion equations, as a model for computation.
  4. Lisp was conceived by John McCarthy
  5. Lisp is a practical programming language

The Elements of Programming

  1. Primitive expressions - represent the simplest entities the language is concerned with
  2. Means of combination - by which compound elements are built from simpler ones
  3. Means of abstraction - by which compound elements can be named and manipulated as units


  1. Expression - the thing you type into the terminal (interpreter)
  2. Response - the result of its evaluating that expression
  3. Examples
(+ 137 349)
  1. Expressions are formed by delimiting a list of expressions with parentheses in order to denote procedure application, are called combinations
  2. The leftmost element in the list is called the operator
  3. The other elements are called operands
  4. The value of the combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands
  5. Prefix notation - convention of placing the operator to the left of the operands
  6. repl - read-eval-print-loop

Naming and the Environment

A programming language must provide a means for using names to refer to computational objects. A name identifies a variable whose value is the object

(define size 2)

In Lisp, things are named with define

Define is the language's simplest means of abstraction

The possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment

percolate values upward form the evaluation rule is an example of a general kind of process known as tree accumulation

special forms exceptions to the general evaluation rule, define

Elements that must appear in any powerful programming language:

  • Numbers and arithmetic operations are primitive data and procedures
  • Nesting of combinations provides a means of combining operations
  • Definitions that associate names with values provide a limited means of abstraction

procedure defintions - a much more powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit

example: squaring

(define (square x) (* x x))

To square something, multiply it by itself

The general form of a procedure definition is:

(define (<name> <formal parameters>) <body>)

name - is a symbol to be associated with the procedure definition in the environment

formal parameters - are the names used within the body of the procedure to refer to the corresponding arguments of the procedure

body - is an expression that will yield the value of the procedure application when the formal parameters are replaced by the actual arguments to which the procedure is applied

The Substitution Model for Procedure Application

This can be taken as a model that determines the "meaning" of procedure application

Applicative order versus normal order

Applicative order - evaluate the arguments and then apply
Normal-order - fully expand and then reduce

Lisp uses applicative-order evaluation, partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions AND because normal-order evaluation becomes much more complicated to deal with when we leave the realms of procedures that can be modeled by substitution

Conditional Expressions and Predicates

Case analysis is represented by cond which stands for "conditional"

(p e) - where p is the predicate, that is, an expression whose value is interpreted as either true or false

e is the corresponding expression of the clause

predicate is used for procedures that return true or false, as well as for expressions that evaluate to true or false

Here is an example

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

Another way is: (if <predicate> <consequent> <alternative>)

(define (abs x)
    (if (< x 0)
        (- x)
Structure and Interpretation of Computer Programs
Share this