\documentclass[10pt,twocolumn]{article}
\usepackage[utf8]{inputenc} % ggf. utf8 oder so für Unicode
\usepackage[T1]{fontenc}
\usepackage{times}
\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{float}
\usepackage{listings}
\usepackage{hyperref} % shall be included last
\newcommand{\thecont}{$(\mathcal{O}, \mathcal{A},\, T)$}
\newcommand{\theprog}{\mathcal{P}}
\newcommand{\exprog}{\mathcal{P}_1}
\newcommand{\classpv}{ClassPtrVars(\theprog)}
\newcommand{\classv}{ClassVars(\theprog)}
\begin{document}
% Das Thema hier eintragen
\title{Formal Concept Analysis and Lattices}
% Hier die richtigen Daten eintragen
\author{Philipp Martis\\
Seminar ``Verfahren zur Analyse von Programmcode''\\
%\today
}
\maketitle
\thispagestyle{empty}
% Kurze Zusammenfassung
\begin{abstract}
\emph{This paper provides an introduction to lattices and Formal Concept Analysis using lattices.
Also, their applications are discussed. In particular, their application in the analysis of class
hierarchies in object-oriented programming is discussed and illustrated by an example.
A brief introduction to order theory is given to provide the information
necessary to understand the other topics.}
\end{abstract}
%-------------------------------------------------------------------------
\section{Introduction}
Lattices are a very general and valuable mathematical concept laying the foundations for Formal
Concept Analysis. Formal Concept Analysis in turn provides a formal model to gain insight
into the structure of knowledge and information. It can help to analyze, visualize and restructure
information, and find correlations and dependencies between information.
In particular, it can be used to do analysis and restructuring of class hierarchies in
object-oriented programming.
(Semi-)automatic tools can be built to do this job with the aid of computers \cite{book}.
Other application areas involve data in computer programs and data
occurring in biology, physics, psychology, sociology and other sciences.
This article mainly deals with the applications of lattices and Formal Concept Analysis in the
analysis and restructuring of class hierarchies. All topics necessary to understand this subject are
covered. In particular, the basic principles of order theory are discussed and lattices and Formal
Concept Analysis are explained. All topics discussed are described formally and illustrated by
examples. Wherever feasible, some contextual information is provided, e.g. superficial descriptions of
algorithms. Problems arising from the great expressiveness of modern programming languages and their
impact on Formal Concept Analysis are also discussed briefly.
%-------------------------------------------------------------------------
\section{Order and lattice theory}
To use the model of Formal Concept Analysis, one first has to understand its basic
principles, especially lattices. This section provides this understanding.
First, the mathematical notion of \emph{order} is discussed, which builds the foundation for lattices.
Then, lattices are introduced, which in turn build the foundation for Formal Concept Analysis.
%-------------------------------------------------------------------------
\subsection{Order}
There exist many different kinds of order in mathematics, distinguished by having or not having
certain exactly defined properties. One of the most important kinds is the \emph{partial order}:\\
\textbf{Definition 1:}\\
\begingroup
\par \leftskip=0.5cm \noindent
A \emph{(partially) ordered set} $(M, \leq)$ is a set $M$ with a relation ``$\leq$'' defined on it
such that for all $x, y, z \in M$ \cite{book}:
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{lll}
\textbullet & $x \leq x$ & \emph{(reflexivity)}\\
\textbullet & $x \leq y \; \land y \leq x \; \Rightarrow \; x = y$ & \emph{(antisymmetry)}\\
\textbullet & $x \leq y \; \land y \leq z \; \Rightarrow \; x \leq z$ & \emph{(transitivity)}
\end{tabular} \end{setlength}
\par \endgroup
~\\\\$(M, \leq)$ is often just denoted by $M$. Also, instead of $(x, y) \in \; \leq$,
usually $x \leq y$ is written.
The relation ``$\leq \, \cap \, \neq$'' is usually denoted by ``$<$'' or ``$\lneq$.''
If, in a partially ordered set, two elements $x$ and $y$ are not comparable, thus
$x \nleq y \, \land \, y \nleq x$, this is often denoted by\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $x \parallel y$.
\end{tabular} \end{setlength}\\
\noindent
Demanding that every two elements of the set are comparable leads to the notion
of a \emph{totally ordered set}, also called a
\emph{linearly ordered set} or \emph{chain}:\\
\textbf{Definition 2:}\\
\begingroup
\par \leftskip=0.5cm \noindent
A \emph{totally ordered set} or \emph{chain} $(M, \leq)$ is a partially ordered set with the
restriction that for all $x, y \in M$\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $x \leq y \; \lor \; y \leq x$
\end{tabular} \end{setlength}\\
holds \cite{book}.
\par \endgroup
~\\\noindent
With respect to orders $\leq$ on sets $P$ and $Q$ (in this case, the same symbol
can be used for both orders without the risk of ambiguity), maps between $P$ and $Q$
can be classified as follows:\\
\textbf{Definition 3:}\\
\begingroup
\par \leftskip=0.5cm \noindent
A map $\varphi \, \colon P \to Q$ between ordered sets $(P, \leq)$ and $(Q, \leq)$ is said to
be \cite{book}:\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & \emph{order-preserving} or \emph{monotone} if $x \leq y$ in $P$\\
& implies $\varphi (x) \leq \varphi (y)$ in Q.\\
\textbullet & an \emph{order-embedding} if $x \leq y$ in $P$ if and only if\\
& $\varphi (x) \leq \varphi (y)$ in Q.\\
\textbullet & an \emph{order-isomorphism} if it is an order-embedding\\&which maps $P$ onto $Q$.
\end{tabular} \end{setlength}
\par \endgroup
~\\It is easily shown that every order-embedding is injective (one-to-one), so the only difference
to order-isomorphisms is that these are always surjective (map into the whole codomain).
%-------------------------------------------------------------------------
\subsubsection{Hasse diagrams}
\label{subsec:hasse}
Ordered sets can be visualized in different ways. A very clean yet complete depiction is
\emph{Hasse diagrams}.
A Hasse diagram is yielded when each element $x$ of a partially ordered set $(M, \leq)$ is represented
as a point $p(x)$ in the Euclidian plane $\mathbb{R}^2$ and these points are connected according
to the following rules \cite{book}:
\begin{itemize}
\item Connect every two points $x$ and $y$ $\in M$, for which
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $x \lneq y \; \land \; \lnot \, \exists \: z \in M \colon \, x \lneq z \lneq y$
\end{tabular} \end{setlength}\\
holds, that is points being direct ``neighbours'' in terms of $\leq$.
\item Do this in such a way, that the line is ascending from $p(x)$ to $p(y)$ (thus, $p(x)$
has a strictly smaller second coordinate) if $x \leq y$.
\end{itemize}
\noindent Because of the transitivity of $\leq$, every two points $p(x)$, $p(y) \in \mathbb{R}^2$
with $x, y \in M \colon \, x \leq y$
either are the same point (if $x = y$) or have an ascending path between them.
In both cases, $p(y)$ is said to be \emph{above} $p(x)$ and $p(x)$ to be \emph{below} $p(y)$.
The above rules still leave much freedom in placing the points. Doing so in an advantageous way to
obtain a clear diagram can be challenging for large ordered sets and requires experience
\cite{book}.
All visualizations of lattices presented in the following sections are Hasse diagrams.
%-------------------------------------------------------------------------
\subsubsection{Supremum and infimum}
\label{subsec:supinf}
With the notion of order, the terms \emph{upper bound}, \emph{lower bound}, \emph{supremum} and
\emph{infimum} can be defined, which are basic to the notion of a lattice:\\
\textbf{Definition 4:}\\
\begingroup
\par \leftskip=0.5cm \noindent
Let $P$ be an ordered set and $S \subseteq P$. An element $x \in P$ is an \emph{upper bound}
of $S$ if $s \leq x$ for all $s \in S$ \cite{book}.
The term \emph{lower bound} is defined dually.\\
\par \endgroup
\textbf{Definition 5:}\\
\begingroup
\par \leftskip=0.5cm \noindent
Let $P$ be an ordered set and $S \subseteq P$. An element $x \in P$ is called the
\emph{least upper bound} or \emph{supremum} of $S$ if \cite{book}\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & $x$ is an upper bound of $S$ and\\
\textbullet & $x \leq y$ for all upper bounds $y$ of $S$.
\end{tabular} \end{setlength}\\
The term \emph{greatest lower bound} or \emph{infimum} is defined dually.
\par \endgroup
~\\The supremum of a set $S$ -- if any -- is denoted as $\sup S$ and its infimum as $\inf S$.
In the context of lattices, a more convenient notation is common \cite{book}:
$\bigvee\!S$ is written instead of $\sup S$ and $\bigwedge\!S$ instead of $\inf S$ and
they are called \emph{join} and \emph{meet}, respectively.
The join and meet of two-element sets $\{x, y\}$ is denoted by $x \lor y$ and $x \land y$,
respectively.
To indicate that the join or meet of $S$ is being found in a particular set $P$,
$\bigvee_{P}\!S$ or $\bigwedge_{P}\!S$ is written.
%-------------------------------------------------------------------------
\subsection{Lattices}
The core idea behind lattices is, that, if, in a partially ordered set $M$, not every
two elements are comparable, at least the join and meet of every two elements can be determined
(the definitions of these terms and their notation can be found in Section \ref{subsec:supinf}).
Informally, a \emph{lattice} is an ordered set for which this restriction holds. If the join and
meet of \emph{every} subset of $M$ can be determined, $M$ is called a \emph{complete lattice}.\\
\textbf{Definition 6:}\\
\begingroup
\par \leftskip=0.5cm \noindent
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & A \emph{lattice} is an ordered set $P$, such that $x \lor y$\\&and $x \land y$
exist for all $x, y \in P$ \cite{book}\\
\textbullet & A \emph{complete lattice} is an ordered set $P$, such that\\&$\bigvee\!S$ and
$\bigwedge\!S$ exist for all $S \subseteq P$ \cite{book}
\end{tabular} \end{setlength}\\
\par \endgroup
%-------------------------------------------------------------------------
\subsubsection{Examples}
The following two examples are lattices (more precisely: Hasse diagrams of lattices) \cite{wikipedia}:
\begin{figure}[H]
\includegraphics[scale=0.22]{"Figures/Hasse_diagram_of_nat_num".png}
\caption{The natural numbers with $\leq$}
\label{fig:hass_ex_nat}
\end{figure}
\noindent
The example in Figure \ref{fig:hass_ex_nat} shows a Hasse diagram for\\
$(\mathbb{N}, \leq)$. Obviously, every two elements are comparable, because there is an ascending
or descending path between every two elements, as described in Section \ref{subsec:hasse}.
Therefore, every two elements have a join and a meet: the larger or smaller element, respectively.
\begin{figure}[H]
\includegraphics[scale=0.24]{"Figures/Hasse_diagram_of_powerset_of_3".png}
\caption{The powerset of $\{x, y, z\}$ with $\subseteq$}
\label{fig:hass_ex_sets}
\end{figure}
\noindent
The example in Figure \ref{fig:hass_ex_sets} shows a Hasse diagram of the lattice
$(\mathcal{P}(M), \subseteq)$ where $M = \{x, y, z\}$ is some three-element set.
Since the order is given by $\subseteq$, a subset $M_{1}$ of $M$ is ``less than or equal to''
another subset $M_{2}$ if $M_{1} \subseteq M_{2}$.
The join of two subsets $M_{1}$ and $M_{2}$ of $M$ is hence the smallest set $M_j \subseteq M$,
both $M_1$ and $M_2$ are subsets of. Conversely, the meet of $M_{1}$ and $M_{2}$ is the largest
set $M_m \subseteq M$, which is both a subset of $M_{1}$ and $M_{2}$.
As described in Section \ref{subsec:hasse}, there is an ascending path from every element $m$ to every
element which is ``bigger than'' (that is, a superset of) $m$. For example, there is an ascending
path from the empty set to every other set. The sets $\{x\}$ and $\{y\}$, for example, are not
comparable, so there is neither an ascending nor a descending path between them.
On the other hand, every two elements have a join and a meet, so there is always an element which
is reachable from these two elements by only taking ascending paths or descending paths, respectively.
For $\{x, y\}$ and $\{z\}$, for example, this is $\{x, y, z\}$ and $\emptyset$, respectively.\\
\noindent
The following example is a Hasse diagram of an ordered set which is not a lattice \cite{wikipedia}:
\begin{figure}[H]
\includegraphics[scale=0.2]{"Figures/NoLatticeDiagram".png}
\caption{No lattice: $b \lor c$ does not exist, for instance}
\label{fig:hass_ex_nolat}
\end{figure}
\noindent
The example in Figure \ref{fig:hass_ex_nolat} is not a lattice.
While some elements do have a join and a meet (like $a$ and $d$, whose join is $d$ and whose meet is
$a$), some do not have both (like $b$ and $c$, who have a meet, $a$, but no join).
%-------------------------------------------------------------------------
\subsubsection{Lattices as algebraic structures}
Having the operators ``$\lor$'' and ``$\land$'' defined allows us to view a lattice $M$ as an
algebraic structure $\langle M, \lor, \land \rangle$, alternatively to viewing it as an ordered
set with certain restrictions.
In particular, \emph{associativity}, \emph{commutativity}, \emph{idempotency} and \emph{absorption}
hold, thus, both $(M, \lor)$ and $(M, \land)$ are semigroups \cite{book}:
\\\\For all $a, b, c \in M$:\\
\begin{tabular}{lll}
\textbullet & $(a \lor b) \lor c = a \lor (b \lor c)$ and\\
& $(a \land b) \land c = a \land (b \land c)$ & \emph{(associativity)}\\
\textbullet & $a \lor b = b \lor a$ and\\
& $a \land b = b \land a$ & \emph{(commutativity)}\\
\textbullet & $a \lor a = a$ and\\
& $a \land a = a$ & \emph{(idempotency)}\\
\textbullet & $a \lor (a \land b) = a$ and\\
& $a \land (a \lor b) = b$ & \emph{(absorption)}
\end{tabular}
~\\\\A map $f \, \colon P \to Q$ is called a \emph{lattice homomorphism} if for all $a, b \in P$\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $f(a \lor b) = f(a) \lor f(b)$ and $f(a \land b) = f(a) \land f(b)$
\end{tabular} \end{setlength}\\
hold.
A lattice homomorphism which is bijective is called \emph{lattice isomorphism}.
It can be shown that a map $f$ is a lattice isomorphism iff it is an order-isomorphism \cite{book}.
%-------------------------------------------------------------------------
\section{Formal Concept Analysis}
%-------------------------------------------------------------------------
\subsection{Introduction}
What knowledge \emph{is} exactly and how it can be modeled and represented is a central question in
epistemology which is unlikely to be satisfiably answered.
Even when restricting oneself to conceptual knowledge, one is confronted with an overwhelming
number of different views and theories \cite{wille}.
This makes clear that we have to focus on ``some specific type of abstraction which enables us to
fulfill specified aims.'' \cite{wille}
The following notion of a \emph{concept} -- contributed by traditional philosophy \cite{book} --
and the approach of Formal Concept Analysis provides a model to meet such aims
in terms of (object-oriented) programming.
Every concept is embedded into a \emph{context}.\\
\textbf{Definition 7:}\\
\begingroup
\par \leftskip=0.5cm \noindent
A \emph{context} is a triple \thecont{}, where $\mathcal{O}$ and
$\mathcal{A}$ are sets and $T$ is a relation
between them, thus\\$T \subseteq \mathcal{O} \times \mathcal{A}$ \cite{book}.
\par \endgroup
~\\As with $\leq$, usually $oTa$ is written instead of $(o, a) \in T$.
$O$ can be imagined as a set of objects and $A$ as a set of attributes with $oTa$ meaning
``object o has attribute a.'' Also, the relation $T$ can be imagined as a boolean table
(indeed, this is one way to visualize contexts) \cite{book}.\\
\textbf{Definition 8:}\\
\begingroup
\par \leftskip=0.5cm \noindent
Let \thecont{} be a context. For $O \subseteq \mathcal{O}$ and
$A \subseteq \mathcal{A}$, define \cite{book}\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & $A' \coloneqq \{ o \in \mathcal{O} \:|\: \forall a \in A \colon oTa \}$ and\\
\textbullet & $O' \coloneqq \{ a \in \mathcal{A} \:|\: \forall o \in O \colon oTa \}$
\end{tabular} \end{setlength}
\par \endgroup~\\
\textbf{Definition 9:}\\
\begingroup
\par \leftskip=0.5cm \noindent
A \emph{concept} in the context \thecont{} is a pair $(O, A)$ where
$O \subseteq \mathcal{O}$, $A \subseteq \mathcal{A}$, $O' = A$ and $A' = O$ \cite{book}.
\par \endgroup
~\\Given a concept $(O, A$), $O$ is called the \emph{extent} and $A$ is called the
\emph{intent} of the concept \cite{book}.
Within this notion, a concept is an object-attribute pair with $A$ being all the
attributes all objects in $O$ have, while $O$ is all the objects having all the attributes
in $A$.
The set of all concepts of a context \thecont{} is denoted
$\mathfrak{B}(\mathcal{O}, \mathcal{A},\, T)$ ($\mathfrak{B}$ comes from the German word
``Begriff'') \cite{book}.\\
\textbf{Lemma:}\\
\begingroup
\par \leftskip=0.5cm \noindent
Given a context \thecont{}, an index set $J$ and sets
$O, O_j \subseteq \mathcal{O}$ for $j \in J$ and $A, A_j \subseteq \mathcal{A} $ for $j \in J$,
the following statements hold \cite{book}:
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & $O \subseteq O''$ and $A \subseteq A''$\\
\textbullet & $O_1 \subseteq O_2 \Rightarrow O_1' \supseteq O_2'$ and\\
& $A_1 \subseteq A_2 \Rightarrow A_1' \supseteq A_2'$\\
\textbullet & $O' = O'''$ and $A' = A'''$\\
\textbullet & $(\bigcup_{j \in J} O_j)' = \bigcap_{j \in J} O_j'$ and\\
& $(\bigcup_{j \in J} A_j)' = \bigcap_{j \in J} A_j'$\\
\textbullet & $O \subseteq A' \Leftrightarrow O' \supseteq A$
\end{tabular} \end{setlength}\\
\par \endgroup
%-------------------------------------------------------------------------
\subsection{Link to lattices}
%-------------------------------------------------------------------------
\subsubsection{The ordering of concepts}
\label{subsec:concept_ordering}
Given a context \thecont{}, an order $\leq$ can be defined by
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $(O_1, A_1) \leq (O_2, A_2)\: \vcentcolon\Leftrightarrow \: O_1 \subseteq O_2
\: \Leftrightarrow \: A_1 \supseteq A_2$ \cite{book}
\end{tabular} \end{setlength}
\noindent It is easily seen that $\leq$ defines a partial order on $\mathfrak{B}(\mathcal{O},
\mathcal{A},\, T)$ -- reflexivity, transitivity and antisymmetry are inherited
from $\subseteq$.
Given that order, contexts can be visualized using Hasse diagrams.
%-------------------------------------------------------------------------
\subsubsection{Concept Lattices}
\label{subsec:concept_lattices}
$(\mathfrak{B}(\mathcal{O}, \mathcal{A},\, T), \leq)$ is a complete lattice, called the
\emph{Concept Lattice} of the context \thecont{} \cite{book}.
%-------------------------------------------------------------------------
\subsection{Visualization of contexts}
\label{subsec:visualization}
There are at least three natural ways to represent a context \thecont{}
visually \cite{book}:
\begin{itemize}
\item As a so-called \emph{cross table} with fields indicating whether an object $o$ has
an attribute or not. Most often, the objects are put in the rows of the table and the
attributes in its columns.
\item As a bipartite graph $G = (V, E)$ with $V = \mathcal{O} \cup \mathcal{A}$ and
$E = T$.
\item As a Hasse diagram of $(\mathfrak{B}(\mathcal{O}, \mathcal{A},\, T), \leq)$, which,
as explained in Section \ref{subsec:concept_lattices}, is a lattice.
\end{itemize}
\noindent The latter solution has the advantage that it can be used even for big contexts and
that it illustrates important information explicitly \cite{book}. In particular, it reveals
hierarchies implicated by $\leq$ as defined in Section \ref{subsec:concept_ordering}.
This can be of great use and is part of the power of Formal Concept Analysis, as will be demonstrated
in Section \ref{sec:analyzing} by means of an example class hierarchy.
%-------------------------------------------------------------------------
\subsection{Implications}
\emph{Implications} between attributes are an important notion within Formal Concept Analysis.
They are valuable in the construction process of the object-attribute relation $T$ or if additional
information about relations between objects and attributes shall be provided \cite{snelting}.
Let $A_1, A_2 \in \mathcal{A}$ be sets of attributes. $A_1$ is said to imply $A_2$ if all objects
having all the attributes in $A_1$ also have all attributes in $A_2$ \cite{snelting}.
This is denoted by $A_1 \rightarrow A_2$.\\
\textbf{Definition 10:}\\
\begingroup
\par \leftskip=0.5cm \noindent
In a context \thecont{}, $A_1 \subseteq \mathcal{A}$ \emph{implies}
$A_2 \subseteq \mathcal{A}$ if for all $o \in \mathcal{O}$\\
\begin{tabular}{ll}
& $\forall a_1 \in A_1 \colon oTa_1 \; \Rightarrow \; \forall a_2 \in A_2 \colon oTa_2
$ \cite{snelting}
\end{tabular}
\par \endgroup
%-------------------------------------------------------------------------
\section{Analyzing class hierarchies using Formal Concept Analysis}
\label{sec:analyzing}
The design of modern information systems -- possibly containing millions of lines of source code --
is an art and requires special care if the system is designed decentrally by many people
-- as in open source systems -- or is a library whose operational area its designer does not even
know of \cite{stroustrup}.
Formal Concept Analysis provides help to analyze such complex systems and find out about certain
inconsistencies, such as:
\begin{itemize}
\item Unused class members, possibly indicating that they should be removed or moved to a derived
class \cite{snelting}
\item Different subsets of class members used separately in a program, possibly indicating that
the class should be split up into multiple classes \cite{snelting}
\end{itemize}
\noindent The aim of Formal Concept Analysis is also to be the basis of (semi-)automatic tools aiding
the programmer in carrying out such restructuring \cite{snelting}.
Formal Concept Analysis can be done in several ways: analyzing the class hierarchy in isolation or
together with a set of programs using it \cite{snelting}. In the latter case, how the programs use the
class hierarchy can be viewed for each program in isolation or as an aggregate view \cite{snelting}.
%-------------------------------------------------------------------------
\subsection{The example class hierarchy}
\label{subsec:example}
Consider the following C++ example \cite{snelting}:
\begin{figure}[H]
\lstset{language=, emph={return,new,for,if,then,else,float,long,int,
class,public,enum,void,nullptr,using,virtual,override}, emphstyle=\textbf}
\begin{lstlisting}
class A {
public:
virtual int f() { return g(); }
virtual int g() { return x; }
int x;
};
class B : public A {
public:
int g() override { return y; }
int y;
};
class C : public B {
public:
int f() override { return g() + z; }
int z;
};
int main() {
A a; B b; C c;
A* ap;
if ( ... )
ap = &a;
else if ( ... )
ap = &b;
else
ap = &c;
ap->f();
}
\end{lstlisting}
\caption{Example class hierarchy}
\label{fig:ex_code}
\end{figure}
%-------------------------------------------------------------------------
\subsection{Applying Formal Concept Analysis}
This section gives a detailed view about how Formal Concept Analysis is used for gaining insight
into the structure of a class hierarchy and possibly getting recommendations for a restructured
class hierarchy.
The example class hierarchy shown in Figure \ref{fig:ex_code} is used to illustrate the procedure.
%-------------------------------------------------------------------------
\subsubsection{Determining the context}
To apply Formal Concept Analysis to the class hierarchy to be analyzed, the context \thecont{}
first has to be defined properly.
Basically, the objects shall represent the variables of user defined types or of type
``pointer to user defined type'' and the attributes the members of user defined types.
$T$ would then reflect which variable (or more precisely, which object in terms of programming)
uses which of its members.
Due to the fact that variables can be assigned to each other, so a variable does not always refer
to the same object, and programming language constructs such as virtual functions, the
algorithm for determining the context becomes rather complicated.
Nevertheless, it shall be described here in some detail.
First, some auxiliary definitions are made, which are all fairly self-explanatory:\\
\textbf{Definition 11:}\\
\begingroup
\par \leftskip=0.5cm \noindent
Given a program or set of programs $\theprog{}$, the following can be defined \cite{snelting}:\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & $\classv{} \coloneqq \{ v \: | \: v$ is a variable of a\\
& user defined type$\}$\\
\textbullet & $\classpv{} \coloneqq \{ p \: | \: p$ is a variable of\\
& type ``pointer to user defined type''$\}$\\
\textbullet & $MemberDcls(\theprog{}) \coloneqq \{ dcl(C\!::\!m) \: | \: m$ is a\\
& data member or virtual method in class $C \}$\\
\textbullet & $MemberDefs(\theprog{}) \coloneqq \{ def(C\!::\!m) \: | \: m$ is a\\
& virtual or nonvirtual method in class $C \}$\\
\textbullet & $MayPointTo(\theprog{}) \coloneqq \{ (p, v) \: | \: v \in$\\
& $\classv{}$, $p \in \classpv{}$,\\
& $p$ may point to $v\}$\\
\textbullet & $MemberAccess(\theprog{}) \coloneqq \{ (m, v) \: | $ \verb+v.m+ occurs\\
& in $\theprog{}$, $m$ is a class member, $v \in \classv{} \}$\\
& $\cup \; \{ (m, *p) \: | $ \verb+p->m+ occurs in $\theprog{}$, $m$ is a class\\
& member, $p \in \classpv{} \}$\\
& $\cup \; \{ (f, y) \: | $ \verb+p->f+ occurs in $\theprog{}$, $(p, y) \in$\\
& $MayPointTo(\theprog{})$, $f$ is a virtual method$\}$\\
\end{tabular} \end{setlength}
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
\textbullet & $Assignments(\theprog{}) \coloneqq \{ (v, w) \: |$ \verb+v = w+ occurs\\
& in $\theprog{}$, $v, w \in \classv{} \}$\\
& $\cup \; \{ (*p, w) \: |$ \verb+p = &w+ occurs in $\theprog{}$, $p \in$\\
& $\classpv{}, w \in \classv{} \}$\\
& $\cup \; \{ (*p, *q) \: |$ \verb+p = q+ occurs in $\theprog{}$, $p, q \in$\\
& $\classpv{} \}$\\
& $\cup \; \{ (*p, w) \: |$ \verb+*p = w+ occurs in $\theprog{}$, $p \in$\\
& $\classpv{}$, $w \in \classv{} \}$\\
& $\cup \; \{ (v, *q) \: |$ \verb+v = *q+ occurs in $\theprog{}$, $v \in$\\
& $\classv{}$, $q \in \classpv{}$\\
& $\cup \; \{ (*p, *q) \: |$ \verb+*p = *q+ occurs in $\theprog{}$, $p, q \in$\\
& $\classpv{} \}$
\end{tabular} \end{setlength}
\par \endgroup~\\
\noindent
To model the virtual function call mechanism accurately, declarations and definitions of virtual
functions are distinguished, since a calling function does not have to know the body definition
of a virtual function it calls \cite{snelting}.
$ClassPtrVars$ contains implicitly declared \verb+this+-pointers of functions \cite{snelting},
because track has to be kept of which object a function call was invoked on.
To distinguish the \verb+this+-pointers of different functions, they are referred to using the
name of the respective function, e.g. the \verb+this+-pointer of \verb+A::f()+ is referred to as
\verb+A::f+.
Data members are modeled as declarations because they do not have a \verb+this+-pointer allowing
access of other members associated with them \cite{snelting}.
Naming our example program from Figure \ref{fig:ex_code} ``$\exprog{}$'',
the following sets are obtained \cite{snelting}:
\begin{itemize}
\item $ClassVars(\exprog{}) = \{ a, b, c \}$
\item $ClassPtrVars(\exprog{}) = \{ ap, A\!::\!f, A\!::\!g, B\!::\!g,$\\$C\!::\!f \}$
\item $MemberDcls(\exprog{}) = \{ dcl( A\!::\!f ), dcl( A\!::\!g ),$\\
$dcl( A\!::\!x ), dcl( B\!::\!g ), dcl( B\!::\!y ), dcl( C\!::\!f ),$\\$dcl( C\!::\!z ) \}$
\item $MemberDefs(\exprog{}) = \{ def( A\!::\!f ), def( A\!::\!g ),$\\
$def( B\!::\!g ), def( C\!::\!f ) \}$
\item $MayPointTo(\exprog{}) = \{ (ap, a), (ap, b), (ap, c),$\\
$ (A\!::\!f, a), (A\!::\!f, b), (C\!::\!f, c), (A\!::\!g, a),$\\$(B\!::\!g, b), (B\!::\!g, c) \}$
\item $MemberAccess(\exprog{}) = \{ (x, *A\!::\!g), (y, *B\!::\!g),$\\
$(z, *C\!::\!f), (g, *A\!::\!f), (g, *C\!::\!f), (f, *ap),$\\
$(f, a), (f, b), (f, c), (g, a), (g, b), (g, c) \}$
\end{itemize}
~\\\noindent
Let $\theprog$ be a given program. Then $\mathcal{O}$, $\mathcal{A}$ and $T$ are built up
successively as follows \cite{snelting}:
~\\\noindent
The objects and attributes are the variables and members, respectively, thus\\
\begin{setlength}{\leftmargini}{1cm} \begin{tabular}{ll}
& $\mathcal{O} = \classv{} \cup \classpv{}$ and\\
& $\mathcal{A} = MemberDcls(\theprog{}) \cup MemberDefs(\theprog{})$
\end{tabular} \end{setlength}\\
\noindent
As described in Section \ref{subsec:visualization}, usually the elements of $\mathcal{O}$ become
the rows and the elements of $\mathcal{A}$ become the columns of the table $T$.
Building $T$ is accomplished by an iterative approach, which is repeated until no more
changes take place in $T$.
~\\\noindent
The first step in building the table is to add all obvious member accesses, as written in the code,
to it.
For data members, the member and the variable accessing it are added to $T$; similarly for nonvirtual
member functions.
For virtual functions, their declaration, that is, $dcl(...)$, is added to $T$ if it is called
through a pointer or reference, and their definition, $def(...)$, otherwise.
Note that virtual functions, if not called through a pointer or reference, act just like
normal member functions.
Next, for each function $C\!::\!f()$, the object it is invoked on, given in terms of a
\verb+this+-pointer $*C\!::\!f$, and its definition $def(C\!::\!f)$ are added as a pair to the table,
thereby guaranteeing that the definition will appear above or as the same node as the object in the
resulting lattice.
If this is not done, the natural notion that an object uses a member function it invokes would only
materialize in the table for functions which call themselves (recursive functions).
As will later become clear, the members used by an object will always appear above it in the
lattice.
It is guaranteed anyway that $def(C\!::\!f)$ will appear below or at the same level as the object
$*C\!::\!f$ in the resulting lattice \cite{snelting}. Both guarantees together ensure that both
notions will appear as the same lattice element, allowing us to later remove the objects representing
\verb+this+-pointers from the table again.
When variables are assigned, the object assigned becomes the object associated with the variable being
assigned to and thus can access everything the object previously associated with the variable could
access. Thus, assignment is an implication in terms of Formal Concept Analysis.
Therefore, the next rule when constructing $T$ is to add these implications between objects:
every attribute the object in the ``source row'' has is also associated with the object in the
``target row''.
As the last iteration step, \emph{dominance} or \emph{hiding} effects have to be taken into account.
If two data or nonvirtual function members have the same name and are declared in classes of the
same hierarchy, the member in the derived class hides the member in the base class.
Since potential suggestions for a new class hierarchy must preserve the semantics of the member
accesses occurring in the code, these hiding relationships must be preserved.
Formally, such a relationship is nothing more than an implication between attributes (columns),
analogously to the implication between objects.
Hence, to reflect that implication, the columns representing dominating attributes are copied
to the columns representing dominated attributes.
~\\\noindent
As mentioned previously, these steps are repeated until $T$ doesn't change anymore and
then the rows representing \verb+this+-pointers are erased from $T$.
Background knowledge that is not reflected in the table, for example desired hiding effects
currently not expressed in the source code, can be provided as additional implications
\cite{snelting}.
%-------------------------------------------------------------------------
\subsubsection{Modeling constructors}
\label{subsubsec:constructors}
Special attention has to be payed to constructors. In C++, for instance, the compiler will generate
default constructors, that is, constructors taking no arguments, under certain conditions, which in
turn call the default constructors of all base classes and certain members \cite{stroustrup}.
Furthermore, the compiler will generate calls to constructors in certain cases \cite{snelting},
for example when an object is created on the stack, on the heap or as a member of another object.
There are different approaches to modeling constructors and constructor calls, each persuing
specific aims.
The approach used in the original form of the modeling is to leave compiler generated constructors
and constructor calls -- and only those -- out of account \cite{snelting}.
This eliminates the illusion that members constructed by a compiler-generated call to a
default constructor are actually accessed \cite{snelting}.
Alternatively, all constructors and constructor calls can be left out of account, which, for example,
is useful for finding unused members.
Taking all constructors and constructor calls into account can also be useful. Doing so makes it
possible to check if all members are initialized.
%-------------------------------------------------------------------------
\subsubsection{Building the lattice}
To construct the lattice out of the final table $T$, Ganter's algorithm can be used, which is
exponential in the worst case, but has a typical complexity of $\mathcal{O}(n^3)$ \cite{snelting}.
It can be shown that exponential behavior is extremely rare, though \cite{snelting}.
The final cross table for the example program $\exprog$ from Section \ref{subsec:example} is shown
in Figure \ref{fig:final_table}, and its final lattice in Figure \ref{fig:final_lattice}.
\begin{figure}[]
\includegraphics[scale=0.32]{"Figures/Final_table".png}
\caption{The final cross table for $\exprog$}
\label{fig:final_table}
\end{figure}
\begin{figure}[]
\includegraphics[scale=0.3]{"Figures/Final_lattice".png}
\caption{The final lattice of $\exprog$}
\label{fig:final_lattice}
\end{figure}
%-------------------------------------------------------------------------
\subsubsection{Reading a lattice}
Lattices, especially when visualized as Hasse diagrams, give a clean depiction of the structure they
represent. Although they contain all information about the relations between objects and attributes,
they are easy to read.
As described in Section \ref{subsec:hasse}, the terms ``above'' and ``below'' are used to describe
that two nodes are the same or have an ascending or descending, path between them, respectively.
The most important relationships to be read from a lattice and how this is done are described in the
following:
\begin{itemize}
\item Members appear above the objects that access them (or may access them, at least)
\cite{snelting}.
\item Members not accessed at all would appear at the bottom element of the lattice \cite{snelting}.
\item Objects not accessing any of their members would appear at the top element of the lattice
\cite{snelting}.
\item Data members of a base class \verb+B+ that are not used by (instances of) all derived classes
of \verb+B+ appear above some but not all derived classes of \verb+B+ \cite{snelting}.
\item If constructors are modeled (see Section \ref{subsubsec:constructors}), they appear below the
data members initialized by them \cite{snelting}.
\item Variables of the same type accessing different subsets of their members appear as different
points in the lattice \cite{snelting}.
\item If a function is overridden in a derived class, its declaration and its definition appear as
different points in the lattice. Each definition then will appear above the variables representing
the objects that use it.
\end{itemize}
\noindent
Colors and names for the lattice elements can be used to make the lattice more readable
\cite{snelting}.\\
\noindent
With regard to the example program $\exprog$ from Section \ref{subsec:example}, the following facts
are revealed in the lattice (shown in Figure \ref{fig:final_lattice}):
\begin{itemize}
\item No members are not accessed at all -- the bottom node of the lattice does not contain any
member names.
\item All objects access some of their members -- the top node of the lattice does not contain any
variable names.
\item The function declaration \verb+A::f()+ may be used by every object -- its name appears at the
top node of the lattice.
\item The data member \verb+A::x+ is used by the object \verb+a+ only and not by the objects of the
derived classes -- its name appears above \verb+a+ only.
\item The function definition \verb+A::f()+ may be used by \verb+a+ and \verb+b+, but not by \verb+c+
(since class \verb+C+ has its own definition of \verb+f()+ overriding \verb+A::f()+) -- its name
appears above \verb+a+ and \verb+b+, but not above \verb+c+.
\end{itemize}
\noindent
Since $\exprog$ is an artificial and short example program, its usefulness for illustrating
which possibilities for refining the class hierarchy can be read from a lattice is rather
limited. Nevertheless, some aspects are revealed in the diagram:
\begin{itemize}
\item The classes in the hierarchy are relatively tightly coupled; they cannot be simply
split up into multiple class hierarchies. This is primarily caused by \verb+b+, which uses
members of both class \verb+A+ and class \verb+B+, while class \verb+B+'s members are
also used by \verb+c+.
\item Since class \verb+A+'s data member is not used by objects of derived classes, class \verb+A+
does not play the typical role of a (non-abstract) base class. If its member function \verb+A::f()+
does not really elicit polymorphic behavior of some common aspect by calling \verb+g()+, the function
\verb+f()+ may be split up into two distinct functions \verb+A::f()+ and \verb+B::f()+, thereby
separating class \verb+A+ from the class hierarchy and potentially greatly simplifying it.
\end{itemize}
%-------------------------------------------------------------------------
\subsection{Possibilities for expansion}
As discussed here, Formal Concept Analysis used for analyzing class hierarchies is by itself a
general and valuable concept which reveals many important facts about the hierarchies.
As discussed in Section \ref{subsubsec:constructors}, adaptions can be made to
fit different use cases.
In addition, it can be refined and expanded to take issues like runtime and design concerns into
account. For example:
\begin{itemize}
\item Several cross tables representing different kinds of access operations (cached vs. uncached,
checked vs. unchecked etc.) can be used.
Performance and stability concerns can be addressed by analysing these tables separately.
For example it can be verified that uncached accesses occur only in debug code.
\item Access restrictions refining the usual \verb+public+ / \verb+private+ / \verb+protected+ scheme
can be formulated and checked. For example, it may be stated that a member may only be modified
in certain source files.
\item Small extensions like being able to mark attributes as ``deprecated'' can be used to
make Formal Concept Analysis helpful for the transition of code.
\end{itemize}
%-------------------------------------------------------------------------
\section{Conclusion}
Lattices and Formal Concept Analysis are very general and valuable concepts. They are very
useful for revealing information about the structure of class hierarchies in object-oriented
programming.
More generally, they are useful in every application where dependencies and other relations
between entities play an important role.
Using Hasse diagrams, these relations can be presented in a clear and concise way.
Additionally, Formal Concept Analysis provides the foundation for algorithms doing semi-automatic
or automatic restructuring of the class hierarchy or information.
The approach can be used in a flexible way to adapt it to several use cases.
In terms of analyzing class hierarchies, many opportunities exist to refine and expand it.
This allows to make it more flexible and powerful and to
make it cover interesting topics like runtime concerns.
%-------------------------------------------------------------------------
%\bibliographystyle{latex8-deutsch}
%\bibliography{literatur}
\begin{thebibliography}{}
\bibitem{book}B.A. Davey and H.A. Priestley, in \emph{Introduction to Lattices and Order}, 2nd ed.
Cambridge, England: Cambridge University Press, 2002,
pp. 2-76.
\bibitem{wille}R. Wille, ``Concept Lattices and Conceptual Knowledge Systems'', \emph{Computers
Math. Applic.}, vol. 23, no. 6-9, pp. 493-515, 1992.
Available: \url{http://dx.doi.org/10.1016/0898-1221(92)90120-7}%. \hskip 1em plus 0.5em minus
% 0.4em\relax ISSN 0898-1221
\bibitem{snelting}G. Snelting, ``Understanding Class Hierarchies Using Concept Analysis'',
\emph{ACM Transactions on Programming Languages and Systems}, vol. 22, no. 3, pp. 540-582, 2000
%\hskip 1em plus 0.5em minus 0.4em\relax \url{http://dx.doi.org/}
\bibitem{wikipedia}``Verband (Mathematik)'' in Wikipedia - Die freie Enzyklopädie.
Available: \url{http://de.wikipedia.org/wiki/Verband_(Mathematik)}
\bibitem{stroustrup}B. Stroustrup, \emph{The C++ Programming Language}, 4th ed. Boston, USA:
Addison Wesley, 2014
\end{thebibliography}
\end{document}