Programming by Refinement, as Exemplified by the SETL Representation Sublanguage

ABSTRACT

“Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data structures that will be used to implement an algorithm which has already been written in pure SETL, so as to improve its efficiency. Ideally no rewriting of the algorithm should be necessary. The facilities provided by the representation sublanguage and the run-time data structures that it can generate are described; based on this a heuristic which uses some of the methods of global program analysis and which should be capable of selecting an acceptably efficient representation automatically is given.

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: ALLEN, F. A basis for program optimization. Information Processing 71, North Holland Pub. Co., Amsterdam; 1971, 385-390.
• 3: ALLEN, F. Interprocedural data flow analysis. Information Processing 74, North Holland Pub. Co., Amsterdam, 1974, 398-402.
• 4: KENNEO~, K., AND SCHWARTZ, J. An introduction to the set theoretical language SETL. J. Comptr. and Math. with Applications 1 (1975), 97-119.
• 5: James Richard Low, Automatic coding: choice of data structures., 1974
• 6: Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, Automatic data structure selection in SETL, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.197-210, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567771]
• 7: SCHWARTZ, J. On programming: an interim report on the SETL project. Installment I: generalities; Installment II: the SETL language and examples of its use. Lecture notes, New York U., N.Y., 1973.
• 8: 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]
• 9: SCHWARTZ, J. Optimization of very high level languages-I: value transmission and its corollaries. J. Comptr. Languages 1 (1975), 161-194.
• 10: SCHWARTZ, J. Optimization of very high level languages-Ih deducing relationships of inclusion and membership. J. Comptr. Languages I (1975), 197-218.
• 11: TP. NENBAUM, A. Automatic type analysis in a very high level language. Ph.D. Th., New York U., N.Y., 1974.
• 12: Tsui, W.H. A reformulation of value-flow analysis. SETL Newsletter 181, Comptr. Sci. Dept. New York U., N.Y., 1977. See also SETL Newsletters 31 (May 1971), 39 (May 1971), 64 (Jan. 1972), 71 (April 1972), 118 {Oct. 1973), 130 (May 1974), 131 (June 1974), 134 (July 1974), 162 (Jan. 1976), 171A (Dec. 1976), 174 (July 1976), 179 (Oct. 1976), 183 (Dec. 1976), and 184 (March 1977)

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SETL

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Design, Languages, Performance, Theory