2

SICP 3.2 introduce environment model to replace substitution model.

I did following test while learning this part:

(define a1 1)
(define (f1) a1)
(f1) ; return 1
(define (f2) (define a1 2) a1)
(f2) ; return 2
(define (f3) (define a1 2) (f1))
(f3) ; return 1,not 2

The last expression was beyond my expectations.

A sentence token from SICP

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.

According to this rule, When invoke f1 inside f3, a new environment is created, and its enclosing environment is global, not environment (call E1) created when invoke f2. For me, E1 should be the enclosing environment.

For brevity, I draw two pictures depicting the environment env when define functions env when invoke f3

A similar C example:

int a = 1;
void f1() {
    printf("a = %d from f1\n", a);
}
void f2() {
    int a = 2;
    printf("a = %d from f2\n", a);
}
void f3() {
    int a = 2;
    f1();
}
int main() {
    f2();
    f3();
    return 0;
}
print:
a = 2 from f2
a = 1 from f1

Is there anything I am missing ? or why does f3 in both Scheme and C print 1 instead of 2 ?

2 Answers 2

3

Consider that in the environment model, when you define a function, actually you obtain a closure, that is a couple (function, environment in which to evaluate the free variables of the function). A free variabile is a variable mentioned in the function which is not a parameter or a local variable, so that, when the function is actually executed, it is searched in the environment part of the closure.

So, when you define f1, the closure returned has as environment the current global environment, in which a1 has value 1.

In your definition of f2, you define a1 as 2. This is a local definition, so that in the body, the value of a1 is searched first in the local environment, and 2 is found.

In the definition of f3, you define again a1 as 2, and again this binding is present in the local environment, but you call f1, which is a closure, and during its esecution the value of a1 is searched according to the definition of f1 (and the value found is that present in the environment used at the closure building time, that is 1.)

This way of interpreting variables is called static binding, in contrast to dynamic binding, in which the result would have been 2.

Note that both C and Scheme uses static binding, and your C example show exactly this: the result of calling f3 is 1, since this is the value printed inside f1. The image, on the other hand, is not correct. You should think of an environment as a set of frames, each of them containing bindings (i.e. couples variable, current value), connected to other frames. So that the closure of f1, f2, f3are different.

The following picture shows the growth of the global environment:

enter image description here

E1 is the global environment after the definition of a1. E2 after the definition of f1, you can note that the value of f1 is a closure pointing to the second frame (this to allow recursive definitions, since f1 can in principle call itself). In the closure the value of a1 is the value present in E1. E3 is the environment after the definition of f2, with the closure pointing first to the local environment, where a1 is equal to 2, then to the current global environment. Finally E4 is the global environment after the definition of f3. Note that the new closure has again a local environment with a2 equal to 2.

When f3 is called, the f1 inside its body is retrieved as the value of f1 in E2, and when f1 is evaluated, then a1 = 1 is used.

With dynamic binding, on the other hand, there is no need to create closures. Each function is evaluated in the current environment, which is the global environment extended with the parameter bindings and the local definitions. So you could imagine that the global environment now has simply this form:

enter image description here

but when f3 is evaluated, the (define a1 2) add a new frame to the environment:

enter image description here

and with this environment is evaluate the last form, (f1). During this evaluation, f1 is retrieved in the environment, and its body is again evaluated in the same (unique) environment, in which a2 has value 2.

2
  • Hi Renzo, I have updated the C example.and attach two picture depicting the environment when invoke f3. I think I get your point.In static binding, global env should be the enclosing environment and E1 should be in dynamic binding.Is it right ?
    – Jiacai Liu
    Oct 11, 2015 at 8:27
  • Aha, The thing I have missed is that environment is a sequence of frames. And to be honest, I have no idea how frames make up the environment until see your picture. BTW, how do dynamic binding languages eval f3 return 2, could you draw another picture explaining this. Many thanks.
    – Jiacai Liu
    Oct 11, 2015 at 9:14
1

The tricky part here is the internal define in f2.

If you try this program, which uses set! instead of define you will get the result you expect (for clarity I renamed the last function to f3).

(define a1 1)
(define (f1) a1)
(f1) ; return 1
(define (f2) (set! a1 2) a1)
(f2) ; return 2
(define (f3) (define a1 2) (f1))
(f3) ; return 1,not 2

Output:

1
2
2

Now the reason you don't see that behaviour in the original program is due to the internal define:

 (define (f2) (define a1 2) a1)

The internal define will expand to

 (define (f2) 
   (letrec ((a1 2))
     a1))

which if we rename the variables is:

 (define (f2) 
   (letrec ((a2 2))
     a2))

So internal define will allocate a new variable and thus the original location to which a1 was bound is not affected - and thus keeps the value 1.

Note: In the REPL (top-level) using define to define an already defined variable is equivalent to `set!. That is top-level define and internal define are two separate concepts.

2
  • In your above code,(define (f2) (letrec ((a1 2)) a2)), where does a2 come from? or is a typo and actually is a1 ?
    – Jiacai Liu
    Oct 11, 2015 at 3:05
  • Typo - sorry. For the official description of internal definitions see this section in R5RS: www-sop.inria.fr/indes/fp/Bigloo/doc/…
    – soegaard
    Oct 11, 2015 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.