Program generalization for software reuse: from C to C++

ABSTRACT

We consider the problem of software generalization: Given a program component C, create a parameterized program component C′ such that C′ is usable in a wider variety of syntactic contexts than C. Furthermore, C′ should be a semantically meaningful generalization of C; namely, there must exist an instantiation of C′ that is equivalent in functionality to C.In this paper, we present an algorithm that generalizes C functions via type inference. The original functions operate on specific data types; the result of generalization is a collection of C++ function templates that operate on parameterized types. This version of the generalization problem is useful in the context of converting existing C programs to C++.

REFERENCES

• 1: Gianluigi Caldiera , Victor R. Basili, Identifying and Qualifying Reusable Software Components, Computer, v.24 n.2, p.61-70, February 1991 [doi>10.1109/2.67210]
• 2: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 3: A. Cimitile , G. Visaggio, Software salvaging and the call dominance tree, Journal of Systems and Software, v.28 n.2, p.117-127, Feb. 1995 [doi>10.1016/0164-1212(94)00049-S]
• 4: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 5: F.-J. Grosch and G. Snelting. Polymorphic components for monomorphic languages. In R. Prieto-Diaz and W.B. Frakes, editors, Advances in software reuse: Selected papers from the Second International Workshop on Software Reusability, pages 47-55, Lucca, Italy, March 1993. IEEE Computer Society Press.
• 6: R. Hindley. The principal type-scheme of an object in combinatory logic. Trans. AMS, 146:29-60, 1969.
• 7: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 8: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 9: 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]
• 10: Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, 1978.
• 11: John C. Mitchell, Type systems for programming languages, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 12: Robert O 'Callahan and Daniel Jackson. Detecting shared representations using type inference. Technical Report CMU-CS-95-202, Carnegie Mellon University, September 1995.
• 13: 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
• 14: Rub~n Prieto-D~az and William B. Frakes, editors. Advances in Software Reuse. IEEE Computer Society Press, March 1993.
• 15: Geoffrey Smith , Dennis M. Volpano, Towards an ML-Style Polymorphic Type System for C, Proceedings of the 6th European Symposium on Programming Languages and Systems, p.341-355, April 22-24, 1996
• 16: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 17: Mads Tofte, Type inference for polymorphic references, Information and Computation, v.89 n.1, p.1-34, Nov. 1990 [doi>10.1016/0890-5401(90)90018-D]
• 18: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.
• 19: Mansour Zand , Mansur Samadzadeh, Software reuse: current status and trends, Journal of Systems and Software, v.30 n.3, p.167-170, Sept. 1995 [doi>10.1016/0164-1212(94)00131-6]
• 20: Amy Moormann Zaremski , Jeannette M. Wing, Signature matching: a tool for using software libraries, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.2, p.146-170, April 1995 [doi>10.1145/210134.210179]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous
          Subjects: Reusable software**

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++; C
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure; Functional constructs

General Terms:
Algorithms, Design, Languages