Integrating non-intering versions of programs

ABSTRACT

The need to integrate several versions of a program into a common one arises frequently, but it is a tedious and time consuming task to integrate programs by hand. The main contribution of this paper is an algorithm, called integrate, that takes as input three programs A, B, and Base, where A and B are two variants of Base. Whenever the changes made to Base to create A and B do not “interfere” (in a sense defined in the paper), Integrate produces a program M that integrates A and B.

REFERENCES

• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Allen82: Allen, J. R. and Kennedy, K., "PFC: A program to convert Fortran to parallel form," Rep. MASC-TR82-6, Dept. of Math. Sciences, Rice Univ., Houston, Tex. (March 1982).
• Allen84: John R. Allen , Ken Kennedy, Automatic loop interchange, ACM SIGPLAN Notices, v.19 n.6, p.233-246, June 1984
• Berzins86: V Berzins, On merging software extensions, Acta Informatica, v.23 n.6, p.607-619, Nov. 1986 [doi>10.1007/BF00264309]
• Ferrante87: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• Horwitz87: Horwitz, S., Prins, J., and Reps, T., "Integrating non-interfering versions of programs," TR-690, Computer Sciences Department, University of Wisconsin, Madison, WI (March 1987).
• Horwitz87a: Horwitz, S., Prins, J., and Reps, T., Support for integrating program variants in an environment for programming in the large, Computer Sciences Department, University of Wisconsin, Madison, WI (August 1987).
• Horwitz88: S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
• Kuck72: Kuck, D.J., Muraoka, Y., and Chen, S.C., "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Trans. on Computers C-21 pp. 1293- 1310 (December 1972).
• Kuck81: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• Ottenstein84: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• Reps84: Thomas Reps , Tim Teitelbaum, The synthesizer generator, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.42-48, April 1984
• Reps87: Reps, T. and Yang, W., The semantics of program sl&ing, Computer Sciences Department, University of Wisconsin, Madison, WI (In preparation, Fall 1987).
• Weiser84: Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Methodologies (e.g., object-oriented, structured)
        D.2.10 Design**
            Subjects: Methodologies**
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Design