ProgrammingBits

Exploring Python's awesomeness. By Ariel Ortiz.

Function Decorators

aortiz | 31 January, 2009 12:50

The Python programming language has an interesting syntactic feature called a decorator. Let's use an example in order to explain how and why you would want to use a Python decorator.

NOTE: All Python code examples presented here are based in Python 3.0. Full source code: function_decorators.py

Suppose we want to compute the Fibonacci numbers using a recursive function1. The following function definition does the trick:

1
2
3
4
5
def fib(n):
    if n in (0, 1):
        return n
    else:
        return fib(n - 1) + fib(n - 2)

We can now test the function with different input values: 

>>> fib(0)
0
>>> fib(1)
1
>>> fib(4)
3
>>> fib(10)
55
>>> fib(30)
832040
>>> fib(35)
9227465

If you've actually typed these examples in a Python shell, you've probably noticed that obtaining a result takes longer for bigger inputs. In order to make it run faster, we can use a technique called memoization. A memoized function stores in a cache the results corresponding to some set of specific inputs. Later calls, with previously computed inputs, return the results stored in the cache, thus avoiding their recalculation. This means that the primary cost of a call with certain parameters is taken care of during the first call made to the function with those same parameters.

Instead of modifiying the fib function directly, it's better to write a reusable memoizing function:

1
2
3
4
5
6
7
def memoize(f):
    cache = {}
    def helper(x):
        if x not in cache:            
            cache[x] = f(x)
        return cache[x]
    return helper

The memoize function wraps another function, called helper, which is going to provide additional functionality to the function received through parameter f. The helper function is actually a lexical closure, that is, a function object that remembers the variable bindings that were in its scope when it was created. In this case, helper remembers variables f and cache, which happen to hold a function object and a dictionary, respectively. The last statement in memoize just returns to its caller the helper lexical closure.

Type the following code, and you'll notice right away a speed increase when calling fib. The speedup can be appreciated even in the very first call because the memoization immediately boosts all the recursive calls inside fib's definition.

>>> fib = memoize(fib)
>>> fib(50)
12586269025

The assignment in the first line can be read as: the fib function is being decorated by the memoize function. Because this is such a common programming idiom in Python, there's a special decorator syntax to simplify its use. This syntax was originally inspired by Java's annotations: just above the definition of the function that is to be decorated, place an at sign (@) followed by the name of the decorator function.

In other words, this Python syntax:

1
2
3
@some_decorator
def some_function():
    # function body...

is equivalent to:

1
2
3
def some_function():
    # function body...
some_function = some_decorator(some_function)

Most should agree that the @ notation is more readable and less error prone.

In order to use the Python decorator with our Fibonacci + memoization example, we would have to rewrite as follows:

1
2
3
4
5
6
def memoize(f):
    # Same code as before...
 
@memoize 
def fib(n):
    # Same code as before...

The memoize function shows the general structure that a typical function decorator should have: it receives a function f as its input parameter, and it returns another function that attaches some additional responsibilities to f

Another interesting thing about Python decorators is that you can chain two or more together. Let's extend our example in order to incorporate a tracing decorator that will display a message before the decorated function gets called and also when it returns.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def memoize(f):
    # Same code as before...
 
def trace(f):
    def helper(x):
        call_str = "{0}({1})".format(f.__name__, x)
        print("Calling {0} ...".format(call_str))
        result = f(x)
        print("... returning from {0} = {1}".format(
              call_str, result))
        return result
    return helper
 
@memoize
@trace
def fib(n):
    # Same code as before...

Notice the use @memoize and @trace just before the definition of fib. Now, when invoking fib, first the memoize decorator gets called, then the trace decorator, and finally the original fib code. Check this example:

>>> fib(5)
Calling fib(5) ...
Calling fib(4) ...
Calling fib(3) ...
Calling fib(2) ...
Calling fib(1) ...
... returning from fib(1) = 1
Calling fib(0) ...
... returning from fib(0) = 0
... returning from fib(2) = 1
... returning from fib(3) = 2
... returning from fib(4) = 3
... returning from fib(5) = 5
5

Python has three built-in functions that are intended to be used as function decorators:

  • classmethod: used to indicate that the decorated method is a class method, similar to those in Smalltalk or Ruby.
  • staticmethod: used to indicate that the decorated method is a static method, like those in C++, C# or Java.
  • property: used to decorate methods that will be used to get, set and delete object properties. 

It's also worth noting that Python 3.0 not only allows you to decorate functions, but also complete classes. Hopefully, I'll take some time to write about these specific kinds of decorators in a a future post.

Notes

1 Yes, I know that using recursion to implement the Fibonacci sequence is very inefficient. But that was my intention. I wanted a simple algorithm that produces a perceivable time delay for certain inputs. 

Further Reading

PEP: 318 Decorators for Functions and Methods

Comments

Re: Function Decorators

aortiz | 13/02/2009, 16:36

aortiz

Hi Christo. I'm glad my post was useful. Thanks for your comment.

Excellent post.

Emilio Olivares | 01/06/2009, 00:01

Ariel, I'm from México myself. What city are you from, and what university do you teach at?

Saludos!

Re: Function Decorators

Ariel Ortiz | 01/06/2009, 00:42

aortiz

Hi Emilio. I live at Cuautitlán Izcalli. I teach at the Tecnológico de Monterrey, Campus Estado de México.

Re: Function Decorators

Rodolphe Courtier | 20/06/2009, 15:56

Thanks for writing this! I ran into decorators while learning Django and I had no idea what they were. They make way more sense now.

How is x passed to the memoize instance?

Jacq | 05/12/2010, 12:48

Thanks, great explanation of memoization, but I don't understand one thing...

In your example

>>> fib = memoize(fib)
>>> fib(50)
12586269025

how is '50' passed to 'helper'? In other words, what if the original fib() took multiple arguments and memoize() contained multiple functions (e.g. helper1, helper2...)? Would each different 'helper' function inside memoize() then be passed a complete list of all the arguments passed into the (decorated) fib()?

Re: Function Decorators

Mohammed Sami | 25/12/2010, 11:22

We can see how the original fib(x) executes, if we decorate it as:

@trace
def fib(n):
# Same code as before...

and then call fib(x).

Example:
>>>fib(5)
Calling fib(5) ...
Calling fib(4) ...
Calling fib(3) ...
Calling fib(2) ...
Calling fib(1) ...
... returning from fib(1) = 1
Calling fib(0) ...
... returning from fib(0) = 0
... returning from fib(2) = 1
Calling fib(1) ...
... returning from fib(1) = 1
... returning from fib(3) = 2
Calling fib(2) ...
Calling fib(1) ...
... returning from fib(1) = 1
Calling fib(0) ...
... returning from fib(0) = 0
... returning from fib(2) = 1
... returning from fib(4) = 3
Calling fib(3) ...
Calling fib(2) ...
Calling fib(1) ...
... returning from fib(1) = 1
Calling fib(0) ...
... returning from fib(0) = 0
... returning from fib(2) = 1
Calling fib(1) ...
... returning from fib(1) = 1
... returning from fib(3) = 2
... returning from fib(5) = 5
5

Thunks for your great post.!!

Kei | 06/05/2011, 13:44

Dear aortiz

It's a very useful and understandable.

I lived in Japanese.
I'm studying python and English now..

and I am writing to ask for your permission to translate this entry to Japanese and comment on my blog.

The blog is intended for Japanese beginner learners of python and has no commercial agenda.

I will give credit to ProgrammingBits, of course.

Sincerely,
Kei

Re: Function Decorators

Ariel Ortiz | 06/05/2011, 17:00

aortiz

Hello Kei. You may translate this or any other of my entries to Japanese. Thanks for asking.

Re: Function Decorators

Kei | 07/05/2011, 00:29

Dear aortiz

Thank you for your prompt reply and for your permission to use.

I look forward to your future posts too!

Sincerely,
Kei
http://kobito-kobito.blogspot.com/
(almost entries are Japanese.....)

Lexical Closure

Martin Smith | 18/03/2012, 12:39

Thank you for this illuminating example. It definitely carried me a step farther along.

It seems challenging to write a version of memoize that can be used for several different functions at once.

Re: Function Decorators

Asaf | 11/01/2014, 06:26

Hi

actually showing the sequence as below will be better to understand the code:

Hi

It is worth to also show sequence as
def memoize(f):
print("memo enter")
cache = {}
def helper(x):
print("memo inner enter")
if x not in cache:
cache[x] = f(x)
print("memo inner exit")
return cache[x]
print("memo exit")
return helper

def trace(f):
print("trace enter")
def helper(x):
#call_str = "{0}({1})".format(f.__name__, x)
#print("Calling {0} ...".format(call_str))
print("trace inner enter")
result = f(x)
#print("... returning from {0} = {1}".format(call_str, result))
print("trace inner exit")
return result
print("trace exit")
return helper
@memoize
@trace
def fib(n):
print("fib enter")
if n in (0, 1):
print("fib exit")
return n
else:
print("fib exit")
return fib(n - 1) + fib(n - 2)
print(fib(5))

trace enter
trace exit
memo enter
memo exit
memo inner enter
trace inner enter
fib enter
fib exit
memo inner enter
trace inner enter
fib enter
fib exit
memo inner enter
trace inner enter
fib enter
fib exit
memo inner enter
trace inner enter
fib enter
fib exit
memo inner enter
trace inner enter
fib enter
fib exit
trace inner exit
memo inner exit
memo inner enter
trace inner enter
fib enter
fib exit
trace inner exit
memo inner exit
trace inner exit
memo inner exit
memo inner enter
memo inner exit
trace inner exit
memo inner exit
memo inner enter
memo inner exit
trace inner exit
memo inner exit
memo inner enter
memo inner exit
trace inner exit
memo inner exit
5

Add comment

authimage

 
Accessible and Valid XHTML 1.0 Strict and CSS
Powered by LT - Design by BalearWeb