Reengineering class hierarchies using concept analysis

ABSTRACT

The design of a class hierarchy may be imperfect. For example, a class C may contain a member m not accessed in any C-instance, an indication that m could be eliminated, or moved into a derived class. Furthermore, different subsets of C's members may be accessed from different C-instances, indicating that it might be appropriate to split C into multiple classes. We present a framework for detecting and remediating such design problems, which is based on concept analysis. Our method analyzes a class hierarchy along with a set of applications that use it, and constructs a lattice that provides valuable insights into the usage of the class hierarchy in a specific context. We show how a restructured class hierarchy can be generated from the lattice, and how the lattice can serve as a formal basis for interactive tools for redesigning and restructuring class hierarchies.

REFERENCES

• 1: ACCREDITED STANDARDS COMMITTEE X3, I. P. S. Workingpaperfor draft proposed international standard for information systems-programming languageC*. Dot. No. X3J16/97-010S.DraAof25November1997.
• 2: Ole Agesen , David Ungar, Sifting out the gold: delivering compact applications from an exploratory object-oriented programming environment, ACM SIGPLAN Notices, v.29 n.10, p.355-370, Oct. 1994
• 3: BIRKHOFF, G. Lottice Theory. American Mathematical Society, 1940.
• 4: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 5: DAVEY, B., AND PRIESTLEY, H. Introduction to lattices a&order. Cambridge University Press, 1990.
• 6: GANTER, B., AND WILLE, R. Formale Begriisanalyse - Mathematische Grundlagen. SpringerVerlag, 1996.
• 7: Robert Godin , Hafedh Mili, Building and maintaining analysis-level class hierarchies using Galois Lattices, ACM SIGPLAN Notices, v.28 n.10, p.394-410, Oct. 1, 1993
• 8: Robert Godin , Hafedh Mili , Guy W. Mineau , Rokia Missaoui , Amina Arfi , Thuy-Tien Chau, Design of class hierarchies based on concept (Galois) lattices, Theory and Practice of Object Systems, v.4 n.2, p.117-133, April 1998 [doi>10.1002/(SICI)1096-9942(1998)4:2<117::AID-TAPO6>3.3.CO;2-I]
• 9: Maren Krone , Gregor Snelting, On the inference of configuration structures from source code, Proceedings of the 16th international conference on Software engineering, p.49-57, May 16-21, 1994, Sorrento, Italy
• 10: LINDIG. C. Analyse van Sofhvarevarianten. Tech. Rep. 95-02, TU Braunschweig, FB Informatik, 199%
• 11: Christian Lindig , Gregor Snelting, Assessing modular structure of legacy code based on mathematical concept analysis, Proceedings of the 19th international conference on Software engineering, p.349-359, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253354]
• 12: Ivan Moore, Automatic inheritance hierarchy restructuring and method refactoring, ACM SIGPLAN Notices, v.31 n.10, p.235-250, Oct. 1996
• 13: William F. Opdyke , Ralph E. Johnson, Creating abstract superclasses by refactoring, Proceedings of the 1993 ACM conference on Computer science, p.66-73, February 16-18, 1993, Indianapolis, Indiana, United States [doi>10.1145/170791.170804]
• 14: William F. Opdyke, Refactoring object-oriented frameworks, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 15: Linda M. Ott , Jeffrey J. Thuss, The relationship between slices and module cohesion, Proceedings of the 11th international conference on Software engineering, p.198-204, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74614]
• 16: Hemant D. Pande , Barbara G. Ryder, Data-Flow-Based Virtual Function Resolution, Proceedings of the Third International Symposium on Static Analysis, p.238-254, September 24-26, 1996
• 17: G. Ramalingam , Harini Srinivasan, A member lookup algorithm for C++, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.18-30, June 16-18, 1997, Las Vegas, Nevada, United States
• 18: Jonathan G. Rossie, Jr. , Daniel P. Friedman, An algebraic semantics of subobjects, ACM SIGPLAN Notices, v.30 n.10, p.187-199, Oct. 17, 1995
• 19: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 20: Michael Siff , Thomas W. Reps, Identifying modules via concept analysis, Proceedings of the International Conference on Software Maintenance, p.170-179, October 01-03, 1997
• 21: Gregor Snelting, Reengineering of configurations based on mathematical concept analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.2, p.146-189, April 1996 [doi>10.1145/227607.227613]
• 22: Gregor Snelting, Concept analysis—a new framework for program understanding, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.1-10, June 16-16, 1998, Montreal, Quebec, Canada
• 23: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 24: Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.324-332, June 17-19, 1998, Montreal, Quebec, Canada
• 25: Frank Tip , Jong-Deok Choi , John Field , G. Ramalingam, Slicing class hierarchies in C++, ACM SIGPLAN Notices, v.31 n.10, p.179-197, Oct. 1996
• 26: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, ACM SIGPLAN Notices, v.32 n.10, p.271-285, Oct. 1997
• 27: TIP, F., AND SWEENEY, P. F. Class hierarchy specialization. Tech. Rep. RC21111, IBhi TJ. Watson Research Center, February 1998.
• 28: \VILLE. R. Restructuring lattice theory: an approach based on hierarchies of concepts. OrderedSers(l9S2),445-470.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Measurement, Performance, Theory