This is The summary of The Environment Model of Evaluation in chapter 3 of SICP and a review of an exercise.

Procedure will introduce parameters, nested calls, define variables, scope, etc. How to arrange the life cycle and scope of these variables becomes critical.

Environment

Firstly, the concept of Environment is introduced. An Environment is composed of a series of frames. Each frame is a Bindings table, associated with variable names and their corresponding values.

Procedure

Procedure definition syntax is the syntactic sugar for the underlying implicit lambda-expression.

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


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

Copy the code

So a PROCEDURE is equivalent to a reference to the lambda below. For example, square is a reference to (lambda (x) (* x x)).

And a PROCEDURE object is a pair of code and a pointer to the environment.

add bindings

Define creates definitions by adding bindings to frames. Same as square above.

apply procedure

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

Performing a PROCEDURE creates an environment and binds the parameter to the value of the argument.

the frame has as its enclosing environment the environment part of the procedure object being applied.

Each frame has an environment containing it, which is the environment pointed to by the Procedure object.

If procedure returns a lambda, The environment created after procedure execution is an enclosing environment on this lambda (PROCEDURE is just a definition of lambda). Frames as the Repository of Local State

Exercise 3.20

We first provide a mutable pair defined by PROCEDURE

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cdr!) set-y!)
          (else (error "Undefined 
                 operation: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)

(define (set-cdr! z new-value)
  ((z 'set-cdr!) new-value)
  z)

Copy the code

Exercise 3.20: Draw environment diagrams to illustrate the evaluation of the sequence of expressions

(define x (cons 1 2(a))define z (cons x x))

(set-car! (cdr z) 17)

(car x)
17
Copy the code

using the procedural implementation of pairs given above.

Analysis of the

So let me put up the answer, just to analyze it.

Description:

  • The gray rectangle is Environment
  • A variable that is bound to the Environment can refer to its PROCEDURE object or assign a specific value
  • The two circles are a PROCEDURE object, or pair, with the first pointer to the code and the second pointer to its Environment
  • The green text is the code call
  • For the convenience of drawing, some environments are marked repeatedly. For example, there are two E1 in the figure, which actually point to the same E1

Expressions are mutable according to the above definition of pair Procedure. In the global environment, there are these variables:

  • cons
  • car
  • cdr
  • set-car!
  • set-cdr!
  • x
  • z

As you can see in the figure, these variables point to their respective procedures.

The first is

(define x (cons 1 2(a))define z (cons x x))
Copy the code

Two lines

(define x (cons 1 2)) generates an environment called E1, which refers to the environment specified by the procedure object cons. Corresponds to “The frame has as its enclosing environment the environment part of the procedure object being applied.”. E1’s unique frame binds the arguments x and y to arguments 1 and 2. And the E1 internally bound variable set-x! , set-y! And dispatch.

Since (cons x y) returns Dispatch, x points to the PROCEDURE of Dispatch, the Procedure object points to the environment E1, and a pointer to the actual code of dispatch.

(Define z (cons x x)) is similar. In particular, the x bound in E2, y is the x in the global env.

Then the (set – the car! (CDR Z) 17), (set-car! 17) called (CDR Z) to create E3. Since CDR belongs to the Global env, E3 points to the global env.

The next call to (z ‘cdr) creates E4. Because the procedure referred to by Z points to environment E2, E4 points to E2.

Because (z ‘cdr) = x, so (set-car! (cdr z) 17) = (set-car! X 17). On (the set – the car! X 17) call created E5, pointing to global env.

(set-car! x 17) = ((x ‘set-car!) 17), creating E6. Of (x ‘set – car!) The procedure x points to refers to the environment E1, so E6 points to E1.

On (the set – x! 17) because set-x! The environment bound to the variable is E1, so E7 also points to E1. Finally, the x in E1 is changed to 17.

Call to (car x), creating E8.

The call to (x ‘car) creates E9, points to E1, and returns the x in E1, which is 17.

conclusion

Here is just a very simple explanation of the Environment Model through an exercise, which can also see the delicacy of the design. The binding of variables is maintained by performing procedure to create an Environment. These environments are memory-managed and can be reclaimed without being referenced. The Environment also has a pointer to the Environment containing it, which makes it easy to find variables in the parent Environment.