6 ms·

Show HN: Python decorator that enables arbitrarily-deep tail/non-tail recursion

119 points by tylerhou 5y ago

tylerhou 5y ago
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 5y ago
  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 5y ago
    You're right, fixed.
- KolenCh 5y ago
  May be compare to tco which is not as general.
a-dub 5y ago
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 5y ago
  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 5y ago
    > 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 5y ago
      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...

119 points by tylerhou 5y ago

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 5y ago
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 5y ago
  You're right, fixed.
KolenCh 5y ago
May be compare to tco which is not as general.

a-dub 5y ago

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 5y ago
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 5y ago
  > 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 5y ago
    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...