Study Guide: Environments and HOF

Instructions

This is the companion guide to Quiz 2 with links to past lectures, assignments, and handouts, as well as isomorphic quiz problems and additional practice problems to assist you in learning the concepts.

In Summer 2017, the instructors made a video walkthrough for a similar quiz question.

Draw environment diagrams automatically with Python Tutor.

Assignments

Handouts

Lectures

Readings

Guides

Quiz Rubric

View your work on Gradescope.

We identified common misconceptions and categorized student solutions for each frame of the environment diagram.

Here's an overview of the order of evaluation rules for the call expression, yes(yes)(no)('ok').

  • We're normally accustomed to calling functions of the form, print('ok'). What's in the operator print? It's a primitive expression because it is a name that evaluates to the built-in function that knows how to print values to the display.
  • The difference with this problem is that the operator is a lot more complex. Instead of just being a primitive expression, the name which evaluates to the function that knows how to print, the operator is itself a call expression. We need to evaluate yes(yes)(no) first to identify the function value.

It may help to review the lecture on Higher-Order Functions again.

Common Misconceptions

  • Remember that we cannot leave the value of a binding as yes(yes)(no), or other unevaluated code like 'ok' + 'ok'.
  • Remember that adding two strings together results in a concatenation: 'ok' + 'ok' results in the single string value,'okok', not 'ok' 'ok'.
  • Remember that names like no evaluate to values, like function values. A binding cannot be left as a name like no. In Python, names are bound to values like functions, numbers, booleans, strings, or None, to name a few. Only these values can be written as values for names.
  • Remember that expressions enclosed in quotes evaluate to string values, or sequences of characters. These quoted expressions are primitive expressions that evaluate directly to string values, compared to names which require us to follow a lookup procedure to evaluate the value of the name.
  • Remember to include quotes around string values.
  • Remember that function values are referenced in a diagram with a pointer.
  • Remember to include name-value bindings for all the parameters of a function when opening a new frame before evaluating the body of that function.
  • Remember that assignment occurs in the current frame: each frame keeps track of its own value for the name no, for instance.

Global

  • (-) The final value of the name no is bound to the string 'no'. Remember that the rule for evaluating def statements require us to bind the name of the function, no, to its value, the function object, func no(no).
  • (-) The name yes is not bound to the result of the call expression. Here's a bookkeeping trick to help keep track of our place in the diagram. Whenever user-defined function is applied and a new frame will need to be opened, mark down Python's current position in the code with a label for the frame number to remember to return to that position after completely evaluating the call.
  • (-) The string value 'no' or 'nook' is assigned to both names. This is likely due to a mistake from another frame. From frame f4, the return value should be 'ok' rather than 'no'. In frame f3, return value should be the result of evaluating 'ok' + 'ok', 'okok'. See the frames f3 and f4 for more detail.

f1

  • (-) The name of the function value is written, rather than referenced. The value of a name is often ambiguous so we use arrows to represent references to function values.
  • (-) Missing name-value bindings for the parameter, no. Remember that opening a new frame requires us to also bind the arguments to each of the formal parameters.
  • (-) The assignment statement no = 'no' in the global frame is executed in this local frame. Remember that Python evaluates only the body of the function, or the lines that are indented by a consistent amount.
  • (-) The value 'okok' propagated up from other local frames. Remember that the return value, 'okok', which occurs in later frames doesn't change the return value of this local frame because this frame already returned a function value!

f2

  • (-) A frame for the function no is opened instead of yes. Remember that the return no from the first frame evaluates to func yes(no). Proceeding down this train of thought would cause an error when attempting to add two function values.
  • (-) Parent frame is marked as f1 instead of global. Remember that, when we open a new frame, we copy down the parent directly from the function value. The parent of the frame is the frame in which it is defined, not where it is called.

f3

  • (-) Unevaluated expressions like 'ok' + yes(no) or 'ok' + 'ok' were left in the diagram. Remember that name-value bindings contain two parts: the name of the binding, like no, and the value, like 'ok', which must be a Python value!
  • (-) A new binding was created for the return value of yes(no). Remember that a new name-value binding is created only through assignment or def statements. The environment diagram should only contain your final solution.

f4

  • (-) Frames listed out of order. Remember that frame 1 can open before another frame 2, but then close after frame 2. See the order of evaluation procedure for yes(yes)(no)('ok') above.

Environment Diagrams

Albert Wu's Environment Diagrams Guide provides an alternative view of the rules and additional practice.

Environment diagrams help us visualize Python's process. For each line of code we should first identify what kind of statement or expression it is and then execute the line according to the rules.

A couple tips:

  • You can only bind names to values. No expressions (like 3 + 4) allowed on environment diagrams!
  • Frames and functions both have parents.
  • Primitive values which include booleans (True, False), numbers (42), and strings ('cs 61a') go directly in the box for the value of a binding.
  • Composite values and function values are drawn off to the side and require a pointer from the value box to the object.

Expressions

Primitive Expressions

  1. In the current environment return the value of the primitive expression. If the expression is just a number or a string, it evaluates to the Python representation of that number or string. If the expression is a name, look for the name in the current environment by following the lookup procedure by starting in the current frame and looking up each parent frame until the global frame.

Call Expressions

  1. Evaluate the operator, which could itself be another call expression.
  2. Evaluate the operands from left to right, each of which could be call expressions.
  3. Apply the operator (evaluated as a function) to the operands (evaluated as arguments). If this is a built-in function, we skip directly to the final result because we don't know how built-in functions are implemented. But if the function is user-defined, create a new frame in the environment diagram.
  4. Bind the formal parameters to the argument values (the evaluated operands).
  5. Evaluate the body of the function in the new frame.
  6. After evaluating the body of the function, return to the frame that called the function.

Statements

Assignment Statements

Note that assignment rules become more complicated with nonlocal.

  1. Evaluate the expression to the right of the assignment operator =.
  2. Bind the variable name to the value of the expression in the current frame. Be sure you override the variable name if it had a previous binding.

def Statements

  1. Draw the func name(arg1, arg2, ...).
  2. The parent of the function is wherever the function was defined (the frame we're currently in, since we're creating the function).
  3. Bind the name of the function to the function value in the current frame.

return Statements

  1. Evaluate the expression to the right of return.
  2. In the current frame, create a space for the return value which contains the value of the return expression.

Practice Problems

Easy

Q1: Make Adder

Draw the environment diagram for the following code.

>>> def adder_maker(x):
...     def adder(y):
...         return x + y
...     return adder
>>> add3 = adder_maker(3)
>>> add3(4)
______
7
>>> sub5 = adder_maker(-5) >>> sub5(6)
______
1
>>> sub5(10) == add3(2)
______
True

Q2: Alpaca Zebra

Draw the environment diagram for the following code.

def yak(zebra):
    return 20 // zebra

def llama(alpaca):
    zebra = 0
    def yak(zebra):
        return alpaca(zebra)
    return yak

llama(yak)(4)

Verify your solution with Python Tutor.

Q3: Multiplication

Using a lambda expression, complete the mul_by_num function. This function should take an argument and return a one argument function that multiplies any value passed to it by the original number.

def mul_by_num(num):
    """
    Returns a function that takes one argument and returns num
    times that argument.
    >>> x = mul_by_num(5)
    >>> y = mul_by_num(2)
    >>> x(3)
    15
    >>> y(-4)
    -8
    """
"*** YOUR CODE HERE ***" return ______
return lambda num2: num * num2

Medium

Q4: Community

>>> def troy():
...     abed = 0
...     while abed < 3:
...         britta = lambda: abed
...         print(abed)
...         abed += 2
...     annie = abed
...     annie += 1
...     abed = 6 # seasons and a movie
...     return britta
>>> jeff = troy()
______
0 2
>>> shirley = lambda: jeff >>> pierce = shirley() >>> pierce()
______
6

Q5: Doge

Draw the environment diagram for the following code.

wow = 6

def much(wow):
    if much == wow:
        such = lambda wow: 5
        def wow():
            return such
        return wow
    such = lambda wow: 4
    return wow()

wow = much(much(much))(wow)

Verify your solution with Python Tutor.

Q6: Two Kinds of People

Draw the environment diagram for the following code.

def blondie(f):
    return lambda x: f(x + 1)

tuco = blondie(lambda x: x * x)
angel_eyes = tuco(2)

Verify your solution with Python Tutor.

Q7: Reruns

>>> def troy():
...     abed = 0
...     while abed < 10:
...         britta = lambda: abed
...         abed += 1
...     abed = 20
...     return britta
...
>>> jeff = troy()
>>> shirley = lambda : jeff
>>> pierce = shirley()
>>> pierce()
______
20