Automatic design and implementation of language data types

ABSTRACT

Language implementation is in need of automation. Although compiler construction has long been aided by parser generators and other tools, interpreters and runtime systems have been neglected, even though they constitute a large component of languages like Lisp, Prolog, and Smalltalk. Of the several parts of a runtime system, the primitive datatype definitions present some of the most difficult decisions for the implementor. The effectiveness of type discrimination schemes, interactions between storage allocation and virtual memory, and general time/space tradeoffs are issues that have no simple resolution-they must be evaluated for each implementation. A formalism for describing implementations has been developed and used in a prototype designer of primitive data structures. The designer is a collection of heuristic rules that produce multiple designs of differing characteristics. Cost evaluation on machine code derived from those designs yields performance formulas, which are then used to estimate the designs' effect on benchmark programs.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: [2] D. R. Barstow. Knowledge-Based Program Construction. North Holland, 1977.
• 3: Robert Cartwright, A constructive alternative to axiomatic data type definitions, Proceedings of the 1980 ACM conference on LISP and functional programming, p.46-55, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802789]
• 4: R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
• 5: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 6: Stefan M. Freudenberger , Jacob T. Schwartz , Micha Sharir, Experience with the SETL Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.26-45, Jan. 1983 [doi>10.1145/357195.357197]
• 7: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 8: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 9: [9] C. C. Gotlieb and F. W. Tompa. Choosing a storage schema. Acta Informatica, 3:297-319. 1974.
• 10: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• 11: Christoph M. Hoffmann , Michael J. O'Donnell, Programming with Equations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.83-112, Jan. 1982 [doi>10.1145/357153.357158]
• 12: Elaine Kant, The selection of efficient implementations for a high-level language, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.140-146, August 15-17, 1977
• 13: 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]
• 14: CORPORATE Motorola, Inc. Staff, MC 68000 16-Bit Microprocessor User's Manual, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 15: [15] Pereira, F. C. N., et al. C-Prolog User's Manual. Technical Report, University of Edinburgh, January 1986.
• 16: [16] L. A. Rowe and F. M. Tonge. Automating the selection of implementation structures. IEEE Transactions on Software Engineering, SE- 4:494-506, November 1978.
• 17: Stuart Russell, The compleat guide to MRS, Stanford University, Stanford, CA, 1985
• 18: J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
• 19: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 20: Peter Steenkiste , John Hennessy, LISP on a reduced-instruction-set-processor, Proceedings of the 1986 ACM conference on LISP and functional programming, p.192-201, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319862]
• 21: [21] J. F. Stoy. Denotational Semantics. MIT Press, 1977.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management
          Subjects: Cost estimation
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Design, Languages, Management