61a-mt1-study-guide.key
CS 61A Midterm 1 Study Guide – Page 1
208
mul(add(2, mul(4, 6)), add(3, 5))
add(2, mul(4, 6))
26mul
add 2
mul(4, 6)
mul 4 6
24
add(3, 5)
add 3 5
8
-2
2
-2
None
abs(number):
print(…):
display “-2”
2, 10
1024
pow(x, y):
Pure Functions
Non-Pure Functions
A name evaluates to
the value bound to
that name in the
earliest frame of
the current
environment in which
that name is found.
Defining:
Call expression:
square( x ):
return mul(x, x)
>>> def
square(2+2)
Calling/Applying: square( x ):
return mul(x, x)
Def
statement
Formal parameter
Body
Return
expression
(return statement)
operand: 2+2
argument: 4
operator: square
function: func square(x)
Intrinsic name
4
16
Argument
Return value
…
…
…
Compound statement
Suite
Clause
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.
1. Evaluate the header’s expression.
2. If it is a true value, execute the (whole) suite, then
return to step 1.
Execution rule for while statements:
Execution rule for def statements:
Execution rule for assignment statements:
Evaluation rule for call expressions:
Execution rule for conditional statements: hof.py Page 2
return total
def identity(k):
return k
def cube(k):
return pow(k, 3)
def summation(n, term):
“””Sum the first n terms of a sequence.
>>> summation(5, cube)
225
“””
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
def pi_term(k):
return 8 / (k * 4 � 3) / (k * 4 � 1)
# Local function definitions; returning functions
def make_adder(n):
"""Return a function that takes one argument k and returns k + n.
>>> add_three = make_adder(3)
>>> add_three(4)
7
“””
def adder(k):
return k + n
return adder
def compose1(f, g):
“””Return a function that composes f and g.
f, g �� functions of a single argument
“””
def h(x):
return f(g(x))
return h
@main
def run():
interact()
Function of a single
argument (not called term)
A formal parameter that
will be bound to a function
The function bound to term
gets called here
The cube function is passed
as an argument value
0 + 13 + 23 + 33 + 43 + 55
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
Evaluation rule for or expressions:
Evaluation rule for and expressions:
Evaluation rule for not expressions:
Applying user-defined functions:
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.
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.
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.
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.
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
1.Evaluate
value, and False otherwise.
A name is bound to a value
In a frame, there is at most
one binding per name
Statements and expressions
Red arrow points to next line.
Gray arrow points to the line
just executed
Frames (right):Code (left):
Import statement
Assignment statement
Name Value
Binding
Local frame
Intrinsic name of
function called
Formal parameter
bound to
argument
Return value is
not a binding!
Built-in function
User-defined
function
2
1
“y” is
not found
“y” is
not found
Error
def abs_value(x):
if x > 0:
return x
elif x == 0:
return 0
else:
return -x
1 statement,
3 clauses,
3 headers,
3 suites,
2 boolean
contexts
•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
2
1
1
2
1
B
A B
A
A call expression and the body
of the function being called
are evaluated in different
environments
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
def fib(n):
“””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
while k < n:
pred, curr = curr, pred + curr
k = k + 1
return curr
def make_adder(n):
"""Return a function that takes one argument k and returns k + n.
>>> add_three = make_adder(3)
>>> add_three(4)
7
“””
def adder(k):
return k + n
return adder
CS 61A Midterm 1 Study Guide – Page 2
A function that returns a function
A local
def statement
The name add_three is
bound to a function
Can refer to names in
the enclosing function
square = lambda x,y: x * y
that returns the value of “x * y”
with formal parameters x and y
A function
Must be a single expression
square = lambda x: x * x def square(x): return x * xVS
• 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.
•Every user-defined function has
a parent frame (often global)
•The parent of a function is the
frame in which it was defined
•Every local frame has a parent
frame (often global)
•The parent of a frame is the
parent of the function called
Evaluates to a function.
No “return” keyword!
When a function is defined:
1. Create a function value: func
2. Its parent is the current frame.
3. Bind
(which is the first frame of the current environment).
When a function is called:
1. Add a local frame, titled with the
called.
2. Copy the parent of the function to the local frame: [parent=
the local frame.
2
1
3
Nested
def
A function’s signature
has all the information
to create a local frame
Return value of make_adder is an
argument to compose1
from operator import floordiv, mod
def divide_exact(n, d):
“””Return the quotient and remainder of dividing N by D.
>>> q, r = divide_exact(2012, 10)
>>> q
201
>>> r
2
“””
return floordiv(n, d), mod(n, d)
Two return values,
separated by commas
Multiple assignment
to two names
>>> min(2, 1, 4, 3)
1
>>> max(2, 1, 4, 3)
4
>>> abs(-2)
2
>>> pow(2, 3)
8
>>> len(‘word’)
4
>>> round(1.75)
2
>>> print(1, 2)
1 2
>>> 2 + 3
5
>>> 2 * 3
6
>>> 2 ** 3
8
>>> 5 / 3
1.6666666666666667
>>> 5 // 3
1
>>> 5 % 3
2
>>> print(print(1))
1
None
def search(f):
“””Return the smallest non-negative
integer x for which f(x) is a true value.
“””
x = 0
while True:
if f(x):
return x
x += 1
def is_three(x):
“””Return whether x is three.
>>> search(is_three)
3
“””
return x == 3
def inverse(f):
“””Return a function g(y) that returns
x such that f(x) == y.
>>> sqrt = inverse(lambda x: x * x)
>>> sqrt(16)
4
“””
return lambda y: search(lambda x: f(x)==y)
Printed output:
1
4
9
from operator import add, mul
def curry2(f):
“””Curry a two-argument function.
>>> m = curry2(add)
>>> add_three = m(3)
>>> add_three(4)
7
>>> m(2)(1)
3
“””
def g(x):
def h(y):
return f(x, y)
return h
return g