Revealing the frontier with stacks and queues
17 points by denys_seguret
17 points by denys_seguret
The comments here led me to think “defunctionalizing the continuation” but that’s way more fancy jargon than this article needs :-)
To find a title was the hardest part in writing this article (and probably also the one with the least satisfying outcome). I try to avoid jargon too but I like the idea of execution frontier which appears especially concrete when thinking pathfinding.
A related advantage: with all the state explicit, it's easier to turn into an iterator. You can provide a nice API like:
fn reachable_from(root: Node) -> impl Iterator<Item = Node>;
...
for n in reachable_from(root) {
...
}
which lets the caller break early, etc.
Pardon my ignorance, but I don’t understand what reification of the frontier means after reading your article. In particular I would have appreciated seeing examples of this:
And because we reified the frontier, it's very easy to change the control flow, to deal with interrupts, pause the iteration, have interleaving tasks, like iterating on another tree at the same time, etc.
And why that is made easier without recursion and with stacks and queues. Can you help me understand?
This is probably badly written.
Reification is the operation of making something concrete (from Latin "res"). What's made concrete here, ie changed to data, is the execution frontier, i.e. the process which usually is only existing through the call stack. When you use your own stacks and queues, it's data you can manage.
I see the movement from call stack to function body now, thanks. But what’s stopping you from passing an accumulator object between recursive calls and managing it that way? To be clear, I’d prefer the iterative approach, just curious what iteration within the body actually lets you do that recursion doesn’t
An accumulator doesn't capture the complete execution process and doesn't allow you to restore it. Where the function has to return, for example, isn't reified, it's hidden in the call stack. The iteration index in the calling function is hidden in the upper function stack.