Using modern mathematics as an FOSD modeling language

ABSTRACT

Modeling languages are a fundamental part of automated software development. MDD, for example, uses UML class diagrams and state machines as languages to define applications. In this paper, we explore how Feature Oriented Software Development (FOSD) uses modern mathematics as a modeling language to express the design and synthesis of programs in software product lines, but demands little mathematical sophistication from its users. Doing so has three practical benefits: (1) it offers a simple and principled mathematical description of how FOSD transforms, derives, and relates program artifacts, (2) it exposes previously unrecognized commuting relationships among tool chains, thereby providing new ways to debug tools, and (3) it reveals new ways to optimize software synthesis.

REFERENCES

• 1: Davide Ancona , Giovanni Lagorio , Elena Zucca, Jam---designing a Java extension with mixins, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.5, p.641-712, September 2003 [doi>10.1145/937563.937567]
• 2: Davide Ancona , Ferruccio Damiani , Sophia Drossopoulou , Elena Zucca, Polymorphic bytecode: compositional compilation for Java-like languages, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.26-37, January 12-14, 2005, Long Beach, California, USA
• 3: AHEAD Tool Suite, www.cs.utexas.edu/users/schwartz/index.html
• 4: S. Apel, "The Role of Features and Aspects in Software Development", Ph.D. Dept. of Tech.l and Business Info. Systems, University of Magdeburg, Germany, March 2007.
• 5: Sven Apel , Christian Kästner , Don Batory, Program refactoring using functional aspects, Proceedings of the 7th international conference on Generative programming and component engineering, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449913.1449938]
• 6: Andrew W. Appel, Axiomatic bootstrapping: a guide for compiler hackers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1699-1718, Nov. 1994 [doi>10.1145/197320.197336]
• 7: 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]
• 8: Don Batory , Clay Johnson , Bob MacDonald , Dale von Heeder, Achieving extensibility through product-lines and domain-specific languages: a case study, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.2, p.191-214, April 2002 [doi>10.1145/505145.505147]
• 9: D. Batory, "A Science of Software Design", AMAST 2004.
• 10: Scaling Step-Wise Refinement, IEEE Transactions on Software Engineering, v.30 n.6, p.355-371, June 2004 [doi>10.1109/TSE.2004.23]
• 11: D. Batory, "From Implemention to Theory in Product Synthesis", University of Texas Austin, Dept. Comp. Science TR-07-35, June 2007.
• 12: D. Batory and E. Börger. "On The Modularization of Theorems for Software Product Lines", to appear in JUCS.
• 13: Ira D. Baxter, Design maintenance systems, Communications of the ACM, v.35 n.4, p.73-89, April 1992 [doi>10.1145/129852.129859]
• 14: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 15: Manfred Broy , Ingolf H. Krüger , Michael Meisinger, A formal model of services, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.1, p.5-es, February 2007 [doi>10.1145/1189748.1189753]
• 16: Muffy Calder , Mario Kolberg , Evan H. Magill , Stephan Reiff-Marganiec, Feature interaction: a critical review and considered forecast, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.1, p.115-141, 15 January 2003 [doi>10.1016/S1389-1286(02)00352-3]
• 17: Juei Chang , Debra J. Richardson, Structural specification-based testing: automated support and experimental evaluation, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.285-302, September 06-10, 1999, Toulouse, France
• 18: Yoonsik Cheon , Gary T. Leavens, A Simple and Practical Approach to Unit Testing: The JML and JUnit Way, Proceedings of the 16th European Conference on Object-Oriented Programming, p.231-255, June 10-14, 2002
• 19: Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
• 20: Krzysztof Czarnecki , Ulrich W. Eisenecker, Generative programming: methods, tools, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 2000
• 21: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 22: Jay Earley , Howard Sturgis, A formalism for translator interactions, Communications of the ACM, v.13 n.10, p.607-617, Oct. 1970 [doi>10.1145/355598.362740]
• 23: H. Ehrig , Bernd Mahr, Fundamentals of algebraic specification 2: module specifications and constraints, Springer-Verlag New York, Inc., New York, NY, 1990
• 24: E. Ernst, "Higher Order Hierarchies", ECOOP 2003.
• 25: JosT Luiz Fiadeiro, Categories for Software Engineering, SpringerVerlag, 2004
• 26: J. Goguen. "Principles of Parameterized Programming" in T. Biggerstaff and A. Perlis, Software Reusability Volume II: Applications and Experiences, Addison-Wesley, 1990.
• 27: J. Goguen. "A Categorical Manifesto". Mathematical Structures in Computer Science, 1991.
• 28: Hassan Gomaa, Designing Software Product Lines with UML: From Use Cases to Pattern-Based Software Architectures, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 2004
• 29: John B. Goodenough , Susan L. Gerhart, Toward a theory of test data selection, ACM SIGPLAN Notices, v.10 n.6, p.493-510, June 1975
• 30: J. Gray, et al. "Model Driven Program Transformation of a Large Avionics Framework", GPCE 2004.
• 31: Wolfgang Grieskamp , Yuri Gurevich , Wolfram Schulte , Margus Veanes, Generating finite state machines from abstract state machines, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 32: Daniel Jackson, Software Abstractions: Logic, Language, and Analysis, The MIT Press, 2006
• 33: Daniel Jackson, Alloy: a lightweight object modelling notation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.2, p.256-290, April 2002 [doi>10.1145/505145.505149]
• 34: K. Kang, et al., "Feature-Oriented Domain Analysis (FODA) Feasibility Study", Tech Report CMU/SEI-90-TR-21.
• 35: S. Khurshid, E. Uzuncaova, D. Garcia, and D. Batory. "Testing Software Product Lines Using Incremental Test Generation". Submitted.
• 36: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 37: Chang Hwan Peter Kim , Christian Kästner , Don Batory, On the modularity of feature interactions, Proceedings of the 7th international conference on Generative programming and component engineering, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449913.1449919]
• 38: Anneke G. Kleppe , Jos Warmer , Wim Bast, MDA Explained: The Model Driven Architecture: Practice and Promise, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 39: F. William Lawvere , Stephen H. Schanuel, Conceptual mathematics: a first introduction to categories, Buffalo Workshop Press, Buffalo, NY, 1991
• 40: Gary T. Leavens , Jean-Raymond Abrial , Don Batory , Michael Butler , Alessandro Coglio , Kathi Fisler , Eric Hehner , Cliff Jones , Dale Miller , Simon Peyton-Jones , Murali Sitaraman , Douglas R. Smith , Aaron Stump, Roadmap for enhanced languages and methods to aid verification, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173740]
• 41: Harry C. Li , Shriram Krishnamurthi , Kathi Fisler, Modular Verification of Open Features Using Three-Valued Model Checking, Automated Software Engineering, v.12 n.3, p.349-382, July 2005 [doi>10.1007/s10515-005-2643-9]
• 42: 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]
• 43: R. Lopez-Herrejon, D. Batory, and W. Cook. "Evaluating Support for Features in Advanced Modularization Technologies", ECOOP 2005.
• 44: Roberto Lopez-Herrejon , Don Batory , Christian Lengauer, A disciplined approach to aspect composition, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina [doi>10.1145/1111542.1111554]
• 45: O. L. Madsen , B. Moller-Pedersen, Virtual classes: a powerful mechanism in object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.397-406, October 02-06, 1989, New Orleans, Louisiana, United States
• 46: T. Mens, K. Czarnecki, and P. van Gorp. "A Taxonomy of Model Transformations", Dagstuhl Seminar Proceedings 04101. drops.dagstuhl.de/opus/volltexte/2005/11
• 47: M. Odersky, et al. "An Overview of the Scala Programming Language". September 2004, scala.epfl.ch
• 48: D. Pavlovic and D. R. Smith. "Software Development by Refinement", UNU/IIST 10th Anniversary Colloquium, Formal Methods at the Crossroads: From Panaea to Foundational Support, Springer-Verlag LNCS 2757, 2003.
• 49: Benjamin C. Pierce, Basic category theory for computer scientists, MIT Press, Cambridge, MA, 1991
• 50: Klaus Pohl , Günter Böckle , Frank J. van der Linden, Software Product Line Engineering: Foundations, Principles and Techniques, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 51: T. Reenskaug, et al. "OORASS: Seamless support for the creation and maintenance of object-oriented systems". Journal of Object-Oriented Programming, October 1992.
• 52: D. Roundy, "Theory of Patches", //darcs.net/manual/node8.html
• 53: David E. Rydeheard , Rod M. Burstall, Computational category theory, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 54: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 55: J. M. Spivey, The Z notation: a reference manual, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1992
• 56: Salvador Trujillo , Don Batory , Oscar Diaz, Feature Oriented Model Driven Development: A Case Study for Portlets, Proceedings of the 29th international conference on Software Engineering, p.44-53, May 20-26, 2007 [doi>10.1109/ICSE.2007.36]
• 57: Salvador Trujillo , Maider Azanza , Oscar Diaz, Generative metaprogramming, Proceedings of the 6th international conference on Generative programming and component engineering, October 01-03, 2007, Salzburg, Austria [doi>10.1145/1289971.1289990]
• 58: Michael VanHilst , David Notkin, Using role components in implement collaboration-based designs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.359-369, October 06-10, 1996, San Jose, California, United States
• 59: David M. Weiss , Chi Tau Robert Lai, Software product-line engineering: a family-based software development process, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 60: Engin Uzuncaova , Daniel Garcia , Sarfraz Khurshid , Don Batory, A specification-based approach to testing software product lines, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287701]
• 61: Engin Uzuncaova , Sarfraz Khurshid, Constraint Prioritization for Efficient Analysis of Declarative Models, Proceedings of the 15th international symposium on Formal Methods, May 26-30, 2008, Turku, Finland [doi>10.1007/978-3-540-68237-0_22]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Languages (e.g., description, interconnection, definition)

General Terms:
Design, Theory

Keywords:
commuting diagrams, features, geodesics, model driven design, software product lines