sicpsgjd/3/2/jord/notes.org

• 3.2 the environment model of evaluation
  • 3.2.1 the rules for evaluation
  • 3.2.2 applying simple procedures
  • 3.2.3 frames as the repository of local state
  • 3.2.4 internal definitions

3.2 the environment model of evaluation

substitution has failed with the new power of assignment.

the substitution model: to apply a compound procedure to its arguments, eval the body of the procedure with the formal params replaced by the corresponding argument.

a variable is no longer a name for a value. now it must designate a "place" where its value lies.

these new structures are called environments.

an environment is a sequence of frames.

each frame is a table of bindings. ( a frame has at most one binding per variable)

each frame has a pointer to its enclosed environment (unless it is the global environment )

a variable's value with respect to its environment is the value given by the binding of the variable in the first frame in the environment that contains a binding for that variable. if no frame in the sequence specifies a binding for the variable then the variable is unbound

a binding overiding a different value in a higer frame is shadowed by the other binding

3.2.1 the rules for evaluation

to evaluate a combination:

1. evaluate the subexpressions of the combinataion

2. apply the value of the operator subexpression to the values of the operand subexpressions

in the environment model of evaluation, a procedure is a pair consisting of:

• some code

• a pointer to an environment

to apply a procedure to arguments, create a new environment containing a frame that binds the parameters to the values of the arguments

the environment model of procedure application can be given by two rules:

• a procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the arguments of the call and then evaluating the body of the procedure in the context of the new environment constructed. the new frame has as its enclosing environment the environment part of the procedure object being applied

• a procedure is created by evaluating a lambda expression relative to a given environment. the resulting procedure object is a pair consisting of the text of the lambda expression and a pointer to the environment in which the procedure was created

• define creates a binding in the current frame, assigning the value to the symbol

• (set! variable value) locates the binding of the variable in the environment and changes that binding to a new value

3.2.2 applying simple procedures

  (define (square x)
    (* x x))
  (define (sum-of-squares x y)
    (+ (square x) (square y)))
  (define (f a)
    (sum-of-squares (+ a 1) (* a 2)))
  (f 5)

3.2.3 frames as the repository of local state

  (define (make-withdraw balance)
    (lambda (amount)
      (if (>= balance amount)
	  (begin (set! balance (- balance amount))
		 balance)
	  "insufficient funds")))
  (define W1 (make-withdraw 100))
  (W1 75)

3.2.4 internal definitions

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

with internal definitions:

• names of procedures do not interfere with others in the bigger environment

• local procedures can access enclosing arguments via free vars