Generator and Decorator

from __init__ import install_dependencies

await install_dependencies()

Generator¶

Recall the implementation of Fibonacci numbers using an interation:

def fibonacci_iteration(n):
    if n > 1:
        _, F = 0, 1  # next two Fibonacci numbers
        while n > 1:
            _, F, n = F, F + _, n - 1
        return F
    elif n == 1:
        return 1
    else:
        return 0


fibonacci_iteration(10)

The code can be modified to generate a Fibonacci sequence efficiently:

%%optlite -l -h 1000
def create_fibonacci(Fn, Fnn):
    def next():
        """Returns the next (generalized) Fibonacci number starting with
        Fn and Fnn as the first two numbers."""
        nonlocal Fn, Fnn, n
        value = Fn
        Fn, Fnn, n = Fnn, Fn + Fnn, n + 1
        return value

    def self():  # make the return object callable to replace print_fibonacci_state
        print(
            """States:
        Next Fibonacci number      = {}
        Next next Fibonacci number = {}
        Next order                 = {}""".format(
                Fn, Fnn, n
            )
        )

    n = 0

    self.next = next  # add next as an attribute of self
    return self       # to be returned


fib = create_fibonacci(0, 1)
n = 0
while n < 5:
    print(fib.next())
    n += 1
fib()

# For loop fails. Why?
fib = create_fibonacci(0, 1)
for i in fib:
    print(i)

Unfortunately, the Fibonacci object is not an iterable so one cannot directly iterate over it using a for loop. It is also cubersome to have to write nested functions.

Python provides an easy way to create an iterator that generates a sequence of objects:

fibonacci_generator = (fibonacci_iteration(n) for n in range(3))
fibonacci_generator

The above uses a generator expression to define the generator object fibonacci_generator.

Since a generator is an iterator, we can use the next function to obtain the next item.

fibonacci_generator = (fibonacci_iteration(n) for n in range(3))

while True:
    print(next(fibonacci_generator))  # raises StopIterationException eventually

We can also use a for loop to handle the exception:

fibonacci_generator = (fibonacci_iteration(n) for n in range(5))

for fib in fibonacci_generator:  # StopIterationException handled by for loop
    print(fib)

The implementation of fibonacci_generator is not efficient because of redundant computations. In order to store the last two computed Fibonacci numbers, a better way to is create local states like defining a function. This can be done using the keyword yield:

%%optlite -h 450
def fibonacci_sequence(Fn, Fnn, stop):
    """Return a generator that generates Fibonacci numbers
    starting from Fn and Fnn until stop (exclusive)."""
    while Fn < stop:
        yield Fn  # return Fn and pause execution
        Fn, Fnn = Fnn, Fnn + Fn


for fib in fibonacci_sequence(0, 1, 5):
    print(fib)

def f():
    return 0
    yield 1


for i in f():
    print(i)

Solution to Exercise 1

The above prints nothing because return 0 terminates the execution, leading to a StopIteration exception when the for loop tries to get the first element.

def fibonacci_sequence(Fn, Fnn, stop):
    ### BEGIN SOLUTION
    """Return a generator that generates Fibonacci numbers
    starting from Fn and Fnn to stop (exclusive).
    generator.send(value) sets and returns the next number."""
    ### END SOLUTION
    while Fn < stop:
        value = yield Fn
        if value is not None:
            Fnn = value  # set next number to the value of yield expression
        Fn, Fnn = Fnn, Fnn + Fn


fibonacci_generator = fibonacci_sequence(0, 1, 5)
print(next(fibonacci_generator))
print(fibonacci_generator.send(2))
for fib in fibonacci_generator:
    print(fib)

Optional Arguments¶

Fibonacci sequence normally starts with 0 and 1 by default. Is it possible to make arguments Fn and Fnn optional with default values?

How to give arguments default values?

def fibonacci_sequence(Fn=0, Fnn=1, *, stop=None):
    while stop is None or Fn < stop:
        value = yield Fn
        Fn, Fnn = Fnn, Fnn + Fn

Arguments with default values specified by =... are called default arguments. They are optional in the function call.

for fib in fibonacci_sequence(stop=5):
    print(fib)  # with default Fn=0, Fnn=1

stop=5 in the function call is called a keyword argument. As supposed to positional arguments, it specifies the name of the argument explicitly. Indeed, stop is a keyword-only argument, which can not be specified as a positional argument:

for fib in fibonacci_sequence(0, 1, 5):
    print(fib)

for fib in fibonacci_sequence(5):
    print(fib)
    if fib > 10:
        break  # Will this be executed?

Solution to Exercise 3

With fibonacci_sequence(5), Fn=5 while Fnn=1 and stop=None by default. The while loop in the definition of fibonacci_sequence becomes an infinite loop. The generator keeps generating the next Fibonacci number without raising a StopIteration exception, and so the for loop will be an infinite loop unless it is terminated by the break statement.

E.g., the following results in an error:

fibonacci_sequence(stop=10, 1)

fibonacci_sequence(1, Fn=1)

The following shows that the behavior of range is different.

for count in range(1, 10, 2):
    print(count, end=" ")  # counts from 1 to 10 in steps of 2
print()
for count in range(1, 10):
    print(count, end=" ")  # default step=1
print()
for count in range(10):
    print(count, end=" ")  # default start=0, step=1
range(stop=10)  # fails

range takes only positional arguments.
However, the first positional argument has different intepretations (start or stop) depending on the number of arguments (2 or 1).

range is indeed NOT a generator. How is range implemented?

print(type(range), type(range(10)))

Variable number of arguments¶

The implementation of range uses a variable number of arguments.

def print_arguments(*args, **kwargs):
    """Take any number of arguments and prints them"""
    print("args ({}): {}".format(type(args), args))
    print("kwargs ({}): {}".format(type(kwargs), kwargs))


print_arguments(0, 10, 2, start=1, stop=2)

args is a tuple of positional arguments.
kwargs is a dictionary of keyword arguments, which is a list of values indexed by unique keys that are not necessary integers.

d = {'start': 1, 'stop': 2}
d['start'], d['stop'], d.keys(), d.values(), d.items()

* and ** are unpacking operators for tuple/list and dictionary respectively:

args = (0, 10, 2)
kwargs = {"start": 1, "stop": 2}
print_arguments(*args, **kwargs)

The following function converts all the arguments to a string, which will be useful later on.

def argument_string(*args, **kwargs):
    """Return the string representation of the list of arguments."""
    return "({})".format(
        ', '.join(
            [
                *[f'{v!r}' for v in args],  # arguments
                *[
                    f'{k}={v!r}' for k, v in kwargs.items()
                ],  # keyword arguments
            ]
        )
    )


argument_string(0, 10, 2, start=1, stop=2)

repr?
print(repr('a'))
repr('a')

def fibonacci_sequence(*args):
    """Return a generator that generates Fibonacci numbers
    starting from Fn and Fnn to stop (exclusive).
    generator.send(value) sets next number to value.

    fibonacci_sequence(stop)
    fibonacci_sequence(Fn,Fnn)
    fibonacci_sequence(Fn,Fnn,stop)
    """
    Fn, Fnn, stop = 0, 1, None  # default values

    # handle different number of arguments
    if len(args) == 1:
        ### BEGIN SOLUTION
        stop = args[0]
        ### END SOLUTION
    elif len(args) == 2:
        Fn, Fnn = args[0], args[1]
    elif len(args) > 2:
        Fn, Fnn, stop = args[0], args[1], args[2]

    while stop is None or Fn < stop:
        value = yield Fn
        if value is not None:
            Fnn = value  # set next number to the value of yield expression
        Fn, Fnn = Fnn, Fnn + Fn

for fib in fibonacci_sequence(5):  # default Fn=0, Fn=1
    print(fib)

for fib in fibonacci_sequence(1, 2):  # default stop=None
    print(fib)
    if fib > 5:
        break

args = (1, 2, 5)
for fib in fibonacci_sequence(*args):  # default stop=None
    print(fib)

Decorator¶

The code below decorates the fibonacci function by printing each recursive call and the depth of the call stack.

def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    global count, depth
    count += 1
    depth += 1
    print("{:>3}: {}fibonacci({!r})".format(count, "|" * depth, n))

    value = fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0

    depth -= 1
    if depth == -1:  # recursion done
        print("Done")
        count = 0  # reset count for subsequent recursions
    return value


count, depth = 0, -1
for n in range(6):
    print(fibonacci(n))

The decoration is useful in showing the efficiency of the function, but it rewrites the function definition.

How to decorate a function without changing its implementation?

Decorations are often temporary. Is it possible to avoid

going through the source codes to remove decorations?
switching back and forth between the original and decorated codes?

def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0


def fibonacci_decorated(n):
    """Returns the Fibonacci number of order n."""
    global count, depth
    count += 1
    depth += 1
    print("{:>3}: {}fibonacci({!r})".format(count, "|" * depth, n))

    value = fibonacci(n)

    depth -= 1
    if depth == -1:  # recursion done
        print("Done")
        count = 0  # reset count for subsequent recursions
    return value


count, depth = 0, -1
for n in range(6):
    print(fibonacci_decorated(n))

Solution to Exercise 5

The recursive calls to fibonacci does not print the function calls, because fibonacci does not call fibonacci_decorated.

Solution to Exercise 6

The call leads to an infinite recursion. The desired recursion fibonacci points to originally is no longer invoked.

An elegant solution is to

capture the function to be decorated in the closure of the decorated function, and
rename the decorated function to the same name as the function to be decorated.

def print_function_call(f):
    def wrapper(*args, **kwargs):
        nonlocal count, depth
        count += 1
        depth += 1
        call = f"{f.__name__}{argument_string(*args, **kwargs)}"
        print(f"{count:>3}:{'|' * depth}{call}")
        value = f(*args, **kwargs)  # calls f
        depth -= 1
        if depth == -1:
            print("Done")
            count = 0
        return value

    count, depth = 0, -1
    return wrapper  # return the decorated function

The above defines a decorator print_function_call that takes in a function f to be decorated and returns the decorated function wrapper that captures and decorates f:

wrapper expects the same set of arguments for f,
returns the same value returned by f on the arguments, but
can execute additional codes before and after calling f to print the function call.

By redefining fibonacci as the returned wrapper, the original fibonacci captured by wrapper calls wrapper as desired.

def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0


fibonacci = print_function_call(fibonacci)  # so original fibonnacci calls wrapper
fibonacci(5)

The redefinition does not change the original fibonacci captured by wrapper.

import inspect

for cell in fibonacci.__closure__:
    if callable(cell.cell_contents):
        print(inspect.getsource(cell.cell_contents))

Python provides the syntactic sugar below to simplify the redefinition.

@print_function_call
def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0


fibonacci(5)

Solution to Exercise 7

To decorate any function with possibly different number of arguments.

%%ai chatgpt -f text
Explain in one paragraph what software design pattern is and why decorator is considered a design pattern but generator is not.

Examples of Decorators¶

Note that the decorated fibonacci does not have the correct docstring. Even the function name is wrong.

help(fibonacci)

This can be fixed using decorator @functools.wraps:

import functools

def print_function_call(f):
    @functools.wraps(f)  # give wrapper the identity of f and more
    def wrapper(*args, **kwargs):
        nonlocal count, depth
        count += 1
        depth += 1
        call = "{}{}".format(f.__name__, "({})".format(", ".join([*(f"{v!r}" for v in args), *(f"{k}={v!r}" for k, v in kwargs.items())])))
        print(f"{count:>3}:{'|' * depth}{call}")
        value = f(*args, **kwargs)  # calls f
        depth -= 1
        if depth == -1:
            print("Done")
            count = 0
        return value

    count, depth = 0, -1
    return wrapper  # return the decorated function

@print_function_call
def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0

fibonacci(5)
help(fibonacci)

We can also undo the decoration using __wrapped__.

fibonacci, fibonacci_decorated = fibonacci.__wrapped__, fibonacci  # recover
print("original fibonacci:")
print(fibonacci(5))

fibonacci = fibonacci_decorated  # decorate
print("decorated fibonacci:")
print(fibonacci(5))

Another application is to use decorator to improve recursions. For instance, we can make recursion more efficient by caching the return values.

def caching(f):
    """Cache the return value of a function that takes a single argument.

    Parameters
    ----------
    f: Callable
        A function that takes a single argument.

    Returns
    -------
    Callable:
        The function same as f but has its return valued automatically cached
        when called. It has a method cache_clear to clear its cache.
    """

    @functools.wraps(f)
    def wrapper(n):
        if n not in cache:
            cache[n] = f(n)
        else:
            print("read from cache")
        return cache[n]

    cache = {}
    wrapper.cache_clear = lambda: cache.clear()  # add method to clear cache
    return wrapper


@print_function_call
@caching
def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0

fibonacci(5)
fibonacci(5)
fibonacci.cache_clear()
fibonacci(5)

cache is a dictionary, which will be formally introduced later in the course. For now, think of cache[n] as a variable that stores the computed value of F_n to avoid redundant calculations. If you are curious about why a dictionary is used, consider exploring the following question:

%%ai chatgpt -f text
Explain in one paragraph why one would use a Python dictionary instead of a list to store values with integer keys.

functools also provides a similar decorator called lru_cache, which can be applied to functions with multiple input arguments. It also allows you to specify a maximum cache size with a default value of 128. This means that the least recently used (lru) items are automatically removed from the cache when the cache size reaches its limit.

@print_function_call
@functools.lru_cache
def fibonacci(n):
    """Returns the Fibonacci number of order n."""
    return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1 else 0

fibonacci(5)
fibonacci(5)

To clear the cache, we can use the cache_clear method added by @functools.lru_cache:

fibonacci.__wrapped__.cache_clear()
fibonacci(5)

Note that fibonacci.cache_clear() results in an error unless we call update_wrapper first as follows. (Why?)

functools.update_wrapper(fibonacci, fibonacci.__wrapped__, assigned=('cache_clear',))
fibonacci.cache_clear()
fibonacci(5)

%%ai chatgpt -f text
Explain in one paragraph what LRU means in caching and why a strategy like LRU is used.

Writing a Module¶

How to create a module?

To create a module, simply put the code in a python source file <module name>.py in

the current directory, or
a python site-packages directory in system path.

import sys

print(sys.path)

For example, recurtools.py in the current directory defines the module recurtools.

from IPython.display import Code

Code(filename="recurtools.py", language="python")

The module provides the decorators print_function_call and caching defined earlier.

import recurtools as rc


@rc.print_function_call
@rc.caching
def factorial(n):
    return factorial(n - 1) if n > 1 else 1

factorial(5)
factorial(5)
factorial.cache_clear()
factorial(5)

In Python, large modules often consist of many submodules, which can themselves contain further submodules. To manage this complexity, Python uses packages. A package is essentially a directory that contains an __init__.py file, which serves to initialize the package. For instance, if we go up one directory level, Lecture6 becomes a package on the search path that contains the recurtools as a submodule:

%%bash
cd .. && python -c 'from Lecture6.recurtools import *; help(print_function_call)'

A submodule can import another submodule relatively. It can also run as a script.

Code(filename="demo.py", language="python")

%%bash
cd .. && python -m 'Lecture6.demo'

%%ai chatgpt -f text
How to use Sphinx and its AutoDoc extension to create a user manual for a package?