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.
-- 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 TermAnnotations to let a term point to the next term in a breadth-first traversal.

-- EelcoVisser - 09 Dec 2001


CategoryToDo? | ToDo | LibraryImprovements

Revision: r1.1 - 09 Dec 2001 - 18:14 - EelcoVisser
Stratego > LibraryImprovements > BreadthFirstTraversal
Copyright © 1999-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback