5 ms·

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 recurs

by 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...
vitus 5y ago
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.)
- falcor84 5y ago
  >Fib is a weird case because it's the poster child of dynamic programming. It's actually got a closed-form solution, so finding the nth fib number is O(1) (assuming O(1) arithmetic). https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e...
  - tylerhou 5y ago
    Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. Fib grows exponentially, so fib(n) takes O(n) bits to write. Python uses Karatsuba’s, which multiples two n-bit numbers in approximately n^1.59 time. Second, to compute the result accurately, you would have to compute many many digits of floating point precision with the closed form solution. That is more expensive than alternative solutions. The fastest freely available, practical implementation that doesn’t have floating point error is probably in libgmp, which uses fast powering (which can be derived from repeated matrix exponentiation). https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm This takes something like O(multiplication * logn) time. With Karatsuba’s, approximately O(n^1.59 * logn). (Now I see you said assuming O(1) arithmetic after I wrote this post, but that’s not a reasonable assumption…)
chrisseaton 5y ago
> i'm guessing that a rewritten function would be nightmarish to debug... or no? I'm going to guess that it's likely irreducible! So yes a problem for both human and machine understanding!
jhanschoo 5y ago
> 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. Yes. Some Lisp implementations do this automatically. See https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style . Note that this differs from the POC of OP in that in OP's POC, only one function is defined, and it is transformed into a tree with if-statements to determine where in the code execution should be resumed, but in CPS it's an anonymous function in the tail being called with all context still relevant to it. Then the tail-call can be optimized out. Note that anonymous functions can be seen as just regular top-level functions with a hidden parameter containing the context relevant to it.
thaumasiotes 5y ago
> wonder if it would be possible to do automated rewrites of recursive functions as iterative ones. Of course. > 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. Rewriting a recursive Fibonacci function to use a loop with an explicit stack doesn't do anything about the growth of memory. You'll need just as many stack elements. It's just an explicit stack that you've assigned to a variable rather than being the function call stack.
- coldtea 5y ago
  >Rewriting a recursive Fibonacci function to use a loop with an explicit stack doesn't do anything about the growth of memory. Sort of. It means the amount of memory you can use is much bigger, and not constrained by the stack size.

by a-dub 5y ago

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...

vitus 5y ago

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.)

falcor84 5y ago
>Fib is a weird case because it's the poster child of dynamic programming. It's actually got a closed-form solution, so finding the nth fib number is O(1) (assuming O(1) arithmetic). https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e...
- tylerhou 5y ago
  Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. Fib grows exponentially, so fib(n) takes O(n) bits to write. Python uses Karatsuba’s, which multiples two n-bit numbers in approximately n^1.59 time. Second, to compute the result accurately, you would have to compute many many digits of floating point precision with the closed form solution. That is more expensive than alternative solutions. The fastest freely available, practical implementation that doesn’t have floating point error is probably in libgmp, which uses fast powering (which can be derived from repeated matrix exponentiation). https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm This takes something like O(multiplication * logn) time. With Karatsuba’s, approximately O(n^1.59 * logn). (Now I see you said assuming O(1) arithmetic after I wrote this post, but that’s not a reasonable assumption…)

chrisseaton 5y ago

> i'm guessing that a rewritten function would be nightmarish to debug... or no? I'm going to guess that it's likely irreducible! So yes a problem for both human and machine understanding!

jhanschoo 5y ago

> 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. Yes. Some Lisp implementations do this automatically. See https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style . Note that this differs from the POC of OP in that in OP's POC, only one function is defined, and it is transformed into a tree with if-statements to determine where in the code execution should be resumed, but in CPS it's an anonymous function in the tail being called with all context still relevant to it. Then the tail-call can be optimized out. Note that anonymous functions can be seen as just regular top-level functions with a hidden parameter containing the context relevant to it.

thaumasiotes 5y ago

> wonder if it would be possible to do automated rewrites of recursive functions as iterative ones. Of course. > 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. Rewriting a recursive Fibonacci function to use a loop with an explicit stack doesn't do anything about the growth of memory. You'll need just as many stack elements. It's just an explicit stack that you've assigned to a variable rather than being the function call stack.

coldtea 5y ago
>Rewriting a recursive Fibonacci function to use a loop with an explicit stack doesn't do anything about the growth of memory. Sort of. It means the amount of memory you can use is much bigger, and not constrained by the stack size.