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)

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

*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**.

[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.

ELP | GPLIS | DSIC | UPV |

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