Program slicing is a well-known technique that has been widely used for debugging in the context of imperative programming. Despite the fact that debugging is a particularly difficult task within the lazy declarative languages, one can find very few approaches to program
slicing in this context. In order to overcome this problem, we have implemented a slicing tool for a first-order, lazy functional logic language. In this page we describe the results obtained from some experiments and put available the source code of the tool.

Modern functional logic languages like Curry and Toy combine the most important features of functional logic languages, e.g., lazy evaluation and non-determinism. Due to the complexity of their operational semantics, following the actual trace of a computation is often useless. In the context of (purely) functional lazy languages like Haskell, this drawback is overcome by introducing higher-level models that hide the details of lazy evaluation (e.g., Hood, Freja, Buddha, and Hat). Many of these approaches are based on the construction of a redex trail, a directed graph which records copies of all values and redexes reducible expressions) of a computation, with a backward link from each reduct to the parent redex that created it.

 

Recently, Brassel et al introduced an instrumented version of an operational semantics for the kernel of lazy functional logic languages that returns, not only the computed values and bindings, but also a trail of the computation. As in the Augmented Redex Trail approach, this trail can be used to perform tracing and algorithmic debugging, as well as to observe data structures through a computation. Moreover, the correctness of the computed trail is formally proved, which amounts to say that it contains all (and only) the reductions performed in a computation.

While tracing-based debugging provides a powerful tool for inspecting erroneous computations, the task still remains complex. A well-known debugging technique for imperative programs is based on slicing [1], a method for decomposing programs by analyzing their data and control flow. Roughly speaking, a program slice consists of those program statements which are (potentially) related with the values computed at some program point and/or variable, referred to as a slicing criterion. Program slices are usually computed from a program dependence graph that makes explicit both the data and control dependences for each operation in a program. Program dependences can be traversed backwards or forwards (from the slicing criterion), which is known as backward or forward slicing, respectively. Additionally, slices can be dynamic or static, depending on whether a concrete program's input is provided or not. A complete survey on slicing can be found, e.g., in [2].

When debugging programs, we usually start from a particular computation that outputs an incorrect value. In this situation, dynamic slicing may help the programmer to find the location of the bug by extracting a program slice containing only the sentences whose execution influences the incorrect value. Therefore, we are mainly interested in dynamic slicing which only reflects the actual dependences of the erroneous execution, thus producing smaller -more precise- slices than static slicing.

To the best of our knowledge, there is no dynamic slicing tool for lazy languages like Haskell or Curry. Therefore, our original motivation was to fill this gap with a formal technique for dynamic slicing in lazy functional logic languages (nevertheless, the basic ideas also apply to pure lazy functional languages like Haskell). Rather than starting from scratch, our technique relies on a slight extension of redex trails. Basically, we extend the redex trail model in order to also store the location, in the program, of each reduced expression. Then, we compute a dynamic slice by first gathering the reachable nodes of the redex trail -according to the slicing criterion- and, then, deleting those program expressions which are not related to the collected nodes.

From our point of view, dynamic slicing may provide a complementary -rather than alternative- approach to tracing. A clear advantage of our approach is that one can enhance existing tracers with slicing capabilities with a modest implementation effort, since the same data structure -the redex trail- is used for both tracing and slicing.

More information about this schema can be found here.