Safely creating correct subclasses without seeing superclass code

ABSTRACT

A major problem for object-oriented frameworks and class libraries is how to provide enough information about a superclass, so programmers can safely create new subclasses without giving away the superclass's code. Code inherited from the superclass can call down to methods of the subclass, which may cause nontermination or unexpected behavior. We describe a reasoning technique that allows programmers, who have no access to the code of the superclass, to determine both how to safely override the superclass's methods and when it is safe to call them. The technique consists of a set of rules and some new forms of specification. Part of the specification would be generated automatically by a tool, a prototype of which is planned for the formal specification language JML. We give an example to show the kinds of problems caused by method overrides and how our technique can be used to avoid them. We also argue why the technique is sound and give guidelines for library providers and programmers that greatly simplify reasoning about how to avoid problems caused by method overrides.

REFERENCES

• 1: Pierre America, Designing an Object-Oriented Programming Language with Behavioural Subtyping, Proceedings of the REX School/Workshop on Foundations of Object-Oriented Languages, p.60-90, May 28-June 01, 1990
• 2: Ralph-Johan J. Back , Abo Akademi , J. Von Wright , F. B. Schneider , D. Gries, Refinement Calculus: A Systematic Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 3: Yonghao Chen , Betty H. C. Cheung, A semantic foundation for specification matching, Foundations of component-based systems, Cambridge University Press, New York, NY, 2000
• 4: Krishna Kishore Dhara , Gary T. Leavens, Forcing behavioral subtyping through specification inheritance, Proceedings of the 18th international conference on Software engineering, p.258-267, March 25-29, 1996, Berlin, Germany
• 5: Stephen H. Edwards, Representation Inheritance: A Safe Form of "White Box'' Code Inheritance, Proceedings of the 4th International Conference on Software Reuse, p.195, April 23-26, 1996
• 6: P. H. B. Gardier and C. Morgan. A single complete rule for data refinement. In Morgan and Vickers {30}, pages 111-126.
• 7: P. H. B. Gardiner and C. Morgan. Data refinement of predicate transformers. In Morgan and Vickers {30}, pages 71-84.
• 8: John V. Guttag , James J. Horning, Larch: languages and tools for formal specification, Springer-Verlag New York, Inc., New York, NY, 1993
• 9: Eric C. R. Hehner, A practical theory of programming, Springer-Verlag New York, Inc., New York, NY, 1993
• 10: C. A. R. Hoare. Proof of correctness of data representations. Acta Informatica, 1(4):271-281, 1972.
• 11: Gregor Kiczales , Jim des Rivières , Daniel G. Bobrow, The art of metaobject protocol, MIT Press, Cambridge, MA, 1991
• 12: Gregor Kiczales , John Lamping, Issues in the design and specification of class libraries, conference proceedings on Object-oriented programming systems, languages, and applications, p.435-451, October 18-22, 1992, Vancouver, British Columbia, Canada
• 13: John Lamping, Typing the specialization interface, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.201-214, September 26-October 01, 1993, Washington, D.C., United States
• 14: G. T. Leavens, A. L. Baker, and C. Ruby. JML: A notation for detailed design. In H. Kilov, B. Rumpe, and I. Simmonds, editors, Behavioral Specifications of Businesses and Systems, pages 175-188. Kluwer Academic Publishers, Boston, 1999.
• 15: G. T. Leavens, A. L. Baker, and C. Ruby. Preliminary design of JML: A behavioral interface specification language for Java. Technical Report 98-06i, Iowa State University, Department of Computer Science, Feb. 2000. See www.cs.iastate.edu/~leavens/JML.html.
• 16: G. T. Leavens and W. E. Weihl. Specification and verification of object-oriented programs using supertype abstraction. Acta Informatica, 32(8):705-778, Nov. 1995.
• 17: K. Rustan Leino, Toward reliable modular programs, California Institute of Technology, Pasadena, CA, 1995
• 18: K. Rustan M. Leino, Data groups: specifying the modification of extended state, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.144-153, October 18-22, 1998, Vancouver, British Columbia, Canada
• 19: Barbara Liskov , John Guttag, Abstraction and specification in program development, MIT Press, Cambridge, MA, 1986
• 20: Barbara H. Liskov , Jeannette M. Wing, A behavioral notion of subtyping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1811-1841, Nov. 1994 [doi>10.1145/197320.197383]
• 21: Barbara Liskov , Jeannette M. Wing, Specifications and their use in defining subtypes, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.16-28, September 26-October 01, 1993, Washington, D.C., United States
• 22: C. Lucas. Documenting Reuse and Evolution with Reuse Contracts. PhD thesis, Vrije Universiteit Brussel, Brussels, Belgium, Sept. 1997.
• 23: Ole Lehrmann Madsen , Birger Mø-Pedersen , Kristen Nygaard, Object-oriented programming in the BETA programming language, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 24: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 25: Bertrand Meyer, Applying "Design by Contract", Computer, v.25 n.10, p.40-51, October 1992 [doi>10.1109/2.161279]
• 26: Mira Mezini, Maintaining the consistency of class libraries during their evolution, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-21, October 05-09, 1997, Atlanta, Georgia, United States
• 27: Leonid Mikhajlov , Emil Sekerinski, A Study of The Fragile Base Class Problem, Proceedings of the 12th European Conference on Object-Oriented Programming, p.355-382, July 20-24, 1998
• 28: Carroll Morgan, Programming from specifications (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1994
• 29: Carroll Morgan , P. H. B. Gardiner, Data refinement by calculation, Acta Informatica, v.27 n.6, p.481-503, 1990
• 30: Trevor Vickers , Carroll Morgan, On the Refinement Calculus, Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 31: Peter Müller , Arnd Poetzsch-Heffter, Modular specification and verification techniques for object-oriented software components, Foundations of component-based systems, Cambridge University Press, New York, NY, 2000
• 32: William F. Opdyke, Refactoring object-oriented frameworks, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 33: D. E. Perry , G. E. Kaiser, Adequate testing and object-oriented programming, Journal of Object-Oriented Programming, v.2 n.5, p.13-19, Jan./Feb. 1990
• 34: A. D. Raghavan. Design of a JML documentation generator. Technical Report 00-12, Iowa State University, Department of Computer Science, July 2000.
• 35: R. Stata, Modularity in the Presence of Subclassing, Massachusetts Institute of Technology, Cambridge, MA, 1997
• 36: Raymie Stata , John V. Guttag, Modular reasoning in the presence of subclassing, ACM SIGPLAN Notices, v.30 n.10, p.200-214, Oct. 17, 1995
• 37: Object Orientation in Z, January 1992
• 38: Patrick Steyaert , Carine Lucas , Kim Mens , Theo D'Hondt, Reuse contracts: managing the evolution of reusable assets, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.268-285, October 06-10, 1996, San Jose, California, United States
• 39: Clemens Szyperski, Component software: beyond object-oriented programming, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

General Terms:
Design, Languages, Performance, Theory

Keywords:
JML language, Java language, downcalls, method refinement, semantic fragile subclassing problem, specification inheritance, subclass, subclassing contract