Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-10-02
2001-05-08
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06230314
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to object-oriented programming (OOP), and in particular to OOP systems supporting the C++ programming language.
2. Background Description
The C++ programming language provides a number of features such as classes, class members, inheritance, multiple inheritance, and virtual inheritance. These object-oriented features have several advantages. Most importantly, they enable the creation of class libraries that can be reused in many different applications. However, such code reuse comes at a price. In order to facilitate reusability, OO programming encourages the design of classes that incorporate a high degree of functionality. Programs that use a class library typically exercise only a part of the library's functionality. Such a program may pay a performance penalty for library functionality that it does not use. This performance penalty may be due to the following reasons.
A library may contain dead executable code. Dead executable code is code that is not executed during any execution of the program, or code whose execution cannot affect the program's observable behavior. Dead executable code in an application adversely affects execution speed (both directly, through execution of redundant code, and indirectly through cache/page effects) and is hence undesirable. Dead executable code may take the form of unused library procedures. Prior art has addressed the problem of eliminating unused functions; an example of such prior art is, e.g., A. Srivastava, “Unused procedures in object-oriented programming”, ACM Letters on Programming Languages and Systems, 1(4), pp. 355-364. Other prior art has focused on eliminating dead code at the statement level; see e.g., A. Aho, R. Sethi, and J. D. Ullman, “Compilers, Principles, Techniques, and Tools”, Addison-Wesley, 1986, and F. Tip, “A Survey of Program Slicing Techniques”, Journal of Programming Languages 3,3, (1995), pp. 121-189.
Objects may contain unnecessary data members and subobjects. Unused members and subobjects within objects have the effect of increasing the space requirements of an application. This may also result in decreased execution speed because creation/destruction of objects may require more time than is necessary (due to the construction/destruction of redundant components in objects), as well as through cache/page effects. Prior art has addressed the elimination of data members and subobjects that are not accessed during any execution of an application; see Tip et al., “Slicing Class Hierarchies in C++”, Proceedings of the Eleventh Annual Conference on Object-Oriented Programming, Languages, and Applications (OOPSLA'96), (San Jose, Calif., October 1996), ACM SIGPLAN Notices 31(10), pp. 179-197. However, the prior art does not address situations where a given member is (un)used by some, but not all, instances of a given class.
Class hierarchies may unnecessarily exhibit virtual inheritance. Class hierarchies that represent extendable frameworks may exhibit virtual inheritance. The use of virtual inheritance in a program's class hierarchy increases the time require to access class members, and may increase the size of objects.
Such prior art methods that eliminate virtual inheritance are only capable of eliminating classes, eliminating inheritance relations, and replacing virtual inheritance relations with non-virtual inheritance relations, and are only applicable under certain limited situations.
SUMMARY OF THE INVENTION
The problems presented above and the related problems of the prior art are solved by the present invention, method and apparatus for specializing class hierarchies. The present invention is concerned with the elimination of redundant components from objects. Specifically, the invention is capable of detecting situations where a member of a given class is used by some, but not all instances of that class, and the elimination of this member from the instances where it is not needed. This is accomplished by an analysis of the program and its class hierarchy, followed by the construction of a new, specialized class hierarchy and a transformation of the program. These operations preserve the original behavior of the program, and have the effect of “optimizing away” unneeded class members from objects. The invention is also capable of replacing class hierarchies that exhibit virtual inheritance with class hierarchies that only exhibit nonvirtual inheritance, and is applicable across a broad spectrum of inheritance structures. Transformation of virtual into nonvirtual inheritance improves program performance because it reduces the time required to access members that are located in virtual base classes. In addition, it may reduce the space required to represent objects.
The invention is preferably used subsequent to the removal of dead or redundant executable code (i.e., program slicing). In the alternative, the invention may be used in program understanding tools, and in design tools that assist programmers in improving the design of class hierarchies.
REFERENCES:
patent: 5287488 (1994-02-01), Sakata et al.
patent: 5414854 (1995-05-01), Henninger et al.
patent: 5493680 (1996-02-01), Danforth
patent: 5522079 (1996-05-01), Acker et al.
patent: 5544302 (1996-08-01), Nguyen et al.
patent: 5732263 (1998-03-01), Havens et al.
patent: 5845119 (1998-12-01), Kozuka et al.
patent: 6023578 (2000-02-01), Birsan et al.
“Object-Oriented Analysis and Simulation”, David K. C. Hill Addison-Wesley Chapters 1-2 1996.*
Object-Oriented Information Systems Planning and Implementation David A. Taylor, Apr. 1992.*
Aho et al, Compilers Principles, Techniques and Tools Chapters 1, 9, 10, Sep. 1985.*
B. Stroustrup et al, The Annotated C ++Reference Manual Chapters 3,4,9,19,11,12,14 and pp. 47-72 of chapter 5, Jan. 1994.*
Type Systems for Querying Class Hierachies with non strict inheritance, A. Borgida, 1989.*
Issues in the Design and Specification of Class Libraries, G. Kiczales et al., 1992.*
Reuse Contracts: Managing the Evolution of Reusable Assets, P. Steyaert et al., 1996.*
Software Reuse Architecture, Process and Organization for Business Sucess, I. Jacobson et al, Jan. 1997.*
Feature-Oriented Programming A Fresh Look at Objects, C. Prehofer, Jun. 1997.*
Object-Oriented Programming: Themes and Variations, M. Stefik et al., 1985.*
Contracts: Specifying Behavioral Compositions in Object-Oriented Systems, R. Helm et al., Oct. 1990.*
Beginning Visual C ++Components with MFC Extensions & ActiveX Controls, Matt Telles., p. 84, Oct. 1996.*
Aho et al, Compiliers Principles Techniques and Tools pp. 10, 530-534,555-557, 585-710, Sep. 12, 1985.*
Rumbaugh et al. Object-Oriented Modeling and Design pp. 1-45, 60-61 283-291, Nov. 1990.*
B. Stroustrup, The C ++ Programming Language pp. 34,91,147,236,241,283,304,310,313,766, Jul. 7, 1997.*
B. Stroustrup, The Design and Evolution of C ++, pp. 30,53,72,74,108,138,225,257,265,273,275,288,290,331, Mar. 9, 1994.*
R.C.H. Law Object Oriented Program SLicing, May 1994.*
Holze et al. Optimizing Dynamically Dispatched Calls with Run-Time Type Feedback, 1994.*
Larsen et al. Slicing Object Oriented Software, 1996.*
Dean et al Optimization of Object Oriented Programs Using Static Class Hierachy Analysis, Aug. 1985.*
Zhao et al. Static Slicing of Concurrent Object Oriented Programs, 1996.
Sweeney Peter F.
Tip Frank
August Casey P.
Fleit, Kain, Gibbons, Gutman & Bongini P. L.
Gibbons Jon A.
Ingberg Todd
International Business Machines - Corporation
LandOfFree
Method and device for program transformation using class... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for program transformation using class..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for program transformation using class... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2471062