# 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:
1. 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)
```
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:
1. Evaluate "define": This updates ENV2 to the following:
```     ENV2: [f:f3 g:f4]

f4: ParentEnv: ENV2
Param: x
Body: (lambda (x) (f (* x a)))
```
2. Evaluate "let": This creates a new environment
```     ENV3: [f:h a:3] ENV3.Parent = ENV2
```
3. In ENV3, Evaluate (g b). We apply the same 2 step procedure.
Evaluation of (g b) in ENV3:
1. EVALUATE PARAMETERS IN ENV3: b = 2
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.
```
1. EVALUATE PARAMETERS IN ENV1:

The function evaluates to f5 and the parameter to 5.

2. 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:
1. CREATE NEW ENVIRONMENT ENV6
```     ENV6: [x: 5]
```
2. LINK NEW ENVIRONMENT TO THE PARENT ENVIRONMENT OF f3
```     ENV6.Parent = ENV1
```
3. IN ENV6, EVALUATE BODY of f3: (* x 2): RESULT is 10.

The end.