JoostVisser and I have looked at a breadth first for Tools.JJTraveler. The breadth first in the Stratego library
is incorrect:

CategoryToDo^{?} | ToDo | LibraryImprovements

- 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.

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.

-- EelcoVisser - 09 Dec 2001

CategoryToDo

Revision: r1.2 - 06 Jan 2002 - 16:34 - EelcoVisser

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

Ideas, requests, problems regarding TWiki? Send feedback