Two languages for estimating program efficiency

ABSTRACT

Two languages enabling their users to estimate the efficiency of computer programs are presented. The program whose efficiency one wishes to estimate is written in the first language, a go-to-less programming language which includes most of the features of Algol 60. The second language consists of interactive commands enabling its users to provide additional information about the program written in the first language and to output results estimating its efficiency. Processors for the two languages are also described. The first processor is a syntax-directed translator which compiles a program into a symbolic formula representing the execution time for that program. The second processor is a set of procedures for algebraic manipulation which can be called by the user to operate on the formula produced by the first processor. Examples of the usage of the two languages are included. The limitations of the present system, its relation to Knuth's work on the analysis of algorithms, and some of the directions for further research are also discussed.

REFERENCES

• 1: Ahmad, A. The computing speed of a new machine. Computer J. 16, 2 (May 1973), 161-164.
• 2: Ashcroft, E., and Manna, Z. The translation of'go-to' programs to 'while' programs. Proc. IFIP 1971 Cong. North Holland Pub. Co., Amsterdam, 1972.
• 3: Boothroyd, J. Algorithm 231, Matrix inversion, Calgol, ACM, New York.
• 4: Cohen, J. et al. A compiler generator, Brandeis U., Waltham, Mass., 1972.
• 5: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 6: Bernard Elspas , Karl N. Levitt , Richard J. Waldinger , Abraham Waksman, An Assessment of Techniques for Proving Program Correctness, ACM Computing Surveys (CSUR), v.4 n.2, p.97-147, June 1972 [doi>10.1145/356599.356602]
• 7: Floyd, R.W. Toward interactive design of correct programs. Proc. 1971 IFIP Cong. North Holland Pub. Co., Amsterdam, 1972.
• 8: Fitch, J.P. On algebraic simplification. Computer J. 16, 1 (Feb. 1973), 23-27.
• 9: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: Knuth, D.E. Mathematical analysis of algorithms. Proc. 1971 IFIP Cong., North Holland Pub. Co., Amsterdam, 1972.
• 12: McKeeman, W.M., Homing, J.H., and Wortman, D.B. A Compiler Generator. Prentice-Hall, Englewood Cliffs, NJ., 1970.
• 13: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 14: Paul S. Wang, Automatic computation of limits, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.458-464, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806315]
• 15: Wooldridge, D. An algebraic simplify in Lisp. AI Project. Memo 11, Stanford U. Stanford, Calif., 1963.
• 16: The Macsyma Reference Manual, Proj. MAC, MIT, Cambridge, Mass., June 1973.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
analysis of algorithms, program efficiency, programming languages, symbolic manipulation, syntax-directed translation