Towards a Normal Form for Mercury Programs
In this work we define a program transformation that normalises a Mercury program by reordering clauses, body goals, and predicate arguments. The transformation, which preserves the well-modedness and determinism characteristics of the program, aims at re
- PDF / 478,060 Bytes
- 16 Pages / 430 x 660 pts Page_size
- 81 Downloads / 195 Views
Abstract. In this work we define a program transformation that normalises a Mercury program by reordering clauses, body goals, and predicate arguments. The transformation, which preserves the well-modedness and determinism characteristics of the program, aims at reducing the complexity of performing a search for duplicated or similar code fragments between programs. In previous work, we have defined an analysis that searches for such duplicated functionality basically by pairwise comparing atoms and goals. While feasible in theory, the number of permutations to perform during the search renders it hard if not impossible to use in practice. We conjecture that the transformation to normal form, defined in this work, allows to substantially reduce the number of permutations, and hence the complexity of the search.
1
Introduction and Motivation
The problem of deciding whether two code fragments are equivalent, in the sense that they implement the same functionality, is well-known to be undecidable. Nevertheless, there seems to be an interest in developing analyses that are capable to detect such equivalence under particular circumstances and within a certain error margin [3,1,12]. Applications can be found in plagiarism detection and tools for program refactoring. Work in this area can be based on parametrised string matching, an example being the MOSS system [8], or perform a more involved analysis on a graph representation of a program [2,13]. Most of these latter works, including the more recent [11], concentrate on finding behavioral differences between strongly related programs and are often limited to (subsets of) imperative programs. In recent work [10], we have studied the conditions under which two (fragments of) logic programs can be considered equivalent. The main motivation of that and the current work is to develop an analysis capable of detecting program fragments that are susceptible for refactoring, aiming in particular to the removal of duplicated code or to the generalisation of two related predicates into a new (higher-order) one. The basic idea is as follows: two code fragments (be they goals, clauses or complete predicate definitions) are equivalent if they are isomorphic in the sense that one can be considered to be a renaming of the other King, A. (Ed.): LOPSTR 2007, LNCS 4915, pp. 43–58, 2008. c Springer-Verlag Berlin Heidelberg 2008
44
F. Degrave and W. Vanhoof
modulo a permutation of the body goals and the arguments of the predicate. Take for example the definitions of app1 and conc1 below: app1([],Y,Y). app1([Xe|Xs],Y,[XN|Zs]):- XN is Xe + 1, app1(Xs,Y,Zs). conc1(A,[],A). conc1([NB|As],[Be|Bs],C):- conc1(As,Bs,C), NB is Be + 1.
Both definitions basically implement the same ternary relation in which one argument is the result of concatenating both other arguments and incrementing each element by one. This can easily be deduced from the source code, since the definition of conc1 can be obtained from that of app1 by variable renaming, goal reordering and a permutation of the argument positions.
Data Loading...
