Binding performance at language design time

ABSTRACT

An important research goal in software engineering and programming languages is the development of principles underlying the specification of computable problems, the translation of these problems into efficient and correct programs, and the performance analysis of these programs. This paper uncovers some of these principles, which are used to design a problem specification language L1 restricted to problems that can be compiled automatically into programs whose worst case asymptotic time and space complexities are linear in the input/output space. Any problem expressible in L1 can be compiled into a linear cost program. A compiler for L1 has been implemented in the RAPTS transformational programming system.

REFERENCES

• 1: Aho, A., Hopcroft, 3, and Ullman, J.. Demion and AnoAileis o} Computer A~Torithra,. Addison-Wesley, 1974.
• 2: Aho, A., Sethi, R., and Ullman, J. , Comln~erB. Addison-Wesley , 1986.
• 3: R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984 [doi>10.1145/1780.1781]
• 4: Birkhoff, G.. Lattice Theory. American Mathematical Society, Providence, 1066.
• 5: Cai1 J. and Paige, R. Transformational Derivation of Constant Propagation Programs. submitted.
• 6: Chomsky, N. "On Certain Formal Properties of Grammars". ln/o. and Control ~ (1959), 137-167.
• 7: Dijkstra, E. W.. A Discipline o} Programm/W. Prentice-Hall, 1976.
• 8: Earley, J. UHigh Level lterators and a Method for Automatically Designing Data Structure Representation". Journal of Computer Lanquages i, 4 (1976), 321.342.
• 9: G ratzet, G.. Genera/Lattice Theol. Birkhauter, 1978.
• 10: Gurevlch, Y. and Shelah, S. Fixed-point Extensions of First-order Logic, 26th IEEE Syrup. on FOCS, 1985,
• 11: Harel, D. and Kozen, D. "A Programming Language for the Inductive Sets, and Appllcationsn. l~/ornm~on and Control B& 2 (1985), 1-27.
• 12: Harrison, M. Set Comparison Using Hashing Techniques. Tech. Rept. .NYO-1480.155, NYU, 1970.
• 13: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: Neil Immerman, Relational queries computable in polynomial time (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.147-152, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802187]
• 15: Neil Immerman, Languages which capture complexity classes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.347-354, December 1983 [doi>10.1145/800061.808765]
• 16: Knuth, D, "Semantics of Context-free Languages". MatAsnus6~a/ Systems Theoq~ f, 2 (1968).
• 17: Mehlhorn, K.. Data b~ructurem and Aioorlthnu. Volume l:$ort/nf and Scarchin~. Spriuger-Verlag, 1984.
• 18: Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567076]
• 19: Paige, R. Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. In AdoanceJ In DatabaJe Theorp, Volume ~, Gailaire, H., Minker, J., and Nicolas, J.-M., Ed., Plenum Press, New York, 1984, pp. 171-210.
• 20: Robert Paige , Fritz Henglein, Mechanical Translation of Set Theoretic Problem Specifications into Efficient RAM Code - A Case Study, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.554-567, April 01-03, 1985
• 21: Paige, R., Tarjan, R., and Bonic, R. "A Linear Time Solution to the Single Function Coarsest Partition Problem'. TCS 40, 1 (Sep 1985), 67-84.
• 22: Palge, R. "Programming With lnvariants~. IEEE Software $~ 1 (Jan ; 986), 56-69.
• 23: Paige, R. and Schonberg, E. Efficient Set Based Progre~mming. in preparation.
• 24: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 25: Papadimitriou, C. "A Note On The Expressive Power of PROLOG". Btdlflin o/EATCS ~ (1985), 21-23.
• 26: Reif,,}.H. and Lewis,H.R.. Symbolic e~ahtation and the global ~ahte graph. Harvard University, Aiken Computation Laboratory, 1982.
• 27: Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.126-143, April 1981 [doi>10.1145/357133.357135]
• 28: Schwartz, J.T.. On Pro~ammin#: An Interim Report on the SETL Project, in=taUment# { and IL CIMS, New York Univ., New York, 1974.
• 29: J. T. Schwartz, Automatic data structure choice in a language of very high level, Communications of the ACM, v.18 n.12, p.722-728, Dec. 1975 [doi>10.1145/361227.361235]
• 30: Schwartz, J. T. Correct Program Technology. Tech. l~ept. Courant Computer Science Report Num. 12, CIMS, New York University, Sep, 1977.
• 31: Suppes, P.. Aziomatic Set Theorl/. Dover, 1972.
• 32: Tarjan, It. Amortized computational complexity. SIAM J. A|g. Disc, Mesh. to appear.
• 33: Tarski, A. ~A Lattice-Theoretical Fixpoint Theorem and its Application". Pacific Jonrn~ oJ Mathematic., 5 (1955), 285-309.
• 34: Aaron Melvin Tenenbaum, Type determination for very high level languages., 1974
• 35: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 36: Willard, D. Prc&cate Oeiented Dcl~zbasc Search Al~orV.hrn~. Ph.D. Th., Harvard U., 1978.
• 37: Willard, D. Abstract Predicate Retrieval Theory. State University of ,~ew York at Albany~ Albany, New York 12222, Aug, 1983.
• 38: Dan E Willard, Efficient processing of relational calculus expressions using range query theory, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Design, Languages, Performance, Theory