list index in python use a stack call?

Question

If I have a large string which I call eval() on, and within the string I evaluate lots of list indices, does each evaluation of the list constitute a function call?

For instance, say I had a string millions of terms long such as

l = [0.2, 0.534, 0.265, ...]
mystring = "l[0]*l[2] * 3 * ... * l[2304]"
eval(mystring)

Would this evaluation actually be filling my stack recursion? I ask this because I found that the only way I could call eval is if I set

sys.setrecursionlimit(65000)

I understand that types are objects in python, so, my intuition is that the brackets [] are a sort of overloaded get routine?

Answer 1

The evaluation of this code will not overflow the call stack, because the code itself does not call any functions. The RecursionError you get has the following message:

RecursionError: maximum recursion depth exceeded during compilation

The key part of this is during compilation. You should always read and try to understand the full error message.

During compilation means the call stack was overflowed while compiling your string, not while evaluating it. eval doesn't even begin to try evaluating the code; the error is raised before it gets a chance to. On the other hand, once the code is compiled, eval doesn't need a large call stack because the code itself doesn't make function calls. We can demonstrate that by increasing the recursion limit, compiling, then lowering the recursion limit again before evaluating:

>>> lst = list(range(10000))
>>> code = '+'.join('lst[{}]'.format(i) for i in range(10000))
>>> compile(code, '<test>', 'eval') # compilation overflows call stack
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded during compilation
>>> sys.setrecursionlimit(100000) # compile requires a large call stack
>>> code_obj = compile(code, '<test>', 'eval')
>>> sys.setrecursionlimit(100) # eval works fine without a large call stack
>>> eval(code_obj)
49995000

---

Roughly, a string of code is compiled by parsing it as an abstract syntax tree (AST), then converting the AST into bytecode. Either the parsing, or the bytecode conversion, or probably both, are done by recursive functions.

We can see the issue in the example below, which uses the astpretty module to show the AST of the expression a * b * c * d:

>>> import ast, astpretty
>>> expr = ast.parse('a * b * c * d').body[0]
>>> astpretty.pprint(expr, show_offsets=False)
Expr(
    value=BinOp(
        left=BinOp(
            left=BinOp(
                left=Name(id='a', ctx=Load()),
                op=Mult(),
                right=Name(id='b', ctx=Load()),
            ),
            op=Mult(),
            right=Name(id='c', ctx=Load()),
        ),
        op=Mult(),
        right=Name(id='d', ctx=Load()),
    ),
)

Notice that the tree's nesting level is proportional to the number of terms being multiplied together, and has nothing to do with what the terms actually are (in this case, they're just names of variables, not list items). With thousands of terms multiplied together in your code string, the AST is thousands of levels deep; so a recursive function which tries to build or walk such a tree will overflow the call stack. That is, unless you increase the recursion limit.