Anne-Lyse Ravon
email: anne-lyse.ravon@univ-rennes1.fr

Jean-Laurent Monnier

Marine Laforge

Menez-Dregan I, layer 4: a transitional layer between the Lower and Middle Palaeolithic in Brittany

Keywords: Menez-Dregan, transition, Lower Palaeolithic, environmental constraints, Colombanian, cobble tools

: a predominance of cobble tools amongst heavy-duty tools, retouched light-duty tools on flake-supports comprising mostly notches and denticulates, and a knapping method akin to the "SSDA -Clactonian" (wide butts rarely faceted, prominent bulbs, wide open flaking angles, resulting from an alternate flaking of the cores; "système par surface de débitage alternée", Forestier, 1993). The Levallois method is absent, bifaces are absent or extremely rare, and there are few scrapers. The Colombanian proves to be a Lower Palaeolithic industry contemporary with the classic Acheulean, but typologically distinct. However, standardisation of flake production leads us to foresee a change in the lithic industry of layer 4, and allows us to highlight a transitional period from the Lower Palaeolithic to the Middle Palaeolithic in the latest occupation of this deposit. This study is a contribution to the documentation of the diversity and variability of Lower and Middle Palaeolithic lithic industries, demonstrating that the large amount of cobble tools in layer 4 is an unchanged component due to environmental constraints.

Introduction

Menez-Dregan I is a Lower Palaeolithic site situated at Plouhinec, Finistère, in Brittany (fig. 1). The site is located in the Audierne bay, at the westernmost tip of Brittany. It is an ancient marine cave whose roof has gradually collapsed and thus partly protected the site from erosion (fig. 2). In the current state of research, the stratigraphy within Menez-Dregan displays an alternating sequence of pre-Neanderthal occupation layers and marine deposits, which probably date to between OIS 13 and OIS 7 [START_REF] Monnier | A new regional group of the Lower Palaeolithic in Brittany (France) recently dated by Electron Spin Resonance[END_REF][START_REF] Monnier | Rapport de fin d'opération pluri-annuelle sur la fouille du gisement paléolithique inférieur de Menez-Dregan I à Plouhinec[END_REF].

The fauna has not preserved due to the acidic environment, leaving only the lithic industry to show how the human groups who settled at the site lived and, it is worth noting, mastered fire lighting and/or control at a very early date (late OIS 13 or early OIS 12). This study focuses on layer 4, excavated between 1991 and 2004, which appears to be the last occupation of this deposit, at the boundary between the Lower and Middle Palaeolithic [START_REF] Ravon | La transition Paléolithique inférieur-moyen dans l'Ouest armoricain : l'exemple de la couche 4 du site de Menez-Dregan1 (Plouhinec, Finistère)[END_REF].

Regional context and chronological attribution

The Lower Palaeolithic in the Armorican Massif consists of two different groups, which are Acheulean sensu stricto on one side, and "archaic" lithic industries characterised by pebble tools on the other side. The name "Colombanian" has been given to this second group whose type site is Saint-Colomban (Carnac, Morbihan, Brittany) by J.-L. Monnier in the late 80's [START_REF] Monnier | Le gisement paléolithique inférieur de la Pointe de Saint-Colomban, Carnac, Morbihan[END_REF][START_REF] Monnier | Acheuléen et industries archaïques dans le Nord-Ouest de la France[END_REF].

The lithic industry of the site of Menez-Dregan has been attributed to the "Colombanian group" by J.-L. [START_REF] Monnier | Acheuléen et industries archaïques dans le Nord-Ouest de la France[END_REF] on the basis of its composition: predominance of cobble tools among the heavy-duty tools, retouched light-duty tools on flake-supports comprising mostly notches and denticulates, and knapping method akin to the "SSDA -Clactonian" [START_REF] Forestier | Le Clactonien : Mise en application d'une nouvelle méthode de débitage s'inscrivant dans la variabilité des systèmes de production lithique du Paléolithique ancien[END_REF]. The flakes have prominent bulbs, wide butts rarely faceted and wide open flaking angles, resulting from an alternate flaking of the cores (SSDA -"système par surface de débitage alternée", [START_REF] Forestier | Le Clactonien : Mise en application d'une nouvelle méthode de débitage s'inscrivant dans la variabilité des systèmes de production lithique du Paléolithique ancien[END_REF]. The Levallois method is lacking, handaxes are absent or extremely rare, and there are very few scrapers. The Colombanian proves to be a facies of the Lower Paleolithic, essentially localised on the south Armorican shoreline, between Crozon and Noirmoutier, contemporary with classic European Acheulean but typologically distinct [START_REF] Monnier | Acheuléen et industries archaïques dans le Nord-Ouest de la France[END_REF][START_REF] Monnier | Le Colombanien: un faciès régional du Paléolithique inférieur sur le littoral armoricano-atlantique[END_REF][START_REF] Molines | Les industries à galets aménagés du littoral sud-armoricain (France) au Paléolithique inférieur[END_REF][START_REF] Molines | L'Acheuléen de l'Ouest de la France : apports du site de Menez-Dregan 1 (Plouhinec, Finistère, France)[END_REF]. The "Colombanian group" is composed of the sites of St Colomban, la Croix Audran, the island of Groix, Menez-Dregan, Primelin, and Le Bois-de-la-Chaize, plus a large number of isolated finds all along the shore line (fig. 3), and is the subject of a new study that focuses mainly on the Lower Palaeolithic site of Menez-Dregan I (Ravon, in progress).

All the Colombanian sites are located on the current shoreline, sheltered in corridors of marine abrasion or in collapsed marine caves. Settlements are always on ancient marine beaches, this position seems to indicate that the human occupation occurred at the transition between interglacial and glacial periods, in rather mild climatic conditions [START_REF] Monnier | Acheuléen et industries archaïques dans le Nord-Ouest de la France[END_REF].

The Lower Paleolithic site of Menez-Dregan : a human settlement in a marine cave

The site of Menez-Dregan I has been undergoing excavation since 1991. This archaeological operation is part of a multidisciplinary project [START_REF] Monnier | Rapport de fin d'opération pluri-annuelle sur la fouille du gisement paléolithique inférieur de Menez-Dregan I à Plouhinec[END_REF][START_REF] Monnier | Rapport intermédiaire sur la fouille du gisement paléolithique inférieur de Menez-Dregan I, campagne[END_REF]. The deposit is located within the cliff above the current sea level. In Menez-Dregan the sedimentological evidence is strongly reduced because of multiple episodes of marine erosion in the cave (low sedimentary preservation in terms of sedimentation and erosion process). However, the proximity of a section with a longer sedimentary record (Gwendrez cliff) allowed for an attempt at correlation between the different deposits by means of a sedimentological study applied to sandy marker beds (dunes). The resulting new data allowed a more precise chronostratigraphy of this site to be drawn up and contributed to further validation of dating [START_REF] Monnier | Application of sedimentological analysis to the correlation of eroded layers under beaches with local and regional Pleistocene stratigraphy. A contribution to geological dating of Palaeolithic sites on Northern coast of Brittany (France)[END_REF][START_REF] Laforge | Contribution à la chronostratigraphie du gisement Paléolithique inférieur de Menez-Dregan 1 (Plouhinec, Finistère, France). Corrélations avec les dépôts de la falaise de Gwendrez[END_REF]. The layers are described from the oldest to the most recent as follows (fig. 4):

Layer 9 is the first human occupation of the site, dated from a hearth by ESR at 465 000 years ± 65 000 (Monnier et al., 1996, p. 63). The lithic assemblage is composed of more than 2,000 debitage products and heavy-duty tools. Cobble tools have been made on sandstone or microgranite, on large cobbles, big flakes or split cobbles, and have sometimes been retouched in order to create a denticulated edge on the tool (fig. 5). The small tools are retouched with denticulates and notches, mostly on flint and quartz. Some bones were found during the excavation, but in a very poor state of preservation. There are no handaxes or bifacial components in this first layer of palaeolithic occupation.

Layer 8 is a raised beach, with an overlying palaeolithic occupation. It is still undergoing excavation, but the presence of two handaxes was noted.

Layer 7 has been geologically correlated to stage 11 [START_REF] Laforge | Contribution à la chronostratigraphie du gisement Paléolithique inférieur de Menez-Dregan 1 (Plouhinec, Finistère, France). Corrélations avec les dépôts de la falaise de Gwendrez[END_REF]. It is a thick humic layer, witnessing a rather dense human occupation (more than 14 000 artefacts). At least three different sublevels of human occupation coexist in this layer, suggested by the remains of hearths. The heavy duty tools are mostly composed of choppers and of choppingtools, but some particularly interesting cleavers, made on quartzite cobbles, evoke the Acheulian (fig. 6).

On top of layer 7 is layer 6. It is a level of human occupation directly on top of a fossil beach. The ESR dating gave an age of 396 000 years ± 45 000 on the hearth situated at the basis of the immediate overlying layer 5e (Monnier et al., 1996, p. 63). More than 18 000 lithic artefacts were recorded in this layer, composed of debitage products and cobble tools. As far as we know, there are absolutely no handaxes nor material resulting from their manufacture from this layer, however the study of the lithic assemblage is still in progress (Ravon, in progress). Once again, the heavy duty tools mostly comprise of choppers and of few chopping-tools.

The composition of the lithic industry is exactly the same for layer 5, however some interesting features appear, such as the presence of a pseudo-levallois flake and several bifacial tools (fig. 7). The retouched light duty tools are mostly denticulates and notches which show a great variety of shapes and supports. Some of the choppers, which are numerous in this layer too, were also used as hammerstones. Anthracology studies tend to place the different occupations of layer 5 in OIS 9 (Marcoux et al., in preparation).

The last occupation of the marine cave of Menez-Dregan I occurred in layer 4, and was sealed by layer 3, a sand dune dated by ESR at 141 ± 16 ky (Monnier, 1996, p. 63). A head deposit covered this dune, and the top soil formed on top of it.

Layer 4

The paleoenvironmental data indicates that during the prehistoric occupation of layer 4 the sea level was much lower than at present and the shoreline was probably between 5 and 10 km further from the site [START_REF] Lefort | Apport de la géologie marine à la détermination des sources de matières premières au Paléolithique dans le Massif armoricain : Origine possible du silex utilisé sur les stations paléolithique inférieur de Menez-Dregan (Plouhinec, Finistère, France). Implications paléoclimatiques et paléoenvironnementales[END_REF]. Therefore, the deposit would have stood on top of a high promontory and opened out into a vast landscape, providing strategic shelter for palaeolithic populations who had a clear view of the plain below. The study of charcoal from layer 4 allows us to imagine deep valleys around the site, with abrupt slopes and with the formation of a riparian vegetation along the rivers, with the presence of heath, ash and pines (Monnier et al., 1996, p. 72).

No fireplace was found during the excavation, although some burnt artefacts and numerous charcoals are present in this layer, but a paving structure was noticed (fig. 8). This brings us to the organisation of the dwelling place in layer 4: the paving structure was interpreted as the floor of a probable tent. The addition of this tent to the edge of the rockshelter would have largely increased the available space within the shelter [START_REF] Monnier | Rapport intermédiaire sur la fouille du gisement paléolithique inférieur de Menez-Dregan I, campagne[END_REF].

Description of the stratigraphy in layer 4

Geological correlations tend to place layer 4 in OIS 9 or 7, although the only TL dating obtained for this level gave an age of 223 ± 23 ky (Mercier et al., 2004, p. 258). This would place the occupation of layer 4 in OIS 7d (fig. 9), at an average sea level of -60 m (Waelbroeck et al., 2002, fig. 4 p. 299). Therefore, the shoreline could be 10 km further from the site (fig. 10).

The different transgressions that have occurred on the site had an impact on different levels and have truncated the oldest layers. They are generally affected by erosion pools that formed under the collapsed roof blocks, creating numerous stratigraphic hiatuses and complicating the interpretation of the site, for example the interface layer 4 / layer 5. However, three levels have been identified in layer 4, and are thus described [START_REF] Monnier | Rapport de fin d'opération pluri-annuelle sur la fouille du gisement paléolithique inférieur de Menez-Dregan I à Plouhinec[END_REF]: Level 4a: Laminated, brown and compact silty sand, including marine pebbles and few artefacts. This sediment is coarse and poorly sorted.

Level 4b: Laminated, brown and compact silty sand, including marine pebbles and many artefacts. Presence of angular granitic rocks. This sediment is coarse and poorly sorted.

Level 4c: Silty sand and gravels, with few pebbles and artefacts. Lamellar structure, underlined by blacky and humified clayey beds, molding the shape of the underlying rocks from layer 5.

2. Lithic industry from layer 4

14, 909 artefacts were found in this layer [START_REF] Ravon | La transition Paléolithique inférieur-moyen dans l'Ouest armoricain : l'exemple de la couche 4 du site de Menez-Dregan1 (Plouhinec, Finistère)[END_REF]: 140 in level 4a, 4763 in 4b, 9966 in 4c, plus 40 artefacts in layer 4 which could not be attributed to any of these three sub levels. The different raw materials used are strictly local, and come from marine pebbles in the different raised beaches on or around the site. These raw materials are flint, mainly, then sandstone, quartz, microgranite, quartzite and glossy sandstone, as for all the other layers within the site.

Table 1 shows the composition of the lithic assemblage from layer 4. 80% of the assemblage is composed of flakes, flake fragments and debris, made on flint pebbles (70.2%, tabl. 1) or quartz pebbles (14%). The retouched tools are almost equally divided between light duty tools (made on flint for 78.8% of them) and heavy duty tools (made on sandstone for 74.8% of them, fig. 11 andtabl. 1). Retouched flake tools are mostly denticulates (68.2%), scrapers (19.7%) and notches (12.1%, [START_REF] Ravon | La transition Paléolithique inférieur-moyen dans l'Ouest armoricain : l'exemple de la couche 4 du site de Menez-Dregan1 (Plouhinec, Finistère)[END_REF]. Therefore, layer 4 appears to be the level with the highest number of scrapers within the site (Ravon, in progress). Heavy duty tools are mostly choppers and pebbles with single removals, which seems to result from their use as hammerstones. Two very distinct chaînes opératoires are already present since the beginning of the collection of the different raw materials within or in the environment of the site. Indeed, the cobble tools were made on sandstone, microgranite or quartzite cobbles, and the debitage products were made on flint, or quartz pebbles, these being naturally available in the fossil beaches in or surrounding the deposit.

The only raw material that does not come from a pebble is the glossy sandstone which comes from an outcrop situated ca. 20 km from the site. This raw material must have been knapped nearby the outcrop, or outside Menez-Dregan, for cores are totally absent in the lithic assemblage, only flakes, flake fragments and retouched light duty tools remain to show us the use of this raw material.

The main characteristics of the lithic industry of layer 4 are: large quantity of pebble tools (almost 6%), great variety of shapes and supports for the retouched light duty tools, debitage products that tend to be shorter and thicker than in the previous layers.

As for the cores (4,3% of the assemblage), they were made via alternate flaking mainly, from a striking platform obtained after the removal of at least one flake, or two or three unipolar and parallel flakes. Usually, only two core episodes are present, but it can vary with the size and shape of the raw material used. Most of the cores are made on flint, and the smallest pebbles used to obtain flakes are a result of bipolar flaking on an anvil. Two discoid cores are present in the assemblage, and were made on larger quartzite pebbles. These are the only discoid cores present on the site so far.

Discussion

We have presented briefly the lithic industry of layer 4, which simultaneously combines Lower Palaeolithic characteristics, such as large quantities of pebble tools (due to the environment of the site) and "opportunistic" knapping, and the emergence of characteristics that are common to the Middle Palaeolithic, such as standardisation of flake production, and knapping methods adapted to the dimensions of the raw materials (discoid knapping for quartzite, bipolar flaking on an anvil for small flint pebbles).

The standardisation of flake production leads us to foresee a change in the lithic industry of layer 4, and allows us to highlight a transitional period from the Lower Palaeolithic to the Middle Palaeolithic in the latest occupation of this deposit [START_REF] Ravon | La transition Paléolithique inférieur-moyen dans l'Ouest armoricain : l'exemple de la couche 4 du site de Menez-Dregan1 (Plouhinec, Finistère)[END_REF]. The presence of cobble tools within the assemblage is a common characteristic shared by all the layers in Menez-Dregan I, but in different proportions. Layers 4 and 7 have the biggest quantity of cobble tools within the site (6,7% for layer 4, 6% for layer 7). The ability to create desirable cobble tools is likely one of the primary reasons early Palaeolithic people came to settle in Menez-Dregan I cave. Indeed, the presence of the various raised beaches in the area proved to be a reserve of raw materials of a great variety, and furthermore available in large quantities. The large amount of cobble tools in layer 4 seems to be an unchanged component in the lithic industry of the site, due to environmental constraints.

Highlighting this transitional period is rather complex in the south of Brittany, for Middle Palaeolithic sites are absent in the immediate neighbouring area around Menez-Dregan I. The nearest Early Middle Palaeolithic site present in the region is the site of Piégu, at Pléneuf-Val-André, on the northern coast of Brittany (fig. 12). This open air site dating from the end of OIS 7 has been excavated at the end of the 80's, and is composed of two main levels of human occupation, at the bottom of a cliff, next to a river [START_REF] Monnier | Données nouvelles sur le gisement paléolithique moyen de Piégu (Pléneuf-Val-André, Côtes-du-Nord)[END_REF]. Two different but broadly contemporaneous specialized areas coexist on the site: an activity of butchery on top of the cliff (level G), and a knapping floor at the bottom of it (level F). ESR/Useries dating for level G on faunal remains gave an age of 200 ± 16 ky on teeth and 197 ± 12 ky on bones [START_REF] Bahain | ESR and ESR/U-series dating study of the Middle Palaeolithic site of Piégu (Brittany, France). A multi-material approach[END_REF][START_REF] Laforge | Le cadre chronostratigraphique des peuplements pléistocènes de l'Ouest de la France[END_REF]. The lithic industry at Piégu is made on flint, from a Levallois debitage (24%) which led to the production of numerous unretouched points and flakes. The retouched light duty tools mainly compose of elaborated scrapers (ca. 50%) of various types [START_REF] Monnier | Le Paléolithique de la Bretagne dans son cadre géologique[END_REF]. This lithic industry has been attributed to a Mousterian of Levallois facies, and can be linked to the Early Middle Paleolithic [START_REF] Monnier | Application of sedimentological analysis to the correlation of eroded layers under beaches with local and regional Pleistocene stratigraphy. A contribution to geological dating of Palaeolithic sites on Northern coast of Brittany (France)[END_REF].

Although the Levallois method is lacking at the site of Menez-Dregan I, some common characteristics exist in both assemblages, such as the production and use of unretouched flakes, and the presence of "Mousterian" scrapers of various types and shapes, but always rather elaborated. Furthermore, the Levallois method is also absent on the more recent Middle Palaeolithic site of Les Vallées in Pléneuf-Val-André (fig. 12;[START_REF] Huet | Le site Paléolithique moyen des Vallées (Pléneuf-Val-André, Côtesd'Armor)[END_REF]. Therefore, the presence or absence of the Levallois method cannot allow us to attribute a site to the Middle Paleolithic in the Brittany region.

More generally, the period of transition between Lower and Middle Palaeolithic seems complicated to highlight [START_REF] Monnier | The Lower/Middle Paleolithic Periodization in Western Europe[END_REF]. The Middle Palaeolithic appears rather early in the region, such as in the North of France, where the complexity of the nature of this transition has been demonstrated [START_REF] Tuffreau | Les industries acheuléennes de la France septentrionale. The Acheulean industries of Northern France[END_REF]. Objective criterias of attribution to the Middle Paleolithic seem impossible to define, only the systematisation of flake production, or the adaptation of knapping methods to the available raw materials seem to help us to foresee this transition [START_REF] Colonge | De la transition Paléolithique inférieur-moyen dans la vallée de la Garonne : l'Acheuléen supérieur de Raspide 2 (Blagnac, Haute-Garonne)[END_REF]. A systematical production of flakes and tools on flake supports, typologically sophisticated and clearly differentiated can also be a good indication [START_REF] Tuffreau | Les débuts du Paléolithique moyen dans la France septentrionale[END_REF].

Conclusion

This study is a contribution to document the variability of the Lower Palaeolithic assemblages, and the variability in the indications of the transition between Lower and Middle Palaeolithic. In layer 4, although we have the presence of what we could call opportunistic knapping, in the sense that the cores are usually not well reduced, and we also have the presence of a large amount of cobble tools, we can see a change in the composition of the lithic industry. In this layer, the ratio of scrapers is more important than in the older layers of the site, although there is still a large amount of denticulate tools. The production of flakes seems to be more standardised too, and one of the aims of the knappers in this layer appears to be attempting to obtain short and thick products that resemble Mousterian tools for some of them. They also adapted their knapping methods to the dimensions of the raw materials, like discoid knapping for big quartzite pebbles, or bipolar flaking on anvil for some small flint pebbles. But even if we can see the beginning of this transition here, the unchanged component in the lithic industry of Menez-Dregan I, the thing that is most characteristic of this site, is the production of cobble tools, due to the availability of the raw materials around the site. The presence of these large pebbles on or around the site has determined this technical behaviour in the Brittany region during the Lower and Middle Palaeolithic.

It seems likely that one of the main reasons Palaeolithic populations settled on this site is due to the presence of fossil beaches in the area. We think this resource of raw material determined the choices they made for their lithic industry. In regards to the geology, there are absolutely no naturally occurring outcrops of flint in Brittany. The only accessible sources of flint are small marine flint pebbles, naturally found within the local fossil beaches, eroded from a submerged outcrop of cretaceous flint situated 40 km from the site (fig. 13; [START_REF] Lefort | Apport de la géologie marine à la détermination des sources de matières premières au Paléolithique dans le Massif armoricain : Origine possible du silex utilisé sur les stations paléolithique inférieur de Menez-Dregan (Plouhinec, Finistère, France). Implications paléoclimatiques et paléoenvironnementales[END_REF]. Their dimensions (max. 10cm) would not have allowed the Palaeolithic occupants of the site to make cobble tools. Instead, they chose to use sandstone, microgranite and quartzite to create their heavy duty tools. Furthermore, the natural shape of these elongated and rather flat cobbles would have assisted in determining the function of the tool created, and it seems likely that cobbles were selected for these properties. This behaviour persisted from layer 9 to layer 4, during probably 200 ky. (After S. Hinguant, in Monnier et al., 1996, modified). 0: present-day soil; 1: coarse head which filled up the deep (this is the last cold period recorded at the site); 2a: large blocks and flagstones, from the final collapse of the marine cave; 2b: arenaceous head; 3a: flaky and argillaceous sand (littoral dune); 3b: Set sandy crust; 4a to 4c: flaky head mixing marine sand and pebbles, with palaeolithic tools (mainly 4b) and strained black layers at its base (4c); 5a to 5e: anthropic soils alternating black (presence of charcoals) and brown layers, very rich with lithic industry, with the presence, at the top of 5c, of a structure of combustion; 5e-d: disturbed ash-bearing layer with structure of combustion arranged at the top of the underlying pebble beach; 6: pebble beach; 7: alternation of Paleolithic layers and dark organic layers, with rounded and smoothed blocks from the collapsed cave, and presence of pebbles at its basis; 8b: raised beach with rocks from the collapsed roof; 8a: sandy layer from the raised beach (8b); 9: sandy-loamy layer, with lithic tools, bones and charcoals, presence of a structure of combustion in a pit; 10: raised beach; 11: raised beach; gneiss: bedrock. Waelbroeck et al., 2012;[START_REF] Shackelton | Oxygen isotopes, ice volume and sea level[END_REF][START_REF] Lisiecki | A Pliocene-Pleistocene stack of 57 globally distributed benthic D18O records[END_REF]Raymo, 2005. (In Laforge, 2012, p. 94, modified).

Fig. 1 :

 1 Fig. 1: Geographic location of the Lower Palaeolithic site of Menez Dregan I (CAD: L. Quesnel).

Fig. 2 :

 2 Fig. 2: The site of Menez-Dregan I, view from the south (Photo J.-L. Monnier).

Fig. 3 :

 3 Fig. 3: Map showing the distribution of the Colombanian sites (CAD: L. Quesnel & A.-L. Ravon).

Fig. 4 :

 4 Fig. 4: Stratigraphy of the Lower Palaeolithic site of Menez-Dregan I. Drawings: T. Paterson, CAD: A.-L. Ravon.(After S. Hinguant, inMonnier et al., 1996, modified). 0: present-day soil; 1: coarse head which filled up the deep (this is the last cold period recorded at the site); 2a: large blocks and flagstones, from the final collapse of the marine cave; 2b: arenaceous head; 3a: flaky and argillaceous sand (littoral dune); 3b: Set sandy crust; 4a to 4c: flaky head mixing marine sand and pebbles, with palaeolithic tools (mainly 4b) and strained black layers at its base (4c); 5a to 5e: anthropic soils alternating black (presence of charcoals) and brown layers, very rich with lithic industry, with the presence, at the top of 5c, of a structure of combustion; 5e-d: disturbed ash-bearing layer with structure of combustion arranged at the top of the underlying pebble beach; 6: pebble beach; 7: alternation of Paleolithic layers and dark organic layers, with rounded and smoothed blocks from the collapsed cave, and presence of pebbles at its basis; 8b: raised beach with rocks from the collapsed roof; 8a: sandy layer from the raised beach (8b); 9: sandy-loamy layer, with lithic tools, bones and charcoals, presence of a structure of combustion in a pit; 10: raised beach; 11: raised beach; gneiss: bedrock.

Fig. 5 :

 5 Fig. 5: Lithic industry from Menez-Dregan I, layer 9 (Photos: M. Vizdal, CAD A.-L. Ravon).

Fig. 6 :

 6 Fig. 6: Lithic industry from Menez-Dregan I, cleavers in layer 7 (Photos: R. Cheruel, C. Gaillard & A.-L. Ravon, CAD: A.-L. Ravon).

Fig. 7 :

 7 Fig. 7: Lithic industry from Menez-Dregan I, layer 5 (Photos & CAD: A.-L. Ravon).

Fig. 8 :

 8 Fig. 8: Paving structure in layer 4b (after S. Hinguant in Monnier et al., 2000; CAD: F. Sotin).

Fig. 9 :

 9 Fig.9: Relative sea levels and chronological distribution of the isotopic stages for the last 450 ky, after the work ofWaelbroeck et al., 2012;[START_REF] Shackelton | Oxygen isotopes, ice volume and sea level[END_REF][START_REF] Lisiecki | A Pliocene-Pleistocene stack of 57 globally distributed benthic D18O records[END_REF] Raymo, 2005. (In Laforge, 2012, p. 94, modified).

Fig. 10 :

 10 Fig. 10: Digital Terrain Model for a sea level of -60 m (DTM P. Stéphan, LETG-Géomer, Brest; in Laforge, 2012, p. 147).

Fig. 11 :

 11 Fig. 11: Layer 4, cobble tools (Photos: R. Cheruel, CAD: A. L. Ravon).

Fig. 12 :

 12 Fig. 12: Location of the site of Piégu in A -Brittany and Bthe East of the bay of Saint-Brieuc (in Laforge and Huet, 2013, p. 615).

Fig. 13 :

 13 Fig. 13: Geological map of North Western France, showing the location of the site of Menez-Dregan I (white star) and the location of the nearest cretaceous flint outcrop (in black circle). Extrait de la carte géologique de France au 1/1 000 000ème, éd. B.R.G.M., Orléans. CAD: A. L. Ravon.

Acknowledgments

The authors would like to thank Josephine Mills and Tabitha Paterson for their proofreadings of the manuscript, and Pierre Stéphan (LETG-Géomer, Brest) for his DTM of the -60 m sea level. We also thank Rebecca Scott and Marta Arzarello for their reviews and helpful comments on this document.


Anamaria M Vinju
email: anamaria@dcc.ufrj.br

Moreira

Cleverton Hentz
email: chentz@ppgsc.ufrn.br

Jurgen J Vinju
email: jurgen.vinju@cwi.nl

Anamaria M Moreira

Reducing the Cost of Grammar-Based Testing Using Pattern Coverage

Keywords: Software test, meta program, pattern matching, grammarbased testing

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Meta programs are tools which read sentences of software languages, such as programming languages, and produce any kind of output [START_REF] Czarnecki | Generative programming -methods, tools and applications[END_REF]. Examples of meta programs are compilers, interpreters, refactoring tools, static analysis tools, and source code metrics tools. The amount and diversity of such tools are growing as processing power and large memory become available to the machines on which software is being developed, but verifying such tools is quite a challenge. Even simple metric tools are known to contain many bugs [START_REF] Lincke | Comparing software metrics tools[END_REF].

Meta programs for real programming languages are complex and hard to prove or test because the languages are big (more than 400 context-free grammar rules is quite normal) and their semantics is often unclear. Apart from some notable exceptions [START_REF] Leroy | A formally verified compiler back-end[END_REF], proofs of correctness of meta programs are not to be expected. Therefore we wish to quickly find common errors in meta programs by exercising their code based on test generation.

Grammar-based testing is a preferred approach for testing meta programs [START_REF] Boujarwah | Compiler test case generation methods: a survey and assessment[END_REF][START_REF] Kossatchev | Survey of compiler testing methods. Program[END_REF]. The input syntax of most meta programs can be modeled precisely using context-free grammars (CFG). From such CFG specifications we can define sets of input sentences which satisfy different coverage criteria of the input language. However, the amount of sentences necessary to cover an entire language is intractable. For Java, for example, if we consider only sentences generated by derivation tree up to height 7 the amount of sentences that can be generated is around 46.26 × 10 9 . If we increase this value to 10, the amount goes to around 9.43 × 10 43 . But, even if we can run a Java processor on such corpus of inputs in reasonable time, chances are the corpus will still not lead to good coverage of the code of the processor itself as some constructs will only appear deeper in the grammar.

The reason for the bad coverage is that a context-free grammar describes all possible inputs for a meta program, but it does not specify precisely which part of the language is used by the given meta program or how different parts of the language are distributed over the meta program. A random distribution over an input grammar will therefore typically not generate an effective test set for a given meta program. The grammars of real programming languages have hundreds of (recursive) rules, generating a super-exponential amount of syntactically correct inputs. Due to the size of such grammars, statistically it is hard to generate exactly the right combination to cover a meta program with a limited (feasible) set of test cases. To further aggravate this problem, some important semantic information, which is dealt with in the meta program, is often missing from context-free grammar descriptions.

Pattern matching is an interesting feature which is often used during the development of meta programs. With it, it is simpler to describe specific situations over the input language, simplifying the implementation of this kind of programs. Many meta programming languages (specialized languages for the development of meta programs) and libraries are based on expressive forms of pattern matching (Haskell [START_REF]Report on the Programming Language Haskell, A Non-strict Purely Functional Language (Version 1.2)[END_REF], Scala [START_REF] Odersky | An overview of the scala programming language[END_REF], TOM [START_REF] Balland | Tom: Piggybacking rewriting on java[END_REF], ASF+SDF [START_REF] Brand | The ASF+SDF Meta-Environment: a component-based language development environment[END_REF], Maude [START_REF] Clavel | The maude 2.0 system[END_REF], StrategoXT [START_REF] Bravenboer | Stratego/xt 0.17. a language and toolset for program transformation[END_REF], ELAN [START_REF] Borovanský | Elan: A logical framework based on computational systems[END_REF] and Rascal [START_REF] Klint | Rascal: A domain specific language for source code analysis and manipulation[END_REF][START_REF] Klint | Easy meta-programming with rascal[END_REF]).

The challenge we address is: given a grammar which describes syntactically correct inputs, to generate a minimal amount of inputs which will cover the meta program. Our contribution is the notion of pattern coverage which links grammar coverage to conditional coverage in meta programs which use pattern matching. We propose the use of patterns as reference for the definition of test data and a pattern-based coverage criterion which defines a set of test data requirements from a set of language patterns. These patterns may be extracted from different sources: from language or meta program specifications, from the patterns used in the code of the meta program, or even from a non pattern-based meta program from which some mining of patterns has been carried out.

The main contributions of this paper are then:

the definition of the Pattern Coverage criterion; an initial algorithm for generating sentences for Pattern Coverage; an empirical evaluation of the relation between Pattern Coverage and existing notions of grammar coverage.

We conduced the evaluation using two meta programs that implement the Cyclomatic Complexity algorithm [START_REF] Mccabe | A complexity measure[END_REF] for Java and Pico [START_REF] Deursen | Language Prototyping: An Algebraic Specification Approach[END_REF] languages. To evaluate and compare the pattern coverage criterion we used the mutation technique [START_REF] Demillo | Hints on test data selection: Help for the practicing programmer[END_REF] to evaluate the generated test sets. As result of pattern coverage use we could observe a reduction on the test set size and the preservation of the quality level for the pattern coverage test set.

The remainder of this article is organized as follows. Section 2 presents the basic theoretical foundation used to the work presentation. Section 3 define the pattern coverage criterion and present the test data generation algorithm. The Section 4 present the evaluation process and the results obtained during the process. Related work is discussed in Section 5, followed by concluding remarks in Section 6.

Background

In this section we briefly introduce and discuss the theoretical background on which this paper is based. First, in Section 2.1, some grammar-based testing concepts are introduced and discussed. Then, we define pattern matching, the mechanism used to simplify the structure of meta programs and that our proposal uses to make meta program testing more efficient.

Grammar-based Testing

There are many different criteria for software testing in the literature. They may be classified in different (often orthogonal) ways, depending on: the stage of the software development in which they are to be applied (e.g., unit, system or regression testing), the reference artifact used for test design (e.g., white and black box testing), the kind of abstraction used to extract requirements from the reference artifact (e.g., graphs, logical expressions or grammars).

As pointed out in [START_REF] Ammann | Introduction to Software Testing[END_REF], the most important classification when it comes to define or chose a criterion is the used abstraction. As our focus here are meta programs, and the classical way of dealing with criteria-based test design for meta programs is through grammar-based coverage criteria, where tests are derived from grammar descriptions of the software or of some software artifact. As these criteria are defined in terms of grammar components, in the following, we present the definition of the most commonly used type of grammar (Context-Free Grammar (CFG)) where those components are introduced.

Definition 1 (Context-Free Grammar). A Context-Free Grammar G is a 4-tuple (N, S, T, P ) such that:

1. N is a finite set of nonterminals; 2. T is a finite set of terminals; 3. P is a finite subset of N × (T ∪ N ) * called production rules 4. S ∈ N is a start symbol.

Every grammar G defines a language (set of sentences), which is noted L(G). The sentences of the language are the sequences of terminals of G which can be derived from the initial symbol S by sequences of production rule applications (derivations) 6 .

The grammar-based test design process starts with the application of the chosen criterion to the grammar to define a set of test requirements. These test requirements specify properties that need to be satisfied by the set of test cases (test set), and a test requirement is said to be satisfied if at least one of the test cases of the test set satisfies the specified property.

The typical grammar-based test criteria are defined in terms of terminals, production rules or language sentences or derivations.

Definition 2 (Grammar-based Coverage Criteria). For a grammar G = (N, S, T, P ), -Terminal Coverage (TSC): for each terminal symbol t ∈ T there exists exactly one test requirement: t occurs in the sentence, or, simply, t. So, T SC = {t ∈ T } is the set of test requirements to cover this criterion; -Production Coverage (PDC): for each production rule ρ ∈ P there exists exactly one test requirement: ρ is used in the derivation of the sentence, or, simply, ρ. So, P DC = {ρ ∈ P } is the set of test requirements to cover this criterion; -Derivation Coverage (DC): for a grammar G, each derivation represented by s ∈ L(G) one test requirement. So, the set DC = {s ∈ L(G)} represents all test requirements to cover this criterion.

While Terminal Coverage and Production Coverage usually require a small amount of test cases (test sentences) to be attained, Derivation Coverage is obviously impossible to achieve in most cases. A variant is often used [START_REF] Lämmel | Controllable combinatorial coverage in grammarbased testing[END_REF][START_REF] Moreira | Application of a syntaxbased testing method and tool to software product lines[END_REF], then, which is to limit the length of the considered strings or derivations to some fixed limit and define as requirements the subset of L(G) up to length n.

There are some tools that use those coverage criteria to generate test cases, for example the YouGen [START_REF] Hoffman | Grammar-based test generation with yougen[END_REF], XTextGen [START_REF] Härtel | Test-data generation for xtext[END_REF] and LGen [START_REF] Moreira | Application of a syntaxbased testing method and tool to software product lines[END_REF] tools. These tools

N. Instruction Description 1 int x := 3;
Typed pattern, the x variable is bound to value 3.

2 if ( add (l , r ) := add ( var ( " x " ) , var ( " y " )))

println ( l + " ," r );

Constructor pattern, the identifier add is the constructor and the variables l and r are bound to values var("x") and var("b"), respectively.

3 for (/ str x := add ( var ( " x " ) , var ( " y " ))) println ( x );

Deep matching pattern, the matching can happen on any level of the term. Table 1. Example of some pattern-based instructions in Rascal.

basically receive a context-free grammar as input and some additional restrictions and generate a set of test cases (language sentences). These restrictions are necessary to limit the size of the resulting set, since, in general, the language associated to the input grammar is infinite.

Pattern Matching Mechanism

Pattern matching is a programming language feature. It is common to implement meta programs using pattern matching because it facilitates the description of interesting cases over the object language and dubs as a de-structuring variable binding mechanism.

Formally, the pattern matching problem is, given two terms s and l, determine if there is a substitution σ, such that σ(l) = s [START_REF] Baader | Term Rewriting and All That[END_REF]. The substitution itself, if it exists, represents the binding of variables which can be used by the program after the match.

Table 1 depicts a number of pattern types as used in the Rascal language [START_REF] Klint | Rascal: A domain specific language for source code analysis and manipulation[END_REF]. Each line shows a value on the right and a pattern on the left of the match := operator.

A most basic form of pattern, the congruence pattern, is an arbitrarily nested expression using only constructors and open variables. On table item 2, a pattern is used as a condition to the if statement. The congruence match succeeds because the value builds and add term, which the pattern matches literally. Then the children of the add term, var("x") and var("y") can be matched to the unconditional variables l and r respectively. The l and r variables may now be used in the program as normal variables, for example by printing them.

A more advanced pattern is the deep match on table item 3. It can be arbitrarily combined with any other match operator; in this case a typed variable. The current pattern will recursively traverse the matched value and succeed if a value of type str is found anywhere or fail otherwise. Such a pattern is nonunitary in the sense that it could match a single value in many ways (twice in this example). Using the for loop the programmer can iterate over all possible bindings of x, namely "x" and "y". During this section, we will use a meta program (presented on Listing 1.1) as example to illustrate the concepts introduced on the section. This example is a typical implementation for the Cyclomatic Complexity (CC) [START_REF] Mccabe | A complexity measure[END_REF] algorithm. The implementation of CC is coded in Rascal and was used by Landman [START_REF] Landman | Empirical analysis of the relationship between CC and SLOC in a large corpus of Javah methods[END_REF] to calculate and analyze the correlation between the CC and source lines of code on a large corpus of Java code. For the purpose of the current paper this code is assumed to be correct. The visit statement generates a recursive traversal and each case represents a pattern to detect in the traversed tree, and after the colon (:) an action to perform when it matches (increasing a counter). Most of the cases define simple patterns which identify a particular node type, but two are more interesting, filtering only infix expressions with either && or || as operators. The same code was used into our evaluation process and it will be detailed on section 4.

Our first step to address the test of meta programs is to define a coverage criterion that formalizes the requirements for a set of test cases. On Section 3.1 we introduce this criterion. After that, we introduce on Section 3.2 a prototype of algorithm to generate a test set that contains test cases to satisfy those requirements.

A Pattern-based Coverage Criterion

Our proposal is, given some pattern information corresponding to a meta program, to generate test cases exercising these patterns, i.e., to generate sentences that match them. To systematize this strategy, we define a new coverage criterion: Definition 3 (Pattern Coverage). For a pattern-based meta program m, and P m , the set with all instances of patterns of m, the test requirement set TR contains each element of the pattern set P m . Satisfaction of each of these requirements is attained by any subject which matches the corresponding pattern.

To illustrate the pattern coverage definition, we can apply the definition to the CC implementation on Listing 1.1. For the given code the pattern set produced by collecting patterns is P m = {Statement impl, \if(_,_), \if(_,_,_), . . . , infix(_,"||",_) }. Since in Rascal functions are dispatched by patterns, the formal parameter Statement impl is also considered a pattern, namely matching only abstract syntax trees of type Statement. The set TR = P m , and to cover TR the test data must include the set of java statements that match the corresponding patterns. For example, the pattern \if(_,_) would be covered by a program including the statement "if (true) {}", and an input which covers also the patterns for the Boolean operators would be "if (true && false || true) { }".

A Simple Algorithm to Generate Pattern Covering Test Sets

We propose an effective algorithm to generate test cases from grammars which cover a selected set of patterns extracted from the meta program under test. In this algorithm, we assume one constructor in a pattern corresponds to one labeled production rule of a context-free grammar. This initial algorithm guarantees full pattern coverage but not minimality of the set of test inputs. We shall see in the evaluation that the expected amount of tests generated is already so small that optimization in this direction is not necessarily an interesting avenue.

Given the set of pattern requirements corresponding to the meta program under test, the algorithm takes the following steps, for each pattern instance on the set:

1. Identify the open variables and their type (nonterminal); 2. Create a term for each identified variable for the given type using standard grammar-based test input generation; 3. Substitute the variable by the generated term in the pattern; 4. From the start symbol of the input grammar generate a sentence in the language including the previously generated term; 5. Add the result sentence to the test set.

On the first step, the algorithm identifies the open variables inside the term and generate terms to bind with them (step 2). Next step is apply a substitution of variable by the generated term (step 3). With this, we have a term that Listing 1.2. Example of a Java sentence produced by the generation algorithm.

public class id0 { static { if ( true ) return ; } }
matches the original patterns, but it is only part of a full input program. So, we generate a sentence using the input grammar (step 4). It is created from the start symbol and needs to reach the same nonterminal associated with the partial term that was generated on the last step. This step could be easily automated by adapting the traditional grammar-based testing algorithms. Finally, the resulting sentence is added to the test set (step 5).

To illustrate the algorithm execution, we use the implementation of CC on Listing 1.1 as example. The test requirement \if(_,_) is a pattern of type constructor and it has two open variables named as _. According to step 1 in the algorithm these two variable are detected and their nonterminal symbols are identified. The next step is to create a subterm for each of them: the first is a Java Boolean expression and the second a Java statement. For example these terms could be true and return;. On step 3 the variables are substituted by these terms and the result is a new subterm, in our example, if (true) return ;. The last step to produce the test data is to generate a sentence from the grammar start symbol including the previous subterm as an instance of its corresponding nonterminal. The Listing 1.2 shows a possible resulting Java sentence generated by this algorithm for the test requirement \if(_,_).

In this paper we propose the use of patterns as reference for the definition of test data and a pattern-based coverage criterion which defines a set of test data requirements from a set of language patterns. These patterns may be extracted from different sources: from language or meta program specifications, from the patterns used in the code of the meta program, or even from a non pattern-based meta program from which some mining of patterns has been carried out.

The algorithm presented here was used in the evaluation process described in Section 4.

Evaluation

To evaluate our claim of effectiveness, we compare our new method of generating test inputs for meta programs to the state-of-art grammar-based testing methods in this section. Our evaluation is scoped to Rascal meta programs, which we assume to be representative for all meta programs which strongly depend on pattern matching.

The evaluations questions are: RQ1 : How efficient and effective are standard grammar-based testing techniques efficient for testing of Rascal meta programs? RQ2 : Is pattern-based testing more efficient and more effective than grammar-based testing for testing Rascal meta programs?

Evaluation Method

We use two variables to measure the efficiency and effectiveness of this criterion: test set size for cover a given coverage criterion and mutation score, respectively.

The mutation score is a measure of effectiveness based on the concept of mutation testing [START_REF] Ammann | Introduction to Software Testing[END_REF][START_REF] Demillo | Hints on test data selection: Help for the practicing programmer[END_REF]. Mutation testing provides a repeatable process for measuring the effectiveness of test cases and identifying disparities in (random) test sets. It involves the use of original software under test to create a variation of it that contains an artificial fault. Each fault inserted in original software produces a mutant and the specific fault injected is called mutation operator. After the application of a mutation operator the mutant is executed using the test set under evaluation, if the test indeed fails for one of the generated test cases the mutant is killed and the test set is good enough to detect that mutant operator. Otherwise, if all all tests set run without any failure, the mutant is alive and the random test case generation is deemed ineffective. For this last case there are two possibilities: the test set is indeed not good enough to trigger the mutant or the mutant is accidentally semantically equivalent to the original program. At the end, the percent of mutants killed by the test set is called mutation score.

The mutation process used in the evaluation is implemented in Rascal for Rascal. The set of mutation operators (Table 2) introduces bugs randomly, simulating programmers forgetting cases, making errors in patterns and making errors in the code that is triggered after a pattern is matched. Rascal is a patternoriented language, where patterns govern both data (binding) and control flow (conditionals) dependency. Patterns occur in the conditions of all structured control-flow statements and the parameters of functions (dynamic dispatch). Common Rascal programming errors are forgetting to update a pattern when a language has changed, accidentally overlapping patterns for which the code is then never or always executed, and writing overly restrictive patterns accidentally. The mutation operators are designed to highlight code which is executed conditionally under a pattern, in order to make observable whether and how quickly the test set can trigger code which depends on (possibly buggy) patterns.

To evaluate the efficiency, we measure the number of test cases necessary to kill 100% of the mutants.

The comparison process.

To provide an answer to the second question, we then run the same process using a test set that covers the pattern coverage criterion. The result of this second experiment is then compared with to the previous experiment. The comparison process is shown in Figure 1. The circles represent the process and the rectangles represent data. The process starts with the generation of a set of test data based on the language's context-free grammar using the algorithm in Section 3.2. An initial test data set is used with the software under test (Listing 1.1) to generate the expected results for this set of input. Since we use mutation testing to evaluate the test set effectivity we may use the not mutated version as the oracle. Given this generated test set and the generated oracle, the mutation process is started and each mutant is tested. This test process logs the two metrics (mutation score and number of test cases).

Selected languages and program under test. We use Java and Pico as the object languages for our experiment and a typical algorithm for computing the Cyclomatic Complexity (CC) [START_REF] Mccabe | A complexity measure[END_REF] of a program for both languages (see Listing 1.1). CC is a basic but non-trivial algorithm, so this evaluation should be seen as an initial experiment and proof-of-concept. Lincke et al. [START_REF] Lincke | Comparing software metrics tools[END_REF] showed how even relatively basic and often used software metric implementations are inconsistent with each other, and thus broken, underlying the relevance of a feasible method for testing them thoroughly. For the Java language, we used the Java Specification Language [START_REF] James Gosling | The Java Language Specification[END_REF] and the ANTLR Java Grammar 7 specification as references. Since Java is a big language and therefore our initial demonstration and evaluation first focuses on a smaller language with a mini grammar: Pico [START_REF] Deursen | Language Prototyping: An Algebraic Specification Approach[END_REF]. The Pico language is a small educational programming language with a Rascal implementation 8 . This initial evaluation would also detect bugs in either our implementations or our evaluation methods. After this we continue with our evaluation on the Java language. Table 3 3. Grammar statistics for Java and Pico used in the evaluation.

To generate production coverage test data we used the LGen tool [START_REF] Moreira | Application of a syntaxbased testing method and tool to software product lines[END_REF]. For both languages we generated the test data and after that ran the software under test, the cyclomatic complexity algorithms, to create the expected result and produce the complete test set.

Results for Pico Cyclomatic Complexity

For the Pico language the results obtained by the evaluation method is presented in Table 4. Using the production coverage test set we reach 100% of mutation score. It means that all mutations generated by mutation process have been killed by the test set. The pattern coverage test set we also killed all mutants, but in this case with a lower number of test cases. This results provides an initial evaluation about the pattern coverage's efficiency but without enough confidence on it because its small scale and low complexity of the Pico language. 4. Results obtained by the evaluation using the Pico language.

Results for Java Cyclomatic Complexity

The results obtained from Java case are shown in Table 5. In this case, we observe a reduction over on the number of test cases using the pattern coverage criterion. This is related to the amount of patterns used on program 1.1. Furthermore, the mutation score for this coverage criterion shows an increase in relation to the production coverage criterion. 5. Results obtained by the evaluation using the Java language.

Discussion and Threats to Validity

Even given the small size and complexity, from the Pico experiment we learn that pattern coverage may reduce the amount of required test cases dramatically without sacrificing test quality. This small demonstration can not be generalized to other languages or meta programs, but it motivates to continue investigating and served as an integration test for our experimental setup.

The Java language results show that the approach will scale to full programming languages. We observe that indeed the number of test cases drops significantly without loss of test quality.

The main threat to validity of the above observations is the size and complexity of the meta program under test, which is not representative of the broader set of meta programs we wish to target. These initial results are promising nevertheless. We expect future investigation on larger meta programs to produce more specific patterns (which does not incur an overhead since pattern extraction is linear in the size of the meta program). More specific patterns will likely lead to larger but not more test cases. We hypothesize that pattern-based testing will still outperform exhaustive grammar-based testing in the number of test cases, while we need to find out experimentally what the mutation scores will show. The mutation score is influenced by the internal complexity of the meta program which may use other kinds of predicates and queries next to pattern matching to guide control flow. More complex meta programs will also require us to extend the set of mutation operators to generate representative mutations. Our future target is a group of type analysis and type inference tools for Rascal, Java and PHP which we wish to test exhaustively.

We believe that future work to extend pattern-based testing to other application domains based on schemata and patterns may be fruitful (XML processing, DOM manipulation and model driven engineering)

Related Work

Grammar-based testing has been used in compiler testing for many years [START_REF] Boujarwah | Compiler test case generation methods: a survey and assessment[END_REF][START_REF] Kossatchev | Survey of compiler testing methods. Program[END_REF]. Compilers are a specific kind of meta programs and could be tested using similar techniques. The YouGen tool [START_REF] Hoffman | Grammar-based test generation with yougen[END_REF] generates test data based on grammar definitions, controlling depth of derivation trees based on annotations. The major difference is about the algorithm based on enumeration and filtering of the derivation trees. This also reduces the number of test data generated, but the filtering is guided only using information from the grammar. Our approach also uses information from the program under test.

In the same direction, the XTextGen [START_REF] Härtel | Test-data generation for xtext[END_REF] generates test-data based from grammars. This tool has a different approach to generate the data. It uses Cantor pairing and mandatory multiplicity control. The generation process is split into two phases. First, an enumeration process and then a semantics-directed postprocessing over the result a set of transformation. With XTextGen it should be possible, in principle, to simulate pattern-based testing as we propose in the current paper. An appropriate encoding would have to be developed to do so, which would amount to an alternative implementation of our sentence generation algorithm.

Jagannath et al. [START_REF] Jagannath | Reducing the costs of bounded-exhaustive testing[END_REF] propose several ways of reducing the cost of bounded exhaustive testing (the generalization of grammar-based testing) by test prioritization and by merging smaller inputs into fewer bigger inputs. Our approach also reduces the cost of exhaustive testing, by selecting the right test inputs to run, but in a completely different way.

SafeRefactor [START_REF] Daniel | Automated testing of refactoring engines[END_REF] also uses bounded exhaustive search for generating test programs (in AST format and for the purpose of refactoring tools). A key ingredient is programmable specialization of the generated ASTs to better fit the specific meta program under test. This framework, which was elaborated on later for scalability [START_REF] Mongiovi | Scaling testing of refactoring engines[END_REF][START_REF] Soares | Automated behavioral testing of refactoring engines[END_REF], could be extended with our approach to automatically feedback patterns back into the AST generators.

With concolic testing [START_REF] Sen | Cute: A concolic unit testing engine for c[END_REF] a similar effect of selecting the right test cases could be achieved as our approach can. Concolic testing is based on symbolically simulating a program for a given test input and using a SMT solver or theorem prover to generate the next input which will cover a different execution path than the previous test input did. One would need to add a theory for grammar and pattern matching to the solver and a simulation engine for the meta language for this approach to work. Our approach is different and much more lightweight, neither requiring a hard-to-obtain efficient solver nor a symbolic execution engine, just a pattern extraction tool and a grammar-based sentence generator.

Conclusions and Future Work

In this paper, we presented a new coverage criterion for test case design, pattern coverage) and its preliminary evaluation of effectiveness in the context of pattern-based meta programs. The evaluation considered the amount of test cases and mutation score, taking as reference traditional grammar-based testing. We conclude that our experiments indicate a significant reduction in necessary test cases to achieve coverage, while improving the quality of the tests in terms of mutation score. Further evaluation with a richer set of meta programs and mutation operators is planned in the next steps of the research.

This work is part of a more general research direction in which we are investigating lightweight techniques to more effectively test meta programs: extracting constraints from the source code of the programs under test (or their specifications) to direct a sentence generator.

Fig. 1 .

 1 Fig. 1. An overview of evaluation process.

  Listing 1.1. Example of a pattern-based meta program written in Rascal[START_REF] Landman | Empirical analysis of the relationship between CC and SLOC in a large corpus of Javah methods[END_REF].

		int calcCC ( Statement impl ) {
		int result = 1;
		visit ( impl ) {
		case \ if (_ , _ ) : result += 1;
		case \ if (_ ,_ , _ ) : result += 1;
		case \ case ( _ ) : result += 1;
		case \ do (_ , _ ) : result += 1;
		case \ while (_ , _ ) : result += 1;
		case \ for (_ ,_ , _ ) : result += 1;
	10	case \ for (_ ,_ ,_ , _ ) : result += 1;
	11	case \ foreach (_ ,_ , _ ) : result += 1;
	12	case \ catch (_ , _ ): result += 1;
	13	case \ conditional (_ ,_ , _ ): result += 1;
	14	case \ infix (_ , " && " ,_ ) : result += 1;
	15	case \ infix (_ , " || " ,_ ) : result += 1;
	16	}
	17	return result ; }
		3 Testing Meta Programs Using Pattern Coverage

Our proposal to deal with the original problem is to use the pattern information related to a meta program and with it generate a test set that will be used in the test process. This strategy may be applied on white-box testing, if the patterns are derived from the program, or black-box testing, if they are extracted from some more abstract model or specification of the meta program.

Table 2 .

 2 Table of Rascal Mutation Operators.

	Operator Code	Description
	OP0	Remove pattern rewrite.
	OP1	Remove pattern with action.
	OP2	Remove if conditionals. Simple if.
	OP3	Remove if conditionals. Remove if code block.
	OP4	Remove if conditionals. Remove else code block.
	OP5	Remove while conditionals.
	OP6	Remove for conditionals.

  lists the sizes of the Pico and Java grammars we used.

	Structure	Size Pico Java
	Production Rules 18 272
	Terminals	23	98
	Nonterminals	9	142
	Table

In the absence of grammar ambiguity, there is a one-to-one correspondence between sentences and derivation. We assume here non ambiguous grammars to simplify presentation.

https://github.com/antlr/examples-v3/blob/master/java/java/Java.g

http://tutor.rascal-mpl.org/Recipes/Languages/Pico/Pico.html