SICP

Building Abstractions with Procedures

The Elements of Programming

primitive expressions

which represent the simplest entities the language is concerned with,

means of combination

by which compound elements are built from simpler ones, and

means of abstraction

by which compound elements can be named and manipulated as units.

Expression

(operator operand ... )

combination donote procedure application. the value of combination is obtained by applying the procedure specified by operator to the arguments that are values of the operands.

Naming and Environment

naming means associating a name with an object. The memory that keeps track of the name-object pairs is called environment.

Evaluating Combinations

the evaluation rule for expressions can be described by a simple general rule together with specialized rules for a small number of special forms

Compound Procedures

The Substitution Model for Procedure Application

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

- applicative-order

- normal-order

Conditional Expressions and Predicates

(cond ... )

case analysis.

Example: Square Roots by Newton's Method

(define (square x)
  (* x x))
(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))

Procedures as Black-Box Abstractions

• bound variable: formal parameter.
• free variable: If a variable is not bound, we say that it is free.
• scope: The set of expressions for which a binding defines a name is called the scope of that name.

• Internal definitions and block structure, lexical scoping.

(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))

Procedures and the Processes They Generate

Linear Recursion and Iteration

• linear recursive process.the amount of information needed to keep track of it, grows linearly with n (is proportional to n), just like the number of steps
• iterative process. an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.

It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive.

Tree Recursion