Reducing "yield from" overhead in recursive generators

[Rathmann]

On Friday, March 18, 2022 at 2:07:45 AM UTC-7, Antoon Pardon wrote:
> Op 18/03/2022 om 04:14 schreef Rathmann: 
> > 
> > So what do people think of this hack/technique? Is it 
> > 
> > A) A terrible idea? (Please be specific.) 
> > B) Already well-known (and I just missed it.) 
> > C) Potentially useful for the niche case of deeply recursive 
> > generators?
> I would go with B' + C. It seems there is a resemblance with the trampoline technique 
> in order to eliminate tail recursion. I know the people of macropy have written a 
> decorating macro that would eliminate tail recursion from such decorated functions. 
> Maybe if you contact them they can be interested in making a similar decorating macro 
> for use with such recursive decorators. 
> 
> -- 
> Antoon Pardon.

Thank you Antoon.  I was not aware of macropy.  It certainly seems
like a macro could automate the process of switching the "yield from"
to yield forms.  That is already pretty easy to do by hand, though.

The driver itself could be packaged as a decorator using just the
facilities available in regular Python implementations.

**Much** more ambitious would be a macro to automate the
transformation of a generator from (general) recursive to iterative
form, so as to avoid the need for this technique entirely.

The other challenge/question would be to see if there is a way to implement
this basic approach with lower overhead.  So far, the savings don't
kick in until the recursion hits a depth of 12 or so (even more with
CPython), and many use cases have an expected recursion depth
shallower than that.