[HN Gopher] Show HN: Python decorator that enables arbitrarily-d...
___________________________________________________________________
Show HN: Python decorator that enables arbitrarily-deep tail/non-
tail recursion
Author : tylerhou
Score : 58 points
Date : 2021-12-20 19:11 UTC (3 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| a-dub wrote:
| neat idea, but i'm guessing that a rewritten function would be
| nightmarish to debug... or no?
|
| wonder if it would be possible to do automated rewrites of
| recursive functions as iterative ones. specifically for cases
| where stack memory that grows in a recursive implementation can
| be replaced by a few long lived temporaries... like the good ol'
| fibonacci function.
| tylerhou wrote:
| Yeah, debugging the written function is not easy, but that
| could be improved by adding the normal tools for rewrites
| (sourcemap). Also, you can put print/logging statements inside
| the function; the rewrite preserves those.
|
| In theory the rewrite shouldn't change behavior, so you could
| also unittest both the decorated function and the undecorated
| function.
|
| > possible to do automated rewrites of recursive functions as
| iterative ones.
|
| This is basically what we're doing, except the stack is inside
| the trampoline. If you inlined the trampoline into the function
| itself then that is exactly a recursion -> iteration transform.
| a-dub wrote:
| > This is basically what we're doing, except the stack is
| inside the trampoline. If you inlined the trampoline into the
| function itself then that is exactly a recursion -> iteration
| transform.
|
| yeah but aren't you basically creating a stack on the heap,
| and then running the recursive algorithm there?
|
| i mean more like rewriting the unbounded space recursive
| version of the fibonacci function as the constant space two
| temporary iterative version.
| tylerhou wrote:
| Ah, this is definitely possible as well; you could
| statically analyze the function and then topologically sort
| the recursive calls. But that falls into an optimization
| category which requires some sophisticated analysis.
|
| That type of optimization is trivial for fib, but it's
| really difficult in general. Also, it only easily works
| where the recursive parameter that is changing is an
| int/index. You could also make it work with trees/graphs,
| but that requires some substructural analysis...
| vitus wrote:
| Fib is a weird case because it's the poster child of dynamic
| programming. The challenge in this case is that each call
| spawns multiple recursive calls, and you're ultimately just
| adding 1's and 0's (so your runtime is comparable to the number
| you compute). Meanwhile, the DP / iterative approach
| understands the repeated structure of your recursion and can
| use that to eliminate redundant computation.
|
| Compare this to tail-recursive functions, where you can
| basically update the stack variables and jump back to the
| beginning of the function.
|
| (Note that you can approximately achieve the performance of the
| iterative solution by memoizing the results if your functions
| are pure and your input space is small, e.g. via
| @functools.cache, but you're paying for it with space, whereas
| the iterative solution understands when you can discard the
| intermediate results.)
| tylerhou wrote:
| Hi HN, I wrote this.
|
| Admittedly Fiber is not the best name -- in the current
| implementation we don't yield to the scheduler except for
| recursive function calls, and our "scheduler" only runs a
| function to completion. These things could be fixed of course,
| but I didn't have time.
|
| I called it Fiber because I thought coroutine + scheduler is
| approximately equal to a fiber implementation, and other
| schedulers could be added in the future with more clever
| behavior. Plus, you could change the yielding behavior to match
| what is necessary: for example, to yield at an arbitrary point
| one could modify the decorator to emit "pause" returns whenever a
| special `yield_()` function is called. Or you could create a list
| of special functions (e.g. functions associated with normal
| syscalls) that cause the coroutine to yield, and have a scheduler
| that will resume the function when the syscall completes.
|
| One point behind this project is to demonstrate that if you want
| to pause and resume functions, you don't actually need runtime
| (kernel, VM) support; some hacky AST rewrites are also a feasible
| (if slow) implementation. One thing to note is that our overhead
| is mostly per pause/resume; hence the "sum a list" benchmark is
| really a worst-case benchmark. If you have some recursive
| function that does a lot of non-recursive work that needs to be
| paused and resumed (hint hint, React rendering and
| reconciliation) the performance gap will be much narrower.
| Tistron wrote:
| I don't generally write Python code, so maybe that is it, but
| should't the first example:
|
| > print(trampoline.run(cache, [1010]) % 10 * 5)
|
| reference `fib` somehow, rather than `cache`?
| tylerhou wrote:
| You're right, fixed.
___________________________________________________________________
(page generated 2021-12-20 23:00 UTC)