William R. Cook
ABSTRACT
In 1985 Luca Cardelli and Peter Wegner, my advisor, published an ACM Computing Surveys paper called "On understanding types, data abstraction, and polymorphism". Their work kicked off a flood of research on semantics and type theory for object-oriented programming, which continues to this day. Despite 25 years of research, there is still widespread confusion about the two forms of data abstraction, abstract data types and objects. This essay attempts to explain the differences and also why the differences matter.
- N. Adams and J. Rees. Object-oriented programming in Scheme. In Proceedings of the ACM Conf. on Lisp and Functional Programming, pages 277--288, 1988. Google Scholar
Digital Library
- P. America. A behavioral approach to subtyping object-oriented programming languages. In Proceedings of the REX Workshop/School on the Foundations of Object-Oriented Languages, volume 173 of Lecture Notes in Computer Science, 1990. Google ScholarDigital Library
- J. Bergstra and J. Tucker. Initial and final algebra semantics for data type specifications: Two characterisation theorems. Research Report IW 142, Stichting Mathematisch Centrum, 1980.Google Scholar
- G. M. Birtwistle. DEMOS: a system for discrete event modelling on Simula. Springer--Verlag, 1987. Google ScholarDigital Library
- D. Box. Essential COM (DevelopMentor Series). Addison-Wesley Professional, 1998. Google ScholarDigital Library
- C. Boyapati, B. Liskov, and L. Shrira. Ownership types for object encapsulation. SIGPLAN Notices, 38(1):213--223, 2003. Google ScholarDigital Library
- R. Burstall and J. Goguen. Putting theories together to make specifications. In International Joint Conferences on Artificial Intelligence, pages 1045--1058. Department of Computer Science, Carnegie-Mellon University, 1977. Google ScholarDigital Library
- P. Canning, W. Cook, W. Hill, and W. Olthoff. Interfaces for strongly-typed object-oriented programming. In Proceedings of ACM Conf. on Object-Oriented Programming, Systems, Languages and Applications, pages 457--467, 1989. Google ScholarDigital Library
- L. Cardelli. A semantics of multiple inheritance. In Semantics of Data Types, volume 173 of Lecture Notes in Computer Science, pages 51--68. Springer-Verlag, 1984. Google ScholarCross Ref
- L. Cardelli and P. Wegner. On understanding types, data abstraction, and polymorphism. Computing Surveys, 17(4):471--522, 1986. Google ScholarDigital Library
- C. Chambers. Object-oriented multi-methods in Cecil. In ECOOP '92: Proceedings of the European Conference on Object-Oriented Programming, pages 33--56. Springer-Verlag, 1992. Google ScholarDigital Library
- A. Church. The Calculi of Lambda Conversion. Princeton University Press, 1941. Google ScholarDigital Library
- W. Cook. A Denotational Semantics of Inheritance. PhD thesis, Brown University, 1989. Google ScholarDigital Library
- W. Cook. Object-oriented programming versus abstract data types. In Proceedings of the REX Workshop/School on the Foundations of Object-Oriented Languages, volume 173 of Lecture Notes in Computer Science, 1990. Google ScholarDigital Library
- B. C. d. S. Oliveira. Modular visitor components: A practical solution to the expression families problem. In S. Drossopoulou, editor, 23rd European Conference on Object Oriented Programming (ECOOP), 2009. Google ScholarDigital Library
- O.-J. Dahl, B. Myhrhaug, and K. Nygaard. The SIMULA 67 common base language. Technical report, Norwegian Computing Center, 1970. Publication S-22.Google Scholar
- H.-D. Ehrich. On the theory of specification, implementation and parameterization of abstract data types. J. ACM, 29(1):206--227, 1982. Google ScholarDigital Library
- A. Filinski. Declarative continuations and categorical duality. Master's thesis DIKU Report 89/11, University of Copenhagen, 1989.Google Scholar
- J. Gibbons. Unfolding abstract datatypes. In MPC '08: Proceedings of the 9th international conference on Mathematics of Program Construction, pages 110--133, 2008. Google ScholarDigital Library
- J. Goguen, J. Thatcher, and E. Wagner. An initial algebra approach to the specification, correctness, and implementation of abstract data types. Current Trends in Programming Methodology, IV:80--149, 1978.Google Scholar
- J. Gosling, B. Joy, G. Steele, and G. Bracha. Java(TM) Language Specification. Addison-Wesley Professional, 2005. Google ScholarDigital Library
- D. N. Gray, J. Hotchkiss, S. LaForge, A. Shalit, and T. Weinberg. Modern languages and Microsoft's Component Object Model. Commun. ACM, 41(5):55--65, 1998. Google ScholarDigital Library
- C. A. Gunter and J. C. Mitchell, editors. Theoretical aspects of object-oriented programming: types, semantics, and language design. MIT Press, 1994. Google ScholarDigital Library
- J. Guttag. The Specification and Application to Programming of Abstract Data Types. Report, University of Toronto, Computer Science Department, 1975.Google Scholar
- C. Hewitt, P. Bishop, I. Greif, B. Smith, T. Matson, and R. Steiger. Actor induction and meta-evaluation. In POPL '73: Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 153--168. ACM, 1973. Google ScholarDigital Library
- C. A. R. Hoare. Proof of correctness of data representation. Acta Informatica, 1:271--281, 1972.Google ScholarDigital Library
- J. Hogg, D. Lea, A. Wills, D. deChampeaux, and R. Holt. The Geneva convention on the treatment of object aliasing. SIGPLAN OOPS Messenger, 3(2):11--16, 1992. Google ScholarDigital Library
- D. Ingalls. The Smalltalk-76 programming system. In POPL, pages 9--16, 1978. Google Scholar
- B. Jacobs. Objects and classes, co-algebraically. In Object orientation with parallelism and persistence, pages 83--103. 1996. Google ScholarCross Ref
- S. P. Jones. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.Google Scholar
- S. P. Jones. Classes, Jim, but not as we know them. type classes in Haskell: what, why, and whither. ECOOP Keynote, 2009.Google Scholar
- B. W. Kernighan and D. Ritchie. C Programming Language (2nd Edition). Prentice Hall PTR, 1988. Google ScholarDigital Library
- S. Krishnamurthi, M. Felleisen, and D. P. Friedman. Synthesizing object-oriented and functional design to promote re-use. In In European Conference on Object-Oriented Programming, pages 91--113. Springer, 1998. Google ScholarDigital Library
- B. Liskov. Keynote address - data abstraction and hierarchy. In OOPSLA '87: Addendum to the Proceedings on Object-oriented programming systems, languages and applications (Addendum), pages 17--34, 1987. Google ScholarDigital Library
- B. Liskov. A history of CLU. In History of programming languages-II, pages 471--510. ACM, 1996. Google ScholarDigital Library
- B. Liskov, R. Atkinson, T. Bloom, E. Moss, J. C. Schaffert, R. Scheifler, and A. Snyder. CLU Reference Manual. Springer-Verlag, 1981. Google ScholarDigital Library
- B. Liskov and S. Zilles. Programming with abstract data types. SIGPLAN Notices, 9(4):50--59, 1974. Google ScholarDigital Library
- K. C. Louden. Programming Languages: Principles and Practice. Wadsworth Publ. Co., 1993. Google ScholarDigital Library
- D. B. MacQueen. Modules for Standard ML. In Conference on LISP and Functional Programming, 1984. Google ScholarDigital Library
- B. Mahr and J. Makowsky. An axiomatic approach to semantics of specification languages. In Proceedings of the 6th Conference on Theoretical Computer Science, volume 145 of Lecture Notes in Computer Science, pages 211--219. Springer-Verlag, 1983. Google ScholarDigital Library
- R. Milner. Communication and Concurrency. Prentice-Hall, 1989. Google ScholarDigital Library
- R. Milner, M. Tofte, and R. Harper. The definition of Standard ML. MIT Press, 1990. Google ScholarDigital Library
- J. C. Mitchell. Concepts in Programming Languages. Cambridge University Press, 2001. Google ScholarDigital Library
- J. C. Mitchell and G. D. Plotkin. Abstract types have existential type. In Proceedings of the ACM Symp. on Principles of Programming Languages. ACM, 1985. Google ScholarDigital Library
- P. Müller, A. Poetzsch-Heffter, and G. T. Leavens. Modular invariants for layered object structures. Sci. Comput. Program., 62(3):253--286, 2006. Google ScholarDigital Library
- D. A. Naumann. Observational purity and encapsulation. Theor. Comput. Sci., 376(3):205--224, 2007. Google ScholarDigital Library
- M. Odersky, L. Spoon, and B. Venners. Programming in Scala: A Comprehensive Step-by-step Guide. Artima Inc, 2008. Google ScholarDigital Library
- M. Odersky and M. Zenger. Independently extensible solutions to the expression problem. In Proceedings FOOL 12, 2005. http://homepages.inf.ed.ac.uk/wadler/fool.Google Scholar
- U. S. D. of Defense. Reference manual for the Ada programming language. ANSI/MIL-STD-1815 A, 1983.Google Scholar
- B. C. Pierce. Types and Programming Languages. MIT Press, 2002. Google ScholarDigital Library
- T. W. Pratt and M. V. Zelkowitz. Programming languages: design and implementation. Prentice-Hall, 1995. Google ScholarDigital Library
- J. C. Reynolds. User-defined types and procedural data structures as complementary approaches to data abstraction. In New Advances in Algorithmic Languages, pages 157--168. INRIA, 1975.Google Scholar
- M. L. Scott. Programming Language Pragmatics. Morgan Kaufmann, 2000. Google ScholarDigital Library
- R. Sebesta. Concepts of Programming Languages, Eighth Edition. Addison-Wesley, 2007. Google ScholarDigital Library
- J. F. Shoch. An overview of the programming language Smalltalk-72. SIGPLAN Notices, 14(9):64--73, 1979. Google ScholarDigital Library
- G. Steele. LAMBDA: The ultimate declarative. Technical Report AIM-379, MIT AI LAB, 1976.Google Scholar
- A. B. Tucker and R. E. Noonan. Programming Languages: Principles and Paradigms, Second Edition. McGraw-Hill Higher Education, 2007. Google ScholarDigital Library
- P. Wadler. The expression problem. Mail to the java-genericity mailing list, 1998.Google Scholar
- P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad hoc. In POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 60--76. ACM, 1989. Google ScholarDigital Library
- N. Wirth. Programming in Modula-2. Springer-Verlag, 1983. Google ScholarDigital Library
- W. A. Wulf, R. L. London, and M. Shaw. An introduction to the construction and verification of Alphard programs. IEEE Transactions on Software Engineering, SE-24(4), 1976.Google ScholarDigital Library
- S. N. Zilles. Procedural encapsulation: A linguistic protection mechanism. SIGPLAN Notices, 8(9):142--146, 1973. Google ScholarDigital Library
Index Terms
- On understanding data abstraction, revisited
Recommendations
On understanding data abstraction, revisited
OOPSLA '09In 1985 Luca Cardelli and Peter Wegner, my advisor, published an ACM Computing Surveys paper called "On understanding types, data abstraction, and polymorphism". Their work kicked off a flood of research on semantics and type theory for object-oriented ...
On understanding types, data abstraction, and polymorphism
The MIT Press scientific computation seriesOur objective is to understand the notion of type in programming languages, present a model of typed, polymorphic programming languages that reflects recent research in type theory, and examine the relevance of recent research to the design of practical ...
Polymorphic type-checking in scheme
This paper presents a type-inference system for Scheme that is designed to be used by students in an introductory programming course. The major goal of the work is to present a type system that is simple enough to be used by beginner students, yet is ...
Comments