CS 61A Structure and Interpretation of Computer Programs
Fall 2014
INSTRUCTIONS
Midterm 1
• You have 2 hours to complete the exam.
• The exam is closed book, closed notes, closed computer, closed calculator, except one hand-written 8.5” ⇥ 11”
crib sheet of your own creation and the o cial 61A midterm 1 study guide attached to the back of this exam.
• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide a brief explanation.
Last name
First name
SID
Login
TA & section time
Name of the person to your left
Name of the person to your right
All the work on this exam is my own. (please sign)
For sta↵ use only
Q.1 Q.2 Q.3 Q.4 Total /12 /14 /8 /6 /40
2
1. (12 points) World Cup
(a) (10 pt) For each of the expressions in the tables below, write the output displayed by the interactive Python interpreter when the expression is evaluated. The output may have multiple lines.
Whenever the interpreter would report an error, write Error. You should include any lines displayed before an error.
Reminder: the interactive interpreter displays the value of a successfully evaluated expression, unless it is None.
The first three rows have been provided as examples.
Assume that you have started Python 3 and executed the following statements:
def def
def
Expression
5*5
print(5)
1/0
square(x): return x * x
argentina(n): print(n)
if n > 0:
return lambda k: k(n+1) else:
return 1 / n
germany(n): if n > 1:
print(’hallo’)
if argentina(n-2) >= 0:
print(’bye’) return argentina(n+2)
Interactive Output
25
5 Error
Expression
Interactive Output
argentina(1)(square)
print(1, print(2))
germany(1)(square)
argentina(0)
germany(2)(germany)
(b) (2 pt) Fill in the blank with an expression so that the whole expression below evaluates to a number. Hint: The expression abs > 0 causes a TypeError.
(lambda t: argentina(t)(germany)(square))(_________________________________)
2. (14 points) Envy, Iron, Mint
(a) (6 pt) Fill in the environment diagram that results from executing the code below until the entire program is finished, an error occurs, or all frames are filled. You may not need to use all of the spaces or frames.
A complete answer will:
• Add all missing names, labels, and parent annotations to all local frames. • Add all missing values created during execution.
• Show the return value for each local frame.
3
1 2 3 4 5 6 7 8 9
10
func peace(today) [parent=Global]
func joy(peace) [parent=Global]
def peace(today):
harmony = love+2
return harmony + today(love+1)
def joy(peace):
peace, love = peace+2, peace+1
return love // harmony
!
love, harmony = 3, 2
peace(joy)
Global frame
peace
joy
love 3 harmony 2
f1: ___________ [parent=____________]
Return Value
f2: ___________ [parent=____________]
Return Value
f3: ___________ [parent=____________]
Return Value
4
(b) (8 pt) Fill in the environment diagram that results from executing the code below until the entire program is finished, an error occurs, or all frames are filled. You may not need to use all of the spaces or frames.
A complete answer will:
• Add all missing names, labels, and parent annotations to all local frames. • Add all missing values created during execution.
• Show the return value for each local frame.
Global frame
k g3 p7
1 2 3 4 5 6 7
func k(g, b) [parent=Global]
def k(g, b):
def n(s, a):
return g-p
return b(n(b, p))
g, p = 3, 7
k(p+1, lambda s: g+3)
f1: ___________ [parent=____________]
Return Value
f2: ___________ [parent=____________]
Return Value
f3: ___________ [parent=____________]
Return Value
3. (8 points) Express Yourself
(a) (3 pt) A k-bonacci sequence starts with K-1 zeros and then a one. Each subsequent element is the sum of the previous K elements. The 2-bonacci sequence is the standard Fibonacci sequence. The 3-bonacci and 4-bonacci sequences each start with the following ten elements:
n:0,1,2,3,4,5,6, 7, 8,
kbonacci(n, 2): 0, 1, 1, 2, 3, 5, 8, 13, 21,
kbonacci(n, 3): 0, 0, 1, 1, 2, 4, 7, 13, 24,
9,… 35, … 44, … 29, …
kbonacci(n, 4): 0, 0, 0, 1, 1, 2, 4, 8, 15,
Fill in the blanks of the implementation of kbonacci below, a function that takes non-negative integer n and
positive integer k and returns element n of a k-bonacci sequence. def kbonacci(n, k):
“””Return element N of a K-bonacci sequence.
>>> kbonacci(3, 4) 1
>>> kbonacci(9, 4) 29
>>> kbonacci(4, 2) 3
>>> kbonacci(8, 2) 21
“””
if n < k - 1:
return 0 elif n == k - 1: return 1
else:
total = 0
i = ___________________________________________________________________ while i < n:
total = total + ___________________________________________________
i=i+1 return total
5
6
(b) (5 pt) Fill in the blanks of the following functions defined together in the same file. Assume that all arguments to all of these functions are positive integers that do not contain any zero digits. For example, 1001 contains zero digits (not allowed), but 1221 does not (allowed). You may assume that reverse is correct when implementing remove.
def combine(left, right):
"""Return all of LEFT’s digits followed by all of RIGHT’s digits.""" factor = 1
while factor <= right:
factor = factor * 10 return left * factor + right
def reverse(n):
"""Return the digits of N in reverse.
>>> reverse (122543) 345221
“””
if n < 10: return
else: return
n
combine(__________________________ , __________________________)
def remove(n, digit):
"""Return all digits of N that are not DIGIT, for DIGIT less than 10.
>>> remove (243132 , 3) 2412
>>> remove (243132 , 2) 4313
>>> remove(remove(243132, 1), 2) 433
“””
removed = 0 while n != 0:
____________ , ____________ = ____________________ , ____________________
if ___________________________________________________________________:
removed = _________________________________________________________ return reverse(removed)
4. (6 points) Lambda at Last
(a) (2 pt) Fill in the blank below with an expression so that the second line evaluates to 2014. You may only use the names two_thousand, two, k, four, and teen and parentheses in your expression (no numbers, operators, etc.).
two_thousand = lambda two: lambda k: __________________________________________ two_thousand(7)(lambda four: lambda teen: 2000 + four + teen)
(b) (4 pt) The if_fn returns a two-argument function that can be used to select among alternatives, similar to an if statement. Fill in the return expression of factorial so that it is defined correctly for non-negative arguments. You may only use the names if_fn, condition, a, b, n, factorial, base, and recursive and parentheses in your expression (no numbers, operators, etc.).
def if_fn(condition): if condition:
return lambda a, b: a else:
return lambda a, b: b
def factorial(n):
“””ComputeN!fornon-negativeN. N!=1*2*3*…*N.
>>> factorial (3) 6
>>> factorial (5) 120
>>> factorial (0) 1
“””
def base ():
return 1
def recursive ():
return n * factorial(n-1)
return ____________________________________________________________________
7
8
Scratch Paper
Scratch Paper
9
10
Scratch Paper
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
Intrinsic name of function called
Formal parameter bound to argument
Local frame
Return value is
not a binding!
User-defined function
Built-in 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
…
…
!
2 boolean contexts
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
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
pred, curr = curr, pred + curr
k=k+1
def identity(k):
return curr return k
while k < n: 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: A function No "return" keyword! with formal parameters x and y that returns the value of "x * y" Must be a single expression Can refer to names in the enclosing function A function that returns a function def make_adder(n): """Return a function that takes one argument k and returns k + n. ! The name add_three is bound to a function 1. Create a function value: func
>>> add_three = make_adder(3)
>>> add_three(4) 7
“””
def adder(k): return k + n
return adder
A local def statement
3. Bind
(which is the first frame of the current environment).
When a function is called:
1. Add a local frame, titled with the
2. Copy the parent of the function to the local frame: [parent=