# 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

Lectures

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

### 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(1)
1

>>> f2(1)
2   # 1 + 1

>>> f3(3)
10  # 1 + (3**2)

>>> 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
>>> f1(3)
4
>>> f2(3) # should be 1 + (2*3) = 7
7
>>> f3(3) # should be 1 + (2 * (3 + 1)) = 9
9
"""
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 `U` and `D`s 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`.

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_paths` too early. How is a statement like `x = func` different 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
"""