Design, Implementation and Calculation of Circular Programs: Multiple Traversal Algorithms in a Lazy Functional Setting

Circular programming is a powerful technique to express multiple traversal algorithms as a single traversal function in a lazy setting. Such a (virtual) circular program may contain circular definitions, that is, arguments of function calls that are also results of that same call. Although circular definitions always induce non-termination under a strict evaluation mechanism, they can sometimes be immediately evaluated using a lazy evaluation strategy. The lazy engine is able to compute the right evaluation order, if that order exists. Indeed, using this style of circular programming, the programmer does not have to concern him/herself with the definition and the scheduling of the different traversal functions, since only a single (traversal) function has to be defined. Neither does the programmer have to define intermediate gluing data structures to convey values computed in one traversal and needed in a following one. In this book, we present our studies on the design, implementation and calculation of circular programs.