4 ms·

I don't agree with the "constant-stack algorithm" comment. Whether you represent the stack implicitly through recursive function calls, explicitly through build

I don't agree with the "constant-stack algorithm" comment. Whether you represent the stack implicitly through recursive function calls, explicitly through building up lambdas, or again even more explicitly by using a singly linked list or other suitable data structure, it's still a stack, and the memory complexity is the same. They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. This whole thing can be summarised as: 1. Represent the stack as a singly linked list (or std::stack). 2. Data type for encoding stack frame: function state and where to return to in function. As an example, this technique is useful if you are doing an in-order tree traversal and want to avoid using the stack. Define a data type to encode the nodes to be looked at, and encode whether you have already been through the left branch of the node or not.

yakubin 6y ago
> They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. When you use (non-tail) recursive function calls, your memory will grow faster than with an explicitly managed stack, because now at each recursion level not only will you store all the things you would store in the explicitly managed stack, but also all the other variables and some intermediate values. Explicitly managed stack, that is implemented efficiently (i.e. mostly contiguous memory, not a linked list like in the example given), will give you better performance and will be easier to debug, because now you can query its size and identify where in the program you're using a given amount of memory; in the debugger you can inspect it as a whole in a multitude of ways (as opposed to the black box of a function where you'll only inspect one recursion level at a time, leaving you with scattered information and without easy to read performance metrics). That said, recursion is usually the simplest thing to write on the first try, when coming up with a solution to a problem. But I do tend to "defunctionalize" later.
- jpcooper 6y ago
  "Defunctionalising" makes sense for performance. Ability to debug is a pro. I wanted to point out the similarity between these separate methods. In any case though, I would hope that an optimising compiler would not push onto the stack variables which are not used later in the function. Repeatedly pushing a pointer to the structure you're working on is indeed an overhead of recursive calls.
mannykannot 6y ago
Calculating the nth member of the Fibonacci sequence is a commonly-used example of where a naive, literal-translation-to-code recursive solution is inordinately costly - so now I am trying to figure out if the method described in this article, applied mechanically to the literal recursive solution, results in an efficient solution, or merely tranfers the data complexity of its stack frames to the heap (I think you are suggesting it would result in the latter, which seems plausible to me.)
- jpcooper 6y ago
  Might be worth checking https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ https://www.geeksforgeeks.org/program-for-nth-fibonacci-numb....
- ufo 6y ago
  The mechanical transformation described in the article does not change the asymptotic complexity of the program. It just changes it from using an implicit (recursion) stack, to using an explicit stack. The neat thing about that transformation, in my opinion, is that it works even for complicated algorithms. Sometimes you really do need to rewrite something to use an explicit stack, and that can be quite tricky to get right!
  - mannykannot 6y ago
    Point taken - thanks!
CyberRabbi 6y ago
call stack growth only matters in languages that don’t have a way to recover gracefully from call stack overflow, e.g. C. You want to convert recursive implementations into iterative implementations in those languages because you can actually handle malloc() failing instead of corrupting your call stack. You’re right that you’re still implementing a stack no matter what, just moving it from the call stack to the heap.
- jpcooper 6y ago
  Yes. My in-order tree traversal example corresponded to how I would implement it in a C-like language. As long as the person setting the question can confirm that the maximum depth is well below the stack size, it stays recursive, though. By the way, Haskell has stack problems as well when evaluating thunks. Hence the strict foldl’. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
  - CyberRabbi 6y ago
    Right... probably nearly every language has a poor call stack overflow recovery story, not only because of non-heap stacks but I don’t think it’s relatively straightforward to get the program back into a well defined state after call stack overflow. Those errors can happen on any line of code so unless every line of code is guaranteed to be atomic and a coherent state can be derived from the intermediate states, the program will be in an undefined state.
gowld 6y ago
Remember that a linked list is not necessary worse than a stack if you use it like a stack. Linked lists are essentially the same as stacks (for a sufficiently smart compiler/runtime) if you never mutate at the middle/end and you can garbage-collect the head immediately when it's popped, letting you store the list in a contiguous structure.
- jpcooper 6y ago
  Linked lists are generally implemented using pointers to other linked list nodes which reside in memory not necessarily adjacent to the original node. If the nodes are in adjacent memory, then you still have the indirection of using pointers, and the extra memory used by storing the pointers for each node. In that case, why not use a stack defined over contiguous memory in the first place?

yakubin 6y ago

> They're all different ways of doing the same thing. Of course there could be a benefit for cases where you have a limited stack size. The author says that there's no need to do this in Haskell, because the stack is allocated on the heap, but I still wonder what the constant factor overhead of doing this with a linked list plus data types is over simple recursive function calls. When you use (non-tail) recursive function calls, your memory will grow faster than with an explicitly managed stack, because now at each recursion level not only will you store all the things you would store in the explicitly managed stack, but also all the other variables and some intermediate values. Explicitly managed stack, that is implemented efficiently (i.e. mostly contiguous memory, not a linked list like in the example given), will give you better performance and will be easier to debug, because now you can query its size and identify where in the program you're using a given amount of memory; in the debugger you can inspect it as a whole in a multitude of ways (as opposed to the black box of a function where you'll only inspect one recursion level at a time, leaving you with scattered information and without easy to read performance metrics). That said, recursion is usually the simplest thing to write on the first try, when coming up with a solution to a problem. But I do tend to "defunctionalize" later.

jpcooper 6y ago
"Defunctionalising" makes sense for performance. Ability to debug is a pro. I wanted to point out the similarity between these separate methods. In any case though, I would hope that an optimising compiler would not push onto the stack variables which are not used later in the function. Repeatedly pushing a pointer to the structure you're working on is indeed an overhead of recursive calls.

mannykannot 6y ago

Calculating the nth member of the Fibonacci sequence is a commonly-used example of where a naive, literal-translation-to-code recursive solution is inordinately costly - so now I am trying to figure out if the method described in this article, applied mechanically to the literal recursive solution, results in an efficient solution, or merely tranfers the data complexity of its stack frames to the heap (I think you are suggesting it would result in the latter, which seems plausible to me.)

jpcooper 6y ago
Might be worth checking https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ https://www.geeksforgeeks.org/program-for-nth-fibonacci-numb....
ufo 6y ago
The mechanical transformation described in the article does not change the asymptotic complexity of the program. It just changes it from using an implicit (recursion) stack, to using an explicit stack. The neat thing about that transformation, in my opinion, is that it works even for complicated algorithms. Sometimes you really do need to rewrite something to use an explicit stack, and that can be quite tricky to get right!
- mannykannot 6y ago
  Point taken - thanks!

CyberRabbi 6y ago

call stack growth only matters in languages that don’t have a way to recover gracefully from call stack overflow, e.g. C. You want to convert recursive implementations into iterative implementations in those languages because you can actually handle malloc() failing instead of corrupting your call stack. You’re right that you’re still implementing a stack no matter what, just moving it from the call stack to the heap.

jpcooper 6y ago
Yes. My in-order tree traversal example corresponded to how I would implement it in a C-like language. As long as the person setting the question can confirm that the maximum depth is well below the stack size, it stays recursive, though. By the way, Haskell has stack problems as well when evaluating thunks. Hence the strict foldl’. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
- CyberRabbi 6y ago
  Right... probably nearly every language has a poor call stack overflow recovery story, not only because of non-heap stacks but I don’t think it’s relatively straightforward to get the program back into a well defined state after call stack overflow. Those errors can happen on any line of code so unless every line of code is guaranteed to be atomic and a coherent state can be derived from the intermediate states, the program will be in an undefined state.

gowld 6y ago

Remember that a linked list is not necessary worse than a stack if you use it like a stack. Linked lists are essentially the same as stacks (for a sufficiently smart compiler/runtime) if you never mutate at the middle/end and you can garbage-collect the head immediately when it's popped, letting you store the list in a contiguous structure.

jpcooper 6y ago
Linked lists are generally implemented using pointers to other linked list nodes which reside in memory not necessarily adjacent to the original node. If the nodes are in adjacent memory, then you still have the indirection of using pointers, and the extra memory used by storing the pointers for each node. In that case, why not use a stack defined over contiguous memory in the first place?