Skip to content

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.

Expressions

  • The REPL reads and 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.
  • List combinations use prefix notation (the operator comes first).
  • Combinations can be nested: an operator or operand can itself be another combination.

Naming and the Environment

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

Evaluating Combinations

  • To evaluate a combination:
    1. Evaluate the subexpressions of the combination.
    2. Apply the procedure (value of the 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; it is not a combination.
  • Exceptions such as these are special forms. Each one has its own evaluation rule.

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

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.

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.

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 wills always evaluate to true.
  • The if conditional can be used when there are only to cases.
  • Logical values can be combined with and, or, not. The first two are special forms, not procedures, because they have short-circuiting behavior.

Exercises: 1.1, 1.2, 1.3, 1.4, 1.5

Example: Square Roots by Newton's Method

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

  • 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 a 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.
(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.00009155413138 
(sqrt (+ 100 37)) 
~> 11.704699917758145 
(sqrt (+ (sqrt 2) (sqrt 3))) 
~> 1.7739279023207892 
(square (sqrt 1000)) 
~> 1000.000369924366

Exercises: 1.6, 1.7, 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.

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 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.