Decorators

A decorator is a feature that transforms each function call into something else. What do you think about that example?

def fibnaive(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(35)

14930352

First example: write the calls

Our goal is to write a line into the terminal at each call of the function.

Bad solution: Hack the function itself

def fibnaive(n: int) -> int:
    print("fibnaive(", n, ")")
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(5)

fibnaive( 5 )
fibnaive( 4 )
fibnaive( 3 )
fibnaive( 2 )
fibnaive( 1 )
fibnaive( 0 )
fibnaive( 1 )
fibnaive( 2 )
fibnaive( 1 )
fibnaive( 0 )
fibnaive( 3 )
fibnaive( 2 )
fibnaive( 1 )
fibnaive( 0 )
fibnaive( 1 )





8

It works but it is not reusable.

Write a higher-order function

from typing import Callable, Any

def printed(f: Callable[..., Any]) -> Callable[..., Any]:
    """
    Return a version of f that prints the calls

    Arg:
        f (Callable): a function.

    Returns:
        (Callable): the version of f that prints f(..) at each call
    """
    def printerVersion(*args: Any):
        print(f.__name__, "(", *args, ")")
        return f(*args)
    return printerVersion

def fibnaive(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)
    
fibnaive = printed(fibnaive)
fibnaive(3)

fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )





3

Writing the decorator

@printed
def fibnaive(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(3)

fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )





3

Writing a class instead of a function

class Printed:
    def __init__(self, f: Callable[..., Any]):
        self.f = f

    def __call__(self, *args: Any):
        print(self.f.__name__, "(", *args, ")")
        return self.f(*args)

@Printed
def fibnaive(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(4)

fibnaive ( 4 )
fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )





5

Second example: printing the running time

We want measure how fibnaiveis slow.

Bad solution

import time

def fibnaive(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)
    
begin = time.time()
fibnaive(30)
end = time.time()
print("Total time: ", end - begin)

Total time:  0.15117168426513672

The above code is ugly and not reusable.

Writing a function

The code below is nice because it can be reused for any function.

def timedfunction(f):
    def timedf(*args, **kwargs):
        begin = time.time()
        result = f(*args, **kwargs)
        end = time.time()
        print("Total time: ", end - begin)
        return result
    
    return timedf

fibnaive = timedfunction(fibnaive)
fibnaive(3)

Total time:  7.152557373046875e-07
Total time:  2.1457672119140625e-06
Total time:  0.0013761520385742188
Total time:  4.76837158203125e-07
Total time:  0.001458883285522461





3

Attempt to write the decorator with a function

Instead of writing timedfunction(fibnaive) which is combersome, we try to decorate the function before its definition.

@timedfunction
def fibnaive(n):
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(3)

Total time:  4.76837158203125e-07
Total time:  4.76837158203125e-07
Total time:  0.00020813941955566406
Total time:  4.76837158203125e-07
Total time:  0.0002760887145996094





3

def timedfunction(f):
        
    def timedf(*args, **kwargs):
    
        begin = time.time()
        result = f(*args, **kwargs)
        end = time.time()
        print("Total time: ", end - begin)
        return result
    
    return timedf

@timedfunction
def fibnaive(n):
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(3)

Total time:  7.152557373046875e-07
Total time:  7.152557373046875e-07
Total time:  0.00014638900756835938
Total time:  4.76837158203125e-07
Total time:  0.00020551681518554688





3

Write the decorator with a class

class Timed:
    def __init__(self, f):
        self.f = f
        self.__name__ = f.__name__
        self.inside = False

    def __call__(self, *args):
        if not self.inside:
            self.inside = True
            begin = time.time()
            result = self.f(*args)
            end = time.time()
            print("Total time: ", end - begin)
            self.inside = False
            return result
        else:
            return self.f(*args)

@Timed
def fibnaive(n):
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(32)

Total time:  1.010364294052124





3524578

Memoization

The code for computing Fibonnaci numbers with a recursive function is so beautiful…

fibnaive(12)

Total time:  0.0001595020294189453





233

… but is so slow.

Direct code for memoized Fibonacci

It consists in storing the values already computed in a hashmap.

def fibmemo(n):
    valuesAlreadyComputed = {}

    def fibrec(n):
        if n in valuesAlreadyComputed:
            return valuesAlreadyComputed[n]
        if n <= 1:
            return 1
        else:
            valuesAlreadyComputed[n] = fibrec(n-1) + fibrec(n-2)
            return valuesAlreadyComputed[n]
        
    return fibrec(n)

fibmemo(35)

14930352

The previous code is ugly. And it handles two responsabilities: to compute the Fibonacci number, and to perform memoïsation. It should be seperated…

First attempt to write a decorator with a higher-order function

def memo(f):
    valuesAlreadyComputed = {}
    def fmemo(*args):
        if args not in valuesAlreadyComputed:
            valuesAlreadyComputed[args] = f(*args)
        return valuesAlreadyComputed[args]
       
    return fmemo

def fibnaive(n):
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive = memo(fibnaive)
fibnaive(120)

8670007398507948658051921

@memo
def fibnaive(n):
    if n <= 1:
        return 1
    else:
        return fibnaive(n-1) + fibnaive(n-2)

fibnaive(120)

8670007398507948658051921

class Memoize:
    def __init__(self, f: Callable[..., Any]):
        self.f = f
        self.__name__ = f.__name__
        self.valuesAlreadyComputed: dict[Any, Any] = {}
        
    def __call__(self, *args: Any):
        if args not in self.valuesAlreadyComputed:
            self.valuesAlreadyComputed[args] = self.f(*args)
        return self.valuesAlreadyComputed[args]

@Memoize
def fib(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib(120)

8670007398507948658051921

Combining decorators

@Printed
@Timed
@Memoize
def fib(n:int) -> int:
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib(5)

fib ( 5 )
Total time:  5.0067901611328125e-06





8

Exercices

• Apply Dynamic Programming to solve Knapsack problem. Then apply memoization.
• Write factorial in imperative form, recursive form and recursive with tail recursion and compare the running time.