abstract syntax tree - Tracing Python expression evaluation step by step

Question

I'm trying to write Python expression evaluation visualizer, that will show how Python expressions are evaluated step by step (for education purposes). Philip Guo's Python Tutor is great, but it evaluates Python program line by line, and I found that students sometimes do not understand how one-line expressions like sorted([4, 2, 3, 1] + [5, 6])[1] == 2 are evaluated and I'd like to visualize this process. (It seems that nobody did it yet — at least I found nothing.) The ideal solution will create a sequence of strings like this:

sorted([4, 2, 3, 1] + [5, 6])[1] == 2
sorted( >> [4, 2, 3, 1] + [5, 6] << )[1] == 2
>> sorted([4, 2, 3, 1, 5, 6]) << [1] == 2
>> [1 2 3 4 5 6][1] << == 2
>> 2 == 2 <<
True

Here >> and << are used to highlight a part of the expression that is evaluated on the current step and then replaced by its value. (Maybe, I will try to convert this sequence to some kind of animation later.)

My current strategy is to use ast.parse() to parse the string into AST, then find a node that will be evaluated first, evaluate it with eval(compile(node, '', 'eval')) (I'm definitely do not want to reimplement the whole Python :)), convert the result of evaluation into AST Node (with repr and then ast.parse()?) and substitute current node with the result node, then use codegen.to_source to produce modified code string from (modified) AST and continue the same process until I have only one literal in the tree.

My question is: how can I find a node that will be evaluated first? It seems that I can traverse the tree depth-first with subclassing ast.NodeVisitor, but I'm not sure how can I detect that I reached the desired node and how can I stop traversing after it?

---

EDIT.

It is possible that my initial approach with transformation of the tree is not feasible. In fact, an elementary step of evaluation of Python expression is not neccessary have to be a replacement of some sub-expression to a simpler one (like in arithmetic). For example, list comprehensions provide a much more complicated behaviour that cannot be expressed in terms replace this thing by that thing, then repeat recursively. So I restate a the question a little bit. I need some way to programmaticaly show how Python expressions are evaluated step by step. For example, MacroPy's tracing feature, mentioned by @jasonharper, is acceptable solution at this stage. Unfortunately, MacroPy seem to be abandoned and doesn't work with Python 3. Are there any ideas how to resemble this tracing behaviour in Python 3 without porting full MacroPy?

---

EDIT2.

Just after I awarded this bounty, I found similar question and a debugger with very close features. However, as there's no ultimate answer for that question, and I do not need the full debugger, I'm still looking for an answer that can be used for example in Jupyter environment.

Answer 1

Expression stepping is implemented in Thonny IDE.

It uses AST instrumentation, where each (sub)expression e is transformed into after(before(<location info>), e). Functions before and after are dummy functions for causing extra call-events in Python's tracing system. These extra calls notify when (sub)expression evaluation is about to start or has just ended. (Similar dummy functions are added to detect start and end of each statement.)

AST instrumentation and interpretation of these new events is done in thonny.backend.FancyTracer.

Python's AST nodes contain start position of corresponding text ranges, but they are sometimes incorrect. End positions are completely missing. thonny.ast_utils.mark_text_ranges tries to take care of this (but the solution is incomplete at the moment).

It would be nice if somebody extracted relevant functionality from Thonny to a more general package. Maybe even two packages -- one for computing location info for Python AST and other for detailed tracing of Python code. I'd be willing to help with this, if someone took the lead.