Data abstraction from a programming language viewpoint

ABSTRACT

This paper traces the development of data abstraction concepts in programming languages. A data abstraction, or abstract data type, describes a collection of abstract entities and operations on the entities. A program which uses a data abstraction can access or modify the entities only through the abstract operations. Specific research topics discussed in the paper include: the role of type in a programming language, the formal specification of the semantics of a data abstraction, data abstraction language construct design issues, type hierarchies, and type-checking.

REFERENCES

• 1: J. D. Ichbiah, Preliminary Ada reference manual, ACM SIGPLAN Notices, v.14 n.6a, p.1-145, June 1979 [doi>10.1145/956650.956651]
• 2: Russell R. Atkinson , Barbara H. Liskov , Robert W. Scheifler, Aspects Of Implementing CLU, Proceedings of the 1978 annual conference, p.123-129, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804079]
• 3: J.L. Bentley and M. Shaw. Abstraction and Efficiency: The Interaction of Languages and Analysis. Comp. Sci. Dept., Carnegie-Mellon Univ. (1980).
• 4: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 5: 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]
• 6: O.-J. Dahl. Personal Communication (Dec. 1979).
• 7: 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]
• 8: Charles M. Geschke , James H. Morris, Jr. , Edwin H. Satterthwaite, Early experience with Mesa, Communications of the ACM, v.20 n.8, p.540-553, Aug. 1977 [doi>10.1145/359763.359771]
• 9: J.A. Goguen et.al. Abstract Data-Types as Initial Algebras and Correctness of Data Representations. Proc. Conf. on Comp. Graphics; Pattern Rec. and Data Structure(May 1975).
• 10: C.C. Gotileb and F.W. Tompa. Choosing a Storage Schema. Acta Inform., vol.3 (1974), pp. 297-319.
• 11: J. Guttag Notes on Type Abstraction (Version 2). IEEE Trans. on Soft. Eng., vol. SE-6, no. 1 (Jan. 1980).
• 12: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 13: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 14: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 15: Anita K. Jones , Barbara H. Liskov, A language extension for expressing constraints on data access, Communications of the ACM, v.21 n.5, p.358-367, May 1978 [doi>10.1145/359488.359493]
• 16: Barbara Liskov , Stephen Zilles, Programming with abstract data types, ACM SIGPLAN Notices, v.9 n.4, p.50-59, April 1974
• 17: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 18: 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]
• 19: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 20: Mathlab Group. MACSYMA Reference Manual. Lab. for Comp. Sci., MIT, 1977.
• 21: J. Mitchell, et.al. MESA Language Manual. (Ver. 5.0). CSL-79-3, XEROX PARC (Apr. 1979).
• 22: James H. Morris, Jr., Types are not sets, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.120-124, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512938]
• 23: L.A. Rowe and F.M. Tonge. Automating the Selection of Implementation Structures. IEEE Trans. on Soft. Eng., vol. SE-4, no. 6 (Nov. 1978).
• 24: L.A. Rowe, et.al. RIGEL Language Specification. Comp. Sci. Div.-EECS, U.C. Berkeley (March 1980).
• 25: D. Slate and B. Mittman. CHESS 4.6- Where do we go from here? Inform. Tech, J. Moneta (editor). North-Holland, 1978.
• 26: A. van Wijngaarden, et.al. Revised Report on the Algorithmic Language ALGOL 68. Acta Inform., vol. 5 (1975).
• 27: B. Wegbreit. The ECL Programming System. Proc. AFIPS 1971 FJCC, vol. 39 (Nov. 1971).
• 28: Peter Wegner, The Vienna Definition Language, ACM Computing Surveys (CSUR), v.4 n.1, p.5-63, March 1972 [doi>10.1145/356596.356598]
• 29: J. Welsh, M.J. Sneeringer, and C.A.R. Hoare. Ambiguities and Insecurities in PASCAL. Soft. - Prac. and Exp., vol. 7 (Nov. 1977).
• 30: N. Wirth. MODULA: A Language for Modular Multiprogramming. Soft. - Prac. and Exp., vol. 7 (1977).
• 31: W.A. Wulf, R.L. London, and M. Shaw. An Introduction to the Construction and Verification of Alphard Programs. IEEE Trans. on Soft. Eng., vol. SE-2, no. 4 (1976).

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages