Software merge: semantics of combining changes to programs

ABSTRACT

We present a language-independent semantic model of the process of combining changes to programs. This model extends the domains used in denotational semantics (complete partial orders) to Boolean algebras, and represents incompatible modifications as well as compatible extensions. The model is used to define the intended semantics of change-merging operations on programs and to establish some general properties of software merging. We determine conditions under which changes to subprograms of a software system can be merged independently and illustrate cases where this is not possible.

REFERENCES

• 1: BERZINS, V, ED. 1993. Proceedings of the ARO/AFOSR/ONR Workshop on Increaszng the Practical Impact of Formal Methods for Computer-Azded Software Development Software Slicing, Merging, and Integratton. U.S. Naval Postgraduate School, Monterey, Caif
• 2: BERZINS, V. 1991. Software merge Models and methods Int J. Syst. Integr. 1, 2 (Aug.), 121-141.
• 3: V Berzins, On merging software extensions, Acta Informatica, v.23 n.6, p.607-619, Nov. 1986 [doi>10.1007/BF00264309]
• 4: Valdis Berzins , Lucia Luqi, Software engineering with abstractions, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 5: V. Berzins , Luqi , A. Yehudai, Using Transformations in Specification-Based Prototyping, IEEE Transactions on Software Engineering, v.19 n.5, p.436-452, May 1993 [doi>10.1109/32.232011]
• 6: D~F~Ea, D. 1990. A model for merging different versions of a PSDL program. M. S. thesis, Dept. of Computer Science, Naval Postgraduate School, Monterey, Caif.
• 7: DAM}PIER, D., LUQI, AND BERZINS, V. 1994. Automated merging of software prototypes. J Syst. Integr. 4, 1 (Feb.), 33-49.
• 8: DAMPIER, D., LUQI, AND BERZINS, V. 1993. Automated merging of software prototypes. In Proceedtngs of the 5th International Conference on Software Engzneering and Knowledge Engineemng (San Francisco, June 16-18). Knowledge Systems Institute, Skokie, Ill, 604-611.
• 9: John V. Guttag , Deepak Kapur , David R. Musser, Derived Pairs, Overlap Closures, and Rewrite Dominoes: New Tools for Analyzing Term rewriting Systems, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.300-312, July 12-16, 1982
• 10: HALMOS, P. 1963. Lectures on Boolean Algebras. Van Nostrand, Princeton, N.J.
• 11: HOARE, C. A. R. 1985. A couple of novelties in the propositional calculus Zeitschrift fi~r Mathemattsche Log~k und Grundlagen der Mathemat~k 31, 2, 173-178.
• 12: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 13: B. Kramer , Luqi , V. Berzins, Compositional Semantics of a Real-Time Prototyping Language, IEEE Transactions on Software Engineering, v.19 n.5, p.453-477, May 1993 [doi>10.1109/32.232012]
• 14: Luqi, A Graph Model for Software Evolution, IEEE Transactions on Software Engineering, v.16 n.8, p.917-927, August 1990 [doi>10.1109/32.57627]
• 15: Luqi , V. Berzins , R. T. Yeh, A Prototyping Language for Real-Time Software, IEEE Transactions on Software Engineering, v.14 n.10, p.1409-1423, October 1988 [doi>10.1109/32.6186]
• 16: MAcNEILLE, H. 1937. Partially ordered sets. Trans. Am. Math. Soc. 42, 416-460.
• 17: MACLANE, S., AND BIRKHOFF, G. 1967. Algebra. Macmillan, New York.
• 18: MCKINSEY, J., AND TARSKI, n. 1946. On closed elements in closure algebras. Ann. Math. 47, 1 (Jan.), 122-162.
• 19: McKINsEY, J., AND TARSKI, A. 1944. The algebra of topology. Ann. Math. 45, 1 (Jan.), 141-191.
• 20: G. Ramalingam , Thomas Reps, A theory of program modifications, Proceedings of the international joint conference on theory and practice of software development on Advances in distributed computing (ADC) and colloquium on combining paradigms for software development (CCPSD): Vol. 2, p.137-152, April 1991, Brighton, United Kingdom
• 21: Thomas Reps, Algebraic properties of program integration, Science of Computer Programming, v.17 n.1-3, p.139-215, Dec. 1991
• 22: Charles Rich , Richard C. Waters, The programmer's apprentice, ACM Press, New York, NY, 1990
• 23: ROSCOE, W. 1992. Lecture Notes on Domain Theory. Programming Research Group, Oxford University.
• 24: STERLING, L., AND LAKHOTIA, A. 1988. Composing prolog meta-interpreters. In Logic Programruing: Proceedings of the 5th Internattonal Conference and Symposium. MIT Press, Cambridge, Mass., 386-403.
• 25: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 26: Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, Proceedings of the fourth ACM SIGSOFT symposium on Software development environments, p.133-143, December 03-05, 1990, Irvine, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Enhancement**; Version control
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program modification; Program synthesis; Program transformation

General Terms:
Languages, Theory, Verification

Keywords:
domains, semantics, software change merging, software maintenance