How does python implement lookups for mutually recursive function calls?

Question

Suppose I have two functions one after another in the same python file:

def A(n):
    B(n-1)
# if I add A(1) here, it gives me an error
def B(n):
    if n <= 0:
        return
    else:
        A(n-1)

When the interpreter is reading A, B is not yet defined, however this code does not give me an error. This confuses me, because I thought that Python programs are interpreted line by line. How come the attempt to call B within A doesn't give an error immediately, before anything is called?

My understanding is that, when def is interpreted, Python adds an entry to some local name space locals() with {"function name": function address}, but as for the function body, it only does a syntax check:

def A():
    # this will give an error as it isn't a valid expression
    syntax error

def B():
    # even though x is not defined, this does not give an error
    print(x)
    # same as above, NameError is only detected during runtime
    A()

Do I have it right?

Frit

A SyntaxError will be caught at compile time, but most other errors (NameError, ValueError, etc.) will be caught only at runtime, and then only if that function is called. – Edmea

easy enough to check isn't it? def f(): sytax error does product an error... – Champac

See also: stackoverflow.com/questions/1590608 or stackoverflow.com/questions/3754240 or stackoverflow.com/questions/758188. – Hounding

Answer 1

A SyntaxError will be caught at compile time, but most other errors (NameError, ValueError, etc.) will be caught only at runtime, and then only if that function is called.

"if I have written a function, if its not called in my test.." - and that is why you should test everything.

Some IDEs will raise warnings in various situations, but the best option is still to conduct thorough testing yourself. This way, you can also check for errors that arise through factors like user input, which an IDE's automated checks won't cover.

Edmea

I just found out that python can compile WOW...but why python does not check for NameError at compile time? something like def A(): print x can be easily detected without actually allocate memory (you know like c/c++ compiler) – Frit

this method for checking syntax also produce binary code...if all compile does it checking syntax, does that mean the binary output could have a lot of errors and thus useless? – Frit

Other languages can have uncaught runtime errors, too. For example, in Java you can typecast to an incorrect type and the compiler won't complain. This is why you should properly test your program, so that it doesn't "have a lot of errors" and turn out "useless." – Edmea

Answer 2

The line B(n-1) says "when this statement is executed, lookup some function B in the module scope, then call it with parameters n-1". Since the lookup happens when the function is executed, B can be defined later.

(Additionally, you can completely overwrite B with a different function, and A will call the new B afterwards. But that can lead to some confusing code.)

If you're worried about not catching calls to nonexistent functions, you can try using static analysis tools. Other than that, be sure you're testing your code.

Persons

Answer 3

When the interpreter is reading A, B is not yet defined, however this code does not give me an error

The reason why python interpreter doesn't give an error can be found from docs, which is called forward reference technically:

Name resolution of free variables occurs at runtime, not at compile time.

Anaplastic

Answer 4

Considering the first example code specifically:

In Python, def A(): is an executable statement. It is evaluated by using the code inside the block to create a function object, and then assigning that object to the name A. This does more than just a "syntax check"; it actually compiles the code (in the reference implementation, this means it produces bytecode for the Python VM). That process involves determining that B i) is a name, and ii) will be looked up globally (because there is no assignment to B within A).

We can see the result using the dis module from the standard library:

>>> def A(n):
...     B(n-1)
... 
>>> import dis
>>> dis.dis(A)
  2           0 LOAD_GLOBAL              0 (B)
              2 LOAD_FAST                0 (n)
              4 LOAD_CONST               1 (1)
              6 BINARY_SUBTRACT
              8 CALL_FUNCTION            1
             10 POP_TOP
             12 LOAD_CONST               0 (None)
             14 RETURN_VALUE

this result is version-specific and implementation dependent; I have shown what I get using the reference implementation of Python 3.8. As you can infer, the LOAD_GLOBAL opcode represents the instruction to look for B in the global namespace (and failing that, in the special built-in names).

However, none of the code actually runs until the function is called. So it does not matter that B isn't defined in the global namespace yet; it will be by the time it's needed.

From comments:

but why python does not check for NameError at compile time?

Because there is nothing sensible to check the names against. Python is a dynamic language; the entire point is that you have the freedom to Do Whatever It Takes to ensure that B is defined before A uses it. Including, for example, extremely bad ideas like downloading another Python file from the Internet and dynamically executing it in the current global namespace.

Hounding