On Friday, December 24, 2021 at 9:36:21 AM UTC-6 Edward K. Ream wrote: > *A puzzle* > > ...The first puzzle I set myself was to traverse (parse) trees using > neither recursion (including ast.walk) nor generators. > Wow. This is a tricky puzzle. All my instincts are wrong, wrong, wrong.
I was feeling smug yesterday, putting the finishing touches on a fairly simple approach, with simple visitors and a simple supporting infrastructure. Then I realized that the whole approach had no chance of working! When I awoke this morning I had several new thoughts: 1. I would be happy enough with a two-pass algorithm. The first pass would insert parent/child and thread next/back links in some desired order. The second pass would "deliver" nodes using the thread next links. 2. The code that creates the links could visit the tree nodes in *any* order, provided that the links themselves imply the desired order. So I could use ast.walk as a prototype. (ast.walk can't be part of the actual solution because ast.walk uses recursion.) 3. There is *no way* typical node visitors could possibly work. Indeed, visiting in the desired order implies recursion. No clever infrastructure can change that fact. As I write this, I realize that the puzzle is even trickier than I thought. Performing the desired *actions* in the correct order would be difficult *even with* correctly ordered threading links between nodes. What we probably need are threading links that include *actions*. Heh, I think something like these thoughts were behind the scheme that blew up so spectacularly yesterday. What do I mean by actions, you ask? Well, visitors don't just visit nodes. Visitors *do something.* In fact, a better way to state the problem is call specific functions/methods in the "proper" order. *Summary* Any solution must execute arbitrary actions in some desired order. An elegant solution seems tantalizingly close, but my usual instincts lead me astray. *Visitors are a dead end.* There is no way to execute visitors without simulating python's call (or generator) machinery. Instead, at minimum, we must have a table of desired traversal orders for actions, one entry per ast node type. A multi-pass algorithm is acceptable. The doomed method I explored yesterday was very fast, even on an old laptop. That's all for now. Anyone who thinks this is an easy problem is invited to solve it, hehe. Edward -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/cd84ec13-0d86-42bc-855d-22c51cf18281n%40googlegroups.com.
