Automatic data structure selection in SETL

ABSTRACT

SETL is a very high level programming language supporting set theoretical syntax and semantics. It allows algorithms to be programmed rapidly and succinctly without requiring data structure declarations to be supplied, though such declarations can be manually specified later, without recoding the program, to improve the efficiency of program execution. We describe a new technique for automatic selection of appropriate data representations during compile-time for undeclared, or partially declared programs,and present an efficient data structure selection algorithm, whose complexity is comparable with those of the fastest known general data-flow algorithms of Tarjan [TA2] and Reif [RE].

REFERENCES

• 1: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• 2: Robert K. Dewar , Arthur and Ssu-Cheng Liu and Jacob T. Schwartz and Edmond Schonberg, Programming by Refinement, as Exemplified by the SETL Representation Sublanguage, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.27-49, July 1979 [doi>10.1145/357062.357064]
• 3: {GS} Grand, A. and Sharir, M., "On name splitting in SETL optimization," SETL Newsletter 206, Courant Inst. Math. Sci., New York, 1978.
• 4: Maurice H. Halstead, Elements of Software Science (Operating and programming systems series), Elsevier Science Inc., New York, NY, 1977
• 5: Ssu-Cheng Liu, Automatic data structure choice in setl., 1978
• 6: James R. Low, Automatic data structure selection: an example and overview, Communications of the ACM, v.21 n.5, p.376-385, May 1978 [doi>10.1145/359488.359498]
• 7: {RE} Reif, J. H., Ph.D. Thesis, Harvard University, (to appear).
• 8: {SL} Schonberg, E. and Liu, S. C., "Manual and automatic data-structuring in SETL," Proc. 5th Annual III Conference, Guidel, France, 1977, 284-304.
• 9: J. T. Schwartz, Automatic data structure choice in a language of very high level, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.36-40, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512981]
• 10: {SC2} Schwartz, J. T., "Use-use chaining as a technique in typefinding," SETL Newsletter 140, Courant Inst. Math. Sci., New York, 1974.
• 11: {SC3} Schwartz, J. T., "On Programming: an interim report on the SETL project," 2nd edition, Courant Inst. Math. Sci., New York, 1975.
• 12: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 13: Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975
• 14: {TE} Tenenbaum, A. M., "Type determination for very high level languages," Computer Sci. Rep. 3, Courant Inst. Math. Sci., New York, 1974.