I'm not clear what problem you are trying to solve that isn't already being handled in Leo's code, but don't forget that there is depth-first traversal and also width-first traversal. There has to be an immense body of literature out there on tree traversal, and much if not most of it probably does not depend on generators and recursion. There is also lots of literature on traversing graphs, and that might be more suitable for some of Leo's structures that we often call trees but might better be termed graphs.
On Monday, December 27, 2021 at 7:30:04 AM UTC-5 Edward K. Ream wrote: > 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/2ef1a4f8-a620-45bf-a23c-398b8942ff2dn%40googlegroups.com.
