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. 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. 2 AGESEN, O., AND UNGAR, D. Sifting out the gold: Delivering compact applications from an exploratory object-oriented programming environment. In Proceedings of the Ninth Annual Conference on Object-Oriented Programming Systems, Languages. and Applications (OOPSLA'94) (Portland, OR, 1994). pp. 355-370. ACh!SIGPLANNotices 29(10).
3. 3 BIRKHOFF, G. Lottice Theory. American Mathematical Society, 1940.
4. 4 CHOI, J.-D., BURKE, AI., AND CARINI, P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side eRects. In Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages (1993), ACM, pp. 232-245.
5. 5 DAVEY, B., AND PRIESTLEY, H. Introduction to lattices a&order. Cambridge University Press, 1990.
6. 6 GANTER, B., AND WILLE, R. Formale Begriisanalyse - Mathematische Grundlagen. SpringerVerlag, 1996.
7. 7 GODIN, R. AND BItLt. H. Building and maintaininganalysis-levelclass hierarchies using galois lattices. In Praceedings of the Eighth Annual Conference on Object-OrienredProgrammingSjxtems. Languages,andApplications(OOP- S4'93)(:Hshington,DC, 1993),pp. 394-410.ACMSIGPLANNofices28(10).
8. 8 GoDIN.R. hltLt, H., hIINEAU,G. IV., hiISSAOUI,R., ARFI, A., ANDCHAU, T.-T. Design ofclass hierarchies based on concept(galois) lattices. Theory and Practice of Object Systems 4,2 (1998), 117-134.
9. 9 KRONE. hl. AND SNELTING, G. On the inference of configurationstructures from source code. In Proceedingsofrhe I994Intemarional Confirence on Sofzwarr Engineering(ICSE'94) (Sorrento, Italy. hIay 1994), pp. 49-51.
10. 10 LINDIG. C. Analyse van Sofhvarevarianten. Tech. Rep. 95-02, TU Braunschweig, FB Informatik, 199%
11. 11 LINDIG, C., AND SNELTIKG, G. Assessing modularstmcmre of legacy code based on mathematical concept analysis. In Proceedings ofthe 1997 Infernational ConferenceonSofnvareEngineering(IGSE'97)(Boston, MA, hlay 1997), pp. 349-359.
12. 12 MOORE, I. Automatic inheritance hierarchy restructuring and method refactoting. In Proceedings of the EIevenlh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSL4'96) (San Jose, CA. 19961,. 235-250. ACMSIGPLANNofices31(10).
13. 13 OPDYKE. W. ANDJOHNSON, R. Creatingabstractsuperclarsesbyrefactoring. In AC&f I993 Cornpurer Science Conference (1993).
14. 14 OPDYKE, W. F. Refictming Object-Oriented Framework. PhD thesis, University Oflllinois at Urbana-Champaign, 1992.
15. 15 OTT. L. hi. AND THUS, J. The relationship between slices and module cohesion. In Proceedings of rhe 11th International Conference on Sofhvare Engineeting (19S9). pp. 19%204.
16. 16 PANDE, H. D., AND RSDER, B. G. Data-flow-based virtual function resolution. In Proceedings of rhe Third International Symposium on Sratic Analysti (SAS'96)(September 1996).pp. 23S-254. Springer-VerIagLNCS 1145.
17. 17 RAhfALINGAnl. G., AND SRINIVASAN, H. A member loohp algorithm for Cti: In Proceedings of rhe ACM SIGPLANP7 Conference on Programming LanguageDesign andImpIemenrarion(l Vegas, NV, 1997). pp. 18-30.
18. 18 ROSSIE. J. G., AND FRIEDnIAN, D. P. An algebraic semantics of subobjects. In Procerdingv of the Tenth Annual Conference on Object-Oriented Programming .Qslems, Languages, and Applications (OOPSLA '95) (Austin, TX, 1995), pp. 187-199. AW SIGPUNNoJices 30(10).
19. 19 SHAPIRO. hl., AND HORWITZ, S. Fast and accurate flow-insensitive pointsto analysis. In Conference Record of the livemy-Fourth ACM Symposium on Principles ofProgrammingLonguages(Patis, France, 1997),pp. 1-14.
20. 20 SIFF. hf. AND REPS, T. Identifying modules via concept analysis. In Proc. Intemarional Confirence on Sofisare hlaintenance(Bari, Italy, 1997), pp. 170- 179.
21. 21 SNELTING, G. Reengineeringofconfigmationsbased on mathematical concept analysis. ACM Transactions on Sofivare Engineen'ng and Methodology 5, 2 (April 1996). 146159.
22. 22 SNELTINC,G. Conceptanalysis-anewframervorkforprogmmunderstanding. In Proceeding of the ACMSIGPLAi &&hop on Program Anabsis for Sofnsare Took and Engineering(hlontrra1, Canada, 199s). pp. l-10.
23. 23 STEENSCAARD, B. Points-to analysis in almost linear time. In Proceedings of the l'kenty-TJzird ACM Symposium on Principles ofProgrammingLunguage. (St. Petersburg, FL, January 1996), pp. 32-41.
24. 24 SIVEENEY, P. F. AND TIP, F. A study of dead data members in Ci+ applications. In Proceedings of the ACM SIGPLAN'9S Conference on Programming LanguageDerign andlmplemenraion (hlontreal, Canada, June 1998), pp. 32P 332. ACM SIGPLANh'otices 33(6).
25. 25 TIP. E, CHOI. J.-D., FIELD, J., AND RAhlALINGAhI, G. Slicing class hierarchies in Cu. In Proceedings of the Eleventh Annual Conference on Object- Oriented Programming S,:tems, Lunguages, and Applications (OOPSLA '96) (San Jose, CA, 1996), pp. 179-197. ACMSlGPLANNoices31(10).
26. 26 TIP, F., AND SWEENES, P. Class hierarchy specialization. In Proceedings of rhc nse!0h Annual Conference on Object-Oriented Programming Systems, Language&, and Applications (OOPSU'97) (Atlanta, GA, 1997), pp. 271-285. &if SIGPLAXh'oJices 32( 10).
27. 27 TIP, F., AND SWEENEY, P. F. Class hierarchy specialization. Tech. Rep. RC21111, IBhi TJ. Watson Research Center, February 1998.
28. 28 \VILLE. R. Restructuring lattice theory: an approach based on hierarchies of concepts. OrderedSers(l9S2),445-470.

Index Terms

• Mathematics of computing

  • Discrete mathematics

• Software and its engineering

  • Software creation and management

    • Software post-development issues

      • Software reverse engineering

• Theory of computation

  • Logic