Elizaveta Clouet
email: elizaveta.clouet@univ-nantes.fr

Béatrice Daille
email: beatrice.daille@univ-nantes.fr

Splitting of Compound Terms in non-Prototypical Compounding Languages

Compounding is present in a large variety of languages in different proportions. Compound rate in the text obviously depends on the language, but also on the genre and the domain. Scientific and technical texts are especially conducive to compounding, even in the languages that are not traditionally admitted as highly compounding ones. In this article we address compound splitting of specialized terms. We propose a multi-lingual method of compound recognition and splitting, which uses corpus frequencies, lexical data and optionally linguistic rules. This is a supervised method which requires a small amount of segmented compounds as input. We evaluate the method on two languages that rarely serve as a material for automatic splitting systems: English and Russian. The results obtained are competitive with those of a state-of-the-art corpus-driven approach.

Introduction

Compounding is a method of word formation consisting of a combination of two (or more) lexical elements that form a unit of meaning. In this work we only handle so called "closed compounds" [START_REF] Macherey | Language-independent compound splitting with morphological operations[END_REF], i.e. those forming also a graphical unit. A great number of languages resort to this word formation. In some of them such as German, Dutch (Germanic family), Estonian or Finnish (Uralic family) compounding is very regular and well described. In other languages it is less productive (e.g. Slavic family), or even marginal (most of Romance languages). This phenomenon is particularly productive in specialized domains because of the necessity to denote the domain concepts in a very concise and precise way. In addition, specialized texts contain many neoclassical compounds [START_REF] Namer | Morphologie, lexique et traitement automatique des langues[END_REF], i.e. compounds with some elements of Greek or Latin etymological origin: hydro + logy = hydrology.

In this article we discuss processing of compound terms, and we carry out the experiments with English and Russian, which are not prototypical compounding languages. As a matter of fact, compounding in English is rather productive and widely investigated in linguistic studies. But this language is rarely subject to experiments in automatic compound splitting. The first reason is that most of English compounds are formed by simple concatenation (airfoil = air + foil, streamtube = stream + tube), so their splitting is supposed to be straightforward. The second reason is that many compounds in highly compounding languages should be translated into English as multi-word expressions. That is why the works addressing automatic compound splitting in the context of machine translation often admit that English contains only few closed compounds [START_REF] Koehn | Empirical methods for compound splitting[END_REF][START_REF] Macherey | Language-independent compound splitting with morphological operations[END_REF]. In these works, the use of English parallel texts helps to extract the multi-word equivalents of compounds from the texts in highly compounding languages. We assume that English compound terms are still worth splitting and analyzing. The first reason is that the assumption of independent occurring of English compound elements fails when we consider neoclassical compounds. The second ground is that distinguishing between compounds and non-compound out-of-dictionary words (named entities, derivative forms, etc.) can be problematic.

In the Russian language the elements of compounds do not often appear as independent words in texts, for example: водоснабжение 'water supply' vodosnabzhenie1 = voda 'water' + snabzhenie 'supply' Here the inflection "a" of the first component is omitted and the linking morpheme "o" is inserted.

Compounding in Russian is less regular than, for instance, in German. Therefore most of NLP systems for Russian, to our knowledge, store usual compound parts in the lexicon. For specialized vocabularies this solution does not seem to be sufficient, since the new compounds terms constantly appear.

To handle compounds in typologically different languages, including languages with non-independent components, we propose a corpus-driven splitting system using also string similarity and able to integrate language-specific rules2 .

The article has the following structure. Section 2 gives a review of some compound splitting methods proposed in the literature. Section 3 presents our splitting method. In Section 4 the experiments and data are described. We discuss the results and analyse the errors. We also compare our system to the state-of-the-art corpus-based method of [START_REF] Koehn | Empirical methods for compound splitting[END_REF]. We conclude with Section 5.

Related Works

Compound splitting was addressed in many NLP works, as a standalone task or in the pipeline of another application: machine translation [START_REF] Koehn | Empirical methods for compound splitting[END_REF][START_REF] Macherey | Language-independent compound splitting with morphological operations[END_REF][START_REF] Stymne | Generation of compound words in statistical machine translation into compounding languages[END_REF], information retrieval [START_REF] Braschler | How effective is stemming and decompounding for german text retrieval[END_REF][START_REF] Chen | Translation term weighting and combining translation resources in cross-language retrieval[END_REF], etc.

To deal with the non-independent compound elements in morphologically rich languages, different solutions have been proposed. It is possible to store separately the compound stems and the linking morphemes (the morphemes that are inserted at the component boundaries to form a compound), and to have a grammar to combine them. This solution is realized in the morphological analyser for German SMOR [START_REF] Schmid | SMOR: A german computational morphology covering derivation, composition, and inflection[END_REF]. The construction of such a finite-state morphology for a new language is a costly task in terms of time and efforts.

Another approach is to formalize the component modifications as a set of rules describing addition, but also deletion and substitution of some character sequences on the component boundaries within a compound. Thus, the compound splitter BananaSplit [START_REF] Ott | Measuring semantic relatedness of German compounds using GermaNet[END_REF] uses a set of linguistic rules for German to restore independent forms from compound forms, and validates the restored forms with the help of a monolingual dictionary.

Other methods resort to the corpora to validate the analyses. A pioneering work using corpus statistics for compound splitting was done by [START_REF] Koehn | Empirical methods for compound splitting[END_REF]. The algorithm generates all possible segmentations for a given word (taking into account some linking morphemes), and gives a probability for each segmentation, estimated from the geometric mean of the component frequencies in the corpus. The segmentation with the highest score is classed as the best.

Probabilistic splitting methods using machine learning technologies have been proposed [START_REF] Dyer | Using a maximum entropy model to build segmentation lattices for mt[END_REF][START_REF] Hewlett | Fully unsupervised word segmentation with BVE and MDL[END_REF][START_REF] Macherey | Language-independent compound splitting with morphological operations[END_REF]. Actually they are less precise than the languagespecific methods, but their advantage is the usability for any language. Statistical methods also tend to integrate some linguistic knowledge (e.g. list of linking morphemes).

Compound Splitting Method

Our concern was to design a corpus-driven system that could be applied to different languages, but also able to integrate linguistic knowledge. For a given word, the system makes the decision as to whether it is a compound, and for compounds it gives one or several candidate analyses ranked by their scores (in this work we use up to five candidates). Figure 1 illustrates the splitting mechanism, as well as the system training needed to set up splitting parameters.

General Method Description

To split a candidate compound, we start generating all its possible two-part segmentations beginning with the components of minimum permitted length: we used the minimum length of 3 characters, which is a frequent choice for compound splitting systems [START_REF] Koehn | Empirical methods for compound splitting[END_REF][START_REF] Dyer | Using a maximum entropy model to build segmentation lattices for mt[END_REF].

RU ветротурбина 'wind turbine' vetroturbina → vet + roturbina vetroturbina → vetr + oturbina vetroturbina → vetro + turbina ... vetroturbina → vetroturb + ina If we can provide rules for this language to restore independent lexemes from non-independent components, we apply them to the component candidates. We will further refer to these rules as "linguistic rules" or simply "rules". For English only a few rules for correcting lemmatization were needed, for instance "ed" → "e": health-based → health + base. For Russian we defined a set of 15 rules to transform the left component and 14 rules to transform the right component. In the example above, the rule "o" → "" can be applied to the 3rd segmentation candidate: vetro → vetr.

If the rules are not available or not sufficient to cover all modifications, the potential lemmas are proposed using a similarity measure. We use normalized Levenshtein distance [START_REF] Frunza | Identification and disambiguation of cognates, false friends, and partial cognates using machine learning techniques[END_REF] as similarity measure. Thus, vetr is not an independent word, and some candidate lemmas were found: veter 'wind', veto 'veto', and vetka 'branch', all with the similarity value of 0.8.

For each candidate segmentation, the lemmas for both components are matched with a lexicon and with a word list extracted from a specialized monolingual corpus. The lexicon contains a monolingual dictionary filtered by POS and combined with a list of neoclassical roots and prefixes to process neoclassical compounds. In this work, we kept only nouns, adjectives, verbs and adverbs in the lexicon to reduce prospective errors, even if we are aware that compound components can belong to other POS (pronouns, numerals), but in the languages that we investigated such formations are minor. Then, the segmentation score is calculated (see below).

After that we try to split the right side component further in a recursive manner, and so on up to a certain level. This level is a parameter corresponding to the maximum expected number of components, for instance: EN kiloelectronvolt kiloelectronvolt → kilo + electronvolt electronvolt → electron + volt Finally, the algorithm returns a top 5 of the best segmentations ordered by their score. For RU ветротурбина the output is: veter turbina 0.81 veto turbina 0.8 vetka turbina 0.8

The correct split is veter 'wind' + turbina 'turbine', and indeed it has the best score given by the program.

Score Calculation

At each level of segmentation recurrence (at the first level the word is divided into 2 components, at the second level into 3 components and so on), the segmentation score is calculated as follows:

Score(segm) = Score(compA)+Score(compB) 2 if exact match Score(compA)+Score(compB) nbComp otherwise
where nbComp is the number of components in the word at this level of recurrence. "Exact match" means that all components are found "as is" in the dictionary or corpus. We consider that two-part segmentations are more frequent and more plausible than those containing three and more parts, that is why we favor the splits into two components. For example for the RU ветроколеса vetrokolesa (plural form of 'windwheel'):

Correct split is vetro.kolesa = veter 'wind' + koleso 'wheel'

Score(vetro + kolesa) = Score(veter) + Score(koleso) 2
Incorrect split is vetro.ko.lesa = veter 'wind' + ko 'co-, prefix' + les 'wood'

Score(vetro + ko + lesa) = Score(veter) + Score(ko)+Score(les) 2 3
An exception occurs for the splits in which the components exactly match the dictionary or corpus (e.g. EN kiloelectronvolt). These splits are realistic and we do not penalize them dividing by nbComp.

Score(kilo

+ electron + volt) = Score(kilo) + Score(electron)+Score(volt) 2 2
This way of calculating the segmentation score at each splitting level corresponds also to the theoretical principle defended by [START_REF] Benveniste | Problèmes de linguistique générale[END_REF] and that we share: a compound word is always formed by two components. Among these two components, one can be a compound itself, but even in this case only two components take part in a compound formation. However, we have noticed in a separate experiment that the score obtained in such a way is rather close to the arithmetic mean of the component scores.

The score of a component is calculated by a linear interpolation:

Score(comp) = α sim(comp, lemma) + β inDico + γ inCorpus + δ DSpec (1)
where sim (comp,lemma) means similarity between the component and a candidate lemma (from 0 to 1), inDico and inCorpus indicate the existence of the lemma in the lexicon and in the corpus (0 or 1), DSpec means domain specificity value for this lemma (see below). The sum of coefficients α, β, γ and δ is 1. If a lemma in the lexicon is neoclassical, which means it does not occur individually in the corpus, we assign it the value inCorpus = 1, otherwise the score would be penalizing for all neoclassical compounds. The coefficients α, β, γ and δ are parameters and should be learned for each language using a small amount of training data (about a hundred of compounds per language).

Domain specificity

Since we are dealing with specialized vocabularies, we exploit the notion of domain specificity of a lexical unit, or in other terms, the relevance of the lexical unit for a given domain. Our domain specificity is based on Ahmad's "weirdness ratio" [START_REF] Ahmad | What is a term? The semiautomatic extraction of terms from text[END_REF] which is calculated as the ratio between the term frequency in a specialized corpus and the term frequency in a general corpus. As we use a linear interpolation formula, each component of the sum should be between 0 and 1. So we normalize a weirdness ratio of a lemma dividing it by the maximum weirdness ratio found for this specialized corpus.

Domain specificity helps to disambiguate splitting variants. So, for our Russian example ветротурбина vetroturbina, we would like to rank the analysis veter turbina better than veto turbina or vetka turbina, and we rely on the fact that the word veter 'wind' is more specific for the given wind energy domain than the words veto 'veto' and vetka 'branch'.

Our method can also be used to process general language compounds. In this case, one should exploit a list of the words extracted from a general language corpus, with their relative frequency in this corpus instead of the domain specificity list extracted from a specialized corpus.

Training phase

The training phase consists of two steps: optimizing the coefficients used for component scoring, and defining a score threshold to recognize whether an out-of-dictionary word is a compound.

Firstly, for a given language we train our algorithm on a certain number of words annotated with their segmentations (training dataset) in order to find the best coefficients α, β, γ and δ (see equation ( 1)). We try all the possible coefficients from 0 to 1 with a step of 0.1 (the sum of all coefficients equals one) and we retain the combination that results in the highest recall and precision. In this step, the parameters giving the highest recall are generally the same as the ones giving the best precision.

Recall for Top N is calculated as the ratio between the number of words that have a correct split among N segmentations ranked as the best ones by the algorithm and the total number of analysed compounds:

Recall = nbSegmentedCorrectly nbCompounds (2)
Precision for Top N is calculated as the ratio between the number of words having a correct split among N segmentations ranked as the best ones by the algorithm and the number of words split by the algorithm:

P recision = nbSegmentedCorrectly nbSegmented (3)
Note that the denominator here is the number of words which were split, and not the number of all candidates produced. Secondly, we apply again the same algorithm with the selected coefficients to a training dataset. The current objective is to determine an optimal score threshold over which the given word is probably a compound. To do that, we try all the thresholds from 0 to 1 with a step of 0 The user can therefore choose the threshold that he considers as optimal depending on the target application. For instance, for lexicon acquisition task splitting precision will be more important than recall, whereas for the supervised translation task splitting recall may turn out more important. In this work, we optimize the threshold for a better precision. This allows us to compare the results to those of a state-of-the-art method [START_REF] Koehn | Empirical methods for compound splitting[END_REF] which privileges precision rather than recall.

Experiments and Results

We use a unified strategy for the two major types of compounds, native and neoclassical. We also consider in our experiments some prefixed words. Standard prefixation is, of course, a subtype of derivation, and not of compounding. However, in some boundary cases it is difficult to catch the difference between prefixed formations and neoclassical or native compounds: compare prefix bito neoclassical root uniaccording to [START_REF] Hervé | Phonétique et morphologie du franc ¸ais moderne et contemporain[END_REF]. Moreover, from the operational point of view, some prefixed words can be split in the same manner as compounds.

Data

Table 1 summarizes the size of the resources used in this work. Wind Energy corpora3 were crawled from Web pages by means of Babouk (Groc, 2011), a tool dedicated to automatic compilation of domainspecific corpora, with the use of a key-term list. To compute the domain specificity of a term, we needed its frequency in the general language corpus. For the English language, we used a subpart of the New York Times corpus4 . For Russian, we used a frequency list computed from The Russian National Corpus5 .

Concerning the dictionaries, we exploited the monolingual parts of the following bilingual general language dictionaries: FR-EN from the ELRA catalogue6 for the English part, RU-EN from English-Russian full dictionary7 for the Russian part.

To obtain the lists of neoclassical roots and prefixes, we firstly took the English and Russian equivalents of neoclassical elements enumerated in [START_REF] Hervé | Phonétique et morphologie du franc ¸ais moderne et contemporain[END_REF]. Secondly, we completed these lists with some prefixes of Latin, Greek or another origin that have equivalent in numerous languages (co-, pre-, post-, trans-, etc.). For English we consulted publicly available morpheme translation tables8 . We will refer to this source as NCP-list.

We extracted from the specialized corpus a lexicon which contains only the words that (1) are either nouns or adjectives, because most compounds belong to these two categories (about 80% according to cross-language study reported in [START_REF] Scalise | Why compounding?[END_REF])); (2) have frequencies greater than 2; (3) are 6 characters and more long; and (4) do not appear in the general language dictionary used. We applied these criteria to eliminate the words that are not compounds in order not to split them. For POS filtering, TreeTagger9 was used.

The lexicons were randomly sorted and manually annotated until we obtained between 200 and 300 compounds. Each compound word was annotated with the correct segmentation(s), other words were marked as non-compounds. used to train our system and a test dataset used to evaluate the splitting quality. Table 2 shows the lexicon sizes for each language, as well as the number of compounds found.

Experiments

The application of our method to the training data allowed us to obtain the parameters required for splitting algorithm (see Table 3). The selected coefficients were then used to analyse a test dataset for each language. The evaluation in terms of recall, precision, and F-measure is presented in Table 4.

The results vary according to the language. For Russian the precision turns out to be higher than for English: 81% for Top 1 and 82% for Top 5 for Russian against 74% for Top 1 and 78% for Top 5 for English. However, the recall is much higher for English than for Russian: 87% for Top 1 and 91% for Top 5 against 52% for Russian. It can be explained by the abundance of component modifications in the latter and by the lack of correct lemmatization for many terms. We can also notice that for Russian the gain obtained in the Top 5 of segmentation candidates is very small compared to the Top 1, which means that for this language if the correct candidate was found, it was almost always ranked as the best one.

Error Analysis

Pre-processing is very important for proper splitting and recognition of compounds and non-compounds. In our experiments lemmatization was performed by a probabilistic tool, trained on general language data, so some compound and highly specialized non-compound terms were not lemmatized correctly. The rules that we have introduced in order to deal with such cases help to properly split non-lemmatized compounds, but they do not help to recognize non-compounds. Correction of lemmatization should be done before dictionary filtering, it will enable the identification of some words as in-dictionary ones, and enable them to be kept unsplit. This will decrease the number of false segmentations and consequently improve precision. Some false positive segmentations were due to the splitting of named entities: EN Cambridge split into cam + bridge. Named entity recognition would decrease the number of erroneous segmentations.

Among the errors intrinsic to our method, we can state those related to the use of string similarity, so certain affixes or combinations of affixes may be confused with the independent words, e.g., RU керосиновый 'kerosene ADJ', non-compound word Erroneous segmentation: kerosinovyj = kerosin 'kerosene N' + novyj 'new'

To avoid this problem, a large set of morphemes for each morphologically rich language is needed.

Comparison to a State-of-the-art Method

We compared our method to the corpus-driven approach proposed by [START_REF] Koehn | Empirical methods for compound splitting[END_REF] that became a state-of-the-art method of compound splitting. We applied it to our experimental data with the Language Coefficients (α β γ δ) usage of the same rules, stop lists and NCP-lists as we have used in our method. For the elements from the NCP-list, a corpus frequency of 1 was artificially assigned, otherwise they had no chance of being split correctly by this corpus-based method because they never independently occur in the texts. The results are presented in Table 5.

We should notice that this method can produce several segmentation candidates, including the original word kept unsplit. The unsplit word can be ranked as first, second and so on, unlike our method which first of all takes the decision whether a word is a compound or not. If for a given compound the algorithm returned the unsplit word as the first candidate, but a correct segmentation was among the first 5 candidates (e.g. monopile → 1) monopile 2) mono pile), we evaluated this analysis as correct for the Top 5, otherwise the evaluation would be penalizing for this method. But according to the same logic, if for a non-compound the first candidate was unsplit, and the second was split (e.g. district → 1) district 2) di strict), we evaluated it as correct for Top 1 and incorrect for Top 5. The consequence of such an evaluation is that the precision can be lower for the Top 5 experiments than for the Top 1 experiments, as we actually stated.

The method we proposed was more precise than Koehn and Knight's one for Russian (up to 14 points), but less precise for English (up to 13 points). Our method segmented a larger number of compounds in all experiments, except for the Top 5 for Russian. F-measure was also higher with our method (from 2 to 6 points) except for the Top 5 for Russian (1 point difference).

Koehn and Knight's method is based on corpus frequency, and it is possible to integrate linguistic rules too. Our method, besides the corpus evidence and linguistic rules, takes into account the evidence from a monolingual dictionary and the string similarity between compound elements and their lemmas.

The fact that Koehn and Knight's method does not exploit string similarity guards it against producing implausible segmentations and allows achieving, when combined with linguistic rules, a high precision, especially for the English language. However, the use of string similarity allows our method to detect some components not appearing as independent words in the texts/dictionaries even if the rules used do not cover their transformation into lemmas, cf. RU example vetroturbina, which was not split by Koehn and Knight's method.

Koehn and Knight's method is also known to keep some compounds unsplit if they occur more often in the corpus than their components, like the example of EN monopile. The neoclassical compounds also tend to remain unsplit with this method.

Conclusion

In this article, we have investigated the compound splitting of lexical units from specialized domains. We proposed a method for compound recognition and splitting that exploits language-independent features (corpus frequency, string similarity), lexical data (monolingual dictionary, list of neoclassical elements and prefixes) and linguistic rules. We tested this method on two languages that are not traditionally considered as highly compounding ones, but as we have seen, the specialized texts in these languages contain many compounds.

Our method turns out to be competitive with the state-of-the-art corpus-driven approach of [START_REF] Koehn | Empirical methods for compound splitting[END_REF]. The advantage of our method is its domain-orientation, which enables to boost correct segmentations containing specialized words into the Top 1. The use of string similarity may introduce some false positive splitting, but at the same time, it allows detection of additional components not covered by the rules. This point is particularly important to handle compounds in morphologically rich languages in which retrieval of the independent forms from compound elements is not straightforward, such as Russian. The results of both methods tested are lower for Russian than for English. This confirms that processing of Russian compounds is actually challenging for NLP systems and worth further investigating.

Figure 1 :

 1 Figure 1: Parameters setting and compound splitting

Table 1 :

 1 .05 and calculate recall and Resources Statistics precision for Top 1 and Top 5 of segmentations ranked as the best ones by the algorithm and with a score higher than this threshold.

	Language Specialized Corpus General Corpus Dictionary NCP-list
	EN	314,549	5,001,609	145,542	437
	RU	323,929	109,115,810	526,876	132

Table 2 :

 2 The annotated lexicons were then divided into two parts: a training dataset Extracted Lexicon Size and Compound Rate

	Language No. of lemmas No. of compounds Compound rate
			Training dataset
	EN	404	106	27%
	RU	485	116	24%
			Test dataset
	EN	401	100	25%
	RU	700	170	24%

Table 4 :

 4 Splitting quality evaluation in terms of R(ecall), P(precision) and F(-measure). Highlighting corresponds to the experiments in which our method outperforms[START_REF] Koehn | Empirical methods for compound splitting[END_REF].

	Score threshold

Table 5 :

 5 Splitting quality by[START_REF] Koehn | Empirical methods for compound splitting[END_REF] method.

Here and further for Russian examples transliteration is given.

https://logiciels.lina.univ-nantes.fr/redmine/projects/compost

http://www.lina.univ-nantes.fr/?Ressources-linguistiques-du-projet.html

http://catalog.ldc.upenn.edu/LDC2008T19.

http://corpus.leeds.ac.uk/serge/frqlist/rnc-modern-lpos.num.html

http://catalog.elra.info/product_info.php?products_id=667

http://dicto.org.ru/xdxf.html

http://www.lina.univ-nantes.fr/?Linguistic-resources-from-the,1676.html

http://www.cis.uni-muenchen.de/ ˜schmid/tools/TreeTagger/


Martín Dias

Alberto Bacchelli

Georgios Gousios

Damien Cassou

Stéphane Ducasse

Untangling Fine-Grained Code Changes

I. INTRODUCTION

Version Control Systems (VCS), such as Git and Subversion, allow programmers to control changes to source code and make it possible to find who made each software change, when, and where. This information is important to support both the coordination of developers working in teams [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] and the creation of many recommendation and prediction systems related to software quality [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF].

Developers often bundle unrelated changes (e.g., bug fix and refactoring) in a single commit [START_REF] Herzig | Untangling changes[END_REF], thus creating a so-called tangled commit, such as the following taken from Jaxen: 1 ---------------------------------------------------- (revision 1252) @@ -61,7 +61,7 @@ * -* /public interface AdditiveExpr extends BinaryExpr + * / +public interface AdditiveExpr extends BinaryExpr { -String getOperator(); } The tangled commit above contains both a refactoring (the move of 'getOperator' to a different place, not shown in this extract), and code formatting (the move of an interface definition 1 http://jaxen.codehaus.org, commit: svn-1252, 2006-11-09 to its own line). Sharing tangled commits is problematic as they make code review, reversion, and integration harder and historical analyses of the project less reliable [START_REF]The impact of tangled code changes[END_REF]. For example, even integrating the code formatting change included in the aforementioned commit (without the refactoring) would be a demanding task.

Untangling existing commits (i.e., finding how to separate parts of a commit relating to different tasks) is an open research problem. Herzig and Zeller presented the earliest and most significant results in this area [START_REF] Herzig | Untangling changes[END_REF]: They implemented the first algorithm that can automatically untangle commits given artificially tangled ones.

In this paper, we expand on this previous work by: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] working in an untyped setting where a part of the approach by Herzig and Zeller is inapplicable; (2) considering finegrained code change information gathered during development (e.g., time at which each line has changed and all versions of each line); and (3) evaluating the resulting approach both on data generated by programmers who manually label it and with programmers working on real-world development tasks.

The ultimate goal of our work is to help developers of dynamically-typed code share untangled commits. To that end, we: (1) asked 7 developers to manually cluster changes for each of their commits using a dedicated tool, for a period of 4 months; [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF] manually validated the generated data, selecting the data recorded by two of these developers, and computed a number of features based on their fine-grained code changes;

(3) modeled the problem of predicting whether two fine-grained changes belong together, with a variety of machine learning approaches, determined the most appropriate one, and identified the most significant features; (4) designed an algorithm that uses the machine learning result to propose an automatic clustering of any tangled commit and developed a corresponding tool, EpiceaUntangler; and (5) evaluated the effectiveness of our approach with developers who used EpiceaUntangler in their daily work for two weeks.

Our results show that three features are especially important to perform clustering of fine-grained code changes: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] the time between two changes; [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF] the number of other changes between two changes; and (3) whether the two changes modify the same class. By modeling these features with Random Forests [START_REF] Breiman | Random forests[END_REF], we identify whether two changes belong to the same commit with an accuracy of 95%, if training and testing on the same developer, and more than 88% if tested on a different developer. A set of 200 manually clustered fine-grained code changes (i.e., the equivalent of a few days of work) was sufficient to reach good performance. When deploying EpiceaUntangler with new developers during their daily tasks, we recorded an average success rate of 75% and a median one of 91%.

II. PROBLEM DESCRIPTION

When developers want to share their work in a VCS, they will, more often than not, realize that they have done more than one activity, e.g., fixed a bug, reformatted a method, and fixed a typo in a comment. Sharing everything in a single tangled commit is regarded as bad practice because it makes the following activities more difficult:

• Review -Reviewers have to understand the code changes of all the activities at once [6]- [START_REF] Gousios | Work practices and challenges in pull-based development: the integrator's perspective[END_REF]; • Reversion -Developers have to revert all changes of a problematic commit even when only the code change of one activity is problematic [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF]; • Integration -Integrators have to merge or reject whole commits, e.g., they will typically reject a code formatting operation and a bug fix included in the same commit [START_REF] Gómez | Supporting integration activities in object-oriented applications[END_REF]; • Historical analysis -Researchers need to associate activities to files to conduct statistical analyses while, e.g., mining software repositories [START_REF]The impact of tangled code changes[END_REF].

A. Existing Solutions for Tangled Changes

To avoid tangled commits, developers could organize their work so that, at commit time, only one activity's code is to be shared. This requires frequent commits and interruptions in the developer's work flow [START_REF]Subversion best practices[END_REF]- [START_REF] Steinert | CoExist: Overcoming aversion to change[END_REF]. Even with a lot of discipline, there will be times when a developer will have to split changed code into several commits.

To separate code from several activities into different commits, some tools (e.g., 'git add') let the user selects which files and lines to commit first. Being line based, these tools share the following problems: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] The code present at commit time might be incomplete [START_REF] Negara | Is it dangerous to use version control histories to study source code evolution?[END_REF]: Each change to a line shadows previous changes of the same line, thus making it impossible to commit the line as it was before the last change; (2) a commit resulting from a manual selection of a subset of all changed lines might be invalid: e.g., a developer might commit the beginning of a function definition but not the end; and (3) changed lines are shown in the order they appear in their files irrespective of their modification time: This makes it difficult for developers to select lines changed closely in time.

A great source of inspiration for us comes from Herzig et al. [START_REF] Herzig | Untangling changes[END_REF], [START_REF]The impact of tangled code changes[END_REF], who implemented an algorithm to automatically untangle commits. Their algorithm uses several confidence voters to decide whether two lines of a tangled commit should be put in the same cluster. They aggregate the results of each confidence voter into a single score, and then use the concepts of a multilevel graph-partitioning algorithm by Karypis and Kumar [START_REF] Karypis | Analysis of multilevel graph partitioning[END_REF] to generate the clusters. Their voters include:

• 'FileDistance': the number of lines between the two lines if they are both in the same file;

B. Addressing the Current Limitations

In our work, we propose to alleviate the aforementioned limitations by (a) expanding the setting to a dynamically-typed environment where some kinds of analyses are not available; (b) using fine-grained code changes that we collect during development sessions; (c) relying on developer-approved data for the validation of untangling approaches. This results in the following requirements for the approach, EpiceaUntangler, that we present in this paper:

The Dynamically-Typed Setting: Whereas the approach of Herzig et al. relies on static analysis of Java programs to untangle commits, our approach helps developers to create untangled commits in an environment that is dynamically-typed. Certain types of static analysis, e.g., accurate call graph analysis, is not possible for dynamically-typed languages. Therefore, our approach cannot rely on such static analysis.

Fine-Grained Changes: In modern integrated development environments (IDEs), tools can be notified each time a software artifact is changed and saved. As a result, a tool could listen to all fine-grained changes made by developers and, at commit time, present the developer a list of all the changes they have done. For example, a developer changing and saving the source code of a method 3 times will result in 3 fine-grained changes. This is in contrast with most tools that only present the latest version of each changed line; this requirement tackles the incompleteness limitation.

Developer-Approved Data: The untangling algorithm should be based on data created by developers who personally untangle the tangled commits that they produced in the first place. The final version of the approach should provide each developer, at commit time, with a list of the automatically untangled commits containing their fine-grained changes: Each developer could then reorganize these automatically-computed clusters of changes. Results must be validated by comparing the change clusters that are automatically computed against the reorganization done by the developer in a manual way.

III. PROPOSED SOLUTION

In a nutshell, our solution is to develop an approach and associated tools to help developers share untangled commits. The tools log all the fine-grained changes made by developers as they change the source code. When a developer wants to commit her changes, the tool, based on an analysis of the recorded information, presents several automatically-computed clusters of changes: Each cluster represents a distinct activity of the developer since last commit. The developer may then add a comment to each cluster and, if necessary, adapt the automatic clustering (by adding/removing clusters and moving changes to different clusters). Once the developer validates the clusters, the tool generates one commit per cluster and publishes them to the repository. In the following section, we present our solution decomposed in individual parts.

A. Epicea: Event Modeler with Fine-Grained Changes

Central to our approach is the collection of fine-grained information. To conduct this task, we use Epicea [START_REF] Dias | Representing code history with development environment events[END_REF], a tool we developed to model IDE events. In essence, Epicea listens to actions taking place in the IDE and records different types of events. A simplified version of the events recorded by Epicea is shown in Figure 1. Epicea records complete information of these events (e.g., whether a test run failed), including a timestamp. As previous studies (both in Eclipse [START_REF] Hattori | Syde: A tool for collaborative software development[END_REF] and in Smalltalk [START_REF] Robbes | A change-based approach to software evolution[END_REF]) showed that save-based recording produces reliable fine-grained code change data, we record code change operations (add, modify, and delete classes and methods) every time the user saves the code. Epicea is invisible to the user as there is no impact on performance. Epicea stores the collected data as a sequence of serialized objects in plain text files.

B. Voters

Once the data is collected, we have to characterize it in a way that it can be used for generating untangled changes. Similarly to Herzig et al. [START_REF] Herzig | Untangling changes[END_REF], [START_REF]The impact of tangled code changes[END_REF], as a first step we model our clustering task as a binary classification problem: For all the potential pairs of recorded fine-grained changes, we want to determine whether they belong in the same cluster. To this end, we implement a number of features or, maintaining the term used by Herzig et al. [START_REF] Herzig | Untangling changes[END_REF], voters, which describe different relations between the considered changes. Our voters (detailed in Table I) span the following six dimensions: 1) Code structure: Although dynamic languages make it difficult to conduct static analysis, it is possible to compute basic relations. Our three voters in this dimension consider whether two changes happen in the same package, class, and/or method. 2) Content: This voter returns true if the two changes to a method are only source-code reformats, i.e., if the abstract syntax tree of a method remains the same after a change on it. This voter should help linking changes regarding refactoring actions. 3) Testing: Epicea records test runs. The rationale of this voter is that two changes happening between runs of the same test could be related to the same task (e.g., this should hold in the case of test-driven development). 4) Spread: These voters measure the distance between the two considered changes, considering time passed and number of other changes in between. We expect close changes to be more related. 5) Message sending: This dimension analyzes whether the changes involve related message sending (also known as 'method invocations', in languages such as Java or C#). 6) Variable accessing: This dimension computes relations between the variables accessed by the two changes: For example, a change that adds a new instance variable to a class may be related to a change that adds an usage of the same variable in a method.

The input of each voter is a pair of changes, and the output is of the type specified in column 'Type' of Table I.

C. Machine Learning Approaches

Our approach computes the values for each voter for each pair of changes (for performance reasons, we only consider fine-grained change pairs that are less than 3 days apart); to aggregate these values and train models that would predict whether two changes should be in the same cluster, we use machine learning (ML).

We consider three well-known machine learning algorithms that can handle binary classification [START_REF] Hastie | The Elements of Statistical Learning[END_REF]: (1) binary logistic regression ('binlogreg'), (2) naïve bayes ('naivebayes'), and (3) random forests [START_REF] Breiman | Random forests[END_REF] ('ranforest'). We chose these algorithms not only because they have been applied successfully to a number of data mining tasks related to software engineering, but also because they make quite different assumptions on the underlying data and model (e.g., 'naivebayes' relies on the conditional independence assumption, i.e., the value of a voter is unrelated to the value of the others, and 'binlogreg' requires each observation to be independent and linearity of independent variables and log odds), thus they can offer different interpretations. The choice of the most appropriate machine learning algorithm is based on the empirical data collected during the experiment. This machine learning step takes as input the values computed by the voters for two particular changes, and it outputs the probability of the two changes belonging to the same cluster.

D. Clustering

The last necessary step in our approach is to take the output of the machine learning step, computed on each pair of changes, and aggregate it to form the clusters of changes for the user. In this method, each change is initially considered to be a cluster of its own. Then pairs of clusters are successively selected by their maximum scores and merged. The result of this method is a dendrogram, which is a binary tree that represents the nested clustering of code changes. In this dendrogram, each non-leaf node has a similarity level that represents how similar are both children. In our problem, a similarity level of 1 corresponds to two clusters that must be merged, while a level of 0 corresponds to the opposite decision.

Finally, the desired clustering of code changes is obtained by cutting the dendrogram at some similarity threshold. Using a too low threshold produces too many small clusters, while a threshold that is too high produces a single cluster. The choice of the most appropriate similarity threshold depends on the change set and, similarly to the machine learning approach, is based on the empirical data collected during the experiment.

The output of this step is the set of independent clusters of fine-grained changes, which is eventually displayed to the user with a dedicated user interface.

IV. RESEARCH METHOD

In this section, we describe how we structure our research in terms of research questions, we present the research settings, and we outline our research method.

A. Research Questions

The ultimate goal of our work is to help developers of dynamically-typed code share untangled commits. For this we devise and test the approach we previously described to untangle code changes at a fine level of granularity. Accordingly, we structure our empirical investigation through the following three research questions: RQ1: Which voters are significant to untangle fine-grained code changes?

With this question we aim to understand which are the most important voters in our untyped setting. To answer this research question, we consider the machine learning task of deciding whether two changes should belong to the same cluster. In doing so, we also determine which machine learning approach among the three we test, is better suited to model the problem through our voters.

RQ2: How effective is a machine learning model based on the significant voters in untangling historical finegrained code changes?

Once we find the most significant voters and the best machine learning approach, we are interested to know their performance in predicting whether two changes should belong to the same cluster. We also want to investigate the effect asserted by individual developers' working styles on prediction performance; for this we train and test the machine learner on data generated by different developers (e.g., training on one developer's data and testing on another developer's data). RQ3: How effective is a tool based on the best voters and machine learning approach, when deployed with developers working on their daily tasks? Finally, we want to devise an approach EpiceaUntangler, based on the best machine learner and voters, to generate clusters and present them with a graphical user interface. We want to test its effectiveness when deployed with participants (1) whose data should not have been used for training the classifier, and (2) who should be working on their usual development tasks.

B. Research Settings

Our study took place with professional developers, researchers, and students using the Pharo environment. 2 Pharo is an open-source dialect of Smalltalk and implementation of its programming environment. Pharo was forked from Squeak3 in 2008 and it is rapidly evolving. Currently, Pharo has around 60 worldwide contributors, it is used by more than 15 universities to teach programming and by 10 research groups to build tools, and more than 50 companies are using it in production.

We chose Pharo as a case study for two main reasons: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] the Pharo open-source community of developers has been receptive, since its inception, to welcome and thoroughly evaluate research tools (e.g., [START_REF] Renggli | Domain-specific program checking[END_REF]- [START_REF] Hora | Apievolutionminer: Keeping api evolution under control[END_REF]); and (2) the programming language, the development environment, and the versioning system are tightly integrated. The later feature allows for a fast prototyping of an approach to record fine-grained code changes and interaction with testing and the versioning system. The former feature allow us to collect fine-grained data about code changes and IDE interactions from participants doing real-world development work. It also enabled us to deploy our resulting tool with more participants to evaluate its results. Moreover, many research tools tested within Pharo later became integral part of the environment (e.g., [START_REF] Verwaest | Flexible object layouts[END_REF]); we want both to improve the state of the art in untangling code changes and to create an approach that can be used in real-world scenarios.

C. Research Steps

1) Fine-grained data generation and collection: To answer our first two research questions, we need a ground truth to train and test our voters and machine learning approaches. Such a ground truth should be a reliable dataset containing fine-grained code changes correctly split into tasks by their authors. To obtain this, we contacted 7 participants actively contributing to Pharo, including the first author of this paper. We asked them to install Epicea and to use the tool (i.e., Epicea Task Clusterer (ETC), Figure 2) that we devised to manually cluster their fine-grained code changes. We showed a screencast 4 demoing the tool to all the participants before they started using it, so that they could understand the goal of the experiment and adapt their workflow accordingly. Every time the participants decided to commit their code to the versioning system, during their normal work, the ETC's interface would appear (as in Figure 2) with a list of all the fine-grained changes, since the previous commit, that the user had to manually cluster into tasks. In detail, the main user interface of Epicea Task Clusterer (shown in Figure 2) works as follows: In the top pane, each column (e.g., Point 1) represents a task (to group an activity of the user), and each item in a column represents a code change (e.g., Point 2). Each code change is in a ClassName»methodName format, and the icon shows the type of change (as in Figure 1). The bottom pane (Point 3) shows the details of the selected change, in a unified-diff format. The user can review the listed changes and perform three actions to specify the expected clustering for them: Add a new empty task/cluster (Point 4), reopen an already closed task/cluster (Point 5), and move changes between columns (with drag and drop, Point 6). Once the clustering task is completed, the user presses the button 'Done', and the interface disappears.

2) Data analysis and evaluation of voters: Once the participants concluded the data collection period of 4 months, we conducted exploratory data analysis [START_REF] Neil | Doing Data Science[END_REF] on the generated clustered changes. The data generated by five users was extremely sparse and inconsistent; these users confirmed this explaining that they could not afford the time required by Epicea Task Clusterer to review each change made during the experiment period. We removed this data and kept the data generated from the remaining two users (including the first author of this paper) whose features are described in the top half of Table II Using 2devs we answered RQ1 and RQ2. As previously detailed (Section III-C), we used machine learning to identify pairs of changes belonging to the same commit, by modeling it as a binary classification. For all potential pairs of changes in 2devs, we calculated values for all the voters in Table I and labeled with 'true' if the changes belonged to the same commit or 'false' otherwise. As our dataset was unbalanced (the false class overruled the true one by a ratio of 4:1), we adjusted to avoid overfitting. Models where thus trained with a ratio of 2:1 samples for the false and true class respectively.

Evaluation of voters.

To evaluate each trained model, we used standard machine learning metrics [START_REF] Hastie | The Elements of Statistical Learning[END_REF], such as precision (prec), recall (rec), accuracy (acc), the Area Under the receiver operating characteristic Curve (auc) and the Fmeasure (f.measure). Models where trained with an increasing number of samples as input (10 4 to 10 6 samples) to determine the minimum number of samples required to obtain adequate performance. At each input size, we used random selection 10-fold cross validation to evaluate model stability and reported results based on the mean of the 10 runs. We selected the best classifier and applied a classifier-specific process to rank voters according to their importance in the classification. Then we incrementally trimmed the voter set starting from the least important feature until the performance of the classifier was severely impacted. Finally, we retrained the best classifier with the trimmed voter set and used that as our final prediction model. The final model was then exposed as a web service that EpiceaUntangler used to drive the change untangling process to answer RQ3. 3) Deployment and evaluation with developers: Once we completed the creation and evaluation of the best ML approach and features on dataset 2devs, and obtained promising results, we created the corresponding implementation in EpiceaUntangler, a tool that developers can use in real-world development.

During developer's work, EpiceaUntangler records the fine-grained change information, exactly as done for the data collection phase. When the developer wants to commit, our approach computes the values for all the significant voters for each pair of code changes, and queries the web service implementing the final model of the ML classifier. For each pair, the web service returns a score between 0 and 1, indicating the probability that the two changes belong to the same cluster, according to the trained model. EpiceaUntangler aggregates all the scores to form clusters using agglomerative hierarchical clustering method (see Section III-D). This method outputs a dendrogram, which has to be cut at some similarity threshold to obtain the clusters of changes. We created a testbed with 'change set-expected clustering' pairs whose purpose is to help us to conceive a good function for obtaining the similarity threshold for cutting the dendrogram. In Figure 3 we illustrate the function. The similarity threshold we chose corresponds to the maximum similarity gap between all nodes whose similarity level is less than 0.25. The intuition behind taking the maximum similarity gap is that continue merging code changes together is not worth, because the meaningful clusters have already been detected. The reason to use 0.25 as a lower bound is that we observed from data that such a low likelihood indicates in most cases changes that should not be merged. This process happens in the background: After the developer decides to commit, she sees an interface similar to that used to generate the data for 2devs (Figure 2), with the difference that the clusters are already pre-computed by the tool. Then, the user browses the clusters and reorganizes the changes in case the pre-computed clusters are wrong.

Evaluation of clustering.

To conduct this evaluation, we recruited six participants, whose features are described in the bottom half of Table II. They all used EpiceaUntangler for 2

ch3 ch5 ch6 ch1 ch2 ch4 C1 C2 C3 C4 C5 computed ch1 ch2 ch3 ch4 ch5 ch6 E1 E2 E3 E4 E5 expected E1 E2 E3 E4 E5 C1 0 1 0 0 0 C2 0 0 0 ½ ½ C3 1 0 0 0 0 C4 0 0 1 0 0 C5 0 0 0 0 0 Fig. 4.
Comparison between a computed clustering and an expected clustering.

On the left-hand side, each box represents a cluster of changes. The computed clustering contains 4 clusters labeled from C1 to C4 (cluster C5 is a virtual cluster to ease comparison). The expected clustering has 5 clusters: E1 to E5.

On the right-hand side, the matrix shows the corresponding Jaccard indexes.

weeks. To evaluate the clustering, each participant was asked to confirm whether the automatic clustering was correct; if not they could rearrange changes to the correct clusters. We used the resulting data to evaluate the accuracy of our approach.

To measure the success rate of our approach, i.e., how similar the computed clustering (from our algorithm) is to the expected clustering (from the developer), we need to know the ratio between the number of successfully clustered changes and the total number of changes. To know if a change has been successfully clustered, we must find which computed cluster best matches which expected cluster.

Figure 4 shows a sample comparison between a computed clustering and an expected clustering. The matrix on the right represents the Jaccard indexes computed for each pair of clusters; this index is defined as using the following formula:

JCiEj = |Ci ∩ Ej| |Ci ∪ Ej|
This Jaccard index represents how much two sets coincide. It ranges from 0 to 1, where 1 means the two sets are equal (e.g., C3 and E1 in Figure 4) and 0 means the two sets have nothing in common (e.g., C4 and E2 in Figure 4).

From the resulting matrix we want to know which computed cluster matches which expected cluster. This can be obtained by maximizing the sum of the Jaccard indexes over all permutations. For the sample in Figure 4 the maximum sum over all the permutations (3.5) is attained for this set of pairs:

M atching = {(C1, E2)(C2, E4)(C3, E1)(C4, E3)(C5, E5)}
We compute the success rate of our algorithm using the following formula:

SuccessRate = #Successf ullyClusteredChanges #Changes
A change ch i is successfully clustered if the computed and expected clusters that contain ch i are in the same pair of the M atching set. In Figure 4, all changes are successfully clustered except ch6. This gives us a success rate of 5 /6 = 0.83.

V. RESULTS

In this section we answer our research questions, by describing the results we obtained in our evaluations.

A. What Are the Dominant and Significant Voters?

As a first step to answer our first research question, we use all the machine learning approaches we consider on the collected data and we evaluate whether an approach performs undoubtedly better. Table IV reports the results of the classification performance of each machine learning approach for predicting whether two changes belong together, using a training size of n = 320,000 pairs (or 800 fine-grained changes), on the 2devs dataset. Overall, and across all metrics, the Random Forests algorithm delivers the best results, by a large margin. The high REC measurement of the 'binlogreg' result can be justified by its equally low PREC; the classifier marks most of the file changes as belonging in the same cluster, but few of those decisions are correct. Once we established that 'ranforest' delivers the best results, we assessed the importance of each voter for its classification result. We used the process suggested by Genuer et al. [START_REF] Genuer | Variable selection using random forests[END_REF]. Specifically, we run the algorithm 50 times on a randomly selected sample of 10 6 change pairs, using a large number of generated trees (500) and trying 5 random variables per split. Then, we used the mean across 50 runs of the Mean Decrease in Accuracy metric, as reported by the R implementation of the ranforest algorithm, to evaluate the importance of each feature. The results can be seen in Figure 5. The three most important voters are: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] the time difference between the changes, (2) the ordered distance of the changes, (3) and whether the changed code belonged in the same class. We cannot make inferences about whether the effect of each voter is positive or negative to the response class; nevertheless, we believe that the results are indicative of the task-based nature of software development.

B. How Effective Is Random Forests with the Dominant Voters?

We answer our second research question by using only the three most important voters to train the prediction model. The prediction results are reported in Table IV, marked as 'ranforest-trimmed'. We see that even with just those voters we obtain very good prediction results: The new model is within 3% of the performance of the model trained in all metrics. Furthermore, we analyze the impact of the developer who made the changes on training and testing. We expect that behaviors of developers might be different and have a significant impact on the model.

We start showing that we obtain the best results when we train and test from data generated by the same developer (the 'intradev' dataset in Figure 6). This confirms our hypothesis that the behavior of the specific developer has an impact on the q q q q q q q q q q q q q numberOfVariableAccesses numberOfMessageSends sameSelector Mean Decrease in Accuracy Variable Fig. 5. Voter importance for the random forest classifier.

q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q auc acc f.measure Number of fine-grained changes dataset q combined crossdev intradev Fig. 6. Dataset performance metrics model and the results. Furthermore, we see that the results are not equally good when training with data from one developer and testing on the other (the 'crossdev' dataset); moreover we see that as we increase the training size, there is a drop in performance. This can be attributed to overfitting the model to the working habits of each individual developer. Finally, we see that we can train accurate models by combining data from multiple developers. In the 'combined' dataset, we combine the data generated by both developers and use this to train the model; this means that training and testing data is taken from both samples. Figure 6 shows that this dataset reaches high and stable results; and overfitting seems not present.

What is interesting to note is that the number of fine-grained changes required for training in both the combined and intradev cases is low: with 200 changes we can obtain prediction results only 2% worse (in terms of acc) on average than if we train with 800 changes. As 200 fine-grained changes are the equivalent of a few days of work, 5 we have encouraging evidence that an accurate model can be trained fast and deliver good results for a single developer. Moreover, a pre-trained model with data from multiple developers might be enough as a starting point for an untangling tool, which could then be trained to a particular developer's working habits.

Overall, the results show that using the random forest algorithm, a randomized set of about 200 fine grained changes and a few easy-to-calculate voters, we can train a prediction model that can identify whether two changes belong in the same commit with an accuracy of 95% for a single developer.

C. How Effective Is EpiceaUntangler for Developers?

We answer research question three by deploying EpiceaUntangler with developers and recording whether the clustering that it proposes corresponds to participants' expectations. The dataset devEval, resulting from this evaluation is described in Table V. We notice that not all the developers coded full time during the two weeks, thus some produced fewer changes. We compared each cluster we proposed to the cluster that the participant eventually judged as correct to be committed. The histogram in Figure 7 the frequency of the obtained results: We observed a median 6 success rate of 0.915 and an average of 0.753 with a standard deviation of 0.30. By inspecting the instances with a success rate in the range [0,0.4] we could not pinpoint any systematic error; we plan to further address these cases in future work.

We asked developers their opinion on the tool and received diverse feedback. Most developers were positive [P3, P4, P6, P8], e.g., P3 expressed the feeling that "EpiceaUntangler guesses correctly the clusters of changes, also in a big commit were I had 10 different clusters," and P4 said: "It works good in many cases, especially for not so big change sets." At the same time, most developers [P4, P5, P6, P8] expressed concerns with the large amount of fine-grained information to be processed; they explained that it adds too much noise to see not only the last state of a method but also all the intermediate modifications 5 From the data we recorded, 200 fine-grained code changes correspond to two to five days of work, depending on the developer's style and pace. 6 The results are not normally distributed, thus we report the median value. to it, especially when belonging to the same cluster. In the words of P8: "It was a bit painful to check everything."

Some participants suggested improvements to the user interface: For example, P7 said that he "would like to option to delete tasks in the UI", and P6 said: "I would like to type a name for each task in the UI, as a reminder while I cluster."

VI. DISCUSSION

In this section we discuss our results and show how we mitigate the threats that endanger them.

A. Results

In the first research question, we asked which voters, or features are significant to untangle fine-grained code changes. Despite the fact that we implemented voters along six dimensions, only two dimensions were significant and contributed to most of the outcome: code structure and spread. In particular, the latter dimension has the greatest impact, by a large margin; the only significant voter in the former dimension measured whether the two changes were happening in the same class. This implies that these voters can be applied to other objectoriented programming languages regardless of whether they use types or not. This is a ripe opportunity for testing the approach with different languages and in different settings. Moreover, although we have no information about the significance of the voters implemented by Herzig et al. [START_REF] Herzig | Untangling changes[END_REF], [START_REF]The impact of tangled code changes[END_REF], studies can be designed and carried out to determine if and how untangling effectiveness increases as a result of combining their voters with our significant ones.

We were surprised by the low impact of many of the voters in the untangling task: We expected message sending and variable access, as well as testing information, to contribute more. Since our initial data analysis was conducted with changes collected by only two developers, a further study with a larger set of developers for generating training data would be useful to confirm or alter this result.

In the second research question, we asked how effective is the best performing machine learning algorithm (i.e., random forests) when used with the most significant voters. The results were overall very good. Expectedly, we achieved the best results when training and testing on data from the same developer, nevertheless cross-developers results are promising and merged-developers results do not show overfitting; in addition, approximately 200 fine-grained code changes were enough to reach most of the effectiveness. This implies that training on more developers is necessary to achieve a more general approach, and there seem to be no risk of overfitting by doing it. Moreover, ideally every user should train the approach on her own programming behavior; this seems reasonable since the training is effective with as little as a few days of work.

In the third research question, we investigate the effectiveness of the whole approach when deployed to programmers. Considering that the recruited participants were not used for the training phase, the results are in line with the effectiveness measured for RQ2. One of the most recurring complaints was about the large number of changes to be verified and sorted at every commit. This is due to the fact that we showed all the fine-grained changes recorded, thus also intermediate states for the same method (when the developer saved multiple times). We expect this information overload problem to be mitigated once the approach is stable enough to work correctly in most cases. Nevertheless, we see a good opportunity for further investigating how certain fine-grained code changes can be omitted, without losing relevant information that would lead to the incompleteness discussed in Section II-A. Moreover, valuable comments were provided about the UI of EpiceaUntangler. The UI evaluation goes beyond the scope of this paper, but improving the UI can help to have an impact on reducing the information overload of fine-grained code changes.

B. Threats to Validity

Internal Validity. Our models and feature selection process are based on a dataset generated through the actions of two developers. While we have combined the actions of the developers and shown that they provide very good prediction performance and the evaluation of the EpiceaUntangler has been overwhelmingly positive, it is possible that our findings are biased towards the two developers' working habits.

Bias with respect to developer working habits might also occur in our selection of evaluation subjects. To reduce this risk, we selected diverse developers, all of them working in different projects and even in different physical locations. Thus, we believe the participants represent a heterogeneous enough population of Pharo developers.

Construct Validity. The notion of task is ambiguous. In particular, each participant can interpret the task granularity differently. For example, consider a single bug fix which is intended to fix two broken features. The participant could consider the changes either as two individual tasks, or everything as a single bugfixing task. For mitigating this risk, we prepared a screencast with an example for users trying to establish a common criterion for task granularity. Moreover, we kept in close contact with users for answering any doubt. However, this ambiguity in the definition of task does not reduce the precision of our success metric for answering RQ3 (SuccessRate), since it represents each user expectation: it compares EpiceaUntangler's clustering with the participant's expected clustering.

The clustering computed by EpiceaUntangler may have influenced participants. When users had to evaluate the computed clustering (as shown in Figure 2), the initial clustering might have biased their answers.

External Validity. We used a specific platform (Pharo) and language environment (Smalltalk) to facilitate our study. A specific language may dictate a specific working style. For example, in a typed language setting, an IDE would immediately mark as erroneous cases where a type signature has changed and not all uses have been adapted, therefore prompting the developer to fix such cases. Therefore our results may not be generalizable to all languages or working environments.

VII. RELATED WORKS

The impact of tangled changes has been reported in several contexts: The inspiring work by Herzig et al. [START_REF]The impact of tangled code changes[END_REF], reported that at least 16.5% of all source files in the datasets they considered were incorrectly associated with bug reports when ignoring the existence of tangled change sets. In a large-scale study done at Microsoft on how developers understand code changes, Tao et al. reported that developers find it important for understanding to decompose changes into the individual development issues, but there is currently no tool support for doing so [START_REF] Tao | How do software engineers understand code changes?: An exploratory study in industry[END_REF]. Bacchelli and Bird reported that tangled changes in code to be reviewed often cause low quality reviews or require longer time to review [START_REF] Bacchelli | Expectations, outcomes, and challenges of modern code review[END_REF].

Herzig et al. were the first to implement an algorithm to automatically generate untangled commits given a tangled one. Their work greatly inspired our research. However, we see some limitations to their work that we explained in Section II: static-analysis dependency, incompleteness, and artificiality. The main differences with our work is that: (1) we count with fine-grained timing information of code changes as well as IDE events like test runs; [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF] we work in a dynamically-typed language; (3) we evaluated our approach with developers.

Another source of inspiration comes from Robbes, who created a fine-grained change model of software evolution based on three principles [START_REF] Robbes | Of change and software[END_REF]: (1) a program state needs to be represented accurately by an Abstract Syntax Tree (AST); (2) a program's history is a sequence of changes, each one producing a program state (an AST) and changes can be composed into higher-level changes; (3) changes should be recorded by the IDE as they happen, not recovered from a VCS. Robbes et al. show how a fine-grained change model can better detect logical coupling between classes [START_REF] Robbes | Logical coupling based on finegrained change information[END_REF]. Their article presents new measures of logical coupling that we consider as a future extension of our voters.

Steinert et al. propose CoExist, an approach and associated tool set to navigate the different states of a project based on its fine-grained changes [START_REF] Steinert | CoExist: Overcoming aversion to change[END_REF]. CoExist's tool suite allows for reverting any fined-grained change at the project level, comparing different states of a program, localizing the cause of a failing test in the development history, and reassembling changes to share untangled commits. Automatic clustering of dependent fine-grained changes to create untangled commits is left as future work. Our work can be seen as an extension of CoExist tool suite in this direction, despite its totally unrelated implementation.

Wloka et al. presented a program analysis technique to identify committable changes that can be released early, without causing failures of existing tests [START_REF] Wloka | Safe-commit analysis to facilitate team software development[END_REF]. Wloka remarks that an untangling algorithm would clearly benefit from having a model with a more accurate concept of change to add context information for individual change operations. Beyond our 'Same Test Run' voter, we leverage more the results of unit-test execution to cluster related changes.

VIII. CONCLUSION

In this paper, we have devised and evaluated EpiceaUntangler, an approach whose ultimate goal is to help developers share self-contained changes that are well-decomposed into individual tasks. We build on the shoulders of others, and expand previous work by: [START_REF] Guzzi | Supporting developers' coordination in the ide[END_REF] Working in an untyped language setting where static code analyses are more limited;

(2) considering fine-grained code change information gathered during development; and (3) evaluating the resulting approach both on data generated by programmers who manually labeled it and with programmers working on real development tasks.

Our results show that three features are especially important to perform clustering of fine-grained code changes: the time between the changes, the number of other modifications between the changes, and whether the changes modify the same class. By testing the features on historical data manually labeled by developers, we obtained good results (over 88% of accuracy in the worst case) in determining whether two changes should be together. When deploying our approach with new developers, we obtained a median success rate of 91%. Overall, this paper makes the following main contributions:

1) An analysis of the current points for improvement in the state of the art in untangling code changes. 2) A publicly available 7 dataset of fine-grained code changes collected by recording the development sessions of two developers over the course of four months, and the corresponding manual clustering.

3) The creation of different features/voters and their evaluation, based on the aforementioned dataset, using machine learning approaches to model and classify pairs of finegrained code changes, resulting in good accuracy results. 4) The creation of an approach, EpiceaUntangler, and corresponding tool implementation, Epicea Task Clusterer, 8 to untangle fine-grained code changes into clusters based on the three best voters and the best performing machine learning algorithm. 5) The deployment and a two-week evaluation of EpiceaUntangler with developers with good results.

  -r1252 | elharo | 2006-11-09 [...] | 2 lines Pulling getOperator up into BinaryExpr per Jaxen-169 [...] Index: src/java/main/org/jaxen/expr/AdditiveExpr.java ===================================================== ---src/[...]/AdditiveExpr.java (revision 1251) +++ src/[...]/AdditiveExpr.java

Fig. 1 .

 1 Fig. 1. IDE events recorded by Epicea; dashed ones are not considered.

Fig. 2 .

 2 Fig. 2. UI used in training stage. The user manually clusters the changes.

Fig. 3 .

 3 Fig. 3. Determining the similarity threshold to cut the dendrogram.

Fig. 7 .

 7 Fig. 7. Frequency of success rate of EpiceaUntangler clustering approach

  • 'PackageDistance': the number of different package name segments within the package names of the changed files; Dependence on static-analysis: The voters 'CallGraph' and 'DataDependency' rely on static analyses that might not be possible for dynamically-typed programming languages, or that might be available in a weaker form; Incompleteness: The tangled commits used as input to the algorithm suffer from the incompleteness problem described earlier in this section: If a line is changed twice before a commit, the commit only contains the latest version of the line, shadowing a previous version of the line which could have been part of an untangled commit; Artificiality: The validation by Herzig et al. relies on a classification of 7,000 existing commits done by the researchers without feedback from each project's experts. We believe that only the author of each commit can, at commit time, best organize his changes into untangled commits. Moreover, the untangling algorithm by Herzig et al. relies on the knowledge of the expected number of untangled commits for a particular tangled one. With the goal of helping developers creating untangled commits, we do not have access to this information.

• 'CallGraph': the difference between the call graphs of the program with each line change applied separately; • 'ChangeCouplings': the frequency with which the files both lines were changed into are committed together, using the work from Zimmermann et al. [2]; • 'DataDependency': a boolean indicating if the two lines read or write the same variable(s). In the work by Herzig et al. we see the following limitations:

TABLE I .

 I DIFFERENT VOTERS TESTED IN OUR INVESTIGATION. cosmetic (i.e., pretty-printing-both versions of the method return the same result).

	Voter Name	Dimension	Type	Relation between the two considered changes
	samePackage bothCosmeticChanges They are both sameTestRun Content Boolean Testing Boolean They are modified between the same unit-test runs.
	numberOfEntriesDistance	Spread	Numeric	How close they are in the history; the voter computes number of other changes between them.
	timeDifference	Spread	Numeric	How close in time they are in the history; the voter computes the seconds between them.
	reciprocalMessageSends	Message sending	Nominal	They invoke each other; it computes 0, 1 or 2 if, respectively, no, one, or both call the other.
	numberOfSharedMessageSends	Message sending	Numeric	They share a number of the same message sends.
	numberOfSharedMessageSendsInDelta	Message sending	Numeric	They add or remove a number of the same message sends.
	numberOfVariableAccesses	Variable accessing	Numeric	One change modifies or adds definitions of instance variables, the other accesses some of them.
	numberOfSharedVariableAccesses	Variable accessing	Numeric	They access a number of the same instance variable names.
	numberOfSharedVariableAccessesInDelta	Variable accessing	Numeric	They start or stop accessing a number of the same variable names.

TABLE II

 II

		.	PARTICIPANTS' INFORMATION
	P_ID	current role		programming experience (in months) overall industrial with Pharo
		Data generation and collection phase
	P1	Ph.D. student		168	60	48
	P2	Ph.D. student		48	36	24
		Evaluation in real-world development phase
	P3	Ph.D. student		180	18	36
	P4	software engineer	132	72	13
	P5	associate professor	72	12	24
	P6	Ph.D. student		72	11	11
	P7	software engineer	180	10	30
	P8	software engineer	60	18	36

4

Available at: https://www.youtube.com/watch?v=fQVWuMQUBew

  . TableIIIdescribes the resulting dataset (2devs).

TABLE III

 III

		.	DESCRIPTIVE STATISTICS OF DATASET 2DEVS
	P_ID	Total number of changes clusters	Mean	Changes per cluster Median St. Dev.	Max
	P1	15,175	298	50.9	8	153.1	1,582
	P2	9,601	119	80.7	16	151.9	812

TABLE IV .

 IV CLASSIFICATION PERFORMANCE ON 2DEVS BY APPROACH

	Classifier	AUC	ACC	PREC	REC	F.MEASURE	G.MEAN
	'binlogreg'	0.92	0.68	0.43	0.96	0.60	0.76
	'naivebayes'	0.88	0.65	0.41	0.94	0.57	0.73
	'ranforest'	0.99	0.96	0.96	0.88	0.92	0.93
	'ranforest-trimmed'	0.98	0.95	0.96	0.82	0.88	0.90

TABLE V

 V

		.	DESCRIPTIVE STATISTICS OF DATASET DEVEVAL
	P_ID	Total number of changes clusters	Mean	Changes per cluster Median St. Dev.	Max
	P3		350	22	15.9	11	13.5	42
	P4		826	28	29.5	3.5	50.9	228
	P5		200	13	15.4	10	17.3	65
	P6		166	12	13.8	6.5	15.6	47
	P7		347	18	19.3	7	27.8	88
	P8		162	11	14.7	10	12.7	37

Pharo: http://pharo.org/

Squeak: http://www.squeak.org/

ACKNOWLEDGEMENTS

We thank our study participants for their feedback and the European Smalltalk User Group 9 for its support.

Code structure Boolean They involve the same package. sameClass Code structure Boolean They involve the same class. sameSelector Code structure Boolean They involte a method with the same name (regardless its class).