Susan Horwitz
Thomas Reps
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. To date, the only available tools for assisting with program integration are variants of text-based differential file comparators; these are of limited utility because one has no guarantees about how the program that is the product of an integration behaves compared to the programs that were integrated.
This paper concerns the design of a semantics-based tool for automatically integrating program versions. The main contribution of the paper is an algorithm 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), the algorithm produces a program M that integrates A and B. The algorithm is predicated on the assumption that differences in the behavior of the variant programs from that of Base, rather than differences in the text, are significant and must be preserved in M. Although it is undecidable whether a program modification actually leads to such a difference, it is possible to determine a safe approximation by comparing each of the variants with Base. To determine this information, the integration algorithm employs a program representation that is similar (although not identical) to the dependence graphs that have been used previously in vectorizing and parallelizing compilers. The algorithm also makes use of the notion of a program slice to find just those statements of a program that determine the values of potentially affected variables.
The program-integration problem has not been formalized previously. It should be noted, however, that the integration problem examined here is a greatly simplified one; in particular, we assume that expressions contain only scalar variables and constants, and that the only statements used in programs are assignment statements, conditional statements, and while-loops.
- 1 AHO, A. V., SETHI, R., AND ULLMAN, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass., 1986. Google Scholar
- 2 ALLEN, J. R., AND KENNEDY, K. PFC: A program to convert Fortran to parallel form. Tech. Rep. MASC TR82-6, Dept. of Math. Sciences, Rice Univ., Houston, Tex., March 1982.Google Scholar
- 3 ALLEN, J. R. Dependence analysis for subscripted variables and its application to program transformations. Ph.D. dissertation, Dept. of Math. Sciences, Rice Univ., Houston, Tex., April 1983. Google Scholar
- 4 ALLEN, J. R., AND KENNEDY, K. Automatic loop interchange. In Proceedings of the SIGPLAN 84 Symposium on Compiler Construction (Montreal, June 20-22, 1984). ACM SIGPLAN Not. 19, 6 (June 1984), 233-246. Google Scholar
- 5 BALL, T., HORWITZ, S., AND REPS, T. Correctness of an algorithm for reconstituting a program from a dependence graph. Computer Sciences Dept., Univ. of Wisconsin, Madison. Tech. Rep. in preparation, Spring 1989.Google Scholar
- 6 BANNEPJEE, U. Speedup of ordinary programs. Ph.D. dissertation and Tech. Rep. R-79-989, Dept. of Computer Science, Univ. of Illinois, Urbana, Oct. 1979. Google Scholar
- 7 BERZINS, V. On merging software extensions. Acta Inf. 23 (1986), 607-619. Google Scholar
- 8 DIJKSTRA, E.W. A Discipline of Programming. Prentice-Hall, Englewood, Cliffs, N.J., 1976. Google Scholar
- 9 DONZEAU-GouGE, V., HUET, G., KAHN, G., AND LANG, B. Programming environments based on structured editors: The MENTOR experience. In Interactive Programming Environments, D. Barstow, E. Sandewall, and H. Shrobe, Eds., McGraw-Hill, New York, 1984, 128-140.Google Scholar
- 10 FERRANTE, J., AND MACE, M. On linearizing parallel code. In Conference Record of the Twelfth ACM Symposium on Principles of Programming Languages (New Orleans, La., Jan. 14-16, 1985). ACM, New York, 1985, 179-189. Google Scholar
- 11 FERRANTE, J., OTTENSTEIN, K., AND WARREN, J. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (July 1987), 319-349. Google Scholar
- 12 HABERMANN, A. N., AND NOTKIN, D. Gandalf: Software development environments. IEEE Trans. Softw. Eng. SE-12, 12 (Dec. 1986), 1117-1127. Google Scholar
- 13 HOARE, C. A.R. An axiomatic basis for computer programming. Commun. ACM 12, 10 (Oct. 1969), 576-580, 583. Google Scholar
- 14 HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. TR- 690, Computer Sciences Dept., Univ. of Wisconsin, Madison, March 1987.Google Scholar
- 15 HORWITZ, S., PFE1FFER, P., AND REPS, T. Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation (Portland, Ore., June 21-23, 1989). ACM, New York, 1989. Google Scholar
- 16 HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. In Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 13-15, 1988), ACM, New York, 1988, 133-145. Google Scholar
- 17 HORWITZ, S., PRINS, J., AND REPS, T. On the adequacy of program dependence graphs for representing programs. In Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 13-15, 1988). ACM, New York, 1988, 146-157. Google Scholar
- 18 HORWITZ, S., PRINS, J., AND REPS, T. On the suitability of dependence graphs for representing programs. Computer Sciences Dept., Univ. of Wisconsin, Madison, Aug. 1988. Submitted for publication.Google Scholar
- 19 HORWITZ, S., RE?S, T., AND BINKLE~, D. Interprocedural slicing using dependence graphs. In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (Atlanta, Ga., June 22-24, 1988). ACM SIGPLANNot. 23, 7 (July 1988), 35-46. Google Scholar
- 20 JONES, N. D., AND MUCHNICK, S.S. Flow analysis and optimization of Lisp-like structures. In{ Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds., Prentice- Hall, Englewood Cliffs, N.J., 1981.Google Scholar
- 21 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. Comput. C- 21, 12 (Dec. 1972), 1293-1310.Google Scholar
- 22 KUCK, D. J., KUHN, R. H., LEASURE, B., PADUA, D. A., AND WOLFE, M. Dependence graphs and compiler optimizations. In Conference Record of the Eighth ACM Symposium on Principles of Programming Languages (Williamsburg, Va., Jan. 26-28, 1981), ACM, New York, 1981, 207-218. Google Scholar
- 23 NOTKIN, D., ELLISON, R. J, STAUDT, B. J., KAISER, G. E., KANT, E., HABERMANN, A. N, AMBRIOLA, V., AND MONTANGERO, C. Special issue on the GANDALF project. J. Syst. Softw. 5, 2 (May 1985).Google Scholar
- 24 OTTENSTEIN, K. J., AND OTTENSTEIN, L. M. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (Pittsburgh, Pa., Apr. 23-25, 1984). ACM SIGPLAN Not. 19, 5 (May 1984), 177-184. Google Scholar
- 25 REPS, T., AND TEITELBAUM, T. The Synthesizer Generator. In Proceedings of the ACM SIGSOFT/S1GPLAN Software Engineering Symposium on Practical Software Development Environments (Pittsburgh, Pa., April 23-25, 1984). ACM SIGPLAN Not. 19, 5 (May 1984), 42-48. Google Scholar
- 26 REPS, T., AND TEITELBAUM, T. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer, New York, 1988. Google Scholar
- 27 REPS, T., AND YANG, W. The semantics of program slicing. TR-777, Computer Sciences Dept., Univ. of Wisconsin, Madison, June 1988.Google Scholar
- 28 REPS, T., AND YANG, W. The semantics of program slicing and program integration. In Proceedings of the Colloquium on Current Issues in Programming Languages (Barcelona, March 13-17, 1989). Lecture Notes in Computer Science, 352. Springer, New York, 1989, 360-374. Google Scholar
- 29 Tlcn~, W. F. RCS: A system for version control. Softw. Pract. Exper. 15, 7 (July 1985), 637-654. Google Scholar
- 30 WEISER, M. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July 1984), 352-357.Google Scholar
- 31 WOLFE, M.J. Optimizing supercompilers for supercomputers. Ph.D. dissertation and Tech. Rep. R-82-1105, Dept. of Computer Science, Univ. of Illinois, Urbana, Oct. 1982. Google Scholar
Index Terms
- Integrating noninterfering versions of programs
Recommendations
Integrating non-intering versions of programs
POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThe 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 ...
Illustrating interference in interfering versions of programs
SCM '89: Proceedings of the 2nd International Workshop on Software configuration managementThe need to integrate several versions of a program into a common one arises frequently, but it is a tedious and time consuming task to merge programs by hand. The program-integration algorithm recently proposed by S. Horwitz, J. Prins, and T. Reps ...
Illustrating interference in interfering versions of programs
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 merge programs by hand. The program-integration algorithm recently proposed by S. Horwitz, J. Prins, and T. Reps ...
Reviews
Vladimir Zwass
This paper addresses a simplified program-integration problem. The general problem is the need to integrate several different versions of a system. Several scenarios may lead to this situation. The base version of the system in question may have been modified by several different maintainers, who thus produced several versions with different features. In a somewhat different and more regrettable situation, a number of different versions of a program may have been created during system development. An approach to comparing programs as text files, such as UNIX's diff utility provides, does not contribute to a satisfactory solution. It is the behavior of the resulting program that needs to correspond to the behavior of all the versions, rather than its text being a combination of their texts. The authors offer an algorithm that permits the merged version of the program to preserve all the behavior modifications introduced in the variants. The algorithm accepts as input two or more variants of the base program and, if the changes introduced in the different variants do not interfere with each other, produces a new, merged program that incorporates changes made in all variants. The algorithm relies on two tools developed in previous work. Program dependence graphs are employed to represent control and data dependences within the program. A program slicing operation on dependence graphs permits a comparison of program behaviors. It needs to be stressed, echoing the authors' caveat, that the algorithm is offered for a highly simplified programming language. This language contains only the three fundamental programming structures—assignments, conditional statements, and while-do loops—and its expressions contain only scalar variables and constants. The authors offer a number of suggestions for future work that would aim to extend the integration algorithm to realistic programming languages and programming in the large.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments