This was a fun episode. I was introduced to breadth first labeling and attribute grammars by Doaitse Swierstra at the Applied Functional Programming summer school in Utrecht. He was an inspiring figure.
The biggest disadvantage of circular programs is that it is very easy to get into infinite loops when you make mistakes. I wish there was an easy way to guarantee statically that circular programs are terminating (perhaps using types).
There is also a recent paper about implementing breadth-first traversals without relying on laziness: https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/traversals.pdf. Unfortunately, that does not contain any benchmarks.