1.1 The Elements of Programming⁠

There are three mechanisms for combining simple ideas to form more complex ideas found in every powerful programming language:

• primitive expressions
• means of combination
• means of abstraction

Programming deals with procedures and data (which are almost the same thing in Lisp). Procedures manipulate data.

# 1.1.1 Expressions⁠

• The REPL reads an expression, evaluates it, prints the result, and repeats.
• A number is one kind of primitive expression.
• An application of a primitive procedure is one kind of compound expression.
• A combination denotes procedure application by a list of expressions inside parentheses. The first element is the operator ; the rest are the operands.
• Lisp combinations use prefix notation (the operator comes first).
• Combinations can be nested: an operator or operand can itself be another combination.

# 1.1.2 Naming and the Environment⁠

• Scheme names things with the define. This is the simplest means of abstraction.
• The name–value pairs are stored in an environment.

# 1.1.3 Evaluating Combinations⁠

• To evaluate a combination:
  1. Evaluate the subexpressions of the combination.
  2. Apply the procedure (value of leftmost subexpression, the operator) to the arguments (values of other subexpressions, the operands).
• Before evaluating a combination, we must first evaluate each element inside it.
• Evaluation is recursive in nature—one of its steps is invoking itself.
• The evaluation of a combination can be represented with a tree.
• Recursion is a powerful technique for dealing with hierarchical, tree-like objects.
• To end the recursion, we stipulate the following:
  1. Numbers evaluate to themselves.
  2. Built-in operators evaluate to machine instruction sequences.
  3. Names evaluate to the values associated with them in the environment.
• (define x 3) does not apply define to two arguments; this is not a combination.
• Exceptions such as these are special forms. Each one has its own evaluation rule.

# 1.1.4 Compound Procedures⁠

• Procedure definition is a powerful technique for abstraction.
• A squaring procedure: (define (square x) (* x x)).
• This is a compound procedure given the name “square.”
• General form of a procedure definition: (define (name formal-parameters) body).
• If the body contains more than one expression, each is evaluated in sequence and the value of the last one is returned.

# 1.1.5 The Substitution Model for Procedure Application⁠

This is 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. (Section 1.1.5)

An example of procedure application:

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ 36 100)
136

# Applicative order versus normal order

• The example above used applicative order : evaluate all the subexpressions first, then apply the procedure to the arguments.
• With normal order, operands are substituted in the procedure unevaluated. Only when it reaches primitive operators do combinations reduce to values.
• An example of normal-order procedure application:

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

• Here, normal order causes some combinations to be evaluated multiple times.

# 1.1.6 Conditional Expressions and Predicates⁠

• To make more useful procedures, we need to be able to conduct tests and perform different operations accordingly.
• We do case analysis in Scheme using cond.
• cond expressions work by testing each predicate. The consequent expression of the first clause with a true predicate is returned, and the other clauses are ignored.
• A predicate is an expression that evaluates to true or false.
• The symbol else can be used as the last clause—it will always evaluate to true.
• The if conditional can be used when there are only two cases.
• Logical values can be combined with and, or, and not. The first two are special forms, not procedures, because they have short-circuiting behavior.

# 1.1.7 Example: Square Roots by Newton’s Method⁠

But there is an important difference between mathematical functions and computer procedures. Procedures must be effective. (Section 1.1.7)

• In mathematics, you can define square roots by saying, “The square root of $x$ is the nonnegative $y$ such that $y^2 = x$.” This is not a procedure.
• Mathematical functions describe things (declarative knowledge); procedures describe how to do things (imperative knowledge).
• Declarative is what is, imperative is how to.

# 1.1.8 Procedures as Black-Box Abstractions⁠

• Each procedure in a program should accomplish an identifiable task that can be used as a module in defining other procedures.
• When we use a procedure as a “black box,” we are concerned with what it is doing but not how it is doing it.
• This is called procedural abstraction. Its purpose is to suppress detail.

A user should not need to know how the procedure is implemented in order to use it. (Section 1.1.8)

# Local names

• The choice of names for the procedure’s formal parameters should not matter to the user of the procedure.
• Consequentially, the parameter names must be local to the body of the procedure.
• The name of a formal parameter doesn’t matter; it is a bound variable. The procedure binds its formal parameters.
• If a variable is not bound, it is free.
• The expression in which a binding exists is called the scope of the name. For parameters of a procedure, this is the body.
• Using the same name for a bound variable and an existing free variable is called capturing the variable.
• The names of the free variables do matter for the meaning of the procedure.

# Internal definitions and block structure

• Putting a definition in the body of a procedure makes it local to that procedure. This nesting is called block structure.
• Now we have two kinds of name isolation: formal parameters and internal definitions.
• By internalizing auxiliary procedures, we can often eliminate bindings by allowing variables to remain free.
• Scheme uses lexical scoping, meaning free variables in a procedure refer to bindings in enclosing procedure definitions.