🖊️How to Make Environment Diagrams

Draw!

Hello! This is a guide on making environment diagrams for 61A. If you have this playbook open, you should be able to navigate most 61A diagramming questions.

The Environment Diagram Commandments

  1. The parent of a function is the frame in which it was created.

  2. We cannot have two variables with the same name in the same frame.

  3. You can read the values in your parent frame, as well as your grandparent frame, and so on...

  4. You cannot change any values in your parent frame.

Steps to Diagramming — The Big Picture

  1. Draw the current frame. We start in the very beginning by drawing the global frame. If current frame is not the global frame, make sure to add the function's arguments to the frame.

  2. Start assigning values to variables.

  3. Re-assign variables if they already exist in the current frame and they are getting overwritten.

  4. When looking up values of a variable, look in the current frame. If they aren't in the current frame, look in the parent frame. Keep going until variable is found. If not found, Error.

  5. If there is a function call, find the function being called and evaluate the arguments. Then open a new frame, and start back at step 1 in this new frame.

  6. If you reach a return statement, return the value from the frame and close the frame. Go back to where you stopped in the frame that called this function, and continue from step 2.

  7. If you reach the end without a return statement, simply close the frame and return to where you stopped in the frame that called this function. If you are in the global frame, you're done — flip to the next question.

Question Walkthrough

We'll be using this example from Discussion 02 in Fall 2021 as our guiding post:

n = 7

def f(x):
    n = 8
    return x + 1

def g(x):
    n = 9
    def h():
        return x + 1
    return h

def f(f, x):
    return f(x + n)

f = f(g, n)
g = (lambda y: y())(f)

Start at step 1: draw the global frame. The global frame is the top level of execution in a python program. It is created when the file is run.

Continue to step 2: Start assigning values to variables.

This is what our environment diagram looks like by the end of line 12. Notice the following things:

  • The function h() is not defined — anything is tabbed (and thus inside a function) is not read by python. Python only reads the function definition when making functions.

  • The parent of a function is the frame in which it was created.

We now have to use step 3: re-assign variables if they are getting overwritten.

Notice how, when we execute line 13, we don't create another f variable. This is because, in a singular frame, you can have only one instance of a variable. You can, however, have multiple functions with the same name — see func f(x) and func f(f, x) both coexisting in the objects side of our diagram.

Before we continue our environment diagram, we have to tackle line 14 and make sure we understand how step 4: a function call is evaluated.

f = f(g, n)

Python evaluates something like this in the following sequence:

  • It looks to the right side of the assignment statement first, and is going to try to evaluate f(g, n)

    • Python finds what the variable f points to. Looking at our environment diagram, it points to the func f(f, x) function.

    • Python evaluates each of the arguments passed in, and finds what they are referring to. Here, we see that:

      • The variable g refers to the function func g(x)

      • The variable n refers to 7.

    • Thus, we are, in essence, making the following call: func f(func g, 7)

    • Python makes sure that we are passing the correct number of arguments to this function. Here, this is true.

Once all of this is done — the function is found and the arguments evaluated — we circle back to step 1: make the function call and open another frame.

Notice how, while the frame is of the f function, the function itself doesn't exist in the frame. Instead, the f in the frame is the argument we passed into f(f, x).

Also notice that variables can co-exist in the global and the F1 frame — both of them have an f variable. This is perfectly fine — you can think of each frame as a universe of its own.

  • Sanity Check: Can we somehow access the n variable in the F1 frame?

    The answer is yes! When we ask Python to look for n, first it looks in the F1 frame. When it doesn't find any n, it looks in the parent frame — the global frame, where it finds n=7.

  • Sanity Check: Can we somehow access the f(f, x) function in the F1 frame?

    The answer is no! Here's why: The only way to access the function func f(f, x) is through the variable f in the global frame.

    If there was no f defined in the F1 frame, the f would refer to the one in the parent— global— frame. However, in this case, the f is essentially overwritten by the f defined in the F1 frame.

For the return statement of the f(f, x) function, we repeat step 4 — find the function, evaluate the arguments, and then circle back to step 1: open frame.

  • The variable f in f(x+n) evaluates to func g(x)[P=G]. See environment diagram above.

  • The argument x+n evaluates to 14.

    • We look for x in the current frame (F1) and find it x=7.

    • We look for n in the current frame (F1) and don't find it. We look in the parent frame — global. There we find n=7.

And then, viola! Open frame F2.

Here's what that looks like.

Remind to add a "return value" RV to Frame 1, to remind yourself that whatever is returned by frame F2 is returned by frame F1 as well. Then we run steps 2-4 again. This time, we get to step 5: returning a value. Here, the return value is the function func h, so we point to it and return.

And now, we go back to where we stopped in the caller frame — F1. We needed to return the value that the frame F1 returned, so let's do step 5: returning a value and closing the frame again.

And now, we're all the way back to the global frame! Now, we have a value for f(g, n), and we can go back to step 2: assigning values to variables, and complete the expression f=f(g, n). Thus,

Now, let's deal with the last line of this question:

g = (lambda y: y())(f)

You may think you don't know how to tackle this, but you do! Lambdas are functions, and thus follow our environment diagramming rules. So, we do step 4: handling function calls again — evaluating the right side of the expression.

  • We find the lambda function — here, this means adding it to the objects side of the environment diagram!

  • We evaluate the arguments — the variable f evaluates to the function func h().

  • We make the call and open a frame for the lambda function, adding the function arguments in the frame!

In this lambda frame, y() is called, and the whole process starts again. I won't belabor the point — we repeat the same steps again and again until we reach the end of the global frame, in which case, we're done 🎉.

Here's our masterpiece:

Congratulations!

Advice

Now that you have this playbook, environment diagrams should make more sense. However, this is in no way a foolproof tool — the only way to get good at environment diagrams is practice, and a lot of it.

PreviousEnvironments and ScopeNextRecursion

Last updated