Circular Programs

Circular Programs were first proposed by Richard Bird as an elegant and efficient technique to eliminate multiple traversal of data structures.

As the name suggests, Circular Programs are characterized by having what appears to be a circular definition: arguments in a function call depend on results of that same call. That is, they contain definitions of the form:

(...,x,...) = f ... x ...

In order to motivate the use of circular programs, Bird introduces the following problem: consider the problem of transforming a binary leaf tree into a second tree, identical in shape to the original one, but with all the tip values replaced by the minimum tip value.

An instance of such a problem is presented next.

The input tree						The output tree

In a strict and purely functional setting, solving this problem would require a two traversal strategy: the first traversal would compute the original tree's minimum value, and the second traversal would replace all the tip values by the minimum value, therefore producing the desired result.

However, a two traversal strategy is not essential to solve the repmin problem. An alternative solution can, on a single traversal, compute the minimum tip value and, at the same time, replace all tip values by that minimum value.

Bird also showed a program transformation technique to derive circular programs from the straightforward strict, multiple traversal solutions.

The Haskell circular program that solves the repmin problem is presented next.

data R    = RootProd Tree

data Tree = Tip  Int 
          | Fork Tree Tree

repmin (RootProd t)   = replace
   where (replace,m)  = repmin_aux (t, m)
         
repmin_aux (Tip n,      minIn) = (replace, m)
   where replace          = Tip minIn
         m                = n
repmin_aux (Fork t1 t2, minIn) = (replace, m) 
   where replace          = Fork replace1 replace2
         m                = min  m1 m2
         (replace1, m1)   = repmin_aux (t1, minIn)
         (replace2, m2)   = repmin_aux (t2, minIn)

Notice that, on the above program's call:

         (replace,m)  = repmin_aux (t, m)

the variable

m

This type of circular definitions are directly executable on lazy languages only.