Generator and Decorator

Abstract¶

This notebook delves deeper into functional programming techniques, covering the syntax for generators and the design patterns for decorators. Along the way, readers will also explore how to specify positional and keyword arguments in function definitions, as well as how to use default arguments and handle variable numbers of arguments. Finally, we’ll demonstrate how to organize various functions into a module or a package containing multiple submodules.

from recurtools import *

Generator¶

Recall the implementation of Fibonacci numbers using an iteration:

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)

55

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

%%pytutor
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 cumbersome 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

<generator object <genexpr> at 0x74abac5660a0>

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.

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

while True:
    print(next(fibonacci_generator))  # raises StopIteration exception eventually

We can use a for loop to handle the exception:

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

for fib in fibonacci_generator:  # StopIteration exception 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 is to create local states like defining a function. This can be done using the keyword yield:

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

Solution to Exercise 3 #

A Fibonacci generator using yield produces values lazily:

def fib_up_to(limit):
    a, b = 0, 1
    while a <= limit:
        yield a
        a, b = b, a + b

Memory efficiency: The generator yields one value at a time, using O(1) memory, compared to a list-based approach that stores all values up to the limit in memory (O(n) space).
The AI should demonstrate the generator with a loop: for f in fib_up_to(100): print(f).
Compare with [f for f in fib_up_to(100)] which materializes the generator into a list, losing the memory benefit.

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

Parameters with default values specified by =... are called default parameters. 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 a keyword argument. As opposed to positional arguments, it specifies the name of the parameter explicitly. Indeed, stop is a keyword-only parameter, which can not be specified as a positional argument:

%%pytutor
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 4

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:

%%pytutor
fibonacci_sequence(stop=10, 1)

%%pytutor
fibonacci_sequence(1, Fn=1)

The following shows that the behavior of range is different.

%%pytutor
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 interpretations (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)))

<class 'type'> <class 'range'>

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 (<class 'tuple'>): (0, 10, 2)
kwargs (<class 'dict'>): {'start': 1, 'stop': 2}

args is a tuple of positional arguments.
kwargs is a dictionary of keyword arguments, which is a mapping of key-value pairs where keys are strings.

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

(1,
 2,
 dict_keys(['start', 'stop']),
 dict_values([1, 2]),
 dict_items([('start', 1), ('stop', 2)]))

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

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

args (<class 'tuple'>): (0, 10, 2)
kwargs (<class 'dict'>): {'start': 1, 'stop': 2}

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)

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

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

'a'

"'a'"

Signature: repr(obj, /)
Docstring:
Return the canonical string representation of the object.

For many object types, including most builtins, eval(repr(obj)) == obj.
Type:      builtin_function_or_method

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, Fnn=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)

1
2
3

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

  1: fibonacci(0)
Done
0
  1: fibonacci(1)
Done
1
  1: fibonacci(2)
  2: |fibonacci(1)
  3: |fibonacci(0)
Done
1
  1: fibonacci(3)
  2: |fibonacci(2)
  3: ||fibonacci(1)
  4: ||fibonacci(0)
  5: |fibonacci(1)
Done
2
  1: fibonacci(4)
  2: |fibonacci(3)
  3: ||fibonacci(2)
  4: |||fibonacci(1)
  5: |||fibonacci(0)
  6: ||fibonacci(1)
  7: |fibonacci(2)
  8: ||fibonacci(1)
  9: ||fibonacci(0)
Done
3
  1: fibonacci(5)
  2: |fibonacci(4)
  3: ||fibonacci(3)
  4: |||fibonacci(2)
  5: ||||fibonacci(1)
  6: ||||fibonacci(0)
  7: |||fibonacci(1)
  8: ||fibonacci(2)
  9: |||fibonacci(1)
 10: |||fibonacci(0)
 11: |fibonacci(3)
 12: ||fibonacci(2)
 13: |||fibonacci(1)
 14: |||fibonacci(0)
 15: ||fibonacci(1)
Done
5

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

  1: fibonacci(0)
Done
0
  1: fibonacci(1)
Done
1
  1: fibonacci(2)
Done
1
  1: fibonacci(3)
Done
2
  1: fibonacci(4)
Done
3
  1: fibonacci(5)
Done
5

Solution to Exercise 6

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

Solution to Exercise 7

The call leads to an infinite recursion. The original function that fibonacci pointed to 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.

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

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 fibonacci calls wrapper
fibonacci(5)

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.

%%pytutor
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 fibonacci 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))

---------------------------------------------------------------------------
OSError                                   Traceback (most recent call last)
Cell In[62], line 5
      1 import inspect
      2 
      3 for cell in fibonacci.__closure__:
      4     if callable(cell.cell_contents):
----> 5         print(inspect.getsource(cell.cell_contents))

File /opt/conda/lib/python3.14/inspect.py:1166, in getsource(object)
   1160 def getsource(object):
   1161     """Return the text of the source code for an object.
   1162 
   1163     The argument may be a module, class, method, function, traceback, frame,
   1164     or code object.  The source code is returned as a single string.  An
   1165     OSError is raised if the source code cannot be retrieved."""
-> 1166     lines, lnum = getsourcelines(object)
   1167     return ''.join(lines)

File /opt/conda/lib/python3.14/inspect.py:1148, in getsourcelines(object)
   1140 """Return a list of source lines and starting line number for an object.
   1141 
   1142 The argument may be a module, class, method, function, traceback, frame,
   (...)   1145 original source file the first line of code was found.  An OSError is
   1146 raised if the source code cannot be retrieved."""
   1147 object = unwrap(object)
-> 1148 lines, lnum = findsource(object)
   1150 if istraceback(object):
   1151     object = object.tb_frame

File /opt/conda/lib/python3.14/inspect.py:983, in findsource(object)
    981     lines = linecache.getlines(file)
    982 if not lines:
--> 983     raise OSError('could not get source code')
    985 if ismodule(object):
    986     return lines, 0

OSError: could not get source code

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 8

To decorate any function with possibly different number of arguments.

%%hermes
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 value 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:

%%hermes
Explain in one paragraph why one would use a Python dictionary instead of a
list to store values with integer keys.

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'