e-Knife

e-Knife is a program slicing tool for Erlang. It is based on the Expression Dependence Graph (EDG), and allows for the creation and slicing of EDGs.

The Expression Dependence Graph

The EDG is a generalization of the System Dependence Graph (SDG) [1, 2] that works at the expression level (instead of the statement level). Compared to the SDG, it does not need any pre- or post-process to handle complex expressions (e.g. list comprehensions and other functional constructs). Moreover, it allows for selecting any (sub)expression as the slicing criterion.

Its goal is not to reason about a specific language or to solve particular program representation problems, but to provide a general and accurate representation of expressions that allows for decomposing the nodes of the SDG and defining their internal dependences. The EDG is a fundamental advance in the area because it converges in a single data structure many ad-hoc solutions that have been proposed in the literature to solve different problems of the SDG, providing a formal basis for the slicing of functional programs.

The EDG includes several novelties:

  • The introduction of a new expression-result structure to represent expressions. It allow us to distinguish between an expression and its result (e.g., as the slicing criterion).
  • The identification and formal definition of a new inter-expression dependence called value-dependence.
  • The formal definition of declaration dependence, which accounts for the declaration-definition relationship, besides the definition-use relationship (flow dependence).
  • The EDG allows for specifying new kinds of slicing criteria.
  • A slicing criterion can be a variable (as usual), but also any other (sub)expression (e.g., a list comprehension or a conditional expression).

Example

Consider the following Erlang file:

-module(test).
-compile([foo/2]).

-type date() :: {Integer,Integer,Integer}.
-spec main([date()],[date()]) -> any().
foo(X,Y) -> 
  Z = length(Y) == 0
  case Z of
    true -> Y;
    false -> X
  end.

length([]) -> 0;
length(_) -> 1.

Its corresponding EDG would be:

It can also be downloaded in PDF.

Feedback

We appreciate any feedback from the users of this software. Any contribution that can help us to improve the precision of this tool is welcomed. More information is available in the contact page.

Made in the Universitat Politècnica de València (UPV)

This software has been designed and implemented in the computer science labs of the UPV.