Study Guide: Self-Reference

Instructions

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.

Handouts

• Discussion 2 (Solutions)

Lectures

• Environments

Guides

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:

In words, f is a function that, when called, will : 1) print "Hello World!" 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

What does print_highest do?

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 print_highest.

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.

Practice Problems

Easy

Q1: Typewriter

Write a function typewriter, which takes a string 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.

For example,

>>> 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

Toggle Solution

Q2: Protected Secret

Write a function protected_secret which takes in a password, secret, and num_attempts.

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 num_attempts incorrect passwords are used, the secret is locked forever and the function should print "SECRET LOCKED".

For example:

>>> 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.

Run in 61A Code

Medium

Q3: Compose

Write a higher-order function composer that returns two functions, func and func_adder. 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 g, func_adder should return a new func, and a new func_adder.

If no parameters are passed into composer, the func returned is the identity function.

For example:

>>> 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)

Hint: Your func_adder should return two arguments func and func_adder. What function do we know that returns func and func_adder?

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

Toggle Solution

Q4: Both Paths

Let a path be some sequence of directions, starting with S for start, and followed by a sequence of U and Ds representing up and down directions along the path. For example, the path SUDDDUUU represents the path up, down, down, down, up, up, up.

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 degree argument, 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 sofar.

Hints

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

Toggle Solution