Python Function Tracing

To make the process of recursion more visible, this example is given:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

def trace(f):
    f.indent = 0
    def g(x):
        print('|  ' * f.indent + '|--', f.__name__, x)
        f.indent += 1
        value = f(x)
        print('|  ' * f.indent + '|--',开发者_运维问答 'return', repr(value))
        f.indent -= 1
        return value
    return g


fib = trace(fib)
print(fib(4))

I can understand "what" the trace function does, but I don't understand "how". Specifically:

1) Why do we have f.indent instead of, say, simple indent = 0 (well, I see that that doesn't work, but I don't see why).

2) I don't understand how

print('|  ' * f.indent + '|--', 'return', repr(value))

is not executed until a value is found.

Would somebody be kind enough to explain the whole thing thoroughly?

Whew. All right, here we go!

First, you have a function, any function. In your case, that's fib(). Now, in python, functions are also objects, and they can be created in runtime, so we can actually do this:

def give_me_a_function():
    def f(x):
        return x

    return f

(Warning: horrible repetition of the word 'function' for the rest of this answer).

Well, we defined a function that takes no arguments and returns,... another function? That's right! Functions are objects! You can create them in runtime! So we defined a second function inside our original one, and returned it, as we would any other object.

Now, let's do something a tad more complicated:

def alter(other_function):
    def altered(x):
        return other_function(x) + 1

    return altered

What the hell was that?

Well, we defined a function, alter(). Just as in the example above, it creates a function in run-time and returns it, as the object it is. That much we already covered.

Now, if functions are objects, and can be created and returned, why wouldn't you be able to pass one as argument? And call it, while it you're at it! That's right: alter() takes a function as argument(*), and uses it.

All it takes to have alter() is combining the above magic with this new magic: we receive a function as an argument, create another one on the fly that makes use of it, and return this new function-object!

Let's try it.

>>> def f(x):
...     return 2*x
>>> new_function = alter(f)
>>> f(2)
4
>>> new_function(2)
5

There it goes! alter() takes my f(), creates a new function that will return f() + 1, and gives that to me as a return value. I assign it to new_function, and I have a new, home-brewed, run-time created function.

(I did warn you about the use of the word 'function', did I not?)

Now, to your piece of code. You're doing something more complicated than just f() + 1. Or not? Well, you're creating a new function that takes the original one, calls it, and prints some data. That's not much more magical than what we just did. Where's the big difference?

Well, there is one detail: fib() is recursive, so it calls itself, right? Nope! Not itself. It calls fib(), and you happened to do this:

fib = trace(fib)

WHAM. fib() is not itself anymore! Now fib() is trace(fib)! So when fib() goes into recursion, it's not calling itself, it's calling the wrapped version of itself we created.

That's why the indentation is handled like that. Look at trace() again, now knowing it's actually recursively indenting, and it makes sense, doesn't it? You want to have one indentation per level of recursion, so increment it, call fib() (which, remember, is now trace(fib)), and then when we're back (so the recursion went and came, and we're about to return to a previous step in the calling chain) we decrement it.

If you still don't see it, try moving all the functionality to fib(). Forget about the decorating function, that's plain confusing.

Ah. I really hope this helps, and that the 2.000 guys that beat me to the answer didn't already make this question obsolete.

Cheers!

(*) Yeah yeah duck typing yadda yadda callable objects bla bla irrelevant.

1. If we would just use indent instead of f.indent, it would become a local variable inside the inner function g(), due to the assignments to indent in g(). Since this seems to be Python 3, it is actually not necessary to use a function attribute -- you could also use the nonlocal keyword:

   def trace(f):
       indent = 0
       def g(x):
           nonlocal indent
           print('|  ' * indent + '|--', f.__name__, x)
           indent += 1
           value = f(x)
           print('|  ' * indent + '|--', 'return', repr(value))
           indent -= 1
           return value
       return g
   

2. The second print() call won't be reached before at least one invocation of f() has returned. It appears in the code after the call to f(), so the flow of execution will only get there after f() has returned.

If you would store the indent level just in indent, it would be local to the current function call. Each time the function is called, you would get a new variable, with the value 0. By storing it in the function object, it will be the same for each function call (function are objects too in python).

For the second part, I'm not really sure what you are asking. Whenever the argument is greater then 1, two new calls to fib are made, and thus, no value is returned. Until the argument equals 1 or 0, a return call is made.