Lazy debugging of lazy functional programs

The debugging of fully lazy functional programs can require searching a very large reduction-history space containing many delayed computations. A debugger should provide a means to obtain a source level representation of the computation, which can be large, and a means to select the appropriate part of the computation to investigate, which can be difficult. A method is presented to compile functional programs to combinator code such that a source-like representation of any part of a computation graph can be efficiently reconstructed at run-time. Other less efficient methods require excessive compile-time guidance as to the specific part of the computation to be investigated. Reconstruction, forward reduction, and a history-rollback mechanism combine to make the entire source-like reduction-history space dynamically available at run-time. The deferring of debugging decisions until run-time is called lazy dubugging. Once the computation-sequence is meaningfully and efficiently available, the problem of debugging becomes that of localizing the search for the error. Some searching issues are discussed with respect to graph browsing and user-interface design. The method shows promise as a programmer tool to debug programs and to informally reason about the time and space behavior of fully lazy functional programs, a nonintuitive process due to the subtleness of sharing and delayed computations.