Razvan Caracas
email: razvan.caracas@ens-lyon.fr

Edward J Banigan

Elasticity and Raman and infrared spectra of MgAl 2 O 4 spinel from density functional perturbation theory

We determine the elastic constants and the Raman spectra of spinel under pressure using density functional perturbation theory. Like other spinels, MgAl 2 O 4 shows an increasing bulk modulus and a weakly varying shear modulus under pressure. The Raman spectrum is dominated by two mains peaks whose intensities decrease under pressure. The theoretical Raman spectra of disordered spinel shows a better agreement with measurements on natural samples than the ordered one. We also investigate the high-pressure stability of different structures and find the calcium titanate type to be the stable phase beyond 45 GPa.

Introduction

There has been a significant amount of work done on MgAl 2 O 4 spinel at high pressure. Notably, various studies have found the equations of state and/or crystal structure up to about 70 GPa [START_REF] Kruger | Equations of state of MgAl 2 O 4 spinel up to 65 GPa[END_REF][START_REF] Funamori | High-pressure transformations in MgAl 2 O 4[END_REF][START_REF] Wittlinger | Pressure-induced order-disorder phase transition of spinel single crystals[END_REF][START_REF] Catti | High-pressure stability, structure and compressibility of Cmcm-MgAl 2 O 4 : an ab initio study[END_REF][START_REF] Fang | Crystal structure and chemical bonding of the high-pressure phase of MgAl 2 O 4 from first-principles calculations[END_REF], while others investigated various minerals having spinel structure and systems involving mixtures of MgAl 2 O 4 spinel and similar minerals [START_REF] Bina | Olivine-spinel transitions: experimental and thermodynamic constraints and implications for the nature of the 400-km seismic discontinuity[END_REF][START_REF] Kiefer | Calculated elastic constants and anisotropy of Mg2SiO4 spinel at high pressure[END_REF][START_REF] Akaogi | High pressure transitions in the system MgAl 2 O 4 -CaAl 2 O 4 : a new hexagonal aluminous phase with implication for the lower mantle[END_REF][START_REF] Miura | Crystal structure of CaMg 2 Al 6 O 1 2, a new Al-rich high pressure form[END_REF].

At ambient pressure and temperature, MgAl 2 O 4 spinel is cubic with space group Fd3m (Kruger et al., 1997, Fang andDe With 2002). As pressure is applied, this structure becomes unstable and disassociates into a periclase (MgO) and corundum (Al 2 O 3 ) mixture around 15 GPa [START_REF] Akaogi | High pressure transitions in the system MgAl 2 O 4 -CaAl 2 O 4 : a new hexagonal aluminous phase with implication for the lower mantle[END_REF]. At about 26-27 GPa, this mixture has been observed to undergo a transition into an orthorhombic calcium ferrite-like structure (Decker and Kasper, 1957;[START_REF] Kruger | Equations of state of MgAl 2 O 4 spinel up to 65 GPa[END_REF][START_REF] Funamori | High-pressure transformations in MgAl 2 O 4[END_REF][START_REF] Akaogi | High pressure transitions in the system MgAl 2 O 4 -CaAl 2 O 4 : a new hexagonal aluminous phase with implication for the lower mantle[END_REF]. This phase is stable over a limited pressure range as it was proposed that MgAl 2 O 4 undergoes another phase transition above 40 GPa to an orthorhombic calcium titanate-type (space group Cmcm) phase (Bertraut and Blum, 1956;[START_REF] Funamori | High-pressure transformations in MgAl 2 O 4[END_REF][START_REF] Catti | High-pressure stability, structure and compressibility of Cmcm-MgAl 2 O 4 : an ab initio study[END_REF]. Some experiments show directly the formation of the calcium titanate structure after recombination [START_REF] Ono | The stability and compressibility of MgAl 2 O 4 high-pressure polymorphs[END_REF].

Several other structures including a hexagonal phase, a tetragonal phase, and additional orthorhombic phases have been linked to spinel and spinel-like materials. For example, it has been shown that MgAl [START_REF] Giesber | Redetermination of CaMn 2 O 4[END_REF]).

Here we analyze the behavior and properties of MgAl 2 O 4 up to 150 GPa. First we investigate the relative stability of several structures. We find that cubic spinel decomposes into a mixture of oxides around 15GPa and then recomposes into calcium titanate structure around 45 GPa. This is the most favorable structure up to at least 150 GPa. Then for the cubic structure we compute the elastic constants tensor and the Raman spectra within the density-functional perturbation theory.

Methodology

General

We perform first-principles calculations using the ABINIT implementation [START_REF] Gonze | First-principles computation of material properties: the ABINIT software project[END_REF], Gonze et al., 2005) of the density functional theory (DFT) [START_REF] Hohenberg | Inhomogenous electron gas[END_REF][START_REF] Hohenberg | Inhomogenous electron gas[END_REF][START_REF] Kohn | Self-consistent equations including exchange and correlation effects[END_REF] and the density functional perturbation theory (DFPT) [START_REF] Gonze | Dielectric tensor, effective charges and phonon in a-quartz by variational density-functional perturbation theory[END_REF][START_REF] Gonze | First-principle responses of solids to atomic displacements and homogeneous electric fields: Implementation of a conjugate-gradient algorithm[END_REF][START_REF] Gonze | Dynamical matrices, born effective charges, dielectric permittivity tensors, and interatomic force constants from density-functional perturbation theory[END_REF][START_REF] Baroni | Phonons and related crystal properties from density-functional perturbation theory[END_REF], Gonze et al., 2005a) based on planewaves and pseudopotentials.

We use the local density approximation for the exchange-correlation energy.

As usual with planewave basis sets, the numerical accuracy of the calculation can be systematically improved by increasing the cut-off kinetic energy of the planewaves and the density of the sampling of the Brillouin zone (Payne We use two 4x4x4 grids of k-points interpenetrating in a body-centered cubicway for the elasticity calculations and simple cubic-like grids of 4x4x4 k points for the vibrational calculations. The 4x4x4 grid and the 38Ha cut-off energy yield a precision in total energy on the order of 1mHa/molecule. The Raman spectra are also converged at the 4x4x4 grids with respect to the 6x6x6 grid.

The determination of the response function with respect to strains usually requires a better sampling in k-points, hence our choice of using a double dense grid for these calculations. For the structural relaxations we use grids of 4x4x4 k-points or larger until convergence.

The Born effective charges, the dielectric tensors and the dynamical matrices were computed using the DFPT. In DFPT the energy is analytically expanded as a Taylor series, built around small perturbations, λ:

E[λ] = E (0) + i δE ∇λ i λ i + 1 2 i,j δ 2 E ∇λ i ∇λ j λ i λ j + 1 6 i,j,k δ 3 E ∇λ i ∇λ j ∇λ k λ i λ j λ k + ...( 1
)
The perturbations can be atomic displacements, electric fields, lattice strains, etc. or any combination thereof. Each term of the series can be related to a physical property and is obtained calculating the appropriate derivative of the total energy with respect to these perturbations.

The first term of the series represents the standard ground-state energy. If the perturbation λ represents the atomic displacements then the first term corresponds to the forces on the atoms. This term is null at equilibrium. In this case the next term, the second derivative of the energy with respect to atomic displacements, is a matrix of size 3xN by 3xN where N is the number of atoms per unit cell and whose entries represent the interatomic force constants. By diagonalization this matrix yields the phonon frequencies and the phonon eigenvectors, their corresponding displacements. When one considers the interatomic forces between all the atoms within the same unit cell the diagonalization gives the frequencies of the phonon modes visible in Raman (g-modes) and infrared (u-modes) and of the silent modes. The remaining terms correspond to different higher-order effects, like anharmonicities.

The formalism behind DFPT has been extensively described elsewhere in much detail (Gonze, 1997, Gonze and Lee, 1997, [START_REF] Baroni | Phonons and related crystal properties from density-functional perturbation theory[END_REF], Gonze et al., 2005a) and thus we will not describe it any further. We primarily want to stress that DFPT offers an elegant, analytical and straightforward way to obtain physical properties which can be expressed as derivatives of the energy with respect to specific perturbations.

A c c e p t e d M a n u s c r i p t

In the following we apply DFPT to compute the elasticity and the Raman spectra of cubic MgAl 2 O 4 spinel. Alternatively, both of these properties can be computed from finite differences methods, as done previously [START_REF] Karki | Elastic properties of major materials of Earth's mantle from first principles[END_REF]. But DFPT offers a more straightforward and elegant approach with several useful physical properties computed on-the-fly.

We also study the effect of Mg-Al order/disorder on the properties of cubic spinel. The classical method to address this type of problem is the cluster expansion model. According to this approach the properties of the disordered solid may be inferred using the computed results for only several supercells with different representative atomic configurations and making use of statistical physics. This model is straightforward and it can be applied to any type of disordered structure or solid solution, but the results are highly dependent on the quality of the sampling. Each individual calculation is more tedious because of larger system sizes and possible losses of symmetry due to the specific atomic configuration.

Here we adopt an alternative approach, the virtual crystal approximation (Bellaiche and Vanderbilt, 2000). For each of the disordered sites we construct one alchemical pseudopotential mixing the atoms that participate in the solid solution in the appropriate amounts [START_REF] Giantomassi | Electrons and phonons in the ternary alloy CaAl 2-x Si x as a function of composition[END_REF][START_REF] Cohen | Quantum alchemy in Chemistry for the 21st century[END_REF]. This approach uses small simulation cells and preserves the symmetry, but the mixing should be realized between chemically similar atoms. In practice the alchemical pseudopotentials are obtained as follows: the local potentials of the original pseudopotentials are linearly mixed, the form factors of the non-local projectors are all preserved, and all considered to generate the alchemical potential, the scalar coefficients of the non-local projectors are multiplied proportionally and the core charge cutoff radius and functions are linear combinations of respectively the radii and the functions of the original pseudopotentials.

Elasticity

In the DFPT approach the elastic constants tensor is obtained analytically, considering the strains as the perturbation. The theoretical basis has been put forth a few decades ago [START_REF] Baroni | Greens-function approach to linear response in solids[END_REF][START_REF] Gonze | Dielectric tensor, effective charges and phonon in a-quartz by variational density-functional perturbation theory[END_REF][START_REF] Baroni | Phonons and related crystal properties from density-functional perturbation theory[END_REF]) with further developments and implementations emerging recently [START_REF] Hamann | Metric tensor formulation of strain in density-functional perturbation theory[END_REF]. Notably in the ABINIT implementation (Hamann et al., 2005) the perturbation with respect to the strains is described using the metric of the point group. Solving the perturbation expansion in a reduced coordinate framework rather than a cartesian one has the advantage of being universal and symmetry independent. The bare second-order energy derivative with respect to two strains η i and η j for fixed atomic positions, namely the derivative without taking into account the atomic rearrangements due to the strain itself (s = 0), yields the clamped-ion elastic constants:

C ij = 1 Ω dE 2 dη i dη j (2)
where Ω is the unit cell volume, and the energy is normalized to one unit cell.

The relaxed-ion elastic constants are obtained by correcting the above clampedion elastic constants as follows:

C ij = C ij - 1 Ω Λ mi (K -1 ) mn Λ nj ( 3
)
where Λ is the energy derivative with respect to atomic displacements, dr and strains, dǫ, and K are the interatomic force constants,

K = d 2 E/dr 2 .
These terms ensure that the coupling between different perturbations through first order derivatives of the total energy is correctly taken into account. The corrections applied to the clamped tensors are straightforward. The full theoretical derivation of these formulas and the implementation in ABINIT have been detailed in the original paper [START_REF] Hamann | Metric tensor formulation of strain in density-functional perturbation theory[END_REF] and will not be reproduced here again.

In the finite difference approach we first relax the structure minimizing the energy, the forces and the residual stresses. Next we apply different strains, η, and for each of these we relax at fixed cell geometry the positions of the atoms, minimizing the energy and the residual forces. We compute the resulting stresses, ǫ. Finally we apply the linear relation between the stresses, ǫ and the strains, η to extract the complete elastic constants tensor, C: ǫ = Cη. Despite the large amount of calculations required for the low-symmetry systems, this procedure has been applied with much success over the years (see e.g. Karki et al, 2001).

Raman intensities

The Raman intensity for an xy-oriented single-crystal depends on the frequency of the incident laser ω L , on temperature, T, which are user-defined parameters, on the frequency of the Raman mode ω i and on the xy element of the Raman tensor, α xy (e.g. [START_REF] Cardona | Light Scattering in Solids II: Basic Concepts and Instrumentation[END_REF]:

I xy ∼ Cα 2 xy (4) 5
A c c e p t e d M a n u s c r i p t

where the prefactor C is

C ∼ (ω L -ω i ) 4 1 + n(ω i ) 30ω i (5)
The temperature dependence is given by the Bose occupancy factor, n(ω):

1 + n(ω i ) = [1 -exp(-hω i /kT )] -1 (6)
The Raman tensors are defined as:

α xy = √ Ω ατ ∂χ xy ∂r ατ ( 7
)
where Ω is the unit cell volume, the atom τ moves along direction α, and χ xy is the macroscopic dielectric tensor:

χ xy = ǫ ∞ xy -δ xy 4π (8)
The derivative of the macroscopic dielectric tensor is computed with respect to the atomic displacements, r ατ , corresponding to the phonon eigenvector.

The Raman tensors are the key ingredients needed to calculate the Raman spectra. They can be computed either from finite differences, as the change of the dielectric tensor due to infinitesimal atomic displacements, or from perturbation theory, as the derivative of the energy with respect to electric fields and atomic displacements [START_REF] Baroni | Ab initio calculation of the low-frequency Raman cross section in silicon[END_REF], Dal Corso and Mauri, 1994, [START_REF] Lazzeri | First-principles calculation of vibrational Raman spectra in large systems: signature of small rings in crystalline SiO 2[END_REF]Mauri, 2003, Veithen et al., 2005). In this study we use the second approach as in the ABINIT implementation [START_REF] Veithen | Nonlinear optical susceptibilities, Raman efficiencies, and electro-optic tensors from first-principles density functional perturbation theory[END_REF].

For this we need to calculate the third order derivative of the energy with respect to two electric fields and one atomic displacements. The derivatives with respect to electric fields yields the dielectric tensor and the derivative with respect to the atomic displacements yields the change in dielectric tensor as the atoms vibrate according to a certain phonon eigenvector. Computing these high-order terms of the Taylor expansion is possible based on the previous availability of the lower-order terms with some limited amount of extra-coding and computing [START_REF] Veithen | Nonlinear optical susceptibilities, Raman efficiencies, and electro-optic tensors from first-principles density functional perturbation theory[END_REF].

This approach gives us the Raman susceptibility tensors for each phonon mode for a single crystal. As most experimental spectra from high-pressure diamondanvil cell experiments are recorded on powders, we report here the Raman spectra for crystalline powders. For this we neglect the surface reconstruction 10)

G (0) = ii,i=x,y,z (α ii ) 2 3 (9) G (1) = ij,i,j=x,y,z (α ij -α ji ) 2 2 (
G (2) = ij,i,j=x,y,z (α ij + α ji ) 2 2 + (α ii -α jj ) 2 3 ( 11
)
The intensities of the two polarized components of the powder spectra, parallel and perpendicular, and the resulting total powder spectra are :

I powder = C(10G (0) + 4G (2) ) (12)
I powder ⊥ = C(5G (1) + 3G (2) ) (13)
I powder tot = I powder + I powder ⊥ ( 14
)
We have successfully applied this approach to several other phases [START_REF] Caracas | Theoretical determination of the Raman spectra of MgSiO 3 perovskite and post-perovskite at high pressure[END_REF][START_REF] Caracas | Raman spectra and lattice dynamics of cubic gauche nitrogen[END_REF] under pressure and obtained excellent agrement between calculations and experimental data.

Using the formalism described above one computes the total intensity of the Raman peaks, but not the width of the peaks. This latter quantity comes from anharmonic effects that correspond to even higher-order terms of the Taylor expansion, which are not yet implemented within DFPT.

Results

Elasticity

Table ?? and Figure ?? show the computed elastic constants tensor at several pressures. For one pressure (20GPa) we compute the elastic constants using both methods, DFPT and finite differences. We see an excellent agrement GPa between room temperature and 1200K [START_REF] Suzuki | Harmonic and anharmonic properties of spinel MgAl 2 O 4[END_REF].

We calculate next the isotropic compressional (V p ) and shear (V s ) wave velocities for homogeneous polycrystalline aggregates as:

V p = K + 4 3 G ρ , V s = G ρ (15)
considering the Voigt-Reuss-Hill scheme for the bulk and shear moduli, K = (C 11 + 2C 12 )/3 and G = (G v + G r )/2, where :

G v = C 11 -C 12 + 3C 44 5 , G r = 5(C 11 -C 12 )C 44 4C 44 + 3(C 11 -C 12) (16)
The bulk modulus obtained from the above equation is K=205 GPa in excellent agreement with the bulk modulus obtained from fitting a 3 rd order Birch-Murnagham equation of state on the pressure-volume theoretical results for spinel, which gives K=202 GPa. The values obtained for the seismic wave velocities as well as the densities as a function of pressure are listed in This behavior reproduces the experimental observations for spinel [START_REF] Yoneda | Pressure derivatives of elastic constants of single crystal MgO and MgAl 2 O 4[END_REF]. It is also observed in other spinel structures, like magnetite (Reichmann and Jacobsen, 2004) and gahnite [START_REF] Reichmann | Sound velocities and elastic constants of ZnAl 2 O 4 spinel and implications for spinel-elasticity systematics[END_REF]. However gahnite shows a slightly positive increase in V s , while we obtain a slightly negative variation in V s for spinel.

The large anisotropy of the elastic properties of spinel is reflected in the anisotropy ratio, defined for the cubic crystals as the ratio between the shear modulus and the tetragonal shear. At ambient pressure the anisotropy is 1.72, but it increases to 1.79 at 10GPa, 189 at 20 GPa to reach 2.04 at 30 GPa. This increase is almost linear up to 20 GPa and then it slightly deviates upwards.

The weak variation of the C 44 with pressure is a general characteristic of the oxide spinels. It can be explained based on the coupling between atomic displacements and shear strains. In DFPT we obtain two types of elastic constants: for clamped ions and for non-clamped ions. In the first case the internal coordinates of freedom are not allowed to vary. In other words the atoms are fixed inside the distorted unit cell, so the coordination polyhedra do not distort to accommodate the strain. These elastic constants have a stronger variation with pressure: C 44 changes from 189 GPa at 0GPa to 205 GPa at 10 GPa and up to 220 GPa at 20 GPa. In the case of non-clamped ions, the atoms are allowed to relax and thus the octahedral distortion is adjusted to better accommodate the shear deformation. As a result the elastic stiffness of the structure is decreased. Similarly, the fact that variation of C 44 and G with pressure is smaller for oxide spinels than for silicate spinels can be explained from the difference in the softness of the octahedra; the octahedra in the oxides are softer, whereas those in the silicates are stiffer.

Vibrational spectroscopy

According to group theory, the 39 optical zone-center vibrational modes in cubic spinel decompose as A 1g +E g +3T 2g + T 1g + 2B 1u +2E u +2T 1u +4T 2u . All the u modes are infrared active and the g modes are Raman active, except for T 1g , which is silent. The frequencies of all these modes are obtained from the interatomic force constants matrix as described in Section 2.

The variation with pressure of the u-modes is shown in Figure ??. The B 1u , E u and T 1u modes do not show a LO-TO splitting, while the T 2u modes For the Raman-active g-modes we compute the Raman susceptibility tensors.

The symmetry of the Raman tensors is shown in Table ??. They determine the selection rules: which modes are visible in what geometry in Raman measurements on single-crystals [START_REF] Cardona | Light Scattering in Solids II: Basic Concepts and Instrumentation[END_REF]. For powders we consider all possible orientations of the crystals performing an average over all Euler angles that would rotate the Raman tensors. The three resulting constants as equivalent of an isotropic medium are given by Equations ( 8)- [START_REF] Caracas | Raman spectra and lattice dynamics of cubic gauche nitrogen[END_REF]. The computed Raman spectra for cubic spinel are shown in Figure ?? with both peak positions and intensities. The spectra are computed for ideal powders, where the surface, size and preferred orientation effects are neglected. We show the intensities for parallel polarization, for cross-polarization and for unpolarized spectra (total intensity).

The powder Raman spectra are dominated by the E g mode. There is one intense T 2g mode, the two other T 2g modes being much weaker. The relative difference between the intensities of the E g and the highest T 2g modes increases with pressure. The low-frequency T 2g mode corresponds to out-of-phase offcentering of Mg inside the tetrahedra such that the total polar moment remains null. The E g mode corresponds to bending of the O-Mg-O angles and the A 1g to bending of the O-Al-O angles. The higher-frequency T 2g modes are breathing modes of the octahedra. The silent T 1g modes are rotations of the octahedra. Figure ?? shows that under pressure all the modes harden.

The experimental measurements confirm our theoretical findings. Slotznik and Shim (2008) measured the Raman spectra of different synthetic and natural samples of spinel and found at ambient pressure and temperature peak frequencies in the 305-312 cm -1 for the most intense T 2g mode, in the 666-681 cm -1 for the high-frequency T 2g mode with the third T 2g mode not visible, frequencies of 407-411 cm -1 for the E g mode and of 765-770 cm -1 for the A 1g mode. All the modes soften quasi-linearly with temperature up, but show changes in the 800-1200K range. The same tendency is observed by [START_REF] Cynn | High-temperature Raman investigation of order-disorder behavior in MgAl 2 O 4 spinel[END_REF], who report the T 2g modes at 307 cm -1 and 670 cm -1 , the E g mode at 407 cm -1 and the A 1g mode at 768 cm -1 . One natural sample and one syn-

Page 11 of 26
A c c e p t e d M a n u s c r i p t thetic show a weak peak at 726 cm -1 that may correspond to our computed third T 2g mode. This peak vanishes after annealing from 1234K.

Previous first-principles calculations (de Wijs, 2002) yield the T 2g modes at 319, 570 and 682 cm -1 , the E g mode at 426 cm -1 and the A 1g mode at 776 cm -1 . The full Raman spectra were previously fully computed at ambient pressures for both order and partially disordered spinel (Lazzeri and Thibaudeau, 2006) and show a similar pattern to our results.

Raman spectra of the disordered structure

Next we study the disordered structure of spinel. We allow the cations to intermix; some of Al to occupy the cubic positions and some of the Mg to occupy the octahedral position, resulting in the general formula

(Mg 1-x Al x )(Mg 2x Al 1-2x ) 2 O 4 .
We want to see what is the effect of the disorder on the Raman spectra. We consider one term in the solid solution with x = 0.2 corresponding to (Mg 0.8 Al 0.2 )(Al 0.9 Mg 0.1 ) 2 O 4 . We build the appropriate alchemical pseudopotentials based on the algorithm described above and the corresponding atomic concentrations. We use these pseudopotentials and we relax the cubic structure of spinel at 0, 10 and 20 GPa. For the relaxed structures we compute the dynamical properties in the zone-center and the Raman susceptibilities.

The Raman peaks in the spectra of the disordered structure are softened with respect to the ordered one. This shift can be attributed to a slight variation of the volume due to disorder and change of pseudopotentials. The influence of the disorder is clearly seen on the change in intensity of the peaks. The intensity of the E g modes, which correspond to bending of the O-Mg-O angles is almost tripled by allowing some Al atoms to replace the Mg on the tetrahedral sites. This is due to an enhanced polarizability associated with the presence of the p electrons of Al that hybridize with the O p orbitals more than the Mg s orbitals, which rather tend to lose their electrons. The effect on the most intense T 2g mode is less important. The relative ratio between the intensity of these two main modes is in better agreement with the experimental measurements for the disordered structure than for the ordered one.

Structural stability

We investigate the relative stability of the spinel and post-spinel structures.

In the cubic Fd3m structure the Mg, Al and O atoms are respectively on the 8a(1/8 1/8 1/8), 16d(1/2 1/2 1/2) and 32e(x x x) Wyckhoff positions. The Mg atoms are fourfold coordinated and sit in the middle of tetrahedra and Al

11

A c c e p t e d M a n u s c r i p t are six-fold coordinated and sit in the middle of octahedra. In natural samples often there is some disorder between the cations.

From enthalpy calculations we observe that under pressure the ordered spinel cubic Fd3m structure decomposes into a mixture of oxides at 15 GPa, in agreement with previous observations [START_REF] Akaogi | High pressure transitions in the system MgAl 2 O 4 -CaAl 2 O 4 : a new hexagonal aluminous phase with implication for the lower mantle[END_REF] and calculations [START_REF] Catti | High-pressure stability, structure and compressibility of Cmcm-MgAl 2 O 4 : an ab initio study[END_REF] ). Contrary to some experimental studies we do not obtain the calcium ferrite type structure (Pnma) lower in enthalpy than the calcium titanate type (Cmcm) above the recombination pressure. However, there are experiments that confirm our theoretical findings (e.g. [START_REF] Ono | The stability and compressibility of MgAl 2 O 4 high-pressure polymorphs[END_REF]. The pressure that we obtain for the transition to the calcium titanate structure is consistent with other computational study, performed using both LDA and more advanced formalisms, like B3LYP (Catti, 2001, Fang andde With, 2002). The discrepancies between these different studies can be assigned to temperature or reaction kinetics effects, as the two structures have similar enthalpies, on the order of 2 mHa/molecule or less above 50 GPa. Moreover, there are strong structural similarities between the two phases. We also observe that the calcium manganate structure relaxes into the calcium titanate structure and the tetragonal I4 1 /amd structure relaxes into the cubic spinel in our calculations.

For each of the investigated structures we fit Vinet equation of states on the pressure-volume data. The results are summarized in We obtain the calcium-ferrite structure as competitive but unstable with respect to calcium titanate type. For the cubic structure we computed the elastic constants tensor and the Raman susceptibilities using the perturbation approach to the density functional theory in the ABINIT implementation. We also calculate the Raman spectra for one term along the ideal (Mg,Al)(Al,Mg) 2 O 4 solid solution. We showed that we obtain a better agreement in relative intensities between computed and measured Raman spectra if we allow for Mg-Al exchange between the two crystallographic sites of the cations in the structure.

We also find that the values of the elastic constants computed using the perturbative approach are within a few GPa of the values obtained from the finitedifferences approach and the experimental values. In Raman spectroscopy the positions of the theoretical peaks are found to lie within a few cm -1 and within a few tens of cm -1 of the experimentally recorded peaks in the best and worst cases, respectively. The theoretical dominant Raman peaks and their relative intensities agree well with experiments.

The advantages of the perturbation approach over the finite differences approach are the analytical solutions, faster and fewer calculations and the availability of a whole set of related supplementary properties that are obtained through combinations of perturbations. Moreover these advantages become increasingly more important with decreasing the symmetry of the crystal. Thus, our calculations illustrate the high precision that is now attainable with density functional perturbation theory.

Acknowledgements

Part of the calculations were performed on the IBM Zeus at CINES, grant stl2816. RC acknowledges financial support from the Alexander von Humboldt foundation that made possible the realization of this project. EB acknowledges the Carnegie Institution of Washington and the Bayerisches GeoInstitut for financial support.

* Table(s)

A c c e p t e d M a n u s c r i p t

A c c e p t e d M a n u s c r i p t

  et al., 1992). We use a 38 Ha cut-off energy for the kinetic energy of the planewaves. We sample the reciprocal space using regular grid of special k points according to the Monkhorst-Pack scheme[START_REF] Monkhorst | Special points for Brillouin-zone integrations[END_REF].

Page 5 of 26 A c c e p t e d M a n u s c r i p t

 26

Page 7 of 26 A

 26 c c e p t e d M a n u s c r i p t and the grain size effects and we perform integrals over all possible orientations of ideal bulk crystals. These integrals are reduced to the following three rotational invariants[START_REF] Prosandeev | First-order Raman spectra of AB' 1/2 B" 1/2 O 3 double perovskites[END_REF][START_REF] Placzek | Rayleigh-Streuung und Raman-Effekt[END_REF][START_REF] Hayes | Scattering of Light by Crystals[END_REF]):

A c c e

  p t e d M a n u s c r i p t between the DFPT approach and the finite differences approach as well as between the computed values and the experimental data.With pressure the C 11 and C 12 elastic constants increase by respectively 59 GPa and 81 GPa over 0-20 GPa theoretical pressure range, corresponding to dC 11 /dP and dC 12 slopes of 3.55 and 4.05 (Table?? and Figure . This increase is reflected in the bulk modulus K'=4.27. The tetragonal shear defined as (C 11 -C 12 )/2 decreases by 11GPa over the 0-30GPa pressure range: from 65GPa at 0GPa pressure down to 54GPa at 30GPa pressure. The C 44 elastic constant increases by only about 12 GPa in the 0-20 GPa pressure range, which corresponds to a dC 44 /dP=0.6 and to a roughly constant shear modulus.

A c c e p t e d M a n u s c r i p t

  show an increasingly large LO-TO splitting at high frequencies. In general the low-frequency modes show a weak dependence with pressure. The same features were observed in silicate spinels[START_REF] Hofmeister | Evaluation of shear moduli and other properties of silicates with the spinel structure from IR spectroscopy[END_REF]. The lower frequency B 1u and E u modes correspond to off-centering displacements of the Al, the higher frequency B 1u and E u modes to bending of respectively the O-Al-O and the O-Mg-O angles. The T 1u modes correspond to off-center displacements of Al inside the AlO 6 octahedra associated with displacements of parts of the O sublattice. The low-frequency T 2u mode corresponds to offcenter displacements of the Mg atoms in the MgO 4 tetrahedra and all the other T 2u modes to different off-center displacements of the Al atoms in the AlO 6 octahedra.

A c c e p t e d M a n u s c r i p t 4

 4 Conclusions and perspectivesWe have studied MgAl 2 O 4 under pressure. Based on enthalpy calculations, we show that the phase transition sequence at low temperatures consists of cubic spinel decomposing into a mixture of oxides at 15 GPa and recombination of the oxides into the calcium titanate-type structure at 50 GPa.

13 Page

 13

Fig. 1 .Fig. 2 .

 12 Fig. 1. Pressure variation of the elastic constants of MgAl 2 O 4 spinel. Isolated data points are obtained from finite differences calculations and the connected data points from linear response calculations.

Fig. 3 .

 3 Fig.3. Raman spectra of cubic spinel at several pressures. The spectra are computed for powders with the three averages for parallel polarization (upper row), cross-polarization (middle row) and total intensity (bottom row) at pressures of 0 GPa (left column), 10GPa (middle column) and 20 GPa (right column).

Fig. 4 .

 4 Fig. 4. Pressure dependence of the g modes in ordered cubic spinel. Lines are guide for the eyes.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Pressure dependence of the enthalpy differences with respect to the calcium titanate phase (Cmcm) of the different MgAl 2 O 4 polymorphs considered in this study. This diagram shows that the sequence of phase transitions is: cubic spineloxide mixture -Cmcm structure.

Figure 1

 1 Figure 1 Click here to download Figure(s): fig1_elasticity.eps

Figure 2

 2 Figure 2 Click here to download Figure(s): fig2_umodes.eps

Figure 3

 3 Figure 3 Click here to download Figure(s): fig3_raman.eps

Figure 4

 4 Figure 4 Click here to download Figure(s): fig4_gmodes.eps

Figure 5

 5 Figure 5 Click here to download Figure(s): fig5_new_phase_diagram.eps

  2 O 4 is part of a hexagonal aluminous phase with CaAl 2 O 4 , which is particularly significant for studies of the subducted crust and the lower mantle (Akaogi et al. 1999, Miura et al. 2000). Other suggested postspinel phases include a tetragonal structure, which is observed in high pressure NiMn 2 O 4 (Martin de Vidales et al., 1994; Åsbrink et al., 1998) and the very dense CaMn 2 O 4 -type orthorhombic structure

  Our results are in good agreement with the previous experimental(Yoneda, 2000, Suzuki et al., 2000[START_REF] Reichmann | Sound velocities and elastic constants of ZnAl 2 O 4 spinel and implications for spinel-elasticity systematics[END_REF] measurements at ambient conditions of pressure and temperature or with various other calculations employing LDA or GGA approximations for the exchange-correlation and pseudopotential and all-electron implementations (Wdowik et al., 2006, Khenata et al., 2000, Li et al., 2007), all of which are summarized in Table ??. These studies show a linear dependence of C 11 and only a weak dependence of C 12 and C 44 with Mg/Al disorder (Li et al., 2007). The elastic constants C 11 , C 12 and C 44 decrease linearly with temperature by respectively 32, 12 and 12

  . MgAl 2 O 4 recombines at about 50 GPa into a CaTi 2 O 4 type structure with Cmcm space group (Figure ??), the same trend being observed in other calculations with advanced approximations for the exchange-correlation term, like B3LYP (Gracia et al., 2002). The failure to observe the Ca-ferrite type structure, like in certain experimental studies (Irifune et al., 1991) might be due to the static approximation present in our calculations, where entropic effects due to both order-disorder and to lattice contributions are neglected. We test several other structures common to AB 2 O 4 compounds: CaFe 2 O 4 type with Pnma symmetry (Decker and Kasper, 1957), a CaMn 2 O 4 type with Pbcm symmetry (Giesber et al., 2001), an orthorhombic Imma structure, a hexagonal P-6 structure (Miura et al., 2000) and a tetragonal I4 1 /amd phase (Martin de Vidales et al., 1994). None of these structures have a lower enthalpy than the calcium titanate one at 0K (Figure ??

Table ? ?

 ? and Figure??. The Cmcm phase has the largest bulk modulus and the largest density. The theoretical bulk modulus of the cubic structure, 202 GPa, is slightly larger than the experimental one, 198 GPa. The discrepancy can be attributed to the 2% volume underestimation in our calculations of the experimental volume at ambient pressure because of LDA.

	Page 13 of 26

Table 1

 1 Parameters of the Vinet equation of state fitted on pressure-volume data for all the MgAl 2 O 4 polymorphs considered in this study.

	Structure V 0 ( Å3 ) K 0 (GPa)	K'
	Fd3m	62.339	202 4.27
	Cmcm	56.207	221 4.26
	Pnma	56.494	216 4.74
	Imma	61.086	215 4.15
	P -6	64.350	121 4.23

Table 2

 2 Elastic constants of cubic MgAl 2 O 4 as computed from density functional perturbation theory. Elastic constants computed using finite differences and the linear relation between strains and stresses are denoted by "s-s". Comparison to previous studies are as follows: Experimental data measured at ambient conditions: [1] Yoneda (1990); [2] Suzuki et al. (2000); Theoretical results: [3] Wdowik et al. (2006).; [4] Khenata et al., (2000); [5] Li et al. (2007).

	P (GPa) C 11 C 12 C 44	K	G ρ (g/cm 3 )	Vp Vs
	0 292 162 161 205 112	3.654	9.9 5.5
	10 328 202 167 244 113	3.962 10.0 5.3
	20 363 243 173 283 113	4.116 10.3 5.2
	30 391 283 176 319 110	4.255 10.5 5.1
	s-s
	20 370 251 172 291 113	4.116 10.3 5.2
	exp.
	(1) 283 155 155 198 110	3.578	9.8 5.5
	(2) 281 155 155 198 108	3.585	9.8 5.5
	(3) 293 157 150 203 109	3.652	9.8 5.5
	(4) 378 140 124 219 122	3.582 10.3 5.8
	(5) 317 107 130 177 120	3.48	9.8 5.9

Table 3

 3 Symmetry of the Raman tensors.


Gabriela Arévalo
email: arevalo@iam.unibe.ch

Stéphane Ducasse
email: ducasse@iam.unibe.ch

Oscar Nierstrasz

XRay Views: Understanding the Internals of Classes

Keywords: Class Understanding, Concept Analysis, Logical Views 1

Understanding the internal workings of classes is a key prerequisite to maintaining an object-oriented software system. Unfortunately, classical editing and browsing tools offer mainly linear and textual views of classes and their implementation. These views fail to expose the semantic relationships between the internal parts of a class. We propose XRay views -a technique based on Concept Analysiswhich reveal the internal relationships between groups of methods and attributes of a class. XRay views are composed out of elementary collaborations between attributes and methods, and help the engineer to build a mental model of how a class works internally. In this paper we present XRay views, and illustrate the approach by applying it on the Smalltalk class UIBuilder.

Introduction

Understanding source code is a key activity in the maintenance of software systems [START_REF] Basili | Evolving and packaging reading technologies[END_REF].

In the specific case of object oriented systems, reading the code is harder than procedural systems [START_REF] Dekel | Applications of concept lattices to code inspection and review[END_REF][START_REF] Lanza | A categorization of classes based on the visualization of their internal structure: the class blueprint[END_REF], and therefore the maintenance is actually higher. This is due to several reasons [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF]. The first issue is that, contrary to procedural languages, the method definition order in a file is not important [START_REF] Dekel | Applications of concept lattices to code inspection and review[END_REF]. There is no simple and apparent top-down call decomposition, even if some languages propose the visibility notion (private, protected, and public). Furthermore, the run-time architecture is not apparent from the source code, which only exposes the class hierarchy [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF]. Another important problem is the presence of late-binding leads to "yoyo effects" when walking through a hierarchy and trying to follow the call-flow [START_REF] Wilde | Maintenance support for objectoriented programs[END_REF].

Focusing on classes, considered as cornerstones of object oriented systems, we propose a technique to support software engineers in the task of understanding a complex object-oriented system. Instead of requiring the engineer to read code line-by-line to understand how a class works, we provide logically connected "XRay views" of classes that give the engineer an impression of the relationships between methods, attributes, and the invocation and access patterns of a class. In this way we support opportunistic understanding [START_REF] Littman | Mental models and software maintenance[END_REF] in which the engineer understands a class iteratively by exploring patterns (given by the views) and reading code.

Taking into account the class as a sole unit, we are able to provide answers to the following questions about a class: (a) which methods access any attribute, directly or indirectly, (b) which groups of methods access directly or indirectly all the attributes or some subset of the attributes, (c) which methods are only called internally, (d) which methods/attributes are heavily used and accessed, (e) how the methods and attributes collaborate. Each of these aspects is important for understanding the inner workings of a class, but unfortunately they are dispersed in the source code, and therefore cannot easily be teased out by a straightforward reading of the source. For this reason we generate a graph representation of the source code and run our tool, ConAn, which applies Concept Analysis to detect different collaborations to compose them in the XRay views. Concept analysis (CA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a branch of lattice theory that allows us to identify meaningful groupings of "objects" that have common "attributes" 1 . These groupings (known as concepts) form a partial order known as concept lattice. There are several algorithms for computing the concepts and the concept lattice for a given context [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. For more details, the interested reader should refer to Ganter and Wille [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. In this paper we apply this technique and limit our approach to understanding a single class, without taking into account relationships to subclasses, superclasses, or peer classes.

This paper is a short version of the approach introduced in [START_REF] Arévalo | Understanding classes using x-ray views[END_REF], and is structured as follows: Section 2 introduces the definition of elements and properties used in ConAn, and the collaborations defined to build the XRay views. Sec-tion 3 introduces in detail one specific view and a validation in the Smalltalk class UIBuilder. Sections 4 and 5 summarizes briefly the related work, our main conclusions and future work.

Applying Concept Analysis to Class Understanding

Complex software systems are composed of entities, such as classes, methods, modules, and subsystems, and different kinds of relationships that hold between them. CA can help us to detect patterns in these relationships, but first we must encode the software information at hand in terms of elements and properties. Depending on exactly what kinds of patterns we are interested in, we may apply CA in radically different ways.

In this paper we apply CA to identify concepts that correspond to the collaborations within a single class. We therefore choose as elements the methods and attributes of a class, and as properties the access and invocation relationships between them. Note that we use the term collaboration to express a relationship between a set of methods and a set of attributes.

Elements and Properties of Classes: Suppose a class has a set of methods M and a set of attributes A. The basic properties we use are extracted from the source code as follows:

• m reads x means that the method m ∈ M directly reads the value of attribute x ∈ A

• m writes x means that the method m ∈ M directly updates the value of attribute x ∈ A

• m calls n means that the method m calls the method n explicitly via a self-call.

We also define a number of derived properties, e.g.:

• m accesses x if either m reads x or m writes x (i.e., accesses = reads ∪ writes )

In Figure 1 we see a graphical representation of a class with methods M = {m, n, o, p, q, r, s, t} and attributes A = {a, b, c, d}. Here we have o calls m, m calls n, n accesses a, and so on.

These properties express direct relationships between entities. We are also interested in indirect relationships, for example, m accesses a indirectly (which we write "m accesses * a"). Indirect relationships are important in revealing collaborations between methods and attributes, and are helpful in assessing the impact of changes. We therefore define as well the following derived properties: We apply CA to our example class to reveal some concepts, e.g. ({m, o}, {accesses * a}), ({p}, {accesses a, b})

Collaborations: Since we are interested in collaborations occurring between sets of methods and attributes, we extend our properties to sets in the obvious way. Suppose that F and G are arbitrary subsets of the set of elements E. We define:

• F R G means that each entity in F is related with each one in G, i.e., ∀e ∈ F, e ∈ G, e R e .

• F R G means that the entities in F are related exclusively with those in G, i.e., ∀e ∈ E, e ∈ G, e R e , ⇒ e ∈ F and conversely, ∀e ∈ E, e ∈ F, e R e ⇒ e ∈ G.

Interpretation: We introduce now the collaborations based on which XRay views are built. Note that in each case we are interested in all of the participants of a given collaboration. We will only list those that will be used later in the paper. The complete list of collaborations is listed in [START_REF] Arévalo | Understanding classes using x-ray views[END_REF].

Direct Accessors: Direct accessors, readers or writers M ⊆ M of an attribute a are defined by a non-exclusive relationship: M accesses {a}. This collaboration provides us with a simple classification of the methods according to which attributes they use. In our example, {n, p} accesses {a}.

Exclusive Direct Accessors: A method m is an exclusive direct accessor of a when m is the only method to access a directly. We express it as: M accesses {a}. In our example, we see that {r} accesses {d}.

Exclusive Indirect Accessors: We consider a method to be an exclusive indirect accessor when it calls a direct accessor method of a specific attribute. It is represented as an exclusive relationship: M accesses * {a}. This collaboration helps us to distinguish those methods that define the behaviour of a class without using at all the state from those that use the state of the class.

In our example, we have {s, t} accesses * {d}.

Collaborating Attributes: This collaboration expresses which attributes are used exclusively by a set of methods, and we express it as: M accesses A. In the example, we have the sets of attributes accessed exclusively by sets of methods are all of size 1: {q} reads {c} and {r} accesses {d}.

Stateful Core Methods: This collaboration is a special case of collaborating attributes and expresses which methods access all the state of a class. We express it as: M accesses A. This collaboration is interesting because it provides a guideline if all the attributes are collaborating in the core of the class, and providing a functionality to the class through a set of methods. In the example, there are no methods accessing the entire state of the class.

XRay Views

An XRay view is a group of collaborations that exposes specific aspects of a class. Based on the collaborations specified above, we have defined three XRay views: STATE USAGE, EXTERNAL/INTERNAL CALLS, and BE-HAVIOURAL SKELETON. These three views address different, but logically related aspects of the behaviour of a class. Because of the limited space of the paper, we provide a small explanation of all of them, but we only detail the definitions and case study of the view STATE USAGE. The three views are explained in detail in [START_REF] Arévalo | Understanding classes using x-ray views[END_REF]. STATE US-AGE focuses on the way in which the state of a class is accessed by the methods, and exposes, for example, how cohesive the class is. EXTERNAL/INTERNAL CALLS categorizes methods according to whether they are internally or externally used, while BEHAVIOURAL SKELETON focuses on the way methods invoke each other internally. In order to illustrate our approach, we present the analysis of the class UIBuilder of the VisualWorks framework. It is a complex class that is used to build user interfaces (windows and their subcomponents) according to declarative specifications provided by its clients. We chose this class because it is complex enough in terms of number of instance variables (18) and methods (122) and communication between their methods, and it helps us to show characteristic results of XRay view application. As its name shows it is a Builder Design Patterns [START_REF] Alpert | The Design Patterns Smalltalk Companion[END_REF].

For the view, we ran our analysis tool, ConAn, on the chosen class, we examined the resulting view by looking at and combining the groups presented in the "Used and Shown Collaborations" section of the view definition, and we validated our findings by reading the source code opportunistically.

XRay View: STATE USAGE

Description: Clusters attributes and methods according to the way methods access the attributes. Used and Shown Collaborations: Exclusive Direct Acces- sors, Exclusive Indirect Accessors, Collaborating Attributes, and Stateful Core Methods. Rationale: Objects bundle both public and private behaviour and state. In order to understand the design of a class, it is important to gain insight into how the behaviour accesses the state, and what dependencies exist between groups of methods and attributes. Validation with UIBuilder: Firstly, we find getters and setters for each attribute. If we consider only the methods that access directly the attributes, we can classify the attributes into three groups: (a) attributes that are accessed only through their getter and setter (policy, stack, cache- WhileEditing, and decorator); (b) attributes that are accessed through their getter and setter, and an additional method (labels, values); (c) attributes that are accessed by several methods. The view EXTERNAL/INTERNAL CALLS helps us to refine our understanding of these differences.

We also learned that most accessors are readers, and there are only very few writers. Most of the writer methods are setters. This means that most of the attributes either are initialized when instances are created or are initialized and modified outside the class scope.

If we consider the collaborations among the attributes taking into account only the direct accessors, we find that there are very few groups of collaborating attributes: (wrap- per, component), (bindings, window), (stack, composite), (policy, window), (source, bindings), (component, decorator, wrapper). The methods access groups of attributes only by reading them. 9 over 18 attributes are used with other ones. This means that there are 9 attributes that are used alone in different methods, so this fact reveals that the class is grouping several functionalities and could be split using the set of non-collaborating and collaborating attributes. This kind of hypothesis can be refined using the BEHAVIOURAL SKELE-TON view.

When we look at indirect accesses to attributes we obtain some new groups of collaborating attributes but these new groups only include two new attributes that were not identified by the direct access attribute groups. From this observation we can learn that there is a group of 11 core attributes that are used in the same group of methods.

In this specific case, we do not have any stateful core methods, which is not surprising as the class has a lot of attributes.

Related Work

Within the CA application to understand software systems, we find several approaches. Dekel uses CA to visualize the structure of classes and to select an effective order for reading the methods [START_REF] Dekel | Applications of concept lattices to code inspection and review[END_REF]. Godin and Mili [START_REF] Godin | Design of class hierarchies based on concept (galois) lattices[END_REF] applied concept analysis to maintain, understand and detect inconsistencies in the Smalltalk Collection hierarchy. In C++ and Java, Snelting and Tip [START_REF] Snelting | Reengineering class hierarchies using concept analysis[END_REF] analysed a class hierarchy by making the relationship between methods and variables explicit. Similarly, Huchard [START_REF] Huchard | Galois lattice as a framework to specify algorithms building class hierarchies[END_REF] applied concept analysis to improve the generalization/specialization of classes in a hierarchy.

Conclusions and Future Work

In this paper we have applied concept analysis to help in the understanding of object-oriented classes. The identified concepts are the collaborations between groups of methods and attributes of a single class. We only introduced the view STATE USAGE which helps to understand how the state of the class is used. Two other views are defined and introduced in [START_REF] Arévalo | Understanding classes using x-ray views[END_REF]. Each of them expose specific aspects of a class in terms of groups of collaborations. We have limited our validation in this paper to the Smalltalk class UIBuilder, but also the classes Scanner and OrderedCollection were analyzed in [START_REF] Arévalo | Understanding classes using x-ray views[END_REF]. In our validadtion, we use ConAn, a tool we have developed to automatically generate collaborations that compose the XRay views.

In our first experiences we can observe the following:

• each XRay view has a clear focus, and identifies a set of methods exhibiting some key properties

• the views do not stand on their own, but complement and reinforce each other

• although the generation of collaborations and the views is fully automatic, their interpretation entails iterative application of views and opportunistic code reading

• the current approach does not take inheritance into account, which can be a limitation to understanding Our next steps are to explore the definitions of new kinds of views, and apply them to larger classes. We also intend to explore ways of analysing classes in the context of their class hierarchies, and also considering the possible relationships and collaborations with other class -not necessarily presented in the class hierarchies.

•Figure 1 .

 1 Figure 1. Attributes accesses and methods invocations and the groups they form

  • m reads * x if m calls m or m calls * m , and m reads x (i.e., reads

* = ∪ i≥1 calls i • reads ) • m writes * x if m calls m or m calls * m , and m writes x (i.e., writes * = ∪ i≥1 calls i • writes ) • m accesses * x if m reads * x or m writes * x (i.e., accesses * = reads * ∪ writes * ) In the example, we see that o calls * n and n reads a, and consequently o reads * a.

Proceedings of the 18th IEEE International Conference on Automated Software Engineering (ASE'03) 1527-1366/03 $ 17.00 © 2003 IEEE

Proceedings of the 18th IEEE International Conference on Automated Software Engineering (ASE'03)

Acknowledgments We gratefully acknowledge the financial support of the Swiss National Science Foundation for the project "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02), and Recast: Evolution of Object-Oriented Applications (SNF 2000-061655.00/1). We thank Michele Lanza for his reviews.


Gabriela Beatriz Arévalo

Stéphane Ducasse

Oscar Nierstrasz

Discovering Unanticipated Dependency Schemas in Class Hierarchies

Keywords: Concept Analysis, Class Hierarchies, Schemas

Object-oriented applications are difficult to extend and maintain, due to the presence of implicit dependencies in the inheritance hierarchy. Although these dependencies often correspond to well-known schemas, such as hook and template methods, new unanticipated dependency schemas occur in practice, and can consequently be hard to recognize and detect. To tackle this problem, we have applied Concept Analysis to automatically detect recurring dependency schemas in class hierarchies used in object-oriented applications. In this paper we describe our mapping of OO dependencies to the formal framework of Concept Analysis, we apply our approach to a non-trivial case study, and we report on the kinds of dependencies that are uncovered with this technique. As a result, we show how the discovered dependency schemas correspond not only to good design practices, but also to "bad smells" in design.

Introduction

Inheritance is the cornerstone of object-oriented development, enabling conceptual modeling, subtype polymorphism and software reuse. But inheritance can be used in subtle ways that make complex systems hard to understand and extend [START_REF] Wilde | Maintenance Support for Object-Oriented Programs[END_REF]. In particular, a developer making changes or extensions to an object-oriented system must understand the implicit contracts and dependencies between a class and its subclasses, or risk that seemingly innocuous changes break these contracts [START_REF] Steyaert | Reuse Contracts: Managing the Evolution of Reusable Assets[END_REF] [START_REF] Stata | Modular reasoning in the presence of subclassing[END_REF].

Many dependencies in well-designed object-oriented systems are not ad hoc, but rather correspond to well-known idioms, coding conventions and design patterns. Other dependencies may be signs of weak programming practices. In either case, implicit, undocumented dependencies lead to fragile class hierarchies that are difficult to extend or modify correctly.

Although an experienced software developer may know what to look for, it can be very tedious and time-consuming to search for undocumented dependencies in a large and complex software base. Automated tools can help to search for certain expected types of dependencies, but unfortunately the set of possibilities is open-ended.

Formal Concept Analysis (FCA) is a technique to identify recurring concepts amongst a set of elements with certain properties. A "concept" is a set of properties exhibited by a given number of elements. These concepts are then related to one another in the form of a lattice. We apply FCA to the problem of uncovering implicit dependencies in class hierarchies used in object-oriented software systems. To apply this technique, we map method invocations and attribute (i.e., instance variable) accesses to FCA elements, and consider different predicates over invocations and access as FCA properties. The concepts that are identified correspond to a set of invocations and accesses whose properties characterize what we call dependency schemas -recurring sets of dependencies over methods and attributes in a class hierarchy.

The identified dependency schemas help us to answer such questions as:

• Which classes define and use (or not) their own state and behavior? • Which classes use the state defined in their superclasses? • Which classes use template and hook methods and define behavior for their subclasses? • Which classes reuse or extend (or not) the behavior of their superclasses? • Which classes cancel the behavior of their superclasses?

Uncovered identified dependency schemas may correspond either to well-known best practice in object-oriented design, or they may be signs of degenerated design. Once dependency schemas are classified, they can be a good basis for identifying which parts of a system are in need of repair. The approach thus provides us not only with a global view of the system and which kinds of dependencies and practices occur, but it also provides detailed information about how specific classes are related to others in their hierarchy, and how that hierarchy can be modified and extended.

The paper is structured as follows: Section 2 presents an overview of the architecture of our approach. In Section 3 we provide a summary about the main definitions of FCA. In Section 4 we present our mapping of object-oriented dependencies to the framework of FCA. In Section 5 we provide an overview of the results obtained by applying our approach to the Smalltalk Collection hierarchy and by showing how SortedCollection fits into this hierarchy. Section 6 provides a brief discussion of various technical issues. Section 7 presents some related work. Finally, in Section 8 we conclude with some remarks on future work.

Overview of the Approach

Our approach is based on a pipeline architecture in which the analysis is carried out by a sequence of processing steps (Figure 1). The output of each step provides the input to the next stage. We have implemented the approach as an extension of MOOSE reengineering environment [START_REF] Ducasse | Moose: an Extensible Language-Independent Environment for Reengineering Object-Oriented Systems[END_REF]. In this section we give a brief overview of each step.

Source code

Source code model

Elements and Properties

Magnitude Set

Inheritance

Magnitude isAbstract < self send = ...

Schemas = Combination of Groups

Magnitude

< = = = =

Concept lattice

Model import

FCA Mapping

ConAn Engine

Post-Filtering

Groups

Figure 1. The overall approach

Model Import. The first step is to build a model of the application from the source code. For this purpose we use the MOOSE reengineering platform [START_REF] Ducasse | Moose: an Extensible Language-Independent Environment for Reengineering Object-Oriented Systems[END_REF], a research vehicle for reverse and reengineering object-oriented software. Software models in MOOSE conform to the FAMIX metamodel [START_REF] Tichelaar | A Meta-model for Language-Independent Refactoring[END_REF], a language-independent metamodel for reengineering.

FCA Mapping. In the second step, we map the model entities to elements and properties, and build a incidence table, which shows which elements fullfil each property, so that we can apply FCA. This mapping is described in detail in Section 4.

ConAn Engine. ConAn is our implementation of an FCA engine. Once the elements and properties are defined, we run ConAn to build the concepts and the lattice.

ConAn applies the Ganter algorithm [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] to build the concepts and our own algorithm to build the lattice [START_REF] Arévalo | High Level Views in Object Oriented Systems using Formal Concept Analysis[END_REF].

Post-Filtering. After the concepts and the lattice are built, each concept consists of a group of invocations and accesses with commonalities representing a candidate for a dependency schema. But not all the concepts are relevant. Thus we have a post-filtering process, which is the last step. Thus, we filter out meaningless or uninteresting concepts.

Analysis

We analyze candidate concepts representing the detected dependency schemas -resulting from the previous steps -and we use them to explore how the hierarchy has been built based on these schemas.

This approach is not specific to this case study. It was applied to case studies similar to detect unanticipated dependencies between different software entities in an application [START_REF] Arévalo | X-Ray Views: Understanding the Internals of Classes[END_REF] [START_REF] Arévalo | Detecting Implicit Collaboration Patterns[END_REF].

Formal Concept Analysis in a Nutshell

Formal concept analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a branch of lattice theory that allows us to identify meaningful groupings of "elements" that have common "properties" (referred to, respectively, as objects and attributes in the standard FCA literature1 ).

To illustrate FCA, let us consider a toy example about musical preferences. The elements are a group of people Frank, Anne, Arthur, John, Thomas, and Michael; and the properties are Rock, Pop, Jazz, Folk, and Tango A concept is a pair of sets -a set of elements (the extent) and a set of properties (the intent) (X, Y ) -such that Y = σ(X) and X = τ (Y ). In other words, a concept is a maximal collection of elements sharing common properties. In Table 1, a concept is a maximal rectangle we can obtain with relations between people and musical preferences. For example, ({Frank, Anne}, {Rock, Pop}) is a concept, whereas ({Catherine}, {Jazz}) is not, since σ({Catherine}) = {Jazz}, but τ ({Jazz}) = {Arthur, Catherine, Thomas, Michael}. The extent and intent of each concept is shown in Table 2

Table 2. The set of concepts of the Music example

The set of all the concepts of a given context forms a complete partial order. Thus we define that a concept

(X 0 , Y 0 ) is a subconcept of concept (X 1 , Y 1 ), denoted by (X 0 , Y 0 ) ≤ (X 1 , Y 1 ), if X 0 ⊆ X 1 (or, equivalently, Y 1 ⊆ Y 0 )
. Inversely we define that the concept (X 1 , Y 1 ) is a superconcept of concept (X 0 , Y 0 ). For example, the concept ({Anne}, {Rock, P op, T ango}) is a subconcept of the concept ({F rank, Anne}, {Rock, P op}). Thus the set of concepts constitutes a concept lattice L(T ) and there are several algorithms for computing the concepts and the concept lattice for a given context. For more details, the interested reader should consult Ganter and Wille [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF].

FCA Mapping: Setup of Formal Context

To apply FCA to detect dependency schemas, we must cast models of OO software systems in terms of an FCA context, that is, we must define the elements and properties of interest. We first describe this context, and then show how recurring combinations of properties appearing in the concepts lead to the meaningful dependency schemas.

Elements and Properties of Classes

We choose as elements the invocations of methods via a self or a super send and accesses to the attributes of a class. We choose as properties of invocations whether the call is a self or a super send and the relationships between the class that defines and the one that invokes the methods. For accesses, we are interested in the relationship between the class that defines the attribute and the one that accesses it.

To this end, we define the following predicates with the obvious meanings, where m is a method, a an attribute, i is an invoked method or accessed attribute, and C, C 1 , C 2 are classes:

• i is an invoked method in C 3 • i is an accessed attribute in C 4 • C invokes m via self • C invokes m via super • C defines m • C defines a • C 1 is ancestor of C • C 1 is descendant of C • m is abstract in C • m is concrete in C • m is cancelled in C 5 i is an accessed attribute in C C defines i C1 defines i C1 is ancestor of C C1 is descendant of C Figure 2.
Possible combination of properties applied to accessed attributes.

i is an invoked method in C C defines i C1 defines i C1 is ancestor of C C1 is descendant of C i is concrete in C (C1) i is abstract in C (C1) i is cancelled in C (C1)

Figure 3. Possible combination of properties applied to invoked methods.

Firstly, we directly adopt the predicates C invokes m via self and C invokes m via super as properties, then we combine the rest of predicates to obtain the final list of properties. Not all the combinations are valid. Figures 2 and3 show all the valid combinations to get the properties ('→' and '[ ]' represent the logical symbols and and or respectively). The obtained properties are6 :

• {i accesses } x {local state, state in Ancestor C 1 of C , state in Descendant C 1 of C } (3 properties) • {i is abstract, i is concrete, i is cancelled } x {locally, in ancestor C 1 of C , in descendant C 1 of C } (3 × 3 = 9 properties)
For example, if we take the first three properties we build them in the following way:

• i accesses local state = i is an accessed attribute in C and C defines i • i accesses state in Ancestor C 1 of C = i is an accessed attribute in C and C 1 is ancestor of C and C 1 defines i • i accesses state in Descendant C 1 of C = i is an ac- cessed attribute in C and C 1 is descendant of C and C 1 defines i
The rest of the properties are built in a similar way.

Interpretation of the Properties in Concepts

By applying FCA to this context, we obtain a set of concepts and certain of them correspond to interesting dependency schemas. In our analysis, the conjunction of properties of the intents of the concepts determines if we have found a potential meaningful dependency schema. Let us briefly consider two examples reported in Section 5: Reuse of Superclass Behavior and Broken super send Chain . Just to clarify how the concepts are interpreted we list in both cases the set of elements and properties contained in each concept. But to avoid figures with confusing information, they illustrate some elements (as an example of all elements contained in the concepts) participating in the schema.

The example of schema Reuse of Superclass Behavior (shown in Figure 5) is interpreted with the following elements and properties: Another possible example is the schema Broken super send Chain (shown in the Figure 7) and it is composed of the following elements and properties:

• C invokes i via self
• C invokes i

Case Study Results

We present here the results of our analysis of the Smalltalk Collection hierarchy. This hierarchy is especially interesting because (i) it is an essential part of the Smalltalk system, and (ii) it makes heavy use of subclassing for a variety of purposes. It is an industrial quality class hierarchy that has evolved over 15 years, and has been studied by other researchers [START_REF] Godin | Design of Class Hierarchies based on Concept (Galois) Lattices[END_REF]. It has also influenced the design of current C++ and Java collection hierarchies. The Smalltalk Collection hierarchy is composed of 104 classes distributed over 8 levels of inheritance. There are 2162 defined methods in all the classes, with 3117 invocations of these methods within the hierarchy and 1146 accesses to the state of the classes defined in the hierarchy. We first show our own categorization of detected schemas, then provide a global overview of the schemas discovered, and then we focus on the role of the class Sort- edCollection within the collection.

Detected Dependency Schemas

By applying FCA to the Collection hierarchy, we discovered 451 instances of 16 different dependency schemas. We were then able to manually categorize these into three groups: Classical, "Bad Smell" and Irregularities.

• Classical schemas represent common idioms/styles that are used to build and extend a class hierarchy, i.e., best practices. • "Bad Smell" schemas represent doubtful designs decisions used to build the hierarchy. They are frequently a sign that some parts should be completely changed or even rewritten from scratch. • Irregularities schemas represent irregular situations used to build the hierarchy. Often the implementation can be improved using minimal changes. They are less serious than "Bad Smell" schemas.

Table 3 provides an overview of the three groups, together with the total number of detected instances of each schema. Due to space limitations, we do not describe each schema in detail. We only discuss a few examples of each category. In each case, we show which are the set of properties that allows us to infer the schema.

Global View on Collection Hierarchy

As we said in the Section 1, the dependency schemas provides us with a basis to understand a class hierarchy identifying where the recurring kinds of dependencies relating classes. In this section, we introduce some of the schemas used in a global analysis of a class hierarchy.

Classical: Local Direct State Access.

Description: This schema identifies classes that define and use their own state directly (using or not the accessors). In Collection hierarchy, there are 55 classes contained in this schema. Most of the classes are leaves in the class hierarchy represented as a tree, and it shows that this hierarchy is built based on the subclassing principle, because each class is extending behavior inherited from the superclasses and providing specific functionality. Only in the subhierarchies starting from String and WeakDictionary have no leaves classes that fullfil this form, meaning that eventually these classes either use state of the superclasses or only extend the behavior of the superclasses without extending the state of the superclasses.

FCA Properties: {i accesses local state }.

"Bad Smell": Ancestor Direct State Access.

Description: This schema identifies classes that access (read or modify the values of) the state of an ancestor class without using the accessors defined in the ancestor classes. This is a not good coding practice since it introduces an unnecessary dependency on the internal representation of ancestor classes, and thereby violates encapsulation. We identified 19 classes that are part of the subhierarchies determined by GeneralNameSpace, Dictionary, Or- deredCollection, LinkedList. In most of the cases, the classes are accessing state of the immediate superclass, but in the subhierarchy of OrderedCollec- tion we detected several classes that access state of ancestors higher up in the chain of their superclasses.

FCA properties: {i accesses state in

FCA properties: {C

invokes i via self , i is concrete lo- cally, i is cancelled in descendant C 1 of C } or {C in- vokes i via self , i is concrete in ancestor C 1 of C , i is cancelled in descendant C 2 of C }

Irregularities: Inherited and Local Invocations.

Description: This schema shows methods that are invoked by both self and super sends within the same class. Initially this schema is a good practice coding, but a problem occurs when the super sends are invoked from a method with a different name. This special case of the schema occurs in the classes LinkedOrderedCol- lection, LinkedWeakAssociationDictionary and XMain-ChangeSet. All these classes have a special form: the class overrides a method m and m invokes a method named own-m via self send, and this last method calls m via a super send implemented in the superclass. Figure 4 illustrates this schema. This is an irregular case of the schema Redefined Concrete Behavior because the class is overriding the superclass behavior but is indirectly using the superclass behavior.

FCA properties:

{C invokes i via self , C invokes i via su- per, i is concrete locally, i is concrete in ancestor C 1 of C }

"Class-Based" View on SortedCollection

So far, we have introduced some schemas that help us to analyze a class hierarchy from a global view, but our approach helps also us to analyze how a class is built in the context of its superclasses and subclasses, meaning from local view regarding a class.

We chose to analyze the class SortedCollection a subclass of OrderedCollection. A SortedCollection is an ordered collection of elements, sorted using a function of two arguments. The class has one attribute sortBlock which holds the sorting function; has one class variable (static variable in Java) DefaultSortBlock that holds the default sorting function. As a subclass of OrderedCollection and it inherits two instance variables firstIndex and lastIndex and an indexed variable objects. Regarding its methods, it adds 10 methods and overrides 19 methods from the 403 inherited.

In this class we identify 12 different schemas that involves this class. Again for space reason, we present 4 of them belonging to different categories:

Classical: Reuse of Superclass Behavior.

Description: This schema shows us that the class Sort- edCollection calls via self the methods copyEmpty, insert:before:, reverseDo:, asArray, isEmpty, not-FoundError and they are not defined in the class but different superclasses define their behavior. Specifically, we see that the methods copyEmpty, in- sert:before: and isEmpty are defined in the class Or-deredCollection, reverseDo: and asArray are defined in the class SequenceableCollection; and notFoundError is captured in the class Collection. Thus, we see which are the superclasses that determine the behavior of the class. Figure 5 illustrates this schema.

"Bad Smell": Broken super send Chain.

Description: This schema identifies methods that are extended (i.e., performing a super send) in a class but redefined in their subclasses without calling the overridden behavior, hence giving the impression to break the original extension logic. In SortedCollection the methods = and representBinaryOn: are invoking superclass hidden methods. But the definition of these methods in the subclass SortedCollectionWithPolicy does not invoke the method defined in SortedCollection.

Such a behavior can lead to unexpected results when the classes are extended without a deep knowledge of them. Figure 7 illustrates this schema. Description: This schema shows that the method addLast: is called via a super send and this method is defined in the immediate superclass OrderedCollection, meaning that the class is reusing the behavior of the superclass. But this method is also implemented in the class SortedCollection but the behavior is cancelled.

FCA Properties:

{C invokes i via super, i is concrete lo- cally, i is concrete in descendant C 1 of C , i is con- crete in ancestor C 1 of C }
Although it is not a good practice, it seems a normal situation because the elements in a sorted collection cannot be added in the end of the collection, but in a predefined position defined by the sorting function of the class. As we said previously, this is a case where the inheritance is used as code reuse without regarding subtyping. Specifically, this means that SortedCol- lection is a kind of OrderedCollection but not all the inherited methods can be applied. Figure 6 illustrates this schema. lectionWithPolicy. When checking the code, we see that the most of the calls are self sends and in the method called copyEmpty, we have a super send to a method with the same name. This means that, in spite of a local implementation of copyEmpty, finally the behavior of this method is determined by the superclasses, showing a heavy reuse of the superclass code. Figure 8 illustrates this schema.

FCA properties: {C

invokes i via self , C invokes i via su- per, i is concrete locally, i is concrete in ancestor C 1 of C }
The identified schemas in our approach provide another view on the class. They present some anticipated dependencies between the methods of the classes and their relationships in the hierarchy. Our experience confirms to us that the Collection hierarchy is a rich but difficult to extend hi- erarchy since it is based on a heavy use of subclassing and aggressive code sharing. It relies on some internal knowledge and often contains coding manner that leads to fragile design.

Discussion

Use of FCA: FCA offers the possibility of specifying simple properties between the elements we need to analyze. Based on these simple properties, as we have seen in the Section 2, the FCA algorithm (to build the concepts) implemented in ConAn provides us with all the possible combinations of elements with a common set of properties. In this way we "mine" the concepts we use to identify possible dependency schemas in the class hierarchies. This approach allows us to detect not only well-known, but also unanticipated relationships between the different elements. Thus, we are able to identify all possible combinations of properties that could characterize a schema actually used in a class hierarchy.

Performance of the Algorithm: In Section 4 we saw that we need to map the model entities (in our specific case, the invocations and accesses) to CA elements and build different properties based on them. Due to a limitation imposed by FCA algorithm (to build the concepts) in performance measurements [START_REF] Kuznetsov | Comparing Performance of Algorithms for Generating Concept Lattices[END_REF], we reduce the amount of CA elements to compute the concepts and the lattice without losing information about the class hierarchies. Thus, if we have several invocations of the same method or several accesses to the same attribute in the same class, we keep only one invocation or one access per class as a representative, and we reduce dramatically the number of CA elements used by ConAn, and improved the computing time from around 1 hour to 10 min compared to the approach presented in an earlier paper [START_REF] Arévalo | Understanding Behavioral Dependencies in Class Hierarchies using Concept Analysis[END_REF].

Analysis of State and Behavior:

There are two main differences with regard to our previous work [START_REF] Arévalo | Understanding Behavioral Dependencies in Class Hierarchies using Concept Analysis[END_REF]. First, in the current paper we take dependencies to state into account, whereas our earlier work considered only behaviour. This yields more concepts, and hence more schemas of interest than when only behaviour is considered. Secondly, we are able to categorize schemas into those that represent good, irregular and bad design decisions in the class hierarchies.

Partial Usage of Lattice: In Section 4, we pointed out that once the concepts and the corresponding lattice are built, each concept represents a group of invocations and accesses that relate a group of classes. But not all the concepts are relevant, and we keep only the meaningful concepts for our analysis. There are main two points worth mentioning. Firstly, we only use 64 of 174 concepts in total, meaning that the 1/3 of the lattice represents meaningful information in our approach from our analysis. Finally, we must note that, in this particular application of FCA, we do not use the partial order of the concepts in the lattice. This means that we do not exploit the possible relationships between the schemas (mapped from the concepts).

Mapping from Concepts to Schemas: Of the 64 concepts we identify as "interesting", we derive 16 dependency schemas. This means that in most of cases, a schema is represented in several concepts, meaning that a schema can be described by different combinations of properties. But the policy of mapping is arbitrary so far, meaning that when we interpret the contents of the concepts, we decide which are concepts corresponding to the different schemas. For example, the schema Local Direct State Access is represented in 5 concepts because each concept shows different ways that the state of the class is accessed. On the other hand, the schema Local Behavior is represented by just one concept. In other cases, one schema could represent a good or an irregular design practice. In this specific case, we see that the schema Inherited and Local Invocations is irregular only when the super sends are invoked from a method with a different name.

"Non-invoked" Methods: Our approach is limited to analyzing methods and attributes that are effectively used in the context of the class hierarchy. If there are methods that are defined in any class but are not invoked in the class itself or in any subclasses or in any superclasses, those methods are not included in our analysis. Clearly, we lose some information about the classes in the hierarchy, because we only concentrate on usage of behavior and state of the class.

FCA vs. Logic Engine: One of the main results of this approach is a catalog of schemas to characterize a class hierarchy. As we see in Section 4.2, each schema is the in-terpretation of a conjunction of properties in the concepts. Then, each schema can be expressed as a logic predicate (mapped from the properties) and a logic engine can be run in a class hierarchy to identify the occurrences of the different schemas. Thus, we must remark that the main difference between the use of FCA and a logic engine is that in the first case, we do not know in advance which are the possible schemas occurring in the class hierarchies, and consequently we do not know the combination of properties that characterize them. FCA helps us mainly to discover unpredictable schemas introduced in a class hierarchy. In the case of the use of a logic approach, we must know which are the different properties that characterize a schema. We consider that both approaches are complementary ones, because the catalog of schemas can be complete after the analysis of several class hierarchies, and in that moment, the use of logic engine is most suitable than FCA.

Related Work

Various researchers have explored techniques to support the understanding and evolution of class hierarchies using FCA. We briefly summarize their works.

Dekel uses CA to visualize the structure of the class in Java and to select an effective order for reading the methods and reveal the state usage [START_REF] Dekel | Revealing JAVA Class Structures using Concept Lattices[END_REF]. Godin and Mili [8] uses concept analysis to maintain, understand and detect inconsistencies in the Smalltalk Collection hierarchy. In C++, Snelting and Tip [START_REF] Snelting | Reengineering Class Hierarchies using Concept Analysis[END_REF] analysed a class hierarcy making the relationship between class members and variables explicit. They were able to detect design anomalies such as class members that are redundant or that can be moved into a derived class. As a result, they propose a new class hierarchy that is behaviorally equivalent to the original one. Similarly, Huchard [START_REF] Huchard | Galois Lattice as a Framework to specify Algorithms Building Class Hierarchies[END_REF] applied concept analysis to improve the generalization/specialization of classes in a hierarchy. Tonella and Antoniol [START_REF] Tonella | Object Oriented Design Pattern Inference[END_REF] use CA to detect the structure of Gammastyle design patterns using relationships between classes, such as inheritance and composition.

All the above approaches only take information into account about which selectors are implemented by which classes or how clients classes use the class hierarchy. They do not consider behavioral information (i.e., based on self and super sends) or usage of the state between the different classes in a class hierarchy. As shown in this paper, this information in static analysis helps us to identify different behavioral and state dependency schemas. With these schemas, we evaluate the reuse of the methods and state defined in the classes, and we discover different design decisions used in building the class hierarchies.

Conclusion and Future Work

In this paper, we show how the automatic generation of schemas using FCA helps us to discover different implicit and undocumented dependencies in class hierarchies in terms of the behavior and state usage. The categorization of these schemas into good, irregular and bad smell design decisions allows us to localize where different irregularities or problems occur in the implementation of a class hierarchy. With the dependency schemas we are able to analyze a class hierarchy from a global viewpoint considering all the classes, and from a local viewpoint considering considering one class and the relationships with its subclasses and superclasses.

We have previously explored two other applications of FCA. With X-Ray Views [START_REF] Arévalo | X-Ray Views: Understanding the Internals of Classes[END_REF], we analyze a class in isolation (without the context of superclasses and subclasses). The study is based on the use of behavior and the state, and the collaborations of different defined methods inside the classes. This approach complements the information of the schemas Local Behavior and local state introduced in this paper.

We have also previously used FCA to explore behavioral dependencies [START_REF] Arévalo | Understanding Behavioral Dependencies in Class Hierarchies using Concept Analysis[END_REF] in class hierarchies. In that approach, we analyze only the relationships between classes based on the behavioral dependencies (self and super sends and where the methods are captured). We introduced a possible list of schemas that show the different design decisions in a class hierarchy. In this paper, we complement the information with state accesses and also analyse the cancellation mechanism of methods. We also provide a categorization of the schemas to be able to concentrate on the irregularities and problems in the class hierarchies.

We plan to apply the approach to other class hierarchies to check if the catalog of schemas identified thus far covers all the interesting possible cases or if we discover new cases of implicit contracts. Another interesting analysis is the combination of the methods that are invoked and those that are not invoked but are declared in the classes. This kind of approach can measure how much information defined in the class hierarchy is used or not. Another feature to improve is the refinement of properties to be able to get a mapping 1 to 1 from concept to schema, and thus, reduce the complexity of the lattice in terms of number of concepts. Last but not less important is the analysis of relationships given by the partial order between the different schemas -mapped from the concepts in the lattice.

FCA properties :Figure 7 .

 properties7 Figure 6. Cancelled Local Behavior and Behavior Reuse of Superclasses.

Figure 8 .

 8 Figure 8. Inherited and Local Invocations.

Table 1 . Incidence Table of the Music Exam- ple

 1 2 . Table1shows which people prefer which kind of music, and is called the incidence tableA context is a triple C = (E, P, R), where E and P are finite sets of elements and properties, respectively, and R is

	prefers	Rock Pop Jazz Folk Tango
	Frank	True True	True
	Anne	True True	True
	Arthur	True True
	Catherine	True
	Thomas	True
	Michael	True True
	a binary relation between E and P represented in the in-
	cidence table. In the musical preferences example, the ele-
	ments are the people, the properties are the different kinds
	of music they prefer, and the binary relation prefers is de-
	fined by Table 1. For example, the tuple (Frank, Folk) is in
	R, but (Anne, Jazz) is not.
	Let X ⊆ E, Y ⊆ P , and σ(X) = {p ∈ P |∀e ∈
	X : (e, p) ∈ R} and τ (Y ) = {e ∈ E|∀p ∈ Y :
	(e, p) ∈ R}, then σ(X) gives us all the common prop-
	erties of the elements contained in X, and τ (Y ) gives us
	the common elements of the properties contained in Y , e.g.,
	σ({Arthur, Catherine}) = {Jazz}.

  : {copyEmpty, insert:before:, re- verseDo:, asArray, isEmpty, notFoundError} are selfcalled in SortedCollection • i is concrete in ancestor C 1 of C : {copyEmpty, insert:before:, isEmpty} has concrete behavior in ancestor OrderedCollection; and {reverseDo:, asArray} has concrete behavior in ancestor SequenceableCollection; and {notFoundError} has concrete behavior in ancestor Collection. OrderedCollection, SequenceableCol- lection and Collection are ancestor classes of Sorted-

	Collection.

Table 3 . Commonly Identified Schemas.

 3 Identifies concrete or local inherited methods that are invoked i.e., via self send in a class or its superclasses, but are cancelled in subclasses. Method cancellation is a sign of inheritance for code reuse without regard for subtyping.IrregularitiesInherited and Local Invocations Identifies methods that are invoked by both self and super sends within the same class. This may be a problem if the super sends are invoked from a method with a different name.

	Name	Description

Identifies concrete inherited methods whose behavior is cancelled in the class but whose corresponding superclass behavior is invoked i.e., via a super send from a different method. This workaround is a common sign of difficulty improperly factoring out common behaviour.

6 Broken super send Chain

Identifies methods that are extended (i.e., via a super send) at some point in the hierarchy, but are then simply overridden lower in the hierarchy. This can be the sign of a broken subclassing contract.

7

Reuse of Superclass Behavior. "Bad Smell": Cancelled Local Behavior but Superclass Reuse.

	Collection
	notFoundError
	{ <concrete> }
	Sequenceable
	Collection
	reverseDo:
	{ <concrete> }
	Ordered
	Collection
	isEmpty
	{ <concrete> }
	Sorted
	Collection
	add:
	{ ... self isEmpty ... }
	reverse
	{ ... self reverseDo: ... }
	copyFrom: to:
	{ ... self notFoundError ... }
	Figure 5.

We use the terms element and property instead to avoid the unfortunate clash with object-oriented terminology.

2 The full property names are prefers Pop or prefers Folk. We abbreviate these names for the sake of conciseness. Proceedings of the Ninth European Conference on Software Maintenance and Reengineering (CSMR'05) 1534-5351/05 $20.00 © 2005 IEEE

i is an invoked method in C means that there is a method in C that calls method i

i is an accessed attribute in C means that there is a method in C that accesses attribute i

A method m in class C is cancelled in Smalltalk when it calls the selector shouldNotImplement to indicate that the class C wants to undefine the method m defined in a superclass. Proceedings of the Ninth European Conference on Software Maintenance and Reengineering (CSMR'05)

The notation used is the same as cartesian product, meaning that {a,b}x{c,d} = {(ac),(ad),(bc),(bd)}

Proceedings of the Ninth European Conference on Software Maintenance and Reengineering (CSMR'05) 1534-5351/05 $20.00 © 2005 IEEE

Acknowledgments

We gratefully acknowledge the finan- cial support of the Swiss National Science Foundation for the project "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02, Oct. 2002 -Sept. 2004).