CS61A Fall 2011 – Akihiro, Stephanie, Tom, Eric K., Eric T., Steven, Aditi, Richard, Hamilton, and Phillip 1 CS61A Notes – Week 3: Environments and Higher Order Functions Expressions Expressions describe a computation and evaluates to a value. Primitive Expressions A primitive expression is a single evaluation step: you either look up the value of a name or take the literal value. For example, numbers, function names and strings are all primitive expressions. >>> 2 2 >>> max <built-in function max> >>> “Hello World” #don’t worry about Strings yet ‘Hello World’ Call Expressions Call expressions are expressions that involve a call to some function. Call expressions are just another type of expression, called a compound expression. The point is in the fact that they are calling some function with arguments and returning some value from them. Recall the syntax of a function call: Evaluation of a function call: 1. Evaluate the operator and operands. 2. Apply the function, (the value of the operator), to the arguments, (the values of the operands). QUESTIONS 1. Determine the result of evaluating f(4) in the Python interpreter if the following functions are defined: from operators import add def double(x): return x + x def square(y): return y * y def f(z): add(square(double(z)), 1) Statements A statement in Python is executed by the interpreter to perform an action. For example, assignment is a statement. We are asking Python to assign a certain value to a variable name, assigning being the action that Python is performing. Assignment is a one-line statement, but we also have the idea of compound statements! A good example is an if statement: if <test>: <true_suite> elif <other_test>: <elif_suite> else: <else_suite>CS61A Fall 2011 – Akihiro, Stephanie, Tom, Eric K., Eric T., Steven, Aditi, Richard, Hamilton, and Phillip 2 Let’s consider how Python evaluates an if statement (it is different than the evaluation of an expression): 1. Evaluate the header's expression. 2. If it is a true value, execute the suite & skip the rest 3. Otherwise, go to the next header (either an elif or an else). If there is no other header, you have finished. 4. If it’s an elif, go back to step 1. Otherwise (if it’s an else) go to step 2 (as if the test was True). Note: Each clause is considered in order. What is a suite? A suite is a sequence of statements or expressions. To evaluate a suite means to execute its sequence of statements or expressions in order. We can generalize and say that compound statements are composed of headers and suites like so: <header>: <statement> <statement> ... <separating-header>: <statement> ... Pure Functions vs. Non-Pure Functions (pay attention to domain and range!) Pure function - ONLY produces a return value (no side effects) and always evaluates to the same result, given the same argument value(s). Non-Pure function - may produce some side effects (like printing to the screen). QUESTIONS 2. What do you think Python will print for the following? Assume this definition of the om and nom procedure: def om(foo): return -foo def nom(foo): print(foo) >>> nom(4) __________ >>> om(-4) __________ >>> save1 = nom(4) >>> save1 + 1 __________ >>> save2 = om(-4) >>> save2 + 1 __________CS61A Fall 2011 – Akihiro, Stephanie, Tom, Eric K., Eric T., Steven, Aditi, Richard, Hamilton, and Phillip 3 Expression Trees Now that we have looked at all of these statements, let’s go all the way back to expressions! Remember, an expression describes a computation and evaluates to a value. And an expression tree helps us to break down an expression into smaller “subexpressions” to understand how they combine with one another. QUESTIONS Draw the expression tree for the following expression calls assuming we have imported the correct functions. 3. add(square(mul(5, 6)), add(mul(1, 2), 7)) 4. (2 + 3 * 4) / 7 5. print(print(abs(-4)))CS61A Fall 2011 – Akihiro, Stephanie, Tom, Eric K., Eric T., Steven, Aditi, Richard, Hamilton, and Phillip 4 First Edition Environment Diagrams We are going to use what is called the “environment model” of evaluation. Environment Diagrams are broken up into two main components: 1. the expression tree 2. environments and values We have already seen expression trees, but what about “environments and values?” Briefly, we keep an “environment” of bindings from variable to value, and every time we encounter a variable, we look up its value in the current environment. Note that we only lookup the value when we see the variable, and so we’ll lookup the value of x only after we’ve already defined x to be 3. An environment frame is a box that contains bindings from variables to values. An environment frame can “extend” another frame; that is, this frame can see all bindings of the frame it extends. We represent this by drawing an arrow from an environment frame to the frame it is extending. The global environment is the only environment that extends nothing. An environment is a series of frames, which we get from extending the current frame. The global environment is only made up of the global frame, because its frame extends nothing. Here is how to go about it: 1. Start with a box (a frame) labeled global environment. This box starts out with bindings for all the built-in functions like +, abs, max, etc. 2. Set the current frame to be the global environment. The current frame is just the environment that you're in at the moment (we will want to keep track of this), and of course, you start in the global environment. 3. Evaluate your expressions, one by one. QUESTIONS Fill out the environment diagram, the environments and values as well as the expression tree, for the following code: 4. >>> def a(n): ... return n + 2 ... >>> def b(m): ... return a(n)/2 ... >>> def e(n): ... return a(b(n * 2) + 1) ... >>> n = 5 >>> e(n) ?? 5. >>> def bar(x): ... return x + x ... >>> def foo(x): ... return bar(add(bar(x),1)) ... >>> garply = foo >>> garply(5) ??CS61A Fall 2011 – Akihiro, Stephanie, Tom, Eric K., Eric T., Steven, Aditi, Richard, Hamilton, and Phillip 5 Some rules to keep in mind when evaluating the following: 1. constants: (numbers, strings, etc), they are self-evaluating so don’t do any work. 2. variables: try to find a
View Full Document
Unlocking...