Automatic data structure choice in a language of very high level

ABSTRACT

SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This paper sets forth techniques for the logical analysis and optimization of SETL programs. The techniques described allow relations of inclusion and membership to be established, the domains and ranges of (tabulated) mappings to be estimated from above and below, and the singlevaluedness of (tabulated) mappings to be proved. Once facts of this kind have been established, automatic choice of data structures becomes possible. The methods employed are based upon, and extend, known techniques of data-flow analysis.

REFERENCES

• 1: F. E. Allen {1} A Basis for Program optimization, Proceedings of the IFIP Congress, 1971, North-Holland Publishing Co., Amsterdam.
• 2: {2} Interprocedural Data Flow Analysis, Proceedings of the IFIP Congress, 1974, North Holland Publishing Co., Amsterdam.
• 3: James Richard Low, Automatic coding: choice of data structures., 1974
• 4: J. B. Morris {1} A Comparison of MADCAP and SETL, Los Alamos Sci. Lab., University of California, Los Alamos, New Mexico, 1973.
• 5: J. T. Schwartz {1} On Programming: An Interim Report on the SETL Project. Installment 1. Generalities. Installment 2. The SETL Language and Examples of its Use. 520 pp., New York University, 1973.
• 6: {2} Deducing Relationships of Inclusion and Membership in SETL Programs. SETL Newsletter No. 130, New York University, 1974.
• 7: {3} More on Copy Optimization of SETL Programs. SETL Newsletter No. 131, New York University, June 1974.
• 8: {4} Deducing the Logical Structure of Objects Appearing in SETL Programs. SETL Newsletter No. 71, New York University, April 1972.
• 9: {5} Inter-Procedural Optimization. SETL Newsletter No. 134, New York University, July 1974.
• 10: {6} Optimization of Very High Level Languages, to appear, Journal of Programming Languages, Oxford/New York.
• 11: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 12: Michel Sintzoff, Calculating properties of programs by valuations on specific models, ACM SIGPLAN Notices, v.7 n.1, p.203-207, January 1972
• 13: A. Tenenbaum {1} Revised and Extended Algorithms for Deducing the Types of Objects Appearing in SETL Programs. SETL Newsletter No. 118, New York University, October 1973.
• 14: {2} Automatic Type Analysis in a Very High Level Language. Thesis, New York University, October 1974.

INDEX TERMS

Keywords:
automatic programming, data structure choice, high level languages, program optimization, set-theoretic languages