Toward a formal theory of extensible software

ABSTRACT

As software projects continue to grow in scale and scope, it becomes important to reuse software. An important kind of reuse is extensibility, i.e., the extension of software without accessing existing code to edit or copy it. In this paper, we propose a rigorous, semantics-based definition of software extensibility. Then we illustrate the utility of our definitions by applying them to several programs. The examination shows how programming style affects extensibility and also drives the creation of a variant of an existing design pattern. We consider programs in both object-oriented and functional languages to prove the robustness of our definitions.

REFERENCES

• 2: Robert Allen , David Garlan, A formal basis for architectural connection, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.3, p.213-249, July 1997 [doi>10.1145/258077.258078]
• 3: Don Batory , Sean O'Malley, The design and implementation of hierarchical software systems with reusable components, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.4, p.355-398, Oct. 1992 [doi>10.1145/136586.136587]
• 4: Brown, K. G. Design reverse-engineering and automated design pattern detection in smalltalk. Master' s thesis, North Carolina State University, 1996.
• 5: Robert Cartwright , Matthias Felleisen, Extensible Denotational Language Specifications, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.244-272, April 19-22, 1994
• 6: Drossopoulou, S. and S. Eisenbach. Java is type safeprobably. In European Conference on Object-Oriented Programming, pages 389-418, 1997.
• 7: Dominic Duggan , Constantinos Sourelis, Mixin modules, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.262-273, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 8: A. H. Eden , A. Yehudai , J. Gil, Precise specification and automatic application of design patterns, Proceedings of the 12th international conference on Automated software engineering (formerly: KBSE), p.143, November 02-05, 1997
• 9: Matthias Felleisen, On the expressive power of programming languages, Science of Computer Programming, v.17 n.1-3, p.35-75, Dec. 1991
• 10: Matthias Felleisen , Robert Hieb, The revised report on the syntactic theories of sequential control and state, Theoretical Computer Science, v.103 n.2, p.235-271, 14 Sept. 1992 [doi>10.1016/0304-3975(92)90014-7]
• 11: Findler, R. B. Modular abstract interpreters. Unpublished manuscript, Carnegie Mellon University, June 1995.
• 12: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 13: William Frakes , Carol Terry, Software reuse: metrics and models, ACM Computing Surveys (CSUR), v.28 n.2, p.415-435, June 1996 [doi>10.1145/234528.234531]
• 14: Frappier, hiI., A. h&li and R. Ben Ayed. A relational calculus for software reuse. In IJCAI Workshop on Formal Approaches to the Reuse of Plans, Proofs and Programs, 1995.
• 15: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 16: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 17: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 18: Shriram Krishnamurthi , Matthias Felleisen , Daniel P. Friedman, Synthesizing Object-Oriented and Functional Design to Promote Re-Use, Proceedings of the 12th European Conference on Object-Oriented Programming, p.91-113, July 20-24, 1998
• 19: Charles W. Krueger, Software reuse, ACM Computing Surveys (CSUR), v.24 n.2, p.131-183, June 1992 [doi>10.1145/130844.130856]
• 20: Ronald J. Leach, Software Reuse: Methods, Models and Costs, McGraw-Hill, Inc., New York, NY, 1996
• 21: Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199528]
• 22: McIhoy, M. D. Mass produced software components. In Naur, P. and B. Randell, editors, Report on a Conference of the NATO Science Committee, pages 138-150, October 1968.
• 23: Hafedh Mili , Fatma Mili , Ali Mili, Reusing Software: Issues and Research Directions, IEEE Transactions on Software Engineering, v.21 n.6, p.528-562, June 1995 [doi>10.1109/32.391379]
• 24: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 25: John C. Mitchell, On abstraction and the expressive power of programming languages, Science of Computer Programming, v.21 n.2, p.141-163, Oct. 1993
• 26: Nierstrasz, O., J.-G. Schneider and M. Lumpe. Formalizing composable software systems - a research agenda. In IFIP Workshop on Formal Methods for Open Object-based Distributed Systems, 1996.
• 27: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type systems, John Wiley and Sons Ltd., Chichester, UK, 1994
• 28: Pouhn, J. S. Measuring Software Reuse: Principies, Practices, and Economic Models. Addison-Wesley, 1997.
• 29: Rubén Prieto-Díaz, Status Report: Software Reusability, IEEE Software, v.10 n.3, p.61-66, May 1993 [doi>10.1109/52.210605]
• 30: Mohlalefi Sefika , Aamod Sane , Roy H. Campbell, Monitoring compliance of a software system with its high-level design models, Proceedings of the 18th international conference on Software engineering, p.387-396, March 25-29, 1996, Berlin, Germany
• 31: Mary Shaw , David Garlan, Software architecture: perspectives on an emerging discipline, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 32: Richard M. Stallman, GNU EMACS Manual, Free Software Foundation, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

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

General Terms:
Design, Languages, Performance, Theory, Verification