by María Alpuente, Santiago Escobar and Salvador Lucas.

A number of researchers have noticed that certain processes of optimization, transformation, specialization and reuse of code often introduce anomalies in the generated code that programmers usually (or ideally) do not write [ASU86, Hugh86, LS96, LS02].

An example is the introduction of redundant arguments in the functions defined in the program. Redundancy of a parameter means that replacing it by any expression does not change the result.

Consider the following program, which calculates the last element of a list and the concatenation of two lists of natural numbers, respectively:

data Nat = 0 | S Nat

append::[Nat] -> [Nat] -> [Nat]      last::[Nat] -> Nat
append nil    y = y                  last (x:nil) = x
append (x:xs) y = x:(append xs y)    last (x:y:ys) = last (y:ys)

Assume that we specialize this program for the call applast ys z = last (append ys (z:nil)) which appends an element z at the end of a given list ys and then returns the last element, z, of the resulting list (the example is borrowed from DPPD library of benchmarks). Commonly, the optimized program which can be obtained by using an automatic specializer of functional programs such as INDY or PEVAL is:

applast::[Nat] -> Nat -> Nat          lastnew::Nat -> [Nat] -> Nat -> Nat
applast nil z = z                     lastnew x nil z = z
applast (x:xs) z = lastnew x xs z     lastnew x (y:ys) z = lastnew y ys z

This program is too far from {applast' ys z = lastnew' z, lastnew' z = z} a more feasible program, or even the ``optimal'' program (without redundant parameters) {applast'' z = z} which one would ideally expect (here the rule for the ``local'' function lastnew' is disregarded, since it is not useful when the definition of applast' is optimized).

Indeed, note that the first argument of the function applast is redundant (as well as the first and second parameters of the auxiliary function lastnew) and would not typically be written by a programmer who writes this program by hand. Also note that standard (post-specialization) renaming/compression procedures cannot perform this optimization as they only improve programs where program calls contain dead functors or multiple occurrences of the same variable, or the functions are defined by rules whose rhs's are normalizable [AFJV97, Gal93, GS94]. Known procedures for removing dead code such as [BCDG00, Kob00,LS02] do not apply to this example either.

It seems interesting to develop program analysis techniques for detecting these kinds of redundancies as well as to perform transformations for eliminating dead code which appears in the form of redundant function arguments and which, in some cases, can be safely erased without jeopardizing correctness. We have developed a methodology for the detection and removal of redundant arguments of functions, which is available here.

A prototype system for the analysis and removal of redundant arguments has been developed. The prototype has been implemented in PAKCS the current distribution of the multi-paradigm declarative language Curry. The implementation works as a source to source program transformation for TRSs written in Curry syntax. In concrete, it detects and removes redundant arguments in orthogonal, terminating and completely defined constructor systems.

The system includes a redundancy analyzer and an erasure procedure. The complete implementation consists of about 250 rules (800 lines of code). The analizer is expressed by 75 rules, the erasure procedure by 85 rules, and the meta-interpreter and other helpful facilities by 90 rules.

We have used the prototype to optimize dozens of examples. Preliminary experiments with the system show that our methodology does detect and remove redundant arguments of many common transformation benchmarks. Click here to see our experiments.

Here you can get the elimination useless argument elimination system with some benchmark examples .

[AFJV97] M. Alpuente, M. Falaschi, P. Julián, and G. Vidal. Specialization of Lazy Functional Logic Programs. In Proc. of PEPM'97, ACM Sigplan Notices, volume 32(12):151-162. ACM Press, New York, 1997.

[ASU86] A.V. Aho, R. Sethi, and J.D. Ullman. Compilers, Principles, Techniques and Tools. Addison-Wesley, 1986.

[BCDG00] S. Berardi, M. Coppo, F. Damiani and P. Giannini. Type-Based Useless-Code Elimination for Functional Programs. \newblock In Walid Taha, editor, Proc. of SAIG 2000, LNCS 1924:172-189, Springer-Verlang, 2000.

[Gal93] J. Gallagher. Tutorial on Specialisation of Logic Programs. In Proc. of PEPM'93, pages 88--98. ACM, New York, 1993.

[GS94] R. Glück and M. Sørensen. Partial deduction and driving are equivalent. In Proc. of PLILP'94, LNCS 844:165-181. Springer-Verlag, Berlin, 1994.

[Hugh86] J. Hughes. Backwards Analysis of Functional Programs. In D. Bjorner, A.P. Ershov, and N.D. Jones, editors, IFIP Workshop on Partial Evaluation and Mixed Computation, pages 187-208, 1988.

[Kob00] N. Kobayashi. Type-based useless variable elimination. In Proc. of PEPM-00, pages 84-93, ACM Press, 2000.

[LS96] M. Leuschel and M. H. Sørensen. Redundant Argument Filtering of Logic Programs. In Proc of LOPSTR'96, LNCS 1207:83-103. Springer-Verlag, Berlin, 1996.

[LS02] Y. A. Liu and S. D. Stöller. Eliminating dead code on recursive data. Science of Computer Programming, 2002. To appear. Preliminary version in Proc. of SAS'99, LNCS 1694:211-231. Springer-Verlag, Berlin, 1999.

Last update Feb 2002 # sescobar@dsic.upv.es