This is a study guide with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.
What is Self-Reference?
The definition of self-reference is in the name: a self-referencing function will return some version of itself.
Let’s take a look at the simplest possible version of a self-referencing function:
def f(): print("Hello World!") return f
Not a super exciting function, right? But what's special about this function is that you can change infinite calls to it:
>>> f = f()()()() Hello World! Hello World! Hello World! Hello World!
Why is this possible? Let's take a look at the environment diagram:
f is a function that, when called, will :
2) return another function that will:
1) print `"Hello World!"` when called 2) return another function that will ...
and so on.
Self-Reference and Memory
Why is Self-Reference useful? Recall your commentary functions in the Hog project. These were prime examples of self-reference!
For example, the commentary function that
announce_highest returned, when called, would print something out if a new highest score was rolled, and would return a new commentary function that would now somehow remember the new highest scores.
Here's another example:
def print_highest(n=0): def next_number(x): if x > n: print(x) return print_highest(x) else: return print_highest(n) return next_number
Here's a sample doctest:
f = print_highest()(1)(5)(2)(7)(0) 1 5 7
A call to
print_highest will return a function that takes in a number and prints it out if that number is the highest number it's ever seen before. In this case, it will print out 1 (the first number it sees), 5 (because it's larger than 1), and 7 (because it's larger than the previous maximum of 5). This might look similar to some code in Hog!
Take a second to think about why we need to have a nested function at all here. Why can't we implement the logic of the whole function just in
print_highest without the inner function?
Here we see the beauty of self-reference: our function can remember what the previous highest number it has seen is, because we're storing that value in the parameter of the parent function
print_highest. It might become apparent what's going on internally with an environment diagram:
There's a lot of frames here, but notice how the frames are mostly alternating between a
print_highest frame and a
next_number frame. This alternating pattern shows the inter-dependency between these two functions. In particular,
next_number will return a call to
print_highest, which will, in turn, return a new version of
next_number. What's special is that the call to
print_highest controls what the function "remembers" as the new highest number so far, by passing that as parameter
n into the call to
Here's a general structure for how a lot of more complicated self-reference problems end up looking:
def outer_function(some_parameters): def inner_function(params): # do some stuff here return outer_function(some_new_parameters) return inner_function
Take a few moments to see how this structure applies to your hog code, along with
print_highest and any examples you've seen in lecture or discussion.
Write a function
typewriter, which takes a
word and prints out the
word, then returns a one-argument function which will take in another string. This function, when called, will
print out all the strings it has seen before, concatenated, and then return a function with the same behavior.
>>> f = typewriter('CS')('61')('A') CS CS61 CS61A >>> f = f(' rocks!') CS61A rocks!
See doctests for more detail and examples.
def typewriter(word): """A function that keeps track of a word as it's being typed." >>> t = typewriter("he") he >>> t = t("llo") hello >>> t = t(" w") hello w >>> t = t("orld!") hello world! """ def typing(next_str):___________________________new_word = word + next_str___________________________return typewriter(new_word)____________________print(word)return ____________________return typing
Q2: Protected Secret
Write a function
protected_secret which takes in a
protected_secret should return another function which
takes in a password and prints
secret if the password entered matches the
password given as an argument to
protected_secret. Otherwise, the returned
function should print "INCORRECT PASSWORD". After
passwords are used, the secret is locked forever and the function should
print "SECRET LOCKED".
>>> my_secret = protected_secret("oski2021", "The view from the top of the Campanile.", 1) >>> my_secret = my_secret("oski2021") The view from the top of the Campanile. >>> my_secret = my_secret("goBears!") INCORRECT PASSWORD # 0 Attempts left >>> my_secret = my_secret("zoomUniversity") SECRET LOCKED
See the doctests for a detailed example.
def protected_secret(password, secret, num_attempts): """ Returns a function which takes in a password and prints the SECRET if the password entered matches the PASSWORD given to protected_secret. Otherwise it prints "INCORRECT PASSWORD". After NUM_ATTEMPTS incorrect passwords are entered, the secret is locked and the function should print "SECRET LOCKED". >>> my_secret = protected_secret("correcthorsebatterystaple", "I love UCB", 2) >>> my_secret = my_secret("hax0r_1") # 2 attempts left INCORRECT PASSWORD >>> my_secret = my_secret("correcthorsebatterystaple") I love UCB >>> my_secret = my_secret("hax0r_2") # 1 attempt left INCORRECT PASSWORD >>> my_secret = my_secret("hax0r_3") # No attempts left SECRET LOCKED >>> my_secret = my_secret("correcthorsebatterystaple") SECRET LOCKED """ def get_secret(password_attempt): # BEGIN SOLUTION if num_attempts <= 0: print("SECRET LOCKED") return protected_secret(password, secret, num_attempts - 1) elif password_attempt == password: print(secret) return protected_secret(password, secret, num_attempts) else: print("INCORRECT PASSWORD") return protected_secret(password, secret, num_attempts - 1) # END SOLUTION return get_secret
Write a higher-order function
composer that returns two functions,
func is a one-argument function that applies all of the functions that have been composed so far to it. The functions are applied with the most recent function being applied first (see doctests and examples).
func_adder is used to add more functions to our composition, and when called on another function
func_adder should return a new
func, and a new
If no parameters are passed into
func returned is the identity function.
>>> add_one = lambda x: x + 1 >>> square = lambda x: x * x >>> times_two = lambda x: x + x >>> f1, func_adder = composer() >>> f1(1) 1 >>> f2, func_adder = func_adder(add_one) >>> f2(1) 2 # 1 + 1 >>> f3, func_adder = func_adder(square) >>> f3(3) 10 # 1 + (3**2) >>> f4, func_adder = func_adder(times_two) >>> f4(3) 37 # 1 + ((2 * 3) **2)
func_addershould return two arguments
func_adder. What function do we know that returns
def composer(func=lambda x: x): """ Returns two functions - one holding the composed function so far, and another that can create further composed problems. >>> add_one = lambda x: x + 1 >>> mul_two = lambda x: x * 2 >>> f, func_adder = composer() >>> f1, func_adder = func_adder(add_one) >>> f1(3) 4 >>> f2, func_adder = func_adder(mul_two) >>> f2(3) # should be 1 + (2*3) = 7 7 >>> f3, func_adder = func_adder(add_one) >>> f3(3) # should be 1 + (2 * (3 + 1)) = 9 9 """ def func_adder(g):"*** YOUR CODE HERE ***"return composer(lambda x: func(g(x)))return func, func_adder
Q4: Both Paths
Let a path be some sequence of directions, starting with
S for start, and followed by a sequence of
up and down directions along the path. For example, the path
SUDDDUUU represents the path
Your task is to implement the function
both_paths, which prints out the path so far (at first just
S), and then returns two functions, each of which keeps track of a branch down or up. This is probably easiest to understand with an example, which can be found in the doctest of
both_paths as seen below.
Note about default arguments: Python allows certain arguments to be given default values. For example, the function
def root(x, degree=2): return x ** (1 / degree)
can be called either with or without the
degreeargument, since it has a default value of 2. For example
>>> root(64) 8 >>> root(64, 3) 4
In the given skeleton, we give the default argument
Hint: you can return multiple things from a function
>>> def func(x): ... return x * 2, x * 4 >>> x, y = func(5) >>> print(x, y) 10 20
Another hint: if you get a
RecursionError, you probably accidentally called
both_pathstoo early. How is a statement like
x = funcdifferent from another statement like
x = func(5)?
def both_paths(sofar="S"): """ >>> up, down = both_paths() S >>> upup, updown = up() SU >>> downup, downdown = down() SD >>> _ = upup() SUU """"*** YOUR CODE HERE ***"print(sofar) def up(): return both_paths(sofar + "U") def down(): return both_paths(sofar + "D") return up, down