Automatic data structure selection: an example and overview

ABSTRACT

The use of several levels of abstraction has proved to be very helpful in constructing and maintaining programs. When programs are designed with abstract data types such as sets and lists, programmer time can be saved by automating the process of filling in low-level implementation details. In the past, programming systems have provided only a single general purpose implementation for an abstract type. Thus the programs produced using abstract types were often inefficient in space or time. In this paper a system for automatically choosing efficient implementations for abstract types from a library of implementations is discussed. This process is discussed in detail for an example program. General issues in data structure selection are also reviewed.

REFERENCES

• 1: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 2: Allen, F.E. Bibliography on program optimization. Rep. RC5767, IBM T.J. Watson Res. Ctr., Dec. 1975.
• 3: Birtwistle, G. et al. DECSYSTEM-10 SIMULA Language Handbook. Rep. C8398, C8399, Swedish Nat. Defense Res. Inst., Stockholm, Sweden, 1974.
• 4: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 5: Burstall, R.M., Collins, J.S., and Popplestone, R.J. Programming in POP.2. Edinburgh U. Press, Edinburgh, Scotland, 1971.
• 6: ECL Programmer's Manual. Ctr. Res. Comptng. Tech., Harvard U., Cambridge, Mass., Dec. 1974.
• 7: Jerome A. Feldman , Paul D. Rovner, An ALGOL-based associative language, Communications of the ACM, v.12 n.8, p.439-449, Aug. 1969 [doi>10.1145/363196.363204]
• 8: Feldman, J., et al. Recent developments in SAIL-an ALGOL- based language for artificial intelligence. Proc. AFIPS 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 1193-1202.
• 9: Geschke, C.M., and Mitchell, J.G. On the problem of uniform references to data structures. IEEE Trans. Sofiware Eng. SE-1 (June 1975), 207-219.
• 10: Gary Arlen Kildall, Global expression optimization during compilation, 1972
• 11: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 12: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 13: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• 14: Low, J. Automatic Coding: Choice of Data Structures. Interdisciplinary Syst. Res. Rep. 16, Birkha/iser Verlag, Basel, 1976.
• 15: James Low , Paul Rovner, Techniques for the automatic selection of data structures, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.58-67, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811540]
• 16: John F. Reiser, SAIL, Stanford University, Stanford, CA, 1976
• 17: Rovner, P. Automatic representation selection for associative data structures. Ph.D. Th., Harvard U., Cambridge, Mass; Tech. Rep. TR10, U. of Rochester, Rochester, N.Y., Sept. 1976.
• 18: Schwartz, J. Optimization of very high level languages--l: Value transmission and its corollaries. In Computer Languages, Vol. I, Pergamon Press, Elmsford, N.Y., 1975, 161-194.
• 19: Aaron Melvin Tenenbaum, Type determination for very high level languages., 1974
• 20: Ben Wegbreit , Jay M. Spitzen, Proving Properties of Complex Data Structures, Journal of the ACM (JACM), v.23 n.2, p.389-396, April 1976 [doi>10.1145/321941.321957]
• 21: Wulf, W.A., London, R.L., and Shaw, M. An introduction to the construction and verification of ALPHARD programs. IEEE Trans. Software Eng. SE-2, 4, (Dec. 1976). 253-265.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

  E. Data

General Terms:
Design, Languages, Performance, Theory

Keywords:
abstract data types, automatic programming, data structures, lists, optimizing compilers, sets