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. 1.P. America. Designing an object-oriented programming language with behavioural subtyping. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, Foundations of Object-Oriented Languages, REX School/Workshop, Noordwijkerhout, The Netherlands, May/June 1990, volume 489 of Lecture Notes in Computer Science, pages 60-90. Springer-Verlag, New York, NY, 1991.
2. 2.R.-J. Back and J. von Wright. Refinement Calculus: A Systematic Introduction. Springer-Verlag, 1998.
3. 3.Y. Chen and B. H. C. Cheng. A semantic foundation for specification matching. In G. T. Leavens and M. Sitaraman, editors, Foundations of Component-Based Systems, pages 91-109. Cambridge University Press, New York, NY, 2000.
4. 4.K. K. Dhara and G. T. Leavens. Forcing behavioral subtyping through specification inheritance. In Proceedings of the 18th International Conference on Software Engineering, Berlin, Germany, pages 258-267. IEEE Computer Society Press, Mar. 1996. A corrected version is Iowa State University, Dept. of Computer Science TR #95-20c.
5. 5.S. H. Edwards. Representation inheritance: A safe form of "white box" code inheritance. In Fourth International Conference on Software Reuse, pages 195-204. IEEE Computer Society Press, Apr. 1996.
6. 6.P. H. B. Gardier and C. Morgan. A single complete rule for data refinement. In Morgan and Vickers {30}, pages 111-126.
7. 7.P. H. B. Gardiner and C. Morgan. Data refinement of predicate transformers. In Morgan and Vickers {30}, pages 71-84.
8. 8.J. V. Guttag, J. J. Horning, S. Garland, K. Jones, A. Modet, and J. Wing. Larch: Languages and Tools for Formal Specification. Springer-Verlag, New York, NY, 1993.
9. 9.E. C. R. Hehner. A Practical Theory of Programming. Texts and Monographs in Computer Science. Springer-Verlag, 1993.
10. 10.C. A. R. Hoare. Proof of correctness of data representations. Acta Informatica, 1(4):271-281, 1972.
11. 11.G. Kiczales, J. des Rivieres, and D. G. Bobrow. The Art of the Metaobject Protocol. The MIT Press, Cambridge, Mass., 1991.
12. 12.G. Kiczales and J. Lamping. Issues in the design and documentation of class libraries. ACM SIGPLAN Notices, 27(10):435-451, Oct. 1992. OOPSLA '92 Proceedings, Andreas Paepcke (editor).
13. 13.J. Lamping. Typing the specialization interface. ACM SIGPLAN Notices, 28(10):201-214, Oct. 1993. OOPSLA '93 Proceedings, Andreas Paepcke (editor).
14. 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. 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. 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. 17.K. R. M. Leino. Toward Reliable Modular Programs. PhD thesis, California Institute of Technology, 1995. Available as Technical Report Caltech-CS-TR-95-03.
18. 18.K. R. M. Leino. Data groups: Specifying the modification of extended state. In OOPSLA '98 Conference Proceedings, volume 33(10) of ACM SIGPLAN Notices, pages 144-153. ACM, Oct. 1998.
19. 19.B. Liskov and J. Guttag. Abstraction and Specification in Program Development. The MIT Press, Cambridge, Mass., 1986.
20. 20.B. Liskov and J. Wing. A behavioral notion of subtyping. ACM Trans. Prog. Lang. Syst., 16(6):1811-1841, Nov. 1994.
21. 21.B. Liskov and J. M. Wing. Specifications and their use in defining subtypes. ACM SIGPLAN Notices, 28(10):16-28, Oct. 1993. OOPSLA '93 Proceedings, Andreas Paepcke (editor).
22. 22.C. Lucas. Documenting Reuse and Evolution with Reuse Contracts. PhD thesis, Vrije Universiteit Brussel, Brussels, Belgium, Sept. 1997.
23. 23.O. L. Madsen, B. M~ller-Pedersen, and K. Nygaard. Object-Oriented Programming in the BETA programming Language. Addison-Wesley Inc, 1993.
24. 24.B. Meyer. Object-oriented Software Construction. Prentice Hall, New York, NY, 1988.
25. 25.B. Meyer. Applying "design by contract". Computer, 25(10):40-51, Oct. 1992.
26. 26.M. Mezini. Maintaining the consistency and behavior of class libraries during their evolution. ACM SIGPLAN Notices, 32(10):1-21, Oct. 1997. Conference Proceedings of OOPSLA '97.
27. 27.L. Mikhajlov and E. Sekerinski. A study of the fragile base class problem. In E. Jul, editor, ECOOP '98 - Object-Oriented Programming, 12th European Conference , Brussels, Proceedings, volume 1445 of Lecture Notes in Computer Science, pages 355-382. Springer-Verlag, July 1998.
28. 28.C. Morgan. Programming from Specifications: Second Edition. Prentice Hall International, Hempstead, UK, 1994.
29. 29.C. Morgan and P. H. B. Gardiner. Data refinement by calculation. Acta Informatica, 27(6):481-503, May 1990.
30. 30.C. Morgan and T. Vickers, editors. On the refinement calculus. Formal approaches of computing and information technology series. Springer-Verlag, New York, NY, 1994.
31. 31.P. Muller and A. Poetzsch-Heffter. Modular specification and verification techniques for object-oriented software components. In G. T. Leavens and M. Sitaraman, editors, Foundations of Component-Based Systems, chapter 7, pages 137-159. Cambridge University Press, 2000.
32. 32.W. Opdyke. Refactoring Object-Oriented Frameworks. PhD thesis, University of Illinois at Urbana-Champaign, 1992.
33. 33.D. E. Perry and G. E. Kaiser. Adequate testing and object-oriented programming. Journal of Object-Oriented Programming, 2(5):13-19, Jan/Feb 1990.
34. 34.A. D. Raghavan. Design of a JML documentation generator. Technical Report 00-12, Iowa State University, Department of Computer Science, July 2000.
35. 35.R. Stata. Modularity in the presence of subclassing. Technical Report 145, Digital Equipment Corporation, Systems Research Center, 130 Lytton Avenue Palo Alto, CA 94301, Apr 1997. Order from [email protected] or ftp from gatekeeper.dec.com.
36. 36.R. Stata and J. V. Guttag. Modular reasoning in the presence of subclassing. ACM SIGPLAN Notices, 30(10):200-214, Oct. 1995. Proceedings of OOPSLA '95 Tenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications.
37. 37.S. Stepney, R. Barden, and D. Cooper, editors. Object Orientation in Z. Workshops in Computing. Springer-Verlag, Cambridge CB2 1LQ, UK, 1992.
38. 38.P. Steyaert, C. Lucas, K. Mens, and T. D'Hondt. Reuse contracts: Managing the evolution of reusable assets. In OOPSLA '96 Conference on Object-Oriented Programming Systems, Languagges and Applications, pages 268-285. ACM Press, October 1996. ACM SIGPLAN Notices, Volume 31, Number 10.
39. 39.C. Szyperski. Component Software: Beyond Object-Oriented Programming. ACM Press and Addison-Wesley, New York, NY, 1998.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Object oriented languages

    • System description languages

      • Specification languages