2009-07-06

stack-based vs queue-based langs

6.10:
. Jasvir Nagra (www.cs.auckland.ac.nz/~jas) writes:

Features of some programming languages make some algorithms
more elegantly expressly than others
. E has two calling conventions
- one that is stack-like and one that is queue-
which makes both styles of visitors pleasantly expressible
(slightly modified to emphasize the similarity) .
. I realize its not really much more to allocate a queue
but its a pretty pattern and makes it particularly easy to mix DFS and BFS:

def depth(tree, visit):
""(. stack-based languages might favor depth-first
because it is easy to take advantage of the call stack
instead of having to allocate a new data structure to store a queue
)
for child in tree`children:
depth(child, visit)
visit(tree)

def breadth(tree, visit):
""( in a queue-based language more people would use a breadth-first visitor.
)
for child in tree`children:
breadth<-(child, visit)
visit(tree)