CS 61A Midterm 1 Study Guide – Page 1
Import statement
Name Value
Assignment statement
Code (left):
Statements and expressions
Red arrow points to next line.
Gray arrow points to the line just executed
Binding
Frames (right):
A name is bound to a value
In a frame, there is at most one binding per name
208
mul(add(2, mul(4, 6)), add(3, 5))
mul 26 8 add(2, mul(4, 6)) add(3, 5)
add 2 24 mul(4, 6)
mul 4 6
add 3 5
Pure Functions
-2 abs(number):
2
2, 10 pow(x, y): Non-Pure Functions
-2 print(…): display “-2”
1024
None
Built-in function
Intrinsic name of function called
Formal parameter bound to argument
Local frame
Return value is
not a binding!
User-defined function
Defining:
Formal parameter >>> def square( x ):
return mul(x, x)
(return statement) Call expression: square(2+2) operand: 2+2
argument: 4
operator: square function: func square(x)
Calling/Applying: 4 square( x ):
Argument Intrinsic name
return mul(x, x) 16 Return value
Compound statement
Clause
Suite
…
…
1 statement, 3 clauses,
3 headers,
3 suites,
2 boolean contexts
def abs_value(x):
if x > 0: return x
elif x == 0: return 0
else:
return -x
2
A name evaluates to
the value bound to
that name in the
earliest frame of
the current 1 environment in which
that name is found.
2
Error
1
•An environment is a sequence of frames
•An environment for a non-nested function (no def within def) consists of one local frame, followed by the global frame
Evaluation rule for call expressions:
1.Evaluate the operator and operand subexpressions. 2.Apply the function that is the value of the operator
subexpression to the arguments that are the values of the operand subexpressions.
Applying user-defined functions:
1.Create a new local frame with the same parent as the function that was applied.
2.Bind the arguments to the function’s formal parameter names in that frame.
3.Execute the body of the function in the environment beginning at that frame.
Execution rule for def statements:
1.Create a new function value with the specified name, formal parameters, and function body.
2.Its parent is the first frame of the current environment. 3.Bind the name of the function to the function value in the
first frame of the current environment.
Execution rule for assignment statements:
1.Evaluate the expression(s) on the right of the equal sign. 2.Simultaneously bind the names on the left to those values,
in the first frame of the current environment.
Execution rule for conditional statements:
Each clause is considered in order.
1.Evaluate the header’s expression.
2.If it is a true value, execute the suite, then skip the remaining clauses in the statement.
Evaluation rule for or expressions:
1.Evaluate the subexpression
2.If the result is a true value v, then the expression
evaluates to v.
3.Otherwise, the expression evaluates to the value of the
subexpression
Evaluation rule for and expressions:
1.Evaluate the subexpression
2.If the result is a false value v, then the expression
evaluates to v.
3.Otherwise, the expression evaluates to the value of the
subexpression
Evaluation rule for not expressions:
1.Evaluate
Execution rule for while statements:
1. Evaluate the header’s expression.
2. If it is a true value, execute the (whole) suite, then return to step 1.
B AB
A call expression and the body of the function being called are evaluated in different environments
1
A
2
1
def fib(n): hof.py
“””Compute the nth Fibonacci number, for N >= 1.”””
pred, curr = 0, 1 # Zeroth and first Fibonacci numbers
k = 1 # curr is the kth Fibonacci number return total
while k < n: pred, curr = curr, pred + curr def ikd=eknt+i1ty(k): return curr return k def cube(k): return pow(k, 3) Function of a single argument (not called term) A formal parameter that will be bound to a function def summation(n, term): """Sum the first n terms of a sequence. >>> summation(5, cube)
225
“””
total, k = 0, 1 while k <= n: The cube function is passed as an argument value total, k = total + term(k), k + 1 return total The function bound to term gets called here 0+13 +23 +33 +43 +55 def pi_term(k): return 8 / (k * 4 3) / (k * 4 1) # Local function definitions; returning functions Def statement Body “y” is not found “y” is not found Return expression Higher-order function: A function that takes a function as an argument value or returns a function as a return value Nested def statements: Functions defined within other function bodies are bound to names in the local frame def make_adder(n): CS 61A Midterm 1 Study Guide – Page 2 square = lambda x,y: x * y Evaluates to a function. square = lambda x: x * x VS def square(x): return x * x • Both create a function with the same domain, range, and behavior. • Both functions have as their parent the environment in which they were defined. • Both bind that function to the name square. • Only the def statement gives the function an intrinsic name. When a function is defined: 1. Create a function value: func
3. Bind
When a function is called:
A function
No “return” keyword!
with formal parameters x and y
that returns the value of “x * y”
Must be a single expression
def make_adder(n): A function that returns a function
“””Return a function that takes one argument k and returns k + n.
>>> add_three = make_adder(3) >>> add_three(4)
The name add_three is bound to a function
7
“””
def adder(k):
return k + n return adder
A local def statement
Can refer to names in the enclosing function
1.
2. 3. 4.
Add a local frame, titled with the
Copy the parent of the function to the local frame: [parent=