Master Thesis

Detecting Software Patterns using Formal Concept Analysis

Frank Buchli
University of Bern

Winner of the Faculty Prize Mathematics 2003




Redocumentation and design recovery are two important areas of reverse engineering. Detection of recurring organizations of classes and communicating objects, called Software Patterns, supports this process. Many approaches to detect Software Patterns have been published in the past years.

Most of these approaches need a pattern library as reference. Personal coding style and domain specific requirements lead to creating new patterns or adapting existing ones and make those approaches fail. The second problem is that the found patterns of those methods are presented without connection to the other patterns. To gain an overview of the whole system and its mechanisms, we propose to set the patterns in relation each other.

Our work shows a method to detect Software Patterns using Formal Concept Analysis (FCA). The advantage of this approach is that no reference library is needed and the results are set in relation each other.

FCA is a mathematical theory which detects the presence of groups of classes which instantiate a common, repeated pattern. Those found patterns are presented in a lattice, a partial order relation among the patterns, which allows us to explore the pattern which are in relation to them.

We implemented a prototype tool ConAn PaDi which navigates with the Fish-Eye-View technique over the patterns. For validation we applied this tool to three mid-sized Smalltalk applications.