Notes on Building Environments

Principles of Programming Languages (201-1289101)

This note explains in more detail how to build environments when expressing complex expressions. The notation used instead of the pictures used in the book is the following:

An environment is a list of pairs symbol:value. It has a name. It is written ENV1:[a:x b:y ...].
An environment has a parent environment. We write: ENVi.Parent = ENVj
A function object has the following fields:
- A Parent environment, which is the environment that was current when the function was created (that is, when "lambda" was evaluated).
- A list of parameters
- A body (an expression).
It is written as:
```
     f1: ParentEnv: ENVi
         Param: x, y
         Body: (* x y)
     
```

Let us follow the steps involved in setting up environments with the following example:

(define a 1)
(define b 2)
(define (h x) (+ x 100))
(define (targil f)
  (define (g x) (lambda (x) (f (* x a))))
  (let ((f h) (a 3))
    (g b)))

ENV1 is the main environment. It is initialized with the following values:

ENV1: [a:1 b:2 h:f1 targil:f2]

f1: ParentEnv: ENV1
    Param: x
    Body:  (+ x 100)

f2: ParentEnv: ENV1
    Param: f
    Body: (begin (define (g x) (lambda (x) (f (* x a))))
		 (let ((f h) (a 3))
		   (g b)))

Now let us consider what happens when we evaluate the following expression:

EVAL (targil (lambda (x) (* x 2))) in ENV1

The following steps are evaluated whenever a function call is evaluated:

EVALUATE THE PARAMETERS IN CALLING ENVIRONMENT (APPLICATIVE ORDER):
The first parameter (lambda (x) (* x 2)) is evaluated in ENV1. The result is:
```
     f3: ParentEnv: ENV1
         Param: x
         Body: (* x 2)
     
```
APPLY FUNCTION targil:
1. CREATE NEW ENVIRONMENT: ENV2
  FOR EACH PARAMETER ADD AN ENTRY IN THE NEW ENVIRONMENT:
```
          ENV2: [f: f3]
          
```
2. LINK NEW ENVIRONMENT TO PARENT ENVIRONMENT:
  THIS IS THE CRITICAL POINT Always use the ParentEnv of the function being evaluated (targil).
```
          ENV2.parent = ENV1.
          
```
3. IN NEW ENVIRONMENT (ENV2), EVALUATE BODY

The evaluation of the body of targil proceeds as follows:

Evaluate "define": This updates ENV2 to the following:

     ENV2: [f:f3 g:f4]

     f4: ParentEnv: ENV2
         Param: x
         Body: (lambda (x) (f (* x a)))

Evaluate "let": This creates a new environment

     ENV3: [f:h a:3] ENV3.Parent = ENV2

In ENV3, Evaluate (g b). We apply the same 2 step procedure.

Evaluation of (g b) in ENV3:

EVALUATE PARAMETERS IN ENV3: b = 2
APPLY FUNCTION g:
1. CREATE NEW ENVIRONMENT ENV4.
```
          ENV4: [x: 2]
          
```
2. LINK NEW ENVIRONMENT TO PARENT ENVIRONMENT: This is the critical point
```
          ENV4.Parent = ENV2 [NOT ENV3!!!!!!!!!!!!!!]
          
```
3. IN ENV4, EVALUATE BODY of g (which creates a function).

The result obtained is finally:

f5: ParentEnv: ENV4
    Param: x
    Body: (f (* x a))

What happens if we now apply this result as in the following call:

Eval ((targil (lambda (x) (* 2 x))) 5) in ENV1.

EVALUATE PARAMETERS IN ENV1:
The function evaluates to f5 and the parameter to 5.
APPLY FUNCTION f5 (anonymous) to 5:
1. CREATE NEW ENVIRONMENT ENV5.
```
          ENV5: [x: 5]
          
```
2. LINK NEW ENVIRONMENT TO PARENT ENVIRONMENT: This is the critical point
```
          ENV5.Parent = ENV4 [NOT ENV1!!!!!!!!!!!!!!]
          
```
3. IN ENV5, EVALUATE BODY of f5: (f (* x a))

In ENV5, we find that:

ENV5:[x:5]-->ENV4:[x:2]-->ENV2:[f:f3 g:f4]-->ENV1:[a:1 b:2 h:f1 targil:f2]

x = 5    (defined in ENV5)
a = 1    (defined in ENV1)
f = f3   (defined in ENV2)

We now need to evaluate: (f3 5). The same procedure is repeated:

CREATE NEW ENVIRONMENT ENV6
```
     ENV6: [x: 5]
     
```
LINK NEW ENVIRONMENT TO THE PARENT ENVIRONMENT OF f3
```
     ENV6.Parent = ENV1
     
```
IN ENV6, EVALUATE BODY of f3: (* x 2): RESULT is 10.

The end.