Transform.JoostVisser and I have looked at a breadth first for [[Tools.JJTraveler]]. The breadth first in the Stratego library
is incorrect:
* It doesn't apply s to the root (and hence not to any node);
* It's not overall breadht-first, only breadth-first per node.
-- Transform.ArieVanDeursen; 25 Nov 2001.
It is indeed not a correct implementation of breadth first, but it does actually apply
transformations. Consider the definition:
breadth-first(s) =
rec x(all(s); all(x))
This first applies =s= to all direct subterms of the root, and then recursively applies =x= to
the direct sub-terms. The difference with topdown is that all subterms are visited, before
visiting subterms recursively. What is a better name for this strategy? =kids-first= maybe?
An implementation of proper breadth-first should employ a global queue data structure to which
terms to be visited should be added. It is also interesting to consider using TermAnnotation to
let a term point to the next term in a breadth-first traversal.
-- Main.EelcoVisser - 09 Dec 2001
-----
CategoryToDo | ToDo | LibraryImprovements