4 ms·
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/loggin
by 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 agoAh, 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...