4 ms·

I've got a sneaking suspicion this is one of those clever, elegant, kind-of-awesome-thanks-python, yet entirely evil things you can, but never actually should d

I've got a sneaking suspicion this is one of those clever, elegant, kind-of-awesome-thanks-python, yet entirely evil things you can, but never actually should do in a production app. Is there a use case for something like this?

razimantv 9y ago
We started out trying to write a general method to convert top-down dynamic programming to bottom-up and this was as far as we got. Working around finite stack sizes and generating the topological sort of the function states are the only practical uses that I can think of. Was more of an interesting challenge personally.
- rachitnigam 9y ago
  Take a look at https://github.com/plasma-umass/stopify https://github.com/plasma-umass/stopify We can do it for general JS programs. If you are willing to compile Python to JS, you can transparently use our compiler to get heap bounded stacks.
arghwhat 9y ago
Absolutely not. If you want an iterative function, write one. It's not harder than writing a recursive one (although sometimes a bit less readable). Writing an iterative function is also both faster than the recursive function, and much faster than the hack. Still a neat hack, though.
- odonnellryan 9y ago
  Well, sometimes it is harder. Think, any problem related to traversing a tree, or similar problems related to trees and/or graphs.
  - chronial 9y ago
    You can just replace the call stack with an explicit stack in your function – that should never be hard, just a bit less readable :).
    - scardine 9y ago
      Can you use some structure like a clojure zipper[1] for traversing trees iteratively? [1] http://josf.info/blog/2014/03/21/getting-acquainted-with-clojure-zippers/ http://josf.info/blog/2014/03/21/getting-acquainted-with-clo...
    - odonnellryan 9y ago
      Yes I can see how this makes sense, but I wouldn't say it is easier than recursion! Maybe a good exercise, but when traversing a tree the recursive solution is very easy to understand. The iterate solution ... Then you have other problems, where the recursive solution is actually not super easy to understand why it "works" immediately (think, balanced paren generation) and going on to create an iterative solution, while not insanely hard, is not something super obvious.... what's your condition to stop iteration, again? Maybe I'm thinking about that the wrong way, I'd love to learn more about it! That problem is closely related to tree traversal, anyway, I should fool around with those two ideas a bit more to properly understand.
      - arghwhat 9y ago
        I never said it was easier, I just said it was not much harder. :) Like I said, it is sometimes a bit less readable (tree-walking is a good example of such case), but at the same time, what the code actually does is much clearer. You have no hidden costs, and the code is easier to optimize this way. You mention a case where you do not fully understand why the recursive solution works, in which case you obviously can't easily write an iterative solution. However, in this case, you are poorly equipped to make any implementation, recursive or iterative.

razimantv 9y ago

We started out trying to write a general method to convert top-down dynamic programming to bottom-up and this was as far as we got. Working around finite stack sizes and generating the topological sort of the function states are the only practical uses that I can think of. Was more of an interesting challenge personally.

rachitnigam 9y ago
Take a look at https://github.com/plasma-umass/stopify https://github.com/plasma-umass/stopify We can do it for general JS programs. If you are willing to compile Python to JS, you can transparently use our compiler to get heap bounded stacks.

arghwhat 9y ago

Absolutely not. If you want an iterative function, write one. It's not harder than writing a recursive one (although sometimes a bit less readable). Writing an iterative function is also both faster than the recursive function, and much faster than the hack. Still a neat hack, though.

odonnellryan 9y ago
Well, sometimes it is harder. Think, any problem related to traversing a tree, or similar problems related to trees and/or graphs.
- chronial 9y ago
  You can just replace the call stack with an explicit stack in your function – that should never be hard, just a bit less readable :).
  - scardine 9y ago
    Can you use some structure like a clojure zipper[1] for traversing trees iteratively? [1] http://josf.info/blog/2014/03/21/getting-acquainted-with-clojure-zippers/ http://josf.info/blog/2014/03/21/getting-acquainted-with-clo...
  - odonnellryan 9y ago
    Yes I can see how this makes sense, but I wouldn't say it is easier than recursion! Maybe a good exercise, but when traversing a tree the recursive solution is very easy to understand. The iterate solution ... Then you have other problems, where the recursive solution is actually not super easy to understand why it "works" immediately (think, balanced paren generation) and going on to create an iterative solution, while not insanely hard, is not something super obvious.... what's your condition to stop iteration, again? Maybe I'm thinking about that the wrong way, I'd love to learn more about it! That problem is closely related to tree traversal, anyway, I should fool around with those two ideas a bit more to properly understand.
    - arghwhat 9y ago
      I never said it was easier, I just said it was not much harder. :) Like I said, it is sometimes a bit less readable (tree-walking is a good example of such case), but at the same time, what the code actually does is much clearer. You have no hidden costs, and the code is easier to optimize this way. You mention a case where you do not fully understand why the recursive solution works, in which case you obviously can't easily write an iterative solution. However, in this case, you are poorly equipped to make any implementation, recursive or iterative.