Algorithmic Debugging with Cyclic Traces of Lazy Functional Programs

We have proved the correctness of algorithmic debugging if the traces are acyclic. For cyclic traces, however, does algorithmic debugging still work? There does not exist a common understanding of how to debug cyclic traces in functional programming communities for a long time. In this paper we give two small examples to demonstrate that it is extremely difficult to find a generic algorithmic debugging scheme for cyclic traces. We conjecturre that it is impossible to have a generic scheme for cyclic traces, because the examples are very small and the choices of reasonable debugging trees are very limited. We also present acyclic traces in which constants are shared unless shared constants result in a cycle. The normal algorithmic debugging scheme works fine for acyclic traces and the proof is very similar to our previous paper.