Florjan Bombaj
email: florjan.bombaj@supagro.inra.fr

Dr Dominique Barjolle
email: barjolle@ethz.ch

Jean-Marc Touzard
email: touzard@supagro.inra.fr

Myslym Osmani
email: mosmani@ubt.edu.

Farming system and market integration in southern Albania. Between territorial resource management issues and informal value chain challenges

Introduction

After 46 years of planned economy the Albanian agriculture has changed dramatically since 1991. Before the transition, there were 550 large state farms and cooperatives while nowadays we have 352 315 farm households (MAFCP, 2014) with an average of 1, 16 ha divided into 4.8 parcels. The agrarian reforms towards the market economy have forced farmers to change their farming system production. Major changes in agricultural sector have occurred with a significant increase in livestock production which provides about 57% of total production in the sector, followed by the arable crops with 26% and fruit production with 17% (MAFCP, 2014). Current production systems have evolved largely adjusted to the new situation with very small and fragmented farms that have to deal with other major constraints such as poor physical infrastructure, lack of state support and a non-competitive market situation. This paper presents some recent dynamics of local agricultural development in a disadvantaged mountain territory and the commercialization issues on urban markets for the products originating from this territory. The analysis is based on three stages: (1) analysis on the national and local farming system development dynamics including the local collective actions initiatives; (2) national and local value chain analysis and commercialization issues;

(3) current dynamics and issues on local resource management.

National context

The dairy industry takes an important place in the Albanian agri-food sector (MAFCP, 2014). Since 1991 the total number of cattle and goats declined until the 2010 in the meanwhile the population of sheep increased considerably. In the period 2010 -2012 a slight increase in the total number of sheep and goats is observed. This increase is more accentuated during the period 2012-2014 when the sheep / goats are experiencing a 22% increase compared to 2012. Pastoral resources, including pastures, forests and agricultural land are fundamental to farming but have degraded significantly over the past 20 years, especially in land near communities where overgrazing and excessive cutting wood led to lower productivity and soil erosion [START_REF] Shundi | Country pasture/forage resource profiles[END_REF]. The largest farms are better managed but they still the need to buy part of the feed market since the majority of the farms are often too small to produce enough.

Source: MAFPC, 2014, author's calculation

An important part of the cow's milk is used especially for the manufacture of white cheese. Sheep's milk and goat's milk is also used to produce white cheese, but in smaller quantities and often the separation of white cheese from sheep's and goat's milk is not well defined. In 2014 only 51% of the total milk produced was sold to the wholesale market which is equivalent of 530. The total goat population is dominated by dairy goats that make 76% of the herd. In 2014 the livestock products have a slight increase compared to 2013. In the annual production of milk in 2014 we observe an increase of 0.1%, and the production of meat live weight increased 1.3%.

The national characteristics of the milk value chain

The industry of milk processing grew in the early 1990s and now has over than 400 processors, with several fully equipped dairies. According to official statistics, national milk production reached 1.1 Million tons in 2012, an increase of 3.2% since 2010. In 2012 about half of the milk production has reached the market (561 000 tons) while the other half is used for consumption, consumption by animals or processed on the farm. Of all milk produced, only 12% (132 000 tons) is converted by the dairy industry. The remaining 39% (429,000 tons) reached consumers directly. Albania currently imports 7-10% of consumed dairy products (MAAPC, 2012). According to official and unofficial data in 2012 we have estimated 60,000 tons of transformed milk (pasteurized or UHT), 14,000 tons of yogurt;

13,000 tons of cheese and 630 tons of butter. These products arrive in consumers either directly by small processors or processors via distribution channels and other stores.

Milk production and collection system (mainly cow's milk) is characterized by the existence of the informal market (sales by farmers) and formal channels to market (milk collection and distribution by dairies). Milk production in Albania still suffers from problems of product quality milk. A very large part of the milk is consumed directly and untreated and / or controlled. Because of the low purchasing power and part of the tradition, consumers prefer to buy the cheap milk directly from farmers. Milk that is directly sold by the farmer is packed mainly in used plastic bottles (often 1.5 liter bottles etc.). The milk production and collection system is not very well organized. Although raw milk is of high quality (pasture, flora and rich fauna) dairies are not able to receive it. This results due to various reasons. First the large number of small farms and especially the combination animal farms with production (crops and livestock) produce only small amounts of milk and they do not care too much about the quality. Second, education and awareness of farmers to produce milk with high hygienic conditions are not satisfactory. Small quantities of milk produced by them are not an incentive to put more efforts and investments to ensure quality of raw milk. Most of the raw milk is not refrigerated immediately after milking, and it comes directly from the farmer to the consumer, milk collectors, and milk plants or on the market. The contracts between farmers and collectors do not exist and the transactions are based on trust and longevity of the relationship between actors. For large dairies, milk collection points while a significant cost for small rural producers and direct sellers this is an advantage. The milk of sheep and goats is mainly in areas of hills and mountains where infrastructure is underdeveloped. Milk production of sheep and goats is very seasonal.

The national characteristics of the meat value chain

Meat consumption in Albania is already 43.4 kilograms per capita, but still far from EU levels that are more than twice as high. In the value chain of meat, in addition to farms, there are also slaughtering and processing enterprises. With the exception of a few modern facilities of chicken slaughter, there are some operational modern slaughterhouses in the country. The average size of the sheep flock in country has 38 heads; the number is 36 for the goat herd. Throughout the country the small size of herds between 5 and 50 heads are still very often, since most are bred for consumption. sheep and goats are transhumance marketed are maintained as long as there are sufficient opportunities for grazing, some alpine herders have built very simple barns to house animals in the winter period, small ruminants are in better conditions, but nevertheless in simple farm barns. Small ruminant's subsistence farms are often kept on the farm. The small ruminant production is done in several ways (Cili et al, 2013): a) extensive system with the transhumance 6 to 8 months (all regions); b) the semiintensive system to transhumance 5 to 6 months; c) grazing system on permanent pasture near the farm; d) natural pasture within walking distance, with the return of sheep or goats in the evening on the farm.

The Albanian mountainous areas are well known for their typical Mediterranean pastures which explain the predominance of small ruminants in these areas (Çili et al, 2013). As the farm size is very small and the mountainous areas are rich in typical Mediterranean pastures, breeding cattle, sheep and goats is one of the main economic sources for these territories.

Long economic transition and demographic desertification [START_REF] Lerin | Mobilités spatiales et développement en Albanie : enseignement de la transition post-communiste et enjeux d'avenir. 17 p. 4[END_REF] creates nowadays a binding context to trigger local economic development dynamics.

Research context and questions

According to [START_REF] Manoli | Comment caractériser les relations entre élevage et territoire? Une revue de la diversité des approches existant dans la littérature[END_REF] there is essential to understand the diversity of production systems in a given territory. A farming system deals with two important issues: a) natural resource management; b) market integration perspectives. While in the mountains areas the livestock production is dominant the analysis in terms of natural resource management and market integration is crucial. In these areas important is very important to characterize the breeding practices related to the use of natural resources while understanding the logic and constraints of farmers regarding the production and market's issues. Albanian mountains areas have Mediterranean pastures and particularly Vithkuq [START_REF] Bombaj | Family farming in the Albanian mountainous areas. Local agro pastoral production systems and market integration perspectives[END_REF][START_REF] Çili | Studimi tekniko-ekonomik i fermave blegtorale te bagetive te imeta ne qarqet Korçe, Shkoder, Diber dhe Kukes dhe propozime politikeberje per zhvillim te qendrueshem te tyre[END_REF] is a mountain area with a strong past and present pastoral activity. Livestock farming, as tradition and know-how, remains an important economic source of income for the rural population in this territory. Since 2005 a reduction of the population of 56% occurred, while the herd size has increased 4%. The milk production has decreased by 9% while the meat production has increased by 55%. The management of the mountain pastures and the resource use access affects the farming systems of the local breeders.

Related to this situation the paper is based in the main hypotheses that: the small farmers increase their income and start developing their farm mainly when they reach the markets. In this context this paper tends to respond to the following research question: a) what is the evolution of the family farming model regarding the market integration perspectives of the local livestock production and the local resource management issues in the considered territory after the fall of communism in 1991? Based on fieldwork in the Vithkuq municipality, the paper answer to the research questions not only analyzing the evolution of the family farming model after the fall of communism in 1991 but also identifying market integration and local resource management issues analyzing the milk and meat value chain of the considered territory.

Material and methods

Given the broad extent of the area and the difficulty of access to some very remote villages, we choose a limited number of them. The villages correspond to those who use the mountain pastures of the territory and sell their milk into one of three dairies in the territory. The dairies were identified in the exploratory phase of our fieldwork and they had a high geographical spatial dispersion. This facilitated the identification of the villages by the dairy where the villages sell the milk. Combining statistical and interviews with the local actors and specialists, the selection of villages was done according to the number of families in each village, herd size, proximity and ties with the identified dairies. An important factor was also the significance of traditions and sources available on the history of the village, and the official written sources on the evolution of the population and livestock production. We chose to conduct the interviews by respecting a balance between specialized farmers, intermediate farmers and subsistence farmers according to the importance of their pastoral resources use. We chose to use two kinds of surveys influenced by the daily job program of the local breeders, but also by the local customs and tradition. Surveys called "formal" with farmers were interviews made by appointment in their home or in a public place of the village. This kind of survey helped us to get a maximum of socio-economic data and observe the technical herd conditions. Surveys called "informal" correspond to more spontaneous interviews with breeders met under spontaneous conditions in the field or in the pastures. Stage 2. National and local value chain analysis and commercialization issues. As already mentioned above at the national level we used several documents, including reports, papers and other scientific data. At the local level the value chain analyses was done according to the data collected during our survey. Several interviews were conducted before and during the choice of land. The observations were based on the course of herds and shepherds, the conditions of the farms, the wholesale market in the nearest region of the chosen territory (Korça region) milk processing, transportation of milk and sold animals. These observations were combined with interviews on site or spontaneous defined in advance with the stakeholders.

Stage 3. Current dynamics and issues on local resource management. This step was done analyzing the data collected and doing some meetings with the local actors and institutions concerned by these issues during the field survey.

Results and discussion

Our study area (Vithkuq) is a disadvantaged mountain territory located in the Korça region, which is one of the most developed regions in southeastern Albania. The area has a strong potential of pastoral products (meat and milk) from their special qualities and / or their reputation as products of "Origin Vithkuq". Also this territory has diversified natural resources and promoting a good quality of the multi-potential activity -with a strong importance of pastoral resources. During century this territory was of center of the Vlach minorities, recognized by the farmers of the Municipality for their pastoral tradition recognized. The small ruminants in this region represent 15% of the total small ruminants of the country. In the last five years the local and national market demand for pastoral products, especially those of small ruminants, experienced a strong increase (INSTAT 2014). During this period the region has experienced a 39% increase in the number of cattle heads (43% for sheep and 26% for goats, (Çili et al, 2013). Vithkuq is a mountainous territory whose population decreased by 56% the last ten years. This desertification of the population has been accompanied by a sharp increase in the herd size and new dynamics in the local production.

The dairy products originating from this territory are well known in the regional market and abroad. The dynamics on these markets has caused an increase of the production and new issues on the use of the territorial resources which are considered as crucial for a sustainable development of the dairy value chain products which is mostly informal.

Source: Elaboration on GIS by Florjan Bombaj

Currently the Vithkuq municipality has 13 villages with a total population of 1660 habitants.

The number of cattle heads has increased since 2000. We took two periods analysis to analyze the data. The two years of analysis are 2005 and 2015. Referring to the evolution of the population we can see a reduction of 56% while the increasing of the herd size for the same period is at a rate of 4%. In the municipality of Vithkuq with nearly 11 500 dairy sheep on 18 549 ruminants, the dominant farming system is based on sheep farming. According to our surveys we can state that the local farming system is constituted by three different types of farms: a) small subsistence farms; b) intermediate farms producing market's surpluses; c) specialized farms, whose production is mainly marketed. The local farming systems co-exist on the municipality's territory with farmers from other regions (transhumant). We identified (Bombaj et al, 2016) 6 self-consumption farms; 12 intermediate farms and 21 specialized farms. The livestock system is based on sheep farming. The self-consumption farm is characterized by the self-consumption and with very occasional or no sale. This type of farm has 1-10 sheep/goats and / or 1-4 bovine animals. They don't have young labor force and don't do transhumance. The intermediate farm is characterized by the self-consumption plus some sale and often has multiple activities. This type of farm has 11-99 sheep / goats and / or 5-9 bovine animals. They don't do transhumance but they tend to expand their activity if they have a young labor force. The specialized farm is a specialized livestock farm and they sale the majority of production. This type of farm has more than 100 sheep / goats or more than 10 bovine animals. They do transhumance and tend to expand their activity. The specialized farms tend to increase every year in the territory. [START_REF] Matka | Annual census of the livestock production in the municipality of Vithkuq[END_REF] In 2015 the total milk production has decreased by 9% compared with 2005 while the meat production has increased by 55%. A trend on meat production is observed because the milk has a low price and does not always cover the productions costs.

The milk and meat value chain

In the exploratory phase of our work three dairies were identified and they had a high geographical spatial dispersion. This facilitated the identification of the villages by the dairy where the villages sell the milk. We identified every dairy as a pole. According to [START_REF] Bombaj | Family farming in the Albanian mountainous areas. Local agro pastoral production systems and market integration perspectives[END_REF] the three poles correspond to the identified villages where the three dairies are present in the Municipality, centralizing the majority of sold milk, almost exclusively in processed form. These identified villages correspond also to the most populated ones and the geographical position gives them a "spatial economic influence". There are only two villages that have more proximity with the villages of the neighboring municipality. Source: Author's observations

The most important and technologically well-equipped is the dairy of Vithkuq. Its current processing capacity is 23 quintals of milk per day. In 2014 this dairy produced 150 quintals of white cheese and 20 quintals of cooked cheese called "Kaçkavall" in the local terminology. He covers the transport costs of the milk collecting the milk with his own truck every morning to the villages where he buys the milk. The cheese produced in this dairy is sold directly by his shop in the Korça district. The two other dairies sell the cheese to the capital, in Tirana.

They have stable commercial relations with shops in the capital. The most isolated dairy is in the pole Panarit which is specialized in the production of cheese called "Kaçkavall" and in 2014 the total quantity of cheese produced was 72 quintals. The transport is in charge of the breeders and the milk price is, according to the breeders, very low. They don't have other choices where to sell their milk and in case where no one buys their milk most of them will face a huge loss of money. They have in fact a very few remote appropriated alternatives to this type of organization. Contracts between farmers and dairy owners do not exist. The value chain governance is mostly informal and based on long-term relationship. If a conflict can occur for the milk quality farmers in some cases are subject of collective penalties from the dairy owners.

The meat value chain is totally informal and the sales in live weight of the Calves, Lambs and Goats are in the majority of cases done with social network and family members. (Çili et al, 2013); [START_REF] Matka | Annual census of the livestock production in the municipality of Vithkuq[END_REF]) and author's calculation We tried to understand the logic and strategy of farmers for the products they sell to the market. Some breeders have dual orientation milk / meat. There are three ways in which they sell lambs / calves / goats. First: they go themselves to the wholesale market in Korça. This method is expensive for the majority of farmers who do not have transportation means. They are forced to gather in groups and pay a conveyance. Such is the case of Panarit and Lubonje. Second: Via the wholesale traders in the region, the horse dealers. This way of selling animals is common. The coordination is done by phone and the merchant comes in person to purchase the animals on site. The sale is on live weight price. The price is 2.3 Euros / kg LW for goats; 2.15 Euros / kg LW for lambs and 2.86 Euros / kg LW for calves. Third: Via merchants details of Tirana. There are sometimes large old-traders living in the area who buy animals in the area and who sell to the wholesale market in Tirana. The first two ways cover 80% of total sales of animals in the area. The value chain is totally informal and transactions are on spot without a contract and/or without invoice. No traces of a legal transaction but just a transaction based on trust. The average live weight of lambs at slaughter is in many cases too low but often farmers sell the lambs before the religious holidays with prices that are good at this time and others want to focus more on milk and try to sell the lamb as soon as possible by neglecting the opportunity to feed it with other products that sheep milk. Tableau 6. SWOT analysis for the milk and meat value chain

Collective action initiatives

With the strong institutional support of the regional department of agriculture of Korca, in the period 1997-2000, was founded the first association of breeders in the area (e Shoqate Fermereve you Mbareshtrimit you Lopeve -Cows Breeders Association, as french model UPRA) in 3 of the 13 villages covering the Vithkuq Municipality (Vithkuq, Leshnje, Shtylle) with 32 members. The purpose of this association was to create a race Tarentaise development initiative in the area. In 1999, a dairy cooperative was created in the village of Leshnje with 12 members. The cooperative has been active for only 4 years with a strong local activity which influenced the level of income of those members. The cooperative has created its own dairy and was about to also create their own logo. After 4 years of activity, the cooperative has experienced a lack of stability since 2003 and it ceased activity. Both local initiatives of farmers in the area have been strongly supported by the regional department of agriculture of Korça and the various French and Dutch associations operating in the area at the time.

In the area there are three farmer associations aiming a better organization in matter of livestock production and common natural resource management. Even if some results can be seen in the field, the challenge of the future is to improve the rural infrastructure especially for some remote villages and more support for the livestock sector. But another issue is the federation of the three associations in one structure that may take the institutional form of a cooperative.

4.3.The territorial resource management issues

After the fall of communism the agrarian reform has led to the deconstruction of the old economic regime, which was characterized by centralized productive resource management.

The re-distribution of the communal pastures was done according to the historical organization of the cooperatives, which did manage the communal pastures where they were located. In our study area, farmers who do not perform transhumance made use of the communal pastures (625 ha) from March to November. These farmers are essentially small breeders who are organized in a collective way to manage their herds. The two main pastoral resources of the pastoral space of Vithkuq municipality are the pastures 5,350 ha and forests 8,010 ha. Summer pastures are considered as a key factor for the local farming system. The access to these pastures is one major factor that influences the farming systems of the local breeders. During our surveys [START_REF] Bombaj | Family farming in the Albanian mountainous areas. Local agro pastoral production systems and market integration perspectives[END_REF] we have identified three types of pastoral resource management:

State pastures: this property applies to grazing land belonging to the state. These are managed by the Departments of Forests and Pastures which decides the price and distributes them to farmers. These pastures are expected to be distributed in priority to the local herd. In this type of property is found mainly altitude summer pastures located far from villages.

Private pastures: this property applies to grazing land claimed by the individual owners, according to family property rights dating from before the communist period. There is not necessarily a clear and official status on these types of property. In them we find all kinds of summer pastures, but often quite distant from the villages and both local breeders and breeders from other regions pay for the use rights.

Property of the village: in reality it is communal pastures but whose use is largely managed by the villagers, who consider themselves the legitimate users of a resource being on the territory of their village. We observed this type of ownership of the overall use is not a source of conflict.

The summer pastures are owned by the state or private actors, and farmers need to pay for the use rights. The very last year's some new local breeders willing to expand their herds are in competition with transhumants coming from other of Albania. These transhumants have more than 15 years using the state summer pastures. Only the last years some conflicts are observed for the resource use rights because the herds of the territory are growing and they need this resource. This can cause some conflicts with the local breeders because the boundaries are not always clear.

Within the new territorial reform in 2016 the status of pastures will change in the future. The communal and state pastures (which are pastures managed directly from the state and not by the commune) will become "public pastures" managed by local authorities situated in the next main city of the district. The municipality will lose the management of the communal pastures and there will be no more common pasture management. The pasture management decision will be centralized at the regional level. All breeders will have to ask explicitly for grazing land in order to bring their herds, and to pay for the pastures use. Public pastures will be allocated in priority to local farmers. If the local breeders who need this resource will not be able to pay for it, the region will open access to farmers coming from elsewhere.

Conclusion

The dynamics observed in the near and more distant urban markets enabled the growth of the local milk and meat production. But it's interesting to note that the increase of the herd size in the territory has been more oriented toward the meat production rather than the milk production. While the total milk production has decreased by 9% the last ten years the total meat production has increased by 55%. Some entrepreneurship farming and collective action initiatives are identified in this disadvantaged area aiming a better socio-economic situation. Farmers tend to be more meat oriented producers because the milk has a low price and do not cover the productions costs. The market power according to the farmers is held by the dairies owners who apply low prices for the milk. The increase in the meat production compared to that of milk is that the meat is more paid and requested either in the local market by the restaurants / hotels either by family consumers. The increase of the herd size causes an increased demand for pastures which is a source of conflict for the local farmers that needs this resource during summer. Despite the strong presence of associations of farmers for more than 15 years in this area, the level of collective action and activation of specific territorial resources are still very low. The bargaining power in the milk and meat value chain is asymmetric and the current dynamics of the value chain does not position the products in a niche market capable of engaging a virtuous circle for a good remuneration of the producers and for the reproduction of the natural resources. The main issue is to identify the best option for farmers to better valorize their products respecting the safety food standards while valorizing and respecting the proper use of the territorial resources. In another paper we will explain how the common use of territorial resources affect the productivity and the economic activity of the farmers.

*

  Source: Author's surveys Our method was conducted in three stages: Stage 1. Analysis on the national and local farming system development dynamics including the local collective actions initiatives. At the national level we used several documents, including reports, papers and other scientific data. At the local level we have chosen the Vithkuq Municipality. The choice was done in several steps: a) exploratory phase with literature research and choice of the study area; b) sample characterization. The breeders were selected by age, herd size, specialization (cattle / sheep / goat), but also according to an existing database from the Albanian Ministry of Agriculture; c) fieldwork phase (semistructured interviews with key informants, questionnaires addressed to producers, personal field observations) in two steps. Step 1. Structured interviews, semi-structured and informal observations collected directly from the breeders. Step 2 -Interviews and personal observations on the wholesale and the retail market in Korça and stores in Tirana; d) Results analysis.

Table 1 .

 1 Evolution of Livestock production between 2000 and 2014 (in 000 Heads)

	Livestock	2000 2005 2006 2007 2008 2009 2010 2012 2013 2014
	Cattle	728	655	634	577	541	494	493	498	498	499
	Dairy Cows	448	430	420	396	360	353	395	358		358
	Sheep	1939

1760 1830 1853 1800 1768 1806 1809 1896 2294

	Ewes	1448 1312 1426 1378 1321 1309 1337 1390		1418
	Goats	1104	941	940	876	820	772	775	810	867	904
	Dairy Goats	800	701	700	620	610	574	576	614		694
						Source: MAFPC, 2014, author's calculation

000 Tons Meat Production (Calves, Lambs and Goats (2001-2014)

  Of all farms in Albania 47,039 farms has sheep and 23,445 has goats. The majority of farms that has sheep also have goats. The total number of sheep was almost constant during the period 2010 -2012 (1,806 thousands heads in 2010, 1,809 thousands heads in 2012). Yet in 2014 a 20% increase in the number of sheep is observed since 2012 (respectively 1,896 thousands heads in 2012 and 2,294 thousands heads in 2014) figures for goats is as following: 775 thousands heads in 2010, 820 thousands heads in 2012 and 904 thousands heads in 2014.

			The
	reason for this is that animals are usually slaughtered on the farm or in some cases in local
	primitive slaughtering on farms or in butcher shops. A different picture can be seen in the area
	of processing of meat; there are several companies and larger companies which are very close
	to EU standards. As local meat is limited and expensive, processing companies import nearly
	100% of their raw meat needed mainly Brazil and Canada (INSTAT, Report). According to
	(MAAPC, 2014) there is almost no link between the Albanian farmers and the meat
	processing industry.
		Chart 1. Meat production at national level between 2011 and 2014
		180
		160
		140
		120
		100
		80
	In	60
		40
		20
		0	2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014
	Total		114 118 123 129 133 137 158 141 143 145 147,9 150 153 155
	Calves		62 64 65 66 68 69 83 66 66 68 68,7 69 70 71
	Lambs and Goats 37 38 38 42 41 44 46 43 44 44 45,3 48 49 50
			Source: MAFPC, 2014, author's calculation

Table 1 .

 1 Pastoral dynamics of Vithkuq

				Total Milk	Total meat
		Total Population	Herd Size	Production	production
	Year			(q)	(q)
	2005	2,939	17,920	27,500	1,605
	2014	1,660	18,549	25,200	2,497
	Diff
	in %	-56%	+4%	-9%	+55
		Source: (Çili et al, 2013); (Matka 2015) and author's calculation

Table 3 .

 3 Evolution of the milk production in the Vithkuq municipality

	Milk Production in	2005		2015
	Quintals	Heads	Prod	Heads	Prod
	D. Cows	920	18,400	849	15,228
	Ewes	15,000	7,500	15,900	8,586
	Goats	2,000	1,600	1,800	1,386
	Total	17,920	27 500	18,549	25,200
				Source:

Table 4 .

 4 The three dairies identified as the three poles

		Pole	Pole	Pole
		Vithkuq	Lubonje	Panarit
	Population	805	575	260
	Dairy prod cheese(q)	170	100	72
	Dairy capacity (q/day)	23	10	7

Table 5 .

 5 Evolution of the animal market in the Vithkuq municipality 2005 2011

			Prod		Prod
		Heads	(q)	Heads	(q)
	Calves	500	300	800	560
	Lambs	12,000	1,200	12,000	1,200
	Goats	1,500	105	1,600	128
	Total	14,000	1,605	14,400	1,888
		Source:

Milk and Meat Value Chain in the Vithkuq Municipality (2015), Albania

			Pastures	Pastures 5350 Ha	Winter Pastures
				Breeding		Meat Value Chain
			Control and animal welfare	18 970 heads	Meat Lambs/Calves/Goats	Self-consumption
	Farm			Milk produced at the Farm Level
	Level			25 200,2 (q)		Sales in local wholesalers	Korça Sales to the wholesale market
			Milk self-consumption	Farm processing Cheese and other dairy products
						Slaughter and sale
						Slaughterhouse	Private
			Animal consumtion	Family consumption		Sales to retail stores	Slaughter house
		Description	Strength	Weaknesses	Opportunities	Threats
		Milk					ét
			Private ownership of	Mix farms with	The annual increase of the	Uncertainty over
			farms and	double orientation	milk production	land rights
	Short Semi-circuits	Meat	processing units Very good tradition on milk production / processing Sales to retail stores Korça 32 stores Large sizes of farms with modern stables Sales to retail stores Seasonal consumer / ex resident area	Low productivity of the mix farms The live weight of slaughtered animals is	The increasing demand for dairy products Increase in the number of farms specializing in the production of milk with more than 10 cows, more 100 sheep and goats Consumer preferences for local products Sales to milk processors Weak enforcement of laws regarding the quality Lack of foreign direct investment in the area No export possible because (Baxho) 3 dairy Final consummer	Wholesalers Tirana Export (Greece) Not estimable data Important Dominant
			Tirana	often much too low		of lack of
				resulting in low		enforcement of
				profitability; the		food safety laws
				reasons are the
				demand for very		Public rural
				young animals (of all		infrastructure
				kinds) and the		underdeveloped
				unavailability of
				cheap feed for the
				animals
			Large farms have	In most of the cases	Increase in the number of	Production cost
			tractors and farm	the small farms	farms specializing more in	very high
			equipment for hay	stables are in	the production of meat
				primitive conditions	production	No market
					with more than 10 cows,	information
					more 100 sheep and goats	system in place
				Source: MAFPC, 2014, author's observation


H Dicky
email: dicky@lirmm.fr

C Dony
email: dony@lirmm.fr

M Huchard
email: huchard@lirmm.fr

T Libourel
email: libourel@lirmm.fr

On Automatic Class Insertion with Overloading

Several algorithms Cas92, MS89, Run92, DDHL94a, DDHL95, GMM95] have been proposed to automatically insert a class into an inheritance hierarchy. But actual hierarchies all include overriden and overloaded properties that these algorithms handle either very partially or not at all. Partially handled means handled provided there is a separate given function f able to compare overloaded properties DDHL95, GMM95].

In this paper, we describe a new version of our algorithm (named Ares) which handles automatic class insertion more e ciently using such a function f. Although impossible to fully de ne, this function can be computed for a number of well dened cases of overloading and overriding. We give a classi cation of such cases and describe the computation process for a well-de ned set of nontrivial cases.

The algorithm preserves these important properties: -preservation of the maximal factorization of properties -preservation of the underlying structure (Galois lattice) of the input hierarchy -conservation of relevant classes of the input hierarchy with their properties.

Introduction

This paper deals with automatization of the insertion of a class (de ned by a set of properties) into an existing inheritance hierarchy, we will refer to this as the "class insertion" problem. It also deals with automatic inheritance hierarchy construction or reorganization which is related to the "class insertion" problem. We propose, via a new algorithm, new advances to ll the gap between what current class insertion algorithms are able to do and what automatic handling of actual inheritance hierarchies really requires.

Why automate hierarchy construction? Class or object (Some programming or knowledge representation object-oriented languages are classless DMC92]) inheritance hierarchies are at the heart of object-oriented programs, object knowledge-bases and object data-bases, and they are a cornerstone of frameworks i. e. of adaptable and reusable objectoriented architectures. Any kind of automated help in building, reorganizing or maintaining hierarchies can thus be of interest and can have applications in several important research areas of object technology:

organization of object-oriented frameworks JF88]: automatic reorganization is able to bring to the fore new factorization classes and abstract classes OJ93]. adaptation of legacy systems: numerous object-oriented systems, thus numerous hierarchies, have been developed in the past years, automatic reorganization can help to adapt or reuse them, -by reorganizing poorly designed systems built either by nonspecialists, or too rapidly, or without any concern for generalization, -by reorganizing huge systems built by di erent designers or programmers at di erent time periods,

-by merging hierarchies: the nal hierarchy could be computed by reclassifying classes from the di erent hierarchies. This approach should not be confused with hierarchy combination, as proposed in OH92], where a methodology is proposed to extend existing hierarchies. software adaptability: automatic insertion of a class adds exibility to an object-oriented software system, which becomes for example able to undergo change. Independently of the application area, the more the classes to be structured multiply and become intricate, the more the structuring process can bene t from partial automatization. Given these possible applications, the next question that emerges is: what kind of methods can be provided?

Before going further, it should be stated that it would certainly be impossible to nd a general algorithm that could completely automate, generally speaking, class insertion and/or hierarchy reorganization; rstly, because of the di culty in expressing criteria to de ne a \good" hierarchy independently of the context, and secondly, because the construction rules are often very informal and empirical.

The di erent works describing algorithms for automatic class insertion or hierarchy reorganization that have been published GM93, Cas92, LBSL91, LBSL90, Ber91, MS89, Run92, DDHL94a, DDHL95, Moo95, MC96] focus on the most tangible and one of the most important criteria used when organizing hierarchies: to point out common properties and create classes to store them (i.e. \factor common properties").

Once this criterion is set, there is room for multiple variations: incrementality, maximal factorization, conditions on inputs and outputs of the algorithm, constraints imposed by a particular application domain.

Finally, a common and fundamental characteristic of object-oriented programs, knowledge representation and database hierarchies is that they include properties whose name's are overloaded. So usable and actual class insertion algorithm has to correctly handle overloading. Most existing algo-rithms do not handle this issue and, when done, it is only partial DDHL95, GMM95]. The main issue concerning overloading in our context is to compare properties of the same name using their signatures and codes. Unfortunately, code comparison is undecidable.

This paper describes Ares, explains how we achieve property comparisons in a number of wellde ned cases, and how we use this procedure to e ciently insert classes in the presence of overloading.

In Section 2, we present the terminology used. In Section 3, some commented examples of algorithm inputs-outputs are proposed that highlight its main properties and give an idea on the way overloading is handled. Section 4 compares our approach with related works. Section 5 gives a detailed description of the algorithm that takes overloading into account.

Then a thorough study of how to compare occurrences of generic properties, the key-problem for handling overloading, is presented.

Terminology and context

Before describing examples of class insertion, in the light of the fact that words such as "overloading", "properties", "genericity", "signature" are somehow overloaded in the world of object-oriented languages, let us rst introduce the classical terminology, and terms speci c to our problem.

The algorithm will be applicable, provided it is correctly interfaced, to inheritance hierarchies for various object-oriented systems. Designing an algorithm interface for a particular language may be complicated. In order to describe the algorithm, we have chosen the global context of a standard classbased object-oriented language with inclusion polymorphism, property overloading and overriding.

Classes, inheritance, properties

Classes and types are assimilated, and basic types are interfaced and can be considered as classes. Classes are organized into an inheritance hierarchy H with a root. The subclass relationship induces a partial order, which we denote by > H .

A class is characterized by a set of properties. Class properties can be either instance variables or methods ( Smalltalk terminology). We will refer to variables and methods under the terms property or class property.

All properties have a name and other characteristics such as a signature, and in the case of methods they may have a body or code (a set of instructions).

The signature of an instance variable represents its type. The signature of a method is the ordered list of its parameter types and possibly its return type. Traditionally, the rst element of a signature is the receiver type. In this presentation, the signature does not include this rst element.

For a given class C, Declared(C) denotes the set of properties declared in C, and Inherited(C) is the set of properties declared in C superclasses.

Overloading, overriding and generic properties

Properties can be overloaded, i.e. it is possible to nd properties with the same name and di erent characteristics (signature, code , etc.).

Overriding is a particular case of overloading which makes sense in the presence of inheritance and applies when a rede ned property hides, for a certain object, a property of the same name that is otherwise inherited. The rules of conformance that govern signature rede nition are language dependent 1 . The conformance rule for signature rede nition is one point to be speci ed when the algorithm 1 For example, concerning methods, the rules are di erent in Ei el (multi-covariance, where the type of several or all parameters of a method can be specialized in method redefinitions) and C++ (simple-covariance, only the receiver can be specialized) is to be applied. We present Ares using an Ei el-like covariance policy Mey92] for variable and method rede nitions.

We have to mention the set of all class properties with the same name and same arity (in case of methods ). We call such a set a generic property 2 .

Each property belongs to a generic property, i.e. is an element, or an occurrence of the set of properties having the same name, OGP stands for Occurrence of a Generic Property. P denotes a generic property, and p or p i an occurrence of P, the index is used when necessary, i.e.

when we want to speak, in the same context, about two distinct occurrences of P.

The di erent occurrences of P are ordered by a \specialization" order. For variables, this specialization order can be deduced from the specialization order on their types. For methods, this specialization order can be deduced from a specialization order on the signatures and then on a specialization order on method bodies 3 . A ticklish problem arises when we admit \self-reference" in signatures 4 . We call "lowest common generalizations" and use LCG(p i ; p j ) to denote the set of the most specialized common generalizations of two occurrences of the same generic property. In most cases, LCG(p i ; p j ) is a single element set. In the following, we will assimilate this single element with the set. This simpli cation does not hide di cult problems.

p(C 1 ; C 2 ) : C 3 code] denotes a method with signature (C 1 ,C 2 ,C 3 ), where C 3 is the return type, and code is the method's body.

We also denote: p 0 or p() = 0] for a subclass responsibility or pure virtual method with an empty code. Such a method is automatically the top of the specialization order of P.

2 same name and same meaning than Clos generic functions; note that this notion is rei ed in Clos but is common to all object-oriented languages, for example we can speak of the generic property printOn: in Smalltalk, which is the set of all methods named "printOn:" de ned in the system 3 A method that performs a super call could be considered as a specialization of the method invoked by this call 4 a signature is \self-referent" when it contains the type of the method's receiver

Meaningful classes

The designer may arbitrarily set apart a subset C Mean of meaningful classes. The algorithm will not be allowed to delete these meaningful classes from the hierarchy. Examples of meaningful classes could be: classes with instances (of great importance in a persistent world) or classes which represent an interesting abstract concept.

Maximal factorization

An inheritance hierarchy is maximally factorized if and only if, for any two classes C 3 and C 4 with two properties a 3 and a 4 respectively, and for LCG(a 3 ; a 4 ) = a 2 , the hierarchy always includes a common superclass of C 3 and C 4 that declares a 2 , such that a 2 = LCG(a 3 ; a 4 ) (cf. Figure 1).

Commented examples of inputs-outputs of the algorithm

Before formally describing the algorithm, we will comment on a few examples of class insertions as they are performed by Ares.

Examples without overloading

Here is a sequence of class insertions (cf. The side e ect is that C 6 does not declare any more properties in H 5 .

an empty class is removed. The algorithm could be adjusted by deciding whether to keep or delete an empty class. If a deletion policy is chosen, the result of removing C 6 is H 6 .

Note that maximal factorization is not always compact. Several maximally factorized hierarchies can be built from the same set of classes.

Consider for example (cf. Fig. 3) a hierarchy built from two classes C 1 and C 2 in which properties a and b have to be factorized.

We may obtain the following di erent results. Either a and b are grouped together in the same factorization class C 3 (H 1 ), or a and b are declared in di erent classes C 4 and C 5 (H 2 ) (resp. C 6 and C 7 in H 3 ). All hierarchies are maximally factorized, but H 1 is more compact than the others.

Ares produces compact and maximally factorized hierarchies.

Handling of overloading in an ideal case

In the presence of overloading, we have divided the problem in two parts. The rst problem is to nd the lowest common generalization of two occurrences p 1 and p 2 of the same generic property P. The second problem is how to use this generalization in the algorithm, assuming it is available (either computed or given by a human expert). We present here some examples of how Ares handles the second subproblem.

In Figure 4, C 3 is to be inserted in the hierarchy made of classes C 1 and C 2 ; the order for properties is: a 2 < a 1 < a 0 , b 2 < b 1 < b 0 , LCG(c 1 ; c 2 ) = c 0 , and LCG(d 2 ; d 3 ) = d 1 < d 0 .

Car

()[=0] display()[Code1] display()[Code2] display()[=0] display()[Code1] display()[Code2]
Figure 6: Code gives the LCG Ares determines that C 3 is a subclass of C 1 simply because each property of C 1 is specialized in C 3 . Combining C 2 and C 3 is more complicated, since they are not comparable. For any two occurrences in C 2 and C 3 of a same generic property p, we take the common lowest generalization p m . If p m does not appear in the classes above C 2 (here in C 1 ), we declare p m in the factorization class C 4 .

Examples of class insertion with overloading and automatic determination of LCG

It is generally impossible to automatically compute the lowest common generalization of two OGP, but it is possible in many situations that we have started studying. The detailed results are presented in section 5.3. We give here some concrete examples of overloading where we know how to compute LCG and how Ares exploits it.

Signatures give the LCG

The rst example (cf. Figure 5) comes from Mey92]. The existing hierarchy is made of a single class Car and the class to be inserted is Truck. The two properties to be compared are p 1 = registerDriver(TruckDriver) and p2 = registerDriver(Driver). Given that TruckDriver < Driver, we deduce that p 1 < p 2 regardless of their bodies and that LCG(p1; p2) = p2.

Given this result, Ares knows that p 2 is the method to be stored in the factorization class (which we, not Ares, name V ehicle) made from Car and Truck.

Code gives the LCG In the second example (cf. Using codes and signatures

The last example (cf. Figure 7) is taken from Smalltalk-80 GR83] and adapted to a typed world. The rst issue here is to enrich the language describing our signatures and to recode the signatures of the methods <=; <; = by replacing Date or Time by an anchored type as de ned in Ei el Mey92]. Indeed, the parameter's type of self-referent methods <=; <; = is the type of the method's receiver, thus the possible type of the argument will be determined by the place in the hierarchy where the class will be inserted. In other words, we need to know where the class will be inserted in order to correctly compute LCG and thus to correctly insert it. Thus, to compute LCG, we build new versions of signatures in which anchored types are replaced by the pattern "LC" (which stands for "like current" in reference to Ei el anchored type declaration).

We then de ne two signatures that match (in our terminology signatures \potentially equal") as two signatures having at a given position either both the same type, or both the pattern LC.

In the example of Figure 7:

The two methods < (of Date and Time) now have signatures that match, and have di erent bodies. This is enough to con rm that they are incompatible and that their LCG will be a method having an empty body, de ned in the common superclass |say Magnitude| of Date and Time, and of signature (Magnitude).

The two methods <= (of Date and Time) have signatures that match and the same code p. This is enough to con rm that they can be factored via a LCG, which is a method of code p de ned on the same common superclass | Magnitude |of Date and Time and of signature (Magnitude). This example represents a typical situation showing how Ares is able to highlight interesting factorization classes.

Comparison with related works

Related works GM93, Cas92, LBSL91, LBSL90, Ber91, MS89, Run92, DDHL94a, DDHL95, Moo95, MC96] may be studied from three viewpoints: the strategy used to reorganize hierarchies, the features of the hierarchy and the handling of overloading.

Global, incremental and toolbox strategies

To build a hierarchy, di erent strategies can be considered:

The Toolbox approach, proposed by Ber91], is based on a set of local operations allowing users to modify a hierarchy.

Global algorithms MGG90, LBSL91, LBSL90, Cas91, Moo95, MC96] build in a single step the whole hierarchy from the binary relation Class ? property.

Incremental algorithms insert a new class into an already existing hierarchy. Such a technique is proposed by Cas92, MS89, Run92, DDHL94a, DDHL95, GMM95]. All of these strategies may lead to the same results, no one can be considered better than another. For instance, given a set of classes, a whole hierarchy can be built by successive applications of an incremental algorithm. Conversely, a global algorithm can always be used to insert a class A in a hierarchy whose class set is E |starting from A and E, forgetting the structure of the hierarchy. However, depending on the utilization context, one strategy or another will be more suitably adapted. A global algorithm is obviously more suitable in the rst case above, while an incremental algorithm should be used in the second. Besides, global algorithms are more adapted when the given data is the relation Class-Property |for instance, when reorganizing an unsatisfactory hierarchy from scratch|, while incremental algorithms and toolboxes t evolution better.

Underlying hierarchy models

The underlying model used to represent hierarchies is more or less restrictive.

Cas92] does not impose any constraints on the inheritance graph; this seems powerful at rst sight but there is no formal characterization of the results produced by the algorithm. In LBSL91, LBSL90], there is a strong constraint on hierarchies in which only leaves can represent instanciables classes. Moreover, a second set of algorithms use implicitly ( Run92, MS89, MC96]), or explicitly ( GM93, GMMM95, DDHL94a, DDHL95]) with further adaptations, the Galois lattice of the Class-Property relation to encode hierarchies. The Galois lattice is a mathematical construction ensuring the most compact maximal factorization (more details can be found in Aig79, Wil89, Wil92, GM93, DDHL94a, GMMM95]).

Run92, MS89] use the whole lattice (precisely a sup-semi-lattice) and this raises some problems. Firstly because of space consumption: in the worst case, the space complexity is exponential in max(number of classes, number of properties).

Secondly, because this structure imposes some constraints on the hierarchy; for example, Figure 2 shows how this structure can forbid the deletion of a class (class C 6 in H 5 ); indeed, if the deletion is achieved (as in H 6 ) then C 3 and C 5 have the two lowest common superclasses C 2 and C 8 and the hierarchy is no longer a lattice.

More cleverly, GM93] proposed use of a structure which is a sub-order of the Galois lattice, that we call a Galois subhierarchy, which improves space complexity. However, in the same example of Figure 2, the Galois subhierarchy imposes a contrary constraint to the hierarchy: class C 6 must be deleted even if it is a meaningful class (cf. section 2.3). MC96] seems to produce the same structure of a Galois subhierarchy.

Our algorithm is based on the Galois subhierarchy. It uses and preserves an underlying Galois lattice and thus produces formally well characterized results. We have added a slight modi cation to avoid the deletion of meaningful classes.

Taking overloading into account

Initial studies LBSL90, LBSL91] did not take overloading into account. A rst advance is described in Cas92], which simply allows an abstract (pure virtual) method to be overriden by an implemented one which itself cannot be overriden. A second step is described in MS89, Run92, DDHL95, GMMM95, GMM95], proposing systems able to take overloading into account, provided there is an \oracle" able to compare two occurrences of the same generic property, and give their lowest common generalization(s).

We improve algorithms concerning this topic in two ways: the main one concerns partial automation of the oracle for a set of well-de ned cases, including cases of \self-referent" signatures, the second one is a signi cant improvement of the space complexity.

We present below the speci cations, the algorithm, and then detail our approach of overloading with self-referent signatures.

Speci cations

Input: The algorithm starts with H i = (C i ; ? i ) a class hierarchy with a root 5 and with a meaningful class A to be inserted. C Mean is the set of meaningful classes of H i . Properties(A) is A's property set.

Output: The nal hierarchy H f = (C f ; ? f ) "integrates" H i and A and respects the following properties DDHL94b].

Preservation of the maximal factorization of properties

When H i is maximally factorized, so is H f Preservation of the underlying model When H i is a Galois sub-hierarchy of C Mean , H f is a Galois sub-hierarchy of C Mean S fAg. Inheritance path preservation of the hierarchy For all classes of H i still belonging to H f , the inheritance paths remain.

Conservation of the properties of input classes

Classes which belong to both hierarchies H i and H f keep the same set of properties.

Meaningful class conservation

The set of meaningful classes of H f is C Mean S fAg Note that with any input hierarchy, i. e. not necessarily a Galois subhierarchy and/or a maximally factorized one, everything common to the hierarchy and the class to be inserted is factorized by Ares.

The algorithm

The algorithm (cf. Figure 8) can be split into three parts : (1) search of A superclasses, (2) deletion of non-meaningful empty classes and (3) search of A 5 The root has no properties, and does not appear in the gures subclasses. We focus on part 1, in which A superclasses are found or built and where A is bounded to its immediate superclasses. This part raises the main issues. A complete description of parts 2 and 3 could be adapted from previous work DDHL94b].

The algorithm uses some global variables: AalreadyCreated: a Boolean which is true if, while visiting the hierarchy and creating factorization classes, a class with the same properties as A is found. SH: the current set of A superclasses. At any time, SH holds already visited classes in H i which are A superclasses, as well as the factorizing classes (obviously A superclasses) already created by the algorithm.

EmptyClasses: the set of the non-meaningful classes which, after a factorization, do not declare any more properties.

We use the function SetMeaningful(C) to insert C into C Mean , as well as the predicate

IsMeaningful(C).

The algorithm visits all classes in the input hierarchy H i going down from the root and following a linear extension LEH i of > H i , i.e. a class is visited after all its superclasses. The goal of these visits is to build SH, the set of A superclasses in H f . Then, if needed, A is created and bounded to its direct superclasses.

When a class C is visited, its set of declared properties Declared(C) is compared to the set Properties(A).

We compute ExtractedProperties(C; A) which can be seen as the set of the properties "common" to C and A. -Remainder(A) is empty It means that A and C are the same class. When the whole hierarchy has been visited, SH 6 and possibly adapted as shown later contains all A superclasses. If A has not already been found, it must be created and connected to its immediate superclasses | we use the function Min(E), which returns the minimal (for < H ) classes of set E.

Automatic comparison of occurrences of generic properties

Handling overloading in Ares requires being able to compare an occurrence of a generic property (coming with the class to be inserted) with elements already present in the hierarchy.

A problem arises when the set of properties of the class A to be inserted and the set of properties of an existing class C being visited (cf. section 5.2) contain p A and p C respectively, two OGP of the same generic property P.

In such cases, Ares needs to compute: LCG(p A ; p C ) i. e. the property to be factorized in a common superclass of C and A. LCG(p A ; p C ) can be either p A or p C or the lowest property that both p A and p C specialize.

Remainder(C) and Remainder(A), allowing

Ares to state what is the common superclass of A and C 7 .

In the above section, describing the algorithm, discussions related to (1) the computation of the LCG of two OGP and (2) the precise description of the computation of Remainder(C) and Remainder(A) have been delegated and are presented here.

We rst present additional information and definitions of OGP and their signatures necessary for the comparison of properties. Secondly, we explain how to compute remainders of C and A in the general case, and thirdly we deal with automatic computation of LCG(p a ; p c ). Moreover, as explained in the examples (cf. Section 3.3), we need to separately consider selfreferent signatures, i. e. signatures including the class in which the property is de ned. Such a class has been characterized in the signature as an anchored type and recoded with the pattern "LC".

Comparison relationships for signatures. Definitions of some comparison relationships between signatures used in the algorithm are presented. Let us consider two signatures S A = (A 1 ; A 2 ; :::; A n ) and S C = (B 1 ; B 2 ; :::; B n ), where A i and B i are known types. S A and S C are equal if 8i (Ai = Bi) S A and S C are potentially equal if 8i (Ai = Bi) or (Ai = LC and Bi = LC) S A and S C are comparable if one is a specialization of the other, for example S A < S C if 8i (A i B i ), S A and S C are potentially comparable if one is a potential specialization of the other.

For instance S A is a potential specialization of S C if 8i (Ai <= Bi) or (Ai = LC and Bi = LC), S A and S C are incomparable, if (9i s.t. A i and B i are incomparable) or (9i; j s.t. A i < B i and B j < A j ).

Remainder computation

Let us de ne equal (resp. potentially equal) properties as properties with the same code and equal (resp. potentially equal) signatures.

It is now possible to more precisely compute Remainder(C) and Remainder(A).

-Remainder(C) is obtained by removing, from Declared(C), properties equal or potentially equal to a property of ExtractedProperties(C; A).

-Remainder(A) is obtained by removing, from Properties(A), properties equal or potentially equal to a property of ExtractedProperties(C; A).

Computing LCG of two properties

We deal in this section with the issue of computeraided determination of LCG(p A ; p C ) in the working context de ned in section 2. Recall that we generally distinguish between three kinds of cases in the determination of LCG(p A ; p C ):

Cases where such a determination requires a human expert, for example when comparing two methods with di erent codes doing the same thing. Cases in which an automatic computation is possible that we do not yet handle. For example, it is possible to perform much more clever code comparisons than those we have already done. Cases that we have studied and that we now describe. We consider that the rather simple rules that we have established allow Ares to deal with numerous and nontrivial cases. The cases we have considered are given by mixing code and signature comparisons as summarized in Figure 9. 2. p A and p C have the same code, and their signatures are potentially equal : both signatures have at least one anchored type at the same position.

For instance, if

p A is p A (T 1 ; :::; T i ; A; :::; T n ) code1], and p C is p C (T 1 ; :::; T i ; C; :::; T n ) code1], then LCG(p A ; p C ) = p m = p(T 1 ; :::; T i ; sup(A; C); :::; T n ) code1], where sup(A; C) is the lowest common superclass 8 of C and A in which the algorithm will store p m , if p m is not already \declared" in a superclass of C i. e. if there is no superclass X of C containing p X (T 1 ; :::; T i ; X; :::; T n ) code1].

An example of such a situation can be found in the Magnitude example (cf. Figure 7), where A is Time, C is Date, and the considered property 8 superclass in a broad sense, which can be C or A 9 We will use the name Magnitude for clarity but of course, Ares does not nd the name In the \car-truck" example (cf. Section 3.3, Figure 5), no hypothesis have been put forward concerning the code of the two properties register-Driver. If we consider that they have the same code, this is an example of our current case 3, and we compute: LCG(registerDriver(Driver) code1]; registerDriver(TruckDriver) code1]) = registerDriver(Driver) code1] = p m p m will be declared on the superclass of the two classes Car and Truck, whatever it is. Knowing whether or not the other property (here registerDriver(TruckDriver) code1]) should be considered the same and subsequently be removed from the other class, is an optimization of the algorithm and is language and application dependent. 4. p A and p C have the same code, and their signatures are potentially comparable : both signatures have at least one anchored type at the same position.

For instance, if p A is p A (T 1 ; :::; T i ; X; :::; T j ; A; :::; T n ) code1], p C is p C (T 1 ; :::; T i ; Y; :::; T j ; C; :::; T n ) code1], with Y < X. Then LCG(p A ; p C ) = p(T 1 ; :::; T i ; X; :::; T j ; sup(A; C); :::; T n ) code1]. This case is very similar to Case 2, but sup(A; C) is more constrained, it cannot be C. 5. p A and p C have the same code, and their signatures are incomparable.

For instance, if p A is p A (T 1 ; :::; T i ; :::; T n ) code1], and p C is p C (T 0 1 ; :::; T 0 i ; :::; T 0 n ) code1], then LCG(p A ; p C ) is p(sup(T 1 ; T 0 1 ); :::; sup(T i ; T 0 i ); :::; sup(T n ; T 0 n )) code1].

6. p A and p C have the same signatures, and their codes are di erent.

If codes are di erent, at least a deferred property can be declared for a superclass. For example, if p A is of the form: p A (T 1 ; :::; T n ) code1], and p C is of the form: p C (T 1 ; :::; T n ) code2], then LCG(p A ; p C ) = p(T 1 ; :::; T n ) = 0] This formula for LCG is again an acceptable result, but p A could also be a specialization of p C (or the opposite). Determining this requires either a human expert or more sophisticated techniques for code comparison (is p a 's code a specialization of p c 's code?) or an optimization of the Ares result on which we are currently working. 7. p A and p C have di erent codes, and their signatures are potentially equal.

For instance, if p A is p A (T 1 ; :::; T i ; A; :::; T n ) code1], and p C is p C (T 1 ; :::; T i ; C; :::; T n ) code2], then LCG(p A ; p C ) = p(T 1 ; :::; T i ; sup(A; C); :::; T n ) = 0] The Magnitude hierarchy (cf. Section 3.3, Figure 7) includes an example of such a case, where A is Time, C is Date, and the considered properties are < of Date and Time. The computed LCG to be stored in the factorization class is < (sup(Date; Time)) = 0]. This factorization class being determined (cf. the discussion on Case 2), the nal property to factorize is < (Magnitude) = 0] 8. p A and p C have di erent codes, and their signatures are comparable.

One of the properties is a specialization of the other, if for instance S A < S C , then LCG(p A ; p C ) = p C . This case occurs in the \car-truck" example (cf. Figure 5) if we consider that the two methods registerDriver have di erent codes. The computed LCG is registerDriver(Driver) code1] that will be declared in the common superclass of Car and Truck. The di erence with Case 3 is that here registerDriver(TruckDriver) clearly overrides registerDriver(Driver). 9. p A and p C have di erent codes, and their signatures are potentially comparable |both signatures have at least one anchored type at the same position.

For instance, if p A is p A (T 1 ; :::; T i ; X; :::; T j ; A; :::; T n ) code1], and p C is p C (T 1 ; :::; T i ; Y; :::; T j ; C; :::; T n ) code2], with Y < X, then LCG(p A ; p C ) = p(T 1 ; :::; T i ; X; :::; T j ; sup(A; C); :::; T n ) = 0]. 10. p A and p C have di erent codes, and their signatures are incomparable.

For instance, if p A is p A (T 1 ; :::; T i ; :::; T n ) code1], and p C (T 0 1 ; :::; T 0 i ; :::; T 0 n ) code2], then LCG(p A ; p C ) = p(sup(T 1 ; T 0 1 ); :::; sup(T i ; T 0 i ); :::; sup(T n ; T 0 n )) = 0]. This is a case where further researches are necessary, indeed such a rule may lead, in certain cases, to the creation of uninteresting (only containing deferred 10 properties) factorization classes. The issues here are (1) how to obtain a more precise rule and (2) how to optimize the hierarchy thereafter.

Conclusion

We have presented an incremental algorithm able to automatically insert a class, de ned by the set of its properties, into an existing class inheritance hierarchy. The algorithm takes an input hierarchy and a class and produces a well characterized output hierarchy: it preserves the input hierarchy features such as its structure, maximal factorization of properties, inheritance paths and the set of meaningful classes. Furthermore, handling of overloading in the algorithm has been studied and partially achieved. The problem has been split into two subproblems:

(1) the comparison of occurrences of generic properties and (2) the use of the results of these comparisons in the algorithm. Provided that the rst subproblem is solved, the algorithm works with overloading according to the above descriptions. Concerning the rst subproblem, we have recalled the limits of automatization, i. e. we explained why it will never be able to completely deal with the comparison of generic properties without the assistance of a human expert. These limits being de ned, we have given a rst categorization of properties and some rules to compare them automatically in a certain number of well dened cases, notably in self-referent signatures cases.

The algorithm has been implemented and tested on nontrivial but pre-compiled cases. One of our main current concerns is to apply it to large scale hierarchies produced in foreign applications. This requires interfacing the algorithm, and secondly im-10 subclass responsibility plementing post-processors that will optimize its results | many optimizations are possible but there was no room to describe them there.

Many further studies can be foreseen: We rst plan to extend the number of handled cases of automatic comparison of generic properties; this is possible: (1) by studying in further detail the cases of properties having self-referent signatures, and (2) by analyzing more precisely method bodies via syntactic and even semantic analysis. Concerning method refactoring through syntactic analysis, the reader should refer to OJ93] and Moo96]. Another di cult issue would be to combine this work with linearization algorithms DHHM94] used to solve con icts in hierarchies with multiple inheritance.

Figure 1 :

 1 Figure 1: H' is not maximally factorized, H" is.

Figure 2 :

 2 Figure 2: Insertions without overloading

Fig. 2 )Figure 4 :

 24 Figure 3: Compactness and maximal factorization

  Figure 5: Signatures give the LCG

  Figure 6) two occurrences of the generic property display exist in the hierarchy: d 0 = display() = 0] and d 1 = display() Code1] and a new one, (d 2 = display() Code2]) comes with the class Circle to be inserted. Their code being di erent, d 1 and d 2 can be considered as incomparable. However, another more precise code examination shows that d 0 = LCG(d 1 ; d 2 ). These results allow Ares to correctly produce the nal hierarchy. It should be noted that the class GeometricFigure is created (except for the name) by the algorithm, if not initially present.

Figure 7 :

 7 Figure 7: Using codes and signatures

  Figure 2. ExtractedProperties(C; A) = fdg, Remainder(C) = feg and Remainder(A) = ffg. The two classes are incomparable and the properties of ExtractedProperties(C; A) are factorized 6 in a common superclass C 0 of C and A. C 0 is added in the hierarchy and is stored in SH (the set of A superclasses). C 0 is de ned as a superclass of C, and as a subclass of the classes of Sups(C; SH). We call Sups(C; SH) the minimal elements of the set of classes which are C superclasses while belonging to SH. -Remainder(A) is empty Example: A = C 4 and C = C 3 for H 2 in Figure 2. ExtractedProperties(C; A) = fcg, Remainder(C) = fd; eg and Remainder(A) = fg. A is a superclass of C, the properties of A declared in C are extracted from C and we insert A in the hierarchy as a superclass of C. Remainder(C) is empty -Remainder(A) is not empty Example: A = C 3 and C = C 2 for Hierarchy 1 in Figure 2. ExtractedProperties(C; A) = fbg, Remainder(C)

7Figure 8 :

 8 Figure 8: The ARES Algorithm

  Let us consider again two OGP: p A with signature S A in the class A to be inserted, and p C with signature S C declared in the class C that Ares is visiting. For each case in the array, we give the LCG and when needed explanations and examples. 1. p A and p C have the same signature and the same code : p A and p C are the same property, LCG(p A ; p C ) = p A = p C .

  is . The following provides a snapshot of things computed by the algorithm: LCG( (LC) code1]; (LC) code1]) = (sup(T ime; Date)) code1]) ExtractedProperties(Time; Date) = f (sup(T ime; Date)) code1]; :::g Remainder(Date) = fhour : integer; minut : integer; second : integer; :::g Remainder(Time) = fday : integer; month : integer; year : integer; :::g Knowing that neither Remainder(Date) nor Remainder(Time) are empty, Ares deduces that a factorization class C 0 = Magnitude 9 has to be created. In Magnitude properties stored in ExtractedProperties(Time; Date) will be declared, in particular (Magnitude) code1]. Note that the signature for on Magnitude has been rebuilt. 3. p A and p C have the same code, and their signatures are comparable. In whole generality, one of the properties is a specialization of the other, if for example S A < S C , then LCG(p A ; p C ) = p C .

Figure 9 :

 9 Figure 9: Mixing code and signature comparison

Ackowledgments

We would like to thank Nicolas Prade for its contribution to the automatic comparison of occurrences of generic properties.