Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-05T11:45:42.235Z Has data issue: false hasContentIssue false
  • English
  • Français

Removing redundant arguments automatically

Published online by Cambridge University Press:  01 January 2007

M. ALPUENTE ,
S. ESCOBAR  and
S. LUCAS
M. ALPUENTE
Affiliation:
DSIC, UPV, Camino de Vera s/n, E-46022 Valencia, Spain (e-mail: [email protected],[email protected],[email protected])
S. ESCOBAR
Affiliation:
DSIC, UPV, Camino de Vera s/n, E-46022 Valencia, Spain (e-mail: [email protected],[email protected],[email protected])
S. LUCAS
Affiliation:
DSIC, UPV, Camino de Vera s/n, E-46022 Valencia, Spain (e-mail: [email protected],[email protected],[email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The application of automatic transformation processes during the formal development and optimization of programs can introduce encumbrances in the generated code that programmers usually (or presumably) do not write. 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. In this work, we provide methods for the analysis and elimination of redundant arguments in term rewriting systems as a model for the programs that can be written in more sophisticated languages. On the basis of the uselessness of redundant arguments, we also propose an erasure procedure which may avoid wasteful computations while still preserving the semantics (under ascertained conditions). A prototype implementation of these methods has been undertaken, which demonstrates the practicality of our approach.

Keywords

redundant arguments in functionssemantics-preserving program transformationanalysis and optimizationterm rewriting
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 7 , Issue 1-2 , January 2007 , pp. 3 - 35
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aho, A., Sethi, R. and Ullman, J. 1986. Compilers, Principles Techniques and Tools. Addison-Wesley, Reading, MA.Google Scholar
Alpuente, M., Echahed, R., Escobar, S. and Lucas, S. 2002a. Redundancy of Arguments Reduced to Induction. In Proc. of the 11th Int'l Workshop on Functional and (Constraint) Logic Programming WFLP'02, Comini, M. and Falaschi, M., Eds. Electronic Notes in Theoretical Computer Science, vol. 76. Elsevier Sciences Publisher, 100–200.Google Scholar
Alpuente, M., Escobar, S. and Lucas, S. 2002b. Removing Redundant Arguments of Functions. In 9th International Conference on Algebraic Methodology And Software Technology, AMAST 2002, Kirchner, H. and Ringeissen, C., Eds. Lecture Notes in Computer Science, vol. 2422. Springer-Verlag, Berlin, 117–131.Google Scholar
Alpuente, M., Escobar, S. and Lucas, S. 2006. Removing Redundant Arguments Automatically. CoRR cs.PL/0601039. Available at http://arxiv.org/abs/cs.PL/0601039.Google Scholar
Alpuente, M., Falaschi, M., Julián, P. and Vidal, G. 1997. Specialization of Lazy Functional Logic Programs. In Proc. of the ACM SIGPLAN Conf. on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'97. ACM Sigplan Notices, vol. 32, number 12. ACM Press, New York, 151–162.Google Scholar
Alpuente, M., Falaschi, M. and Vidal, G. 1998. Partial Evaluation of Functional Logic Programs. ACM Transactions on Programming Languages and Systems 20, 4, 768–844.CrossRefGoogle Scholar
Alpuente, M., Hanus, M., Lucas, S. and Vidal, G. 1999. Specialization of Inductively Sequential Functional Logic Programs. In Proc. of the ACM SIGPLAN Conf. on Functional Programming, ICFP'99, Lee, P., Ed. ACM Sigplan Notices, vol. 34, number 9. ACM Press, New York, 273–283.Google Scholar
Arts, T. and Giesl, J. 2001. A collection of examples for termination of term rewriting using dependency pairs. Tech. Rep. AIB-2001-09, RWTH Aachen, Germany.Google Scholar
Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.Google Scholar
Berardi, S., Coppo, M., Damiani, F. and Giannini, P. 2000. Type-based useless-code elimination for functional programs. In Proceedings of SAIG 2000. Lecture Notes in Computer Science, vol. 1924. Springer-Verlag, Berlin, 172–189.Google Scholar
Bert, D., Echahed, R. and Østvold, B. 1993. Abstract Rewriting. In Proc. of Third Int'l Workshop on Static Analysis, WSA'93. Lecture Notes in Computer Science, vol. 724. Springer-Verlag, Berlin, 178–192.Google Scholar
Burn, G. 1991. Lazy Functional Languages: Abstract Interpretation and Compilation. Pitman, London.Google Scholar
Burn, G. L., Hankin, C. L. and Abramsky, S. 1986. The Theory of Strictness Analysis for Higher Order Functions. In Programs as Data Objects. Lecture Notes in Computer Science, vol. 217. Springer-Verlag, Berlin, 42–62.Google Scholar
Comon, H. 2000. Sequentiality, second order monadic logic, and tree automata. Information and Computation 157, 25–51.Google Scholar
Contejean, E., Marché, C., Monate, B. and Urbain, X. 2003. Proving termination of rewriting with CiME.. In Rubio, A., editor, Proc. of 6th International Workshop on Termination, WST'03, pages 71-73, Technical Report DSIC II/15/03, Valencia, Spain, 2003. Available at http://cime.lri.fr.Google Scholar
Cousot, P. and Cousot, R. 1994. Higher-order abstract interpretation (and application to comportment analysis generalizing strictness, termination, projection and PER analysis of functional languages), invited paper. In Proceedings of the 1994 International Conference on Computer Languages, ICCL'94. IEEE Computer Society Press, Los Alamitos, California, Toulouse, France, 95–112.Google Scholar
Dauchet, M., Heuillard, T., Lescanne, P. and Tison, S. 1987. Decidability of the Confluence of Finite Ground Term Rewrite Systems and of Other Related Term Rewrite Systems. Proc. of Second IEEE Symp. on Logic In Computer Science, 353–359.Google Scholar
Dauchet, M., Heuillard, T., Lescanne, P. and Tison, S. 1990. Decidability of the Confluence of Ground Term Rewriting Systems. In Information and Computation. 88. Academic Press, New York, 187–201.Google Scholar
Durand, I. and Middeldorp, A. 1997. Decidable Call by Need Computations in Term Rewriting. In Proc. of CADE'97, McCune, W., Ed. Lecture Notes in Artificial Intelligence, vol. 1249. Springer-Verlag, Berlin, 4–18.Google Scholar
Gallagher, J. 1993. Tutorial on Specialisation of Logic Programs. In Proc. of Partial Evaluation and Seman-tics-Based Program Manipulation, Copenhagen, Denmark, June 1993. ACM, New York, 88–98.Google Scholar
Gallier, J. and Book, R. 1985. Reductions on tree replacement systems. Theoretical Computer Science 37, 2, 123–150.Google Scholar
Giesl, J., Thiemann, R., Schneider-Kamp, P. and Falke, S. 2004. Automated Termination Proofs with AProVE. In Oostrom, V. van, editor, Proc. of 15h International Conference on Rewriting Techniques and Applications, RTA'04, LNCS 3091:210-220, Springer-Verlag, Berlin, 2004. Available at http://www-i2.informatik.rwth-aachen.de/AProVE.Google Scholar
Glück, R. and Sørensen, M. 1994. Partial Deduction and Driving are Equivalent. In Proc. of PLILP'94. Lecture Notes in Computer Science, vol. 844. Springer-Verlag, Berlin, 165–181.Google Scholar
Godoy, G. and Tiwari, A. 2004. Deciding Fundamental Properties of Right-(Ground or Variable) Rewrite Systems by Rewrite Closure. In Basin, D. and Rusinowitch, M., editors, International Joint Conference on Automated Deduction, IJCAR'04, LNAI 3097:91–106, Springer-Verlag, Berlin, 2004.Google Scholar
Gouranton, V. 1998. Deriving Analysers by Folding/Unfolding of Natural Semantics and a Case Study: Slicing. In Proc. of the 5th International Static Analysis Symposium, SAS'98. Lecture Notes in Computer Science, vol. 1503. Springer-Verlag, Berlin, 115–133.Google Scholar
Gramlich, B. 2001. On interreduction of semi-complete term rewriting systems. Theoretical Computer Science 258, 1–2, 435–451.Google Scholar
Hanus, M. 1994. The Integration of Functions into Logic Programming: From Theory to Practice. Journal of Logic Programming 19&20, 583–628.Google Scholar
Hanus, M., Antoy, S., Engelke, M., Höppner, K., Koj, J., Niederau, P., Sadre, R. and Steiner, F. 2003a. PAKCS 1.5.0: The Portland Aachen Kiel Curry System User Manual. Tech. rep., University of Kiel, Germany.Google Scholar
Hanus, M., Antoy, S., Kuchen, H., López-Fraguas, F., Lux, W., Moreno, Navarro J., and Steiner, F. 2003b. Curry: An Integrated Functional Logic Language (version 0.8). Available at http://www.informatik.uni-kiel.de/curry.Google Scholar
Hanus, M. and Lucas, S.. 2001. An Evaluation Semantics for Narrowing-Based Functional Logic Languages. Journal of Functional and Logic Programming, 2001 (2): 1–43.Google Scholar
Hendrix, J., Clavel, M. and Meseguer, J. 2005. A Sufficient Completeness Reasoning Tool for Partial Specifications. In Giesl, Jürgen, editor, Proc. of 16h International Conference on Rewriting Techniques and Applications, RTA'05, LNCS 3467:165–174, Springer-Verlag, Berlin, 2005. Available at http://maude.cs.uiuc.edu/tools/scc.Google Scholar
Hofbauer, D. 2003. An upper bound on the derivational complexity of Knuth-Bendix orderings. Information and Computation 183 (1):43–56.CrossRefGoogle Scholar
Huet, G. and Lévy, J.-J. 1991. Computations in Orthogonal Term Rewriting Systems, Part I + II. In Computational logic: Essays in honour of J. Alan Robinson. The MIT Press, Cambridge, MA, 395–414 and 415–443.Google Scholar
Hughes, J. 1988. Backwards Analysis of Functional Programs. In IFIP Workshop on Partial Evaluation and Mixed Computation (Amsterdam), Bjørner, D., Ershov, A., and Jones, N., Eds. 187–208.Google Scholar
Jacquemard, F. 1996. Decidable approximations to term rewriting systems. In Proc. of 7th International Conference on Rewriting Techniques and Applications, RTA'96, Ganzinger, H., Ed. Lecture Notes in Computer Science, vol. 1103. Springer-Verlag, Berlin, 362–376.CrossRefGoogle Scholar
Jensen, T. P. 1991. Strictness Analysis in Logical Form. In Proc of International Conference on Functional Programming Languages and Computer Architecture, Hughes, R. J. M., Ed. Lecture Notes in Computer Science, vol. 523. Springer-Verlag, Berlin, 352–366.Google Scholar
Jones, S. B. and Métayer, D. L. 1989. Compile-time garbage collection by sharing analysis. In Proc of International Conference on Functional Programming Languages and Computer Architecture. ACM Press, New York, 54–74.Google Scholar
Kapur, D., Narendran, P. and Zhang, Z. 1987. On sufficient-completeness and related properties of term rewriting systems. Acta Informatica 24, 395–416.Google Scholar
Kapur, D., Narendran, P., Rosenkrantz, D. J. and Zhang, Z. 1991. Sufficient-completeness, ground-reducibility, and their complexity. Acta Informatica 28, 311–350.Google Scholar
Kennaway, R., van Oostrom, V. and de Vries, F. 1996. Meaningless terms in rewriting. In Proceedings of the ALP'96. Lecture Notes in Artificial Intelligence, vol. 1139. Springer-Verlag, 254–268.Google Scholar
Klop, J. 1992. Term Rewriting Systems. In Handbook of Logic in Computer Science, Abramsky, S., Gabbay, D., and Maibaum, T., Eds. Vol. 3. Oxford University Press, Oxford, 1–116.Google Scholar
Knoop, J., Rüthing, O. and Steffen, B. 1994. Partial Dead Code Elimination. Proceedings of the International Conference on Programming Language Design and Implementation (PLDI'94) 29, 6, 147–158.Google Scholar
Kobayashi, N. 2000. Type-based useless variable elimination. In Proceedings of PEPM-00. ACM Press, New York, 84–93.Google Scholar
Kounalis, E. 1985. Completeness in data type specifications. In Proc. of European Conference on Computer Algebra, EUROCAL'85, Caviness, B., Ed. Lecture Notes in Computer Science, vol. 204. Springer-Verlag, Berlin, 348–362.Google Scholar
Kuper, J. 1994. Partiality in logic and computation. aspects of undefinedness. Ph.D. thesis, Universiteit Twente.Google Scholar
Leuschel, M. 1998. On the Power of Homeomorphic Embedding for Online Termination. In Proc. of the 5th International Static Analysis Symposium, SAS'98, Levi, G., Ed. Lecture Notes in Computer Science, vol. 1503. Springer-Verlag, Berlin, 230–245.Google Scholar
Leuschel, M. and Martens, B. 1995. Partial Deduction of the Ground Representation and Its Application to Integrity Checking. Tech. Rep. CW 210DSIC-II/8/02, K.U. Leuven.Google Scholar
Leuschel, M. and Sørensen, M. H. 1996. Redundant Argument Filtering of Logic Programs. In Proceedings of the 6th International Workshop on Logic Program Synthesis and Transformation (LOPSTR'96), Gallager, J., Ed. Lecture Notes in Computer Science, vol. 1207. Springer-Verlag, Berlin, Stockholm, Sweden, 83–103.Google Scholar
Liu, Y. A. and Stoller, S. D. 2002. Eliminating dead code on recursive data. Science of Computer Programming.Google Scholar
Lucas, S. 2001. Transfinite Rewriting Semantics for Term Rewriting Systems. In Proc. of 12th Int'l Conf. on Rewriting Techniques and Applications, RTA'01, Middeldorp, A., Ed. Lecture Notes in Computer Science, vol. 2051. Springer-Verlag, Berlin, 216–230.Google Scholar
Mitsuhashi, I. and Oyamaguchi, M. and Ohta, Y. and Yamada, T. 2004. The Joinability and Unification Problems for Confluent Semi-constructor TRSs. In Proc. of 15th Int'l Conf. Rewriting Techniques and Applications, RTA'04, Oostrom, V. van, Ed. Lecture Notes in Computer Science, vol. 3091. Springer-Verlag, Berlin, 285–300.Google Scholar
Mycroft, A. 1980. The theory and practice of transforming call by need into call by value. In 4th International Symposium on Programming, Robinet, B., Ed. Lecture Notes in Computer Science, vol. 83. Springer-Verlag, Berlin, 269–281.Google Scholar
Mycroft, A. and Norman, A. 1992. Optimising compilation. Part ii: lazy functional languages. In XIX Seminar on Current Trends in Theory and Practice of Informatics, SOFSEM'92, Ždiar, Czechoslovakia. Available at http://www.cl.cam.ac.uk/~am/papers/sofsem92b.ps.gz.Google Scholar
Oyamaguchi, M. 1986. The reachability problems for quasi-ground for term rewriting systems. Journal of Information Processing 9, 4, 232–236.Google Scholar
Oyamaguchi, M. 1990. The reachability and joinability problems for right-ground term rewriting systems. Journal of Information Processing 13, 3, 347–354.Google Scholar
Padawitz, P. 1988. Computing in Horn Clause Theories. EATCS Monographs on Theoretical Computer Science, vol. 16. Springer-Verlag, Berlin.CrossRefGoogle Scholar
Park, Y. G. and Goldberg, B. 1992. Escape Analysis on Lists. Proceedings of the International Conference on Programming Language Design and Implementation (PLDI'92) 27, 7, 116–127.Google Scholar
Pettorossi, A. and Proietti, M. 1994. Transformation of Logic Programs: Foundations and Techniques. Journal of Logic Programming 19, 20, 261–320.Google Scholar
Pettorossi, A. and Proietti, M. 1996a. A Comparative Revisitation of Some Program Transformation Techniques. In Proc. of the 1996 Dagstuhl Seminar on Partial Evaluation. Lecture Notes in Computer Science, vol. 1110. Springer-Verlag, Berlin, 355–385.Google Scholar
Pettorossi, A. and Proietti, M. 1996b. Rules and Strategies for Transforming Functional and Logic Programs. ACM Computing Surveys 28, 2, 360–414.Google Scholar
Plasmeijer, R. and van Eekelen, M. 1993. Functional Programming and Parallel Graph Rewriting. Addison Wesley.Google Scholar
Rabin, M. O. 1969. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society 141, 1–35.Google Scholar
Reps, T. and Turnidge, T. 1996. Program Specialization via Program Slicing. In Partial Evaluation, Int'l Seminar, Dagstuhl Castle, Germany, Danvy, O., Glück, R., and Thiemann, P., Eds. Lecture Notes in Computer Science, vol. 1110. Springer-Verlag, Berlin, 409–429.Google Scholar
Schoenig, S. and Ducasse, M. 1996. A Backward Slicing Algorithm for Prolog. In Proc. of the 3rd International Static Analysis Symposium, SAS'96. Lecture Notes in Computer Science, vol. 1145. Springer-Verlag, Berlin, 317–331.Google Scholar
Sekar, R., Pawagi, S. and Ramakrishnan, I. 1990. Small domains spell fast strictness analysis. In 16th Annual ACM Symposium on Principles of Programming Languages, POPL'89. ACM Press, New York, 169–183.Google Scholar
Szilagyi, G., Gyimothy, T., and Maluszynski, J. 2002. Static and Dynamic Slicing of Constraint Logic Programs. Journal of Automated Software Engineering 9, 1, 41–65.Google Scholar
TeReSe, Ed. 2003. Term Rewriting Systems. Cambridge University Press, Cambridge.Google Scholar
Thatcher, J. W. and Wright, J. B. 1968. Generalized finite automata with an application to a decision problem of second-order logic. Math. Systems Theory 2, 57–82.Google Scholar
Thomas, W. 1990. Automata on infinite objects. In Handbook of Theoretical Computer Science, van Leeuwen, J., Ed. Vol. B: Formal Models and Semantics. Elsevier, Amsterdam and The MIT Press, Cambridge, Mass, 133–191.Google Scholar
Tip, F. 1995. A Survey of Program Slicing Techniques. Journal of Programming Languages 3, 121–189.Google Scholar
Verma, M.-R. 2002, Algorithms and Reductions for Rewriting Problems II. Information Processing Letters 84 (4):227–233.Google Scholar
Wadler, P. and Hughes, R. 1987. Projections for Strictness Analysis. In Proc of International Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, vol. 274. Springer-Verlag, Berlin, 385–407.CrossRefGoogle Scholar
Wand, M. and Siveroni, I. 1999. Constraint systems for useless variable elimination. In Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL'99). ACM Press, New York, 291–302.Google Scholar
Weiser, M. 1984. Program Slicing. IEEE Transactions on Software Engineering 10, 4, 352–357.CrossRefGoogle Scholar