Herring Cove
Environment Diagrams

Although environment diagrams come off as very scary and daunting, it really just is a diagram that keeps track of your variables. It does absolutely nothing else. An environment diagram consists solely of frames containing variables bound to their values. Non-primitive values (such as function objects) are drawn on the side of the frames and have arrows pointing to them.

Environment diagrams are, I believe, the most valuable learning tool you can master in 61A. Although they come off as very tricky at first, it’s only a matter of knowing all the rules, and then getting a ton of practice in. Mastering environment diagrams will ensure that you know how assignment statements, call expressions, variable scope, and mutation works.

For 61A purposes, only 3 things can change the state of your environment diagram: function definitions, assignment statements, and call expressions. Below are the steps to evaluate each of these.

Function Definitions

There are two different ways you’ll learn to create functions in this class. The first is a def statement:

def Statements

Evaluating def statements in an environment diagram requires the simplest steps, so don’t overcomplicate it! All a def statement does is create a new function object in the current environment and binds it to its name. That’s it! No evaluating anything, no looking up variables.

Steps

  1. Draw the function object. It should look like this: func <function name>(<params>) [parent=<parent frame>].
  2. Look for the function’s name in the current frame. If it already exists, erase the current binding. If it doesn’t, add it there.
  3. Draw an arrow from the name to the function object.

Important Notes (and Common Pitfalls)

  1. Do not evaluate the body of the function. After completing the 3 steps above, you are DONE. Skip the entire body (all the lines indented under the def header).
  2. Draw the entire function object as I’ve described above and draw the arrow clearly from the name in the frame to the object. Some graders will mark off points if it does not follow this outline exactly.

lambda Expressions

lambda expressions follow a different process than def statements. This is because lambda expressions are expressions, meaning it alone cannot change the state of our diagram; it’s just an expression like 2 + 3! On the other hand, a def statement can change the state of our diagram without having to be paired with anything else. To better understand this, consider this piece of code:

>>> lambda x : x * x 
>>> 5 + 5
>>> def foo(y):
...     x + x

Which line changes our environment? Only the last one! Only the def statement creates a new value and binds it to a name in the environment.

For a lambda expression to change the state of our environment, it must be bound to a name. This can happen in one of three ways:

  1. Explicitly assign the expression to a name. bar = lambda x : x * x
  2. Pass the expression to a higher order function. foo(lambda x : x * x)
  3. Return a lambda expression during a function call. return lambda x : x * x

As you can see, you actually have to evaluate some of the other steps along with or before the lambda! In any of these cases, the process is simple:

Steps

  1. Draw the function object. It should look like this: func λ(\<params\>) [parent=\<parent frame\>]. I often like to put line numbers next to my lambdas since it’s hard to keep track of which is which after several lambdas are created.
  2. Bind the object to whatever it is being assigned to. This depends on how the lambda is being used! See Assignment Statements or Call Expressions for details.

Important Notes (and Common Pitfalls)

  1. If you didn’t read my long winded explanation of how lambda expressions on their own don’t affect the environment, it might seem intuitive to bind these guys to the name λ in your diagram. Make sure you don’t change your diagram unless the lambda occurs in one of the three situations listed above!

Assignment Statements

An assignment statement is any statement with a single equals sign: =, such as x = 3. This is not to be confused with the equality operator ==. Although assignment statements look fairly simple and even trivial, it still involves a series of steps:

Steps

  1. Evaluate the expression on the right hand side of the =.
  2. Look for the name on the left hand side of the = in the current frame of your environment. If it does not exist, write it in.
  3. Bind the value you found in step one to the name you found/wrote in step 2.
    • if the value is primitive (numbers, strings, booleans, None) write it directly next to the name inside the frame
    • if the value is non-primitive (function objects, lists, tuples, etc.), draw it to the side of the frames and connect it to the name with an arrow

Important Notes (and Common Pitfalls)

  1. Do NOT write expressions (e.g. 5 + 10) directly in the frame. Notice how only VALUES are written in the diagram. Expressions have no place there.
  2. Do not write variables next to names or draw arrows to other variables. Variables are not values. Names can only be bound to values.

If you run into one of the above, you did not complete step 1 for assignment statements. That’s why this is the most important step. Executing this step might mean evaluating a function call, which breaks down to even more steps! Let’s get into it.

Call Expressions

This is the most tricky out of the three, but if you follow these steps exactly (actually go through each of the steps!), you will never get confused.

Steps

  1. Evaluate the outermost operator. The operator is the name to the left of the set of parentheses. In the expression foo(bar(x))(y), foo is the operator. Its value should be a function object (i.e. the name in your diagram corresponding to the operator should be pointing to a function object).
  2. Evaluate each of the operands one by one from left to right in the current environment.
  3. Open a new frame and label it with the intrinsic name of the function found in step 1. Also label the parent of the frame with the parent of the function.
  4. Bind the formal parameters to the values of the operands found in step 2.
  5. Evaluate the body of the function in the new environment.

Important Notes (and Common Pitfalls)

  1. Evaluate the operands in the environment where the function was called. Students often open the new frame before evaluating the operands, which leads them to evaluate the operands in this new frame.
  2. Do not open a new frame until you’ve evaluated all the operands, since they might be call expressions which requires opening more frames. Order of the frames does matter for points!
  3. The first thing you do when you open a new frame is bind the parameters.

Bonus question: What does foo return doing for all input x, y?

Let’s try a trickier one!