Techniques for the automatic selection of data structures

ABSTRACT

We are all aware of the development of increasingly sophisticated, elaborate, and expensive computer programs, particularly in the fields of artificial intelligence, data base management, and intelligent systems. The need for techniques to deal with such complexity has renewed interest in programming language research. Recent work on structured programming, intelligent compilers, automatic program generation and verification, and high-level optimization has resulted. A pattern of approach similar to that of earlier research on programming languages is emerging. The work divides naturally into two parts: the search for good linguistic tools for expressing algorithms and data, and the development of practical methods for translating these to working computer programs. Our emphasis in this paper is in the latter.

REFERENCES

• 1: B. Baumgart. Micro Planner Alternate Reference Manual. Stanford Artificial Intelligence Laboratory. Operating Note 67, April 1972.
• 2: J. Earley. Comments on SETL (Symmetric Use of Relations). SETL Newsletter 52. Courant Institute NYU. Sept. 1971.
• 3: Jay Earley, Toward an understanding of data structures, Communications of the ACM, v.14 n.10, p.617-627, Oct. 1971 [doi>10.1145/362759.362764]
• 4: J. Earley. An Overview of the VERS2 Project. Electronic Research Laboratory, College of Engineering memorandum ERL-M416, Dec. 1973, University of California at Berkeley.
• 5: J. Earley. High Level Iterators and a Method of Automatically Designing Data Structure Representation. Electronic Research Laboratory, College of Engineering memorandum ERL-M425, Feb. 1974, University of California at Berkeley.
• 6: 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]
• 7: J. Low. Automatic Coding: Choice of Data Structures. Technical Report No. 1, Computer Science Department, University of Rochester, Rochester, N.Y.
• 8: D. McDermott and G. Sussman. The Conniver Reference Manual. AI Memo No. 259, M.I.T., May 1972.
• 9: J. Morris. A Comparion of MADCAP and SETL. University of California, Los Alamos Scientific Laboratory, 1973.
• 10: P. Rovner. Automatic Selection of Associative Data Structures. Ph.D. thesis, Department of Mathematics, Harvard University (in preparation).
• 11: 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]
• 12: J. Schwartz. Optimization of Very High Level Languages—I. Value Transmission and its Corollaries. In Computer Languages, Vol. 1, pp. 161-194, Pergamon Press, 1975.
• 13: Gerald Sussman , Terry Winograd, Micro-Planner Reference Manual, Massachusetts Institute of Technology, Cambridge, MA, 1970
• 14: G. Sussman. Why Conniving is Better than Planning. AI Memo 255. M.I.T. Artificial Intelligence Lab, Feb. 1972.
• 15: Kurt A. VanLehn, SAIL user manual., Stanford University, Stanford, CA, 1973

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Management