ACE: an automatic complexity evaluator

ABSTRACT

There has been a great deal of research done on the evaluation of the complexity of particular algorithms; little effort, however, has been devoted to the mechanization of this evaluation. The ACE (Automatic Complexity Evaluator) system is able to analyze reasonably large programs, like sorting programs, in a fully mechanical way. A time-complexity function is derived from the initial functional program. This function is transformed into its nonrecursive equivalent according to MacCarthy's recursion induction principle, using a predefined library of recursive definitions. As the complexity is not a decidable property, this transformation will not be possible in all cases. The richer the predefined library is, the more likely the system is to succeed. The operations performed by ACE are described and the use of the system is illustrated with the analysis of a sorting algorithm. Related works and further improvements are discussed in the conclusion.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: John Backus, The Algebra of Functional Programs: Function Level Reasoning, Linear Equations, and Extended Definitions, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.1-43, April 19-25, 1981
• 4: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 5: Jacques Cohen, Computer-assisted microanalysis of programs, Communications of the ACM, v.25 n.10, p.724-733, Oct 1982 [doi>10.1145/358656.358674]
• 6: DARLINGTON, J., AND BURSTALL, R.M. A system which automatically improves programs. Acta Inf. 6, 1 (1976), 41-60.
• 7: DARLINGTON, J. Program transformation. In Functional Programming and Its Applications. J. Darlington, P. Henderson, and D. Turner, Eds. Cambridge University Press, 1982.
• 8: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• 9: John Guttag , James Horning , John Williams, FP with data abstraction and strong typing, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.11-24, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806758]
• 10: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 11: LE M~TAYER, D. Analysis of functional programs by program transformation. In Proceedings of 1987 France-Japan Artificial Intelligence and Computer Science Symposium (Cannes, 1987). North-Holland, Amsterdam.
• 12: MACCARTHY, J. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems. P. Braffort, and D. Hirsberg, Eds. North-Holland, Amsterdam, 1963.
• 13: Zohar Manna , Stephen Ness , Jean Vuillemin, Inductive methods for proving properties of programs, Communications of the ACM, v.16 n.8, p.491-502, Aug. 1973 [doi>10.1145/355609.362336]
• 14: Donald F. Stanat , David F. McAllister, Discrete Mathematics in Computer Science, Prentice Hall Professional Technical Reference, 1977
• 15: Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
• 16: WEGBREIT, B. Goal-directed program transformation. IEEE Trans. Softw. Eng. SE-2, 2 (June 1976), 69-80.
• 17: John H. Williams, On the Development of the Algebra of Functional Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.733-757, Oct. 1982 [doi>10.1145/69622.357193]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation; Program synthesis

General Terms:
Languages, Measurement, Performance