Dominique Colnet
email: dominique.colnet@loria.fr

Luigi Liquori
email: luigi.liquori@loria.fr

Match-O, a Dialect of Eiffel with Match-Types

It is well known that the Eiffel language allows covariant redefinition. Regardless of system-level validity rules, Eiffel is not type safe. In this paper, we present a dialect of Eiffel called Match-O, which prohibits covariant redefinition. We introduce a new kind of types, the match-types, inspired by the papers of Kim Bruce. The scope of this project is many-fold: -allowing binary methods; -keeping sound "mytype method specialization", i.e. anchored type using Current; -allowing subtyping in all other sound cases. We claim that match-types can be added in the Eiffel type system to eliminate type unsoundness without blocking many interesting Eiffel programs (e.g. the ones with "binary methods"). We have implemented a compiler for Match-O and we have experimented our dialect on a large system using the original source code of SmallEiffel itself.

1: Introduction

None of the existing Eiffel compilers implement the system-level validity rules described in [START_REF] Meyer | Eiffel, The Language[END_REF]. As a consequence, an Eiffel program may crash because of run-time type check errors. The main reason for this type unsafety problem are: binary methods [START_REF] Bruce | The Hopkins Object Group[END_REF][START_REF] Castagna | Covariance and Contravariance: Conflict Without a Cause[END_REF][START_REF] Castagna | Object-Oriented Programming: A Unified Foundation[END_REF], unsafe use of subtyping, the possibility to specialize (i.e. override) the body of methods in subclasses, the type like Current in argument position, and many more (see [START_REF] Cook | A Proposal to Make Eiffel Type Safe[END_REF]). This paper presents a real experience to make a statically safe dialect of Eiffel -with extensions and restrictions -without loosing much of its expressiveness.

Eiffel is the only widely used language featuring the possibility to denote a type using the type of the receiver itself. Such an anchored type is denoted by like Current to express the fact that some entity is compatible with the type of the receiver. Specialization of the results. Assume a method foo:like Current is defined in class a and redefined in subclass b of a with the same signature. For a variable a of type a, the type of the expression a.foo is a. For a variable b of type b, the type of the expression b.foo is b. This means that the type of the result specializes as the body does. Note that only static information is used here to type such expressions. In other words, the fact that variable a may reference an instance of b at run-time is not considered when typing Eiffel expressions.

Specialization of the arguments. Assume a method doo(other:like Current) is defined in class a and redefined in a subclass b of a with the same signature. Such a method is usually called a binary method because it takes as argument an object which has the same type as the receiver. Invoking doo with a target a of type a with another variable of type a as argument (i.e. a.doo(another a)) is a correct typable call. Similarly, invoking doo with a target b of type b, with another variable of type b as argument (i.e. b.doo(another b)) is also a valid call.

As for the specialization of the result, only static type information is used to accept or reject some calls. For example, b.doo(a) is statically rejected by Eiffel rules because the type of a -i.e. a -is not compatible with the type of b (a is not a subtype of b).

Like Current with subtyping and inheritance. Unfortunately, in Eiffel , as in most object-oriented languages, if b is a subclass of a, b is also a subtype of a. Actually, a variable of type a can be assigned with an expression of type b as in the instruction a := b, and an expression of type b is a valid actual parameter for a formal argument of type a as in the call a.doo(b).

As a consequence, combining like Current (i.e. the mytype method specialization) with subtyping and inheritance (i.e. the method specialization), we obtain the well-known problem presented below: In this trivial program we observe that the "subtyping routine", present in the Eiffel type checker, can be triggered in two ways: through a simple assignment (1) or using argument passing (2). In both situations, the problem arises at run-time, while accessing the inexistent status attribute of an instance of class point, hence producing a run-time crash. This example points out the fact that a subclass is not always a subtype (for a rich and detailed discussion, see [START_REF] Bruce | The Hopkins Object Group[END_REF][START_REF] Cook | Inheritance is not Subtyping[END_REF]).

The choices of Match-O are rather simple and are based on a simple restriction plus a simple extension of the Eiffel type system; this solution is inspired by Bruce's papers and the Undergraduate Honor Thesis of Jonathan Burstein [START_REF] Burstein | Rupiah: an Extension to Java Supporting Match-bounded Parametric Polymorphism, ThisType, and Exact Typing[END_REF]. The Match-O dialect is obtained by applying the following Extension/Restriction to Eiffel : Extension: We add a type keyword, namely "match", which can prefix any legal explicit non anchored type mark, and we add the new type "match Current".

Restriction: We eliminate the Eiffel type "like Current" and we forbid covariant specialization in subclasses, with the only exception of match Current.

Intuitively, a variable declared of type match point can only be assigned with an expression which is exactly of type point. As an example, an expression of type pixel cannot be assigned to a variable of type match point. Respectively, a variable of type match Current has exactly the same dynamic type as Current. Roughly speaking, using match-types is a way to block the subtyping mechanism. Since we do have unsound covariant specialization, the construct like x is still allowed, also in the case of x declared of type match Current. If a variable or a formal parameter is declared of type like x, then its concrete type is calculated by a syntactic replacement of the type of x (also if its type is match Current).

It follows that all "match-free" Eiffel programs which do (not) respect the typing Match-O rules are (not) accepted by the compiler of Match-O, and the Match-O language has enough expressiveness to encode binary methods (i.e. methods with some arguments typed with match Current). As such, the language Match-O features sound subtyping in presence of a non-trivial form of covariant specialization (i.e. the one related to the use of match Current).

Road map. Section 2 presents the theoretical background of our proposition as well as its translation into Match-O. Section 3 describes how match-types can be smoothly integrated to Eiffel and its libraries. Section 4 explains some problems we encountered while trying to bootstrap the Match-O compiler. Section 5 concludes and presents some related work, together with some future work.

2: The Match-O types

A great theoretical effort has been devoted in the last years to finding sound and expressive type systems [START_REF] Bruce | Safe Type Checking in a Statically-typed Object-oriented Programming Language[END_REF][START_REF] Bruce | A Paradigmatic Object-Oriented Programming Language: Design, Static Typing and Semantics[END_REF][START_REF] Bruce | PolyToil: a Type-safe Polymorphic Object Oriented Language[END_REF][START_REF] Bruce | Subtyping is not a Good Match for Object-oriented Programming Languages[END_REF][START_REF] Abadi | A Theory of Objects[END_REF][START_REF] Fisher | A Delegation-based Object Calculus with Subtyping[END_REF][START_REF] Liquori | A Typed Lambda Calculus of Objects[END_REF][START_REF] Liquori | An Extended Theory of Primitive Objects: First Order System[END_REF][START_REF] Rémy | From Classes to Objects via Subtyping[END_REF][START_REF] Riecke | Privacy via Subsumption[END_REF][START_REF] Bono | Subtyping for Extensible, Incomplete Objects[END_REF][START_REF] Rinat | Type-safe Covariant Specialization with Generalized Matching[END_REF] featuring a subtyping relation compatible with mytype method specialization.

The matching relation over object-types. In Bruce's theory, an object-type (essentially a type-interface) has the form OT v i : a i , m j : b j i∈I j∈J , where OT is a binder for the type-variable Mytype (representing the type of Current), v i : a i are the instance variables with their types, and m j : b j are the methods and their results types, respectively. The type-variable Mytype can freely occurs in the a i , b j and represents the type of Current.

The matching relation is a type-relation weaker than the subtyping relation. Matching over object-types behaves as follows: two object-types matches (denoted by <# ) if the former has more variables and/or methods than the latter. The very intuitive semantics of a <# b, is that any message sent to an object of type b can also be sent to an object of type a. Conversely, the intuition for subtyping (denoted by <: ) is slightly different: given a <: b, an object of type a can be used in every context which expects an object of type b. As example, if we consider only type-interfaces, we can say that pixel <# point, but pixel <: point.

2.1: Exact and hash-types

Exact-types. In [START_REF] Burstein | Rupiah: an Extension to Java Supporting Match-bounded Parametric Polymorphism, ThisType, and Exact Typing[END_REF], Burstein introduced (in the context of an extension of the Java language) the exact-types (denoted by @a) to represent types whose elements are not susceptible to be subsumed. The intuitive meaning of the exact-types is as follows: objects typed with an exact-type are type-checked with a more restrictive algorithm, namely without the subtyping routine. This rigidity in the type system will block many assignments and method calls.

When a program only uses variables declared of type "@" it contains only exactexpressions, and hence it conforms to the matching-based theory of Bruce [START_REF] Bruce | A Paradigmatic Object-Oriented Programming Language: Design, Static Typing and Semantics[END_REF]. In fact, exact-types are the Bruce object-types.

Hash-types. In [START_REF] Bruce | Subtyping is not a Good Match for Object-oriented Programming Languages[END_REF] Bruce introduced another kind of type, the hash-types (denoted by #a). The intuitive meaning of the hash-types is as follows: objects typed with a hash-type are type-checked with a less restrictive algorithm, namely with the subtyping routine. An unfortunate feature of hash-types is that binary methods (i.e. methods which take formal parameters of the same type of the receiver, and specialize its signature in subclasses) cannot be sent to hash-typeable objects.

Is MyType @ or # ? Given Mytype, the type of Current and the above two shapes of types, one natural question that may arise is: "is Mytype an exact-type or a hash-type?" The difference is substantial since the type rules for message sending we want to apply are not the same at all. Both views are correct; for instance, if the receiver a is typed with type @a (resp. #a), and it contains in its interface a method foo which returns an object of type Mytype, then a.foo() will be of type @a (resp. #a).

2.2:

The Match-O translation of @ and # Let a be any concrete type. The interpretation in Match-O of an exact-type @a is match a, whereas that of a hash-type #a is simply a. The interpretation of Mytype is match Current, i.e. the dynamic type of Current. Every time we declare a class a in Match-O, we (implicitly) declare another class match a which "specializes" a.

Following the symmetry between exact and hash-types, in Match-O we have two kinds of objects: objects assigned to concrete types (type-checked with the subtyping routine), and objects assigned to match-types (type-checked without the subtyping routine).

The subtyping relation between concrete and match-types says that the type match a is a subtype of the concrete type a. This is sound with respect to our interpretation of hash and exact-types into match and concrete types. Following this rule, an entity declared of type match a can be also considered as an object of type a.

Another usual rule for objects activates the subtyping routine in the Match-O type system; an object type-checked of type a can masquerade as an object of type b, being a a subtype of b.

2.3: Assignments, passing parameters, and sending messages in Match-O

Assignment in Match-O. The type rules for assignment in Match-O are rather simple. Let a be any concrete type. The rationale is as follows: variables declared of type match a can be assigned only to expressions of the same exact type (i.e. match a). Counterwise, variables declared of type a can be both assigned with expressions of type match a, or a, and any subtype of a.

Let b be a subclass of a; the following table gives the type checking rules for the assignment instruction: "destination := source;". The types of the destination variable are listed in the column, while the types of the source expression are listed in the rows: Note that the type of the receiver is used only to guarantee that foo is in the interface of a.

A different issue is raised when we declare a parameter of type match Current i.e. binary(x:match Current):c. In this case the rationale is as follows: the receiver must be typed with a match-type and the argument must be typed with exactly the same matchtype, i.e. if a: match a and b:match b, the call a.binary(b) is rejected. We will see in Section 3 that this restriction still allows for expressivity and that it only has a minor practical impact from the software engineering point of view.

Sending messages which return match Current. The rules for sending a message which returns an object of type match Current are simple. Given an expression receiver.message(arg list), the type of this expression just follows the type of the receiver: Observe that the type of arg list is not needed for calculating the type of the result. For instance, let twin be a method defined in class a (and inherited in a subclass b of a) which returns a copy of the object itself, i.e. "twin: match Current is ...", and let a: a, ma: match a, b: b, and mb: match b. Then, a.twin (resp. ma.twin) will return an object of type a (resp. match a), while b.twin (resp. mb.twin) will return an object of type b (resp. match b). This is sound since the type match Current represents the type of the receiver.

3: From Eiffel to Match-O

In order to explain the behavior of match-types, we present some more Match-O examples in this Section, as well as some decisions we made to merge this new kind of type with the existing Eiffel language and libraries. This section should also help to clarify the usage of the new match-types from the programmer's point of view.

In the following examples, we assume that we have defined in Match-O both classes point and pixel, where pixel is a subclass of point. To avoid repetition and for clarity, we assume in all the remainder of this paper that the variable match point is declared of type match point, that the variable match pixel is declared of type match pixel, the variable match current is declared of type match Current, etc. We also assume that the variable point is declared of type point, that the variable pixel is declared of type pixel, etc. This naming scheme also applies to all standard Eiffel type names; for example, a variable whose name is match string is declared with type match string.

3.1: Expanded and Match-types, manifest constants, and the type of Current

When a class c is declared as an expanded class, entities of type c are values which are instances of class c and only of class c [START_REF] Meyer | Eiffel, The Language[END_REF]. Despite the fact that the initial purpose of expanded types in Eiffel is to avoid the need for a reference to the corresponding object, the relationship between expanded types and match-types clearly appears. If c is an expanded type, it is also a match-type, because, by definition, entities of type c always denotes an object of class c only. As an example, because the class integer is expanded, the type integer is completely equivalent to the type match integer. Thus, the notation of integer constants, such as 1 or 2, also denote objects of type match integer. As a consequence, the following assignments are allowed in Match-O: match_integer := 1; --is accepted.

match_character := 'a'; --is accepted.

Following the same reasoning, the type of manifest strings, such as "foo", is no longer string but, more precisely, match string; hence the assignment match_string := "foo"; --is accepted.

Because the type match string is a subtype of string, the ordinary assignment of some manifest string into a variable of type string is also allowed, making old existing Eiffel code compatible with the Match-O dialect.

Typing of manifest arrays is also reconsidered the same way in Match-O. For example, the manifest array <<"foo","bar">>, which is of type array[string] in Eiffel , has in Match-O the type match array[match string]. Consequently, the following assignments are both accepted: match_string := (<<"foo", "bar">>).item(1); --is accepted. string := (<<"zoo", "doo">>).item(1); --is accepted.

Typing Current. The problem of the type of the pseudo-variable Current is a bit less obvious. For example, what is the type of Current inside some method defined in the class point (and inherited in a subclass pixel)? Is it point, match point, pixel, or match pixel? The correct answer is match Current, but, as showed in the previous Section, the semantic meaning of Current (hence of match Current) is context dependent (i.e. it depends on the dynamic type of the target).

Taking as example some assignments, when the target is of dynamic type point (resp. pixel), the following instructions are safe and accepted. We assume here that match current, match point, and point are variables declared inside a method of class point:

Target of dynamic type Point

Target of dynamic type Pixel match_current := Current; --is accepted. match_current := Current; --is accepted. match_point := Current; --is accepted. match_point := Current; --is rejected. point := Current; --is accepted. point := Current; --is accepted.

In other words, each method (even when there is no redefinition) is considered for each possible dynamic type and checked accordingly. This is perfectly in agreement with our whole system analysis algorithm which already performs code customization for each possible concrete type (see for more details [START_REF] Collin | Type Inference for Late Binding. The SmallEiffel Compiler[END_REF][START_REF] Zendra | Efficient Dynamic Dispatch without Virtual Function Tables. The SmallEiffel Compiler[END_REF]).

3.2: Adapting some Eiffel constructs

In order to fit with the new match-types, we also have to adapt the behavior of two important constructs of the Eiffel language: the creation instruction and the assignment attempt.

The creation instruction. The Eiffel creation instruction allows the user to select the concrete class to instantiate, which may be different from the static type of the destination variable. When we declare a variable of a match-type, the revisited Match-O creation instruction avoids the possibility to assign an instance of class pixel into some match point variable: !!match_point.set(1.0,2.0); --create a POINT. !POINT!match_point.set(1.0,2.0); --is accepted. !PIXEL!match_point.set(1.0,2.0); --is rejected.

Once more, this decision enforces the fact that a match-typed variable can only hold one dynamic type, the matched one.

The assignment attempt. The Eiffel assignment attempt operator ?= provides a safe way to go down in type hierarchy [START_REF] Meyer | Eiffel, The Language[END_REF]. Because the variable point may reference a pixel at run-time, the assignment of point into pixel makes sense but is not always applicable.

As for the creation instruction, the customization of the assignment attempt for matchtypes is guided by type safety. When the right-hand-side of the assignment attempt is a match-type, only the corresponding exact dynamic type will make the assignment effective. From the implementation point of view, the generated code for an assignment attempt with a right-hand side variable typed with a match-type is a simple efficient conditional expression with only one hard-coded possibility. When the right-hand side is not a matchtype, instead, the number of accepted possibilities can be greater than 1 and thus less efficient (see [START_REF] Colnet | Optimizations of Eiffel programs: SmallEiffel, The GNU Eiffel Compiler[END_REF] for a detailed description of code customization for the ?= assignment).

3.3: Typing some interesting methods

An accurate signature for the twin method. The twin method defined in the general class is the basic object's duplication primitive of the SmallEiffel library. This method is originally defined in Eiffel with the following signature: Because of the usage of the like Current type mark, the previous signature is not valid in Match-O. Furthermore, because the purpose of the twin method is to create a new object with the exact dynamic type of the target, the new Match-O signature we have chosen is more accurate now: twin: match Current is ...

--The new Match-O signature.

According to the rules explained before, here is the Match-O behavior for clients of method twin:

match_string := ("foo").twin; --is accepted. string := ("bar").twin; --is accepted. match_string := string.twin; --is rejected.

Indeed, the type of the expression point.twin is point (not match point) avoiding the possibility to assign a pixel into a match point variable:

point := match_pixel; --is accepted. match_point := point.twin; --is rejected.
This new definition of method twin using match Current as a result type is more accurate and is backward compatible with existing Eiffel code.

A safe definition of is equal. The Eiffel definition of is equal, rejected in Match-O, must be modified in order to remove the like Current type mark used in argument position: A close look at the symmetric: part of the ensure clause reveals that the is equal feature itself is recursively called with Current and other swapped (i.e. other.is equal(Current)). This information from the ensure assertion reveals the very nature of is equal: only two objects with exactly the same dynamic type can be considered to be equal. Knowing this, the very first idea is to change the signature of is equal as follows:

is_equal(other: match Current): BOOLEAN is do ... end;

The obvious advantage would be to make is equal type safe. Unfortunately, this modification breaks a lot of existing code, just because you can use is equal only with match-types both for the target and the argument. Another possibility is to introduce a new method we called match is equal and to redefine a safe version of is equal without covariance, to wrap this method: The assignment attempt ?= is used to know if the dynamic type of other is the one of Current. Inside the then part, the match is equal method is called to finish the comparison process. When the then part is not executed (because the other argument has a different dynamic type), the Result variable keeps its default false value.

The new match is equal function is implemented with a compiler built-in field by field comparison, as in the original Eiffel is equal definition. Because match is equal is type safe, the built-in code, which performs the field by field comparison, no longer needs to check that both objects have the same dynamic type, just because this is statically enforced.

Finally, the new signature of is equal uses the ANY type, making the new definition applicable to any kind of object. This is more tolerant than the original definition in Eiffel and allows backward compatibility.

4: Towards a bootstrap of the Match-O compiler

Starting from the original source code of SmallEiffel, a large program of about 300 classes for about 80K lines of source code, we have progressively worked to obtain our first compiler for Match-O. Before trying to bootstrap our compiler itself, we have validated our first release of the Match-O compiler, written in Eiffel , with a set of examples including correct Match-O programs as well as rejected Match-O programs (those examples are part of the Match-O distribution). We then started to modify the Match-O compiler written in Eiffel, trying to obtain a compiler written in pure Match-O. During this last process, except for one covariant redefinition we will see below, the transformation from Eiffel to Match-O appears to be quite straightforward.

The remainder of this section points out the problems we encountered to migrate our compiler written in Eiffel to the current one which is nearly written in pure Match-O. The result of this experiment should also help other people to switch their unsafe Eiffel code to Match-O safe code.

Tracking unsafe generic dispatches. The most common problem encountered during bootstrap attempts was related to dynamic dispatch when using a generic container with an indirect unsafe covariant derivation. Here is a very simple example of some accepted Eiffel code which points out a safety problem: Because the type array[pixel] is considered to be a subclass of array[point], the previous assignment (1) is valid in Eiffel. The instruction (2) allows storing an instance of class point into an array[pixel], which is obviously wrong and dangerous. Finally, because the same array is referenced by array of pixel, it is possible to assign a point into the pixel variable as done with instruction (3). Unfortunately, this erroneous program is accepted by all Eiffel compilers, because none of them implements the system-level validity rules. Running such a wrong program leads to a run-time type exception error.

The previous example is statically rejected by our Match-O compiler, which reports a compile time covariance error for the instruction (2). Indeed, the put procedure of class array is covariantly redefined from array[point] to array[pixel]: the first argument cannot be changed from point to pixel in Match-O. To fix this problem, one must change the type of array of point to match array [point]. With this simple modification the assignment (1), which is actually at the origin of the problem is now statically rejected and the put call (2) is now accepted in Match-O. Furthermore, because the target of the call (2) has only one possible dynamic type (i.e. array[point]), the Match-O generated code is a direct fast call.

From like Current to match Current. Many other detected problems come from the like Current type which is often used just because match Current does not exist in Eiffel . The most important example is the definition of twin (previously explained in Subsection 3.3). The goal of twin is to return an object of the same dynamic type as its target. Furthermore, the replacement from like Current to match Current as a result type does not break the client code. Unfortunately, such a replacement in argument type position often implies a lot of modifications, because all calls to the modified method must be a target of the corresponding match type, as explained in Subsection 2.3.

Since like Current does not belong to the Match-O types, it is mandatory to remove all occurrences of like Current in argument position. As we have previously seen in the new definition of is equal (in Subsection 3.3), it is sometimes better to replace a like Current type with another concrete type, i.e. no more anchored type. At the time being, the Match-O rule which prohibits like-notations (i.e. like Current, like feature, and like argument) in argument position is not systematically enforced in the compiler code. Actually, as we will see below, a like-notation does not always imply covariant redefinition.

Accepting invariable like-notations. During the bootstrap, a significant number of like-notations proved actually be a useful short-hand notation for some unique invariable concrete type name. The following table gives the type notations used in the live code of the compiler during the bootstrap: The column Attribute shows that the Match-O rules are strictly enforced for the type of attributes: the like-notation is never used and the most common type notation (line Concrete types) is the simple explicit notation. The result type of functions given in column Result shows that match Current is quite often used. This is mainly because of the result type of the twin function. By looking at the table, one may observe that our Match-O compiler does not prohibit all like-notations in argument position: for instance, in the Argument column, 112 like Current and 820 like feature are used and accepted. This is clearly a violation of the strict Match-O rules explained in Section 1. Because our Match-O compiler performs whole system analysis [START_REF] Zendra | Efficient Dynamic Dispatch without Virtual Function Tables. The SmallEiffel Compiler[END_REF] it is possible to safely accept such like-notations. Actually, those like-notations are equivalent to explicit type notations, i.e. each accepted like-notation appears to only have one possible concrete substitution with one unique concrete type. For all those accepted like-notations, the knowledge of the whole system allows us to check that there is no covariance at all.

A hard covariance removal. During the bootstrap process of the Match-O compiler, only one covariant problem was not easy to fix using, for example, a simple declaration type modification. This is the only use of covariance without generic interaction we found in the whole original compiler source code.

The class local var list is used to represent local variable lists, while class formal arg list is used to represent formal argument lists. Those classes both inherit from the abstract (i.e. never created) declaration list class in order to share a few template methods. The type of elements in declaration list is then covariantly redefined in class local var list to handle local variable items and also redefined in class formal arg list to handle argument names items.

In order to make the code type safe, it was necessary to duplicate the invalid template methods originally factorized in class declaration list. This is the only place in the whole Match-O compiler where such an important modification was necessary to avoid covariance. At least for the present implementation of the Match-O compiler, this points out the fact that covariance is not as widely used as one may imagine.

5: Related, further work and conclusion

Related work. Among the interesting related works we would like to mention, we recall the following ones: the language Rupiah [9], a dialect of Java with match-types, the language Tool [START_REF] Gawecki | Integrating Subtyping, Matching, and Type Quantification: a Practical Perspective[END_REF], that integrates matching, subtyping, and parametric-types, and the language PolyToil [START_REF] Bruce | PolyToil: a Type-safe Polymorphic Object Oriented Language[END_REF], probably the first language integrating matching and subtyping.

The choice of blocking covariance is not the only one: [START_REF] Thorup | Genericity in Java with Virtual Types[END_REF] added virtual-types (or virtualmethods) to Java, in the style of the Beta language [START_REF] Madsen | Object-Oriented Programming in the Beta Programming Language[END_REF]. This solution gives the possibility to covariantly specialize variables and method-types, but it requires some extra run-time type checks to ensure type safety. In [START_REF] Bruce | A Statically Safe Alternative to Virtual Types[END_REF][START_REF] Togersen | Virtual Types are Statically Safe[END_REF] the authors proposed, independently, two different solutions to make virtual-methods statically safe. Recently, the LGM language [START_REF] Rinat | Type-safe Covariant Specialization with Generalized Matching[END_REF] proposed another solution to the problem of covariance using Bruce's generalized matching [START_REF] Bruce | A Paradigmatic Object-Oriented Programming Language: Design, Static Typing and Semantics[END_REF].

The experience we have with Match-O shows that the cohabitation of matching and subtyping is fruitful and quite natural.

Further work. The question of whether Match-O is really type safe or not is a work in progress. We plan to formalize the static and the dynamic semantics of Match-O, and to explore the possibility to generalize the match construct to the case of formal generic arguments. Another interesting possible further work is the efficient implementation of Eiffel system-level validity rules combined with match-types.

Conclusions. We have experimented match-types in the Eiffel language. The Match-O compiler is available at http://www.loria.fr/∼colnet/Match-O/macho.tgz. The distribution also includes a large set of examples showing that many unsafe programs can be statically rejected without the need for system-level validity rules.

From the designer's point of view, match-types appear to add expressiveness and accuracy in many situations. The possibility to use match Current in place of like Current also seems to make acceptable the decision which consists in forbidding covariant redefinition.

  Accepted match aRejected Accepted Rejected Rejected bRejected Rejected Accepted Accepted match bRejected Rejected Rejected AcceptedFor example, the assignment of a source expression of type b into a destination variable of type match a is rejected since b is not a subtype of match a; counterwise, the assignment of a source expression of type match b to a destination variable of type b is is accepted since match b is a subtype of b.Passing parameters in Match-O. The type rules for passing parameters in Match-O are the same as the ones for assignment (with the only exception of declaring a formal parameter of type match Current). In the simplest case, you can consider the above table for assignments, where destination\source is substituted by formal arg\actual arg. For instance, let a and c be concrete classes, and let foo(x:a):c be a method declared in class a (and inherited in a subclass b of a). Let a:a and b:match b. The call a.foo(b) is accepted, since the actual parameter b is of type match b, match b being a subtype of b.

  receiver a match a b match b receiver.message(arg list) a match a b match b

  match_pixel ?= point; if match_pixel /= Void then ... --match_pixel is now an alias for point. else ... --The dynamic type of point is not a PIXEL. end;

  twin: like Current is ...--The old Eiffel signature.

  local point: POINT; pixel: PIXEL; array_of_points: ARRAY[POINT]; array_of_pixels: ARRAY[PIXEL]; do !!point; !!array_of_pixels.make(1,1); !!array_of_points.make(1

Acknowledgments. We would like like to thank Karl Tombre for reviewing of this paper.


Pascal Gillet
email: pascalgillet@ymail.com

Cassia Trojahn
email: cassia.trojahn@irit.fr

Ollivier Haemmerlé
email: ollivier.haemmerle@irit.fr

Camille Pradel
email: camille.pradel@irit.fr

Complex Correspondences for Query Patterns Rewriting

This paper discusses the use of complex alignments in the task of automatic query patterns rewriting. We apply this approach in SWIP, a system that allows for querying RDF data from natural language-based queries, hiding the complexity of SPARQL. SWIP is based on the use of query patterns that characterise families of queries and that are instantiated with respect to the initial user query expressed in natural language. However, these patterns are specific to the vocabulary used to describe the data source to be queried. For rewriting query patterns, we experiment ontology matching approaches in order to find complex correspondences between two ontologies describing data sources. From the alignments and initial query patterns, we rewrite these patterns in order to be able to query the data described using the target ontology. These experiments have been carried out on an ontology on the music domain and DBpedia ontology.

Introduction

Despite the fact that SPARQL is the standard de facto language for querying RDF data, its complexity may restrict its use at a large scale, specially for nonexpert RDF users. Translating natural language queries into SPARQL ones is the object of researches in both Natural Language Processing and Semantic Web fields. Within the SWIP system [START_REF] Pradel | A Semantic Web Interface Using Patterns: The SWIP System[END_REF], users express queries in natural language sentences and pre-written query patterns are instantiated with respect to a syntactic analysis of the initial query. Several possible interpretations of the queries are shown to the user which selects the query he/she is interested in. Unlike other proposals, such as the one in [START_REF] Elbassuoni | Searching RDF Graphs with SPARQL and Keywords[END_REF][START_REF] Elbassuoni | Keyword search over rdf graphs[END_REF], where user queries are limited to keywords, or in [START_REF] Russell | Nitelight: A graphical editor for sparql queries[END_REF], where users can express their queries using a visual query language, the originality of SWIP is related to the use of query patterns.

The main principle behind query patterns states that, in real applications, the submitted queries are variations of few typical query families (i.e., the family of queries asking for the actors playing in movies or the queries asking for the members of a musical band, or the albums of a musical artist). On the one hand, the use of patterns avoids exploring the whole ontology to link the semantic entities identified from the keywords since the potential relations are already expressed in the patterns. The process thus benefits from the pre-established families of frequently expressed queries for which real information needs exist.

A query pattern can also be seen as the projection of a subgraph of the underlying knowledge base, used as a mediator for the translation between the query expressed in natural language and the corresponding SPARQL query. On the other hand, one of the main limitations of the query pattern-based approach is that reusing patterns across different data sources can be done in a very limited extent. For each data source to be queried, the corresponding query patterns have to be (manually) built. Rewriting query patterns based on a vocabulary to query patterns based on another vocabulary is a task that can be carried out with the help of ontology alignments.

This paper discusses the use of complex correspondences for automatic query patterns rewriting. While the usefulness of simple correspondences has long been recognised, query rewriting requires more expressive links between ontology entities expressing the true relationships between them. At a lower level of abstraction, ontology alignments have been used to support the task of SPARQL query rewriting [START_REF] Correndo | SPARQL Query Rewriting for Implementing Data Integration over Linked Data[END_REF][START_REF] Makris | Ontology mapping and SPARQL rewriting for querying federated RDF data sources[END_REF][START_REF] Makris | SPARQL-RW: transparent query access over mapped RDF data sources[END_REF]. However, query patterns and SPARQL refer to different levels of expressivity in their representations, where query patterns are articulated as a set of subpatterns and rely solely on the T Box of ontologies. Hence, we experiment ontology matching approaches in order to find complex correspondences between two ontologies describing two different data collections. From the complex alignments and source query patterns, we rewrite these patterns in order to be able to query the data collection described using the target ontology. Experiments have been carried out on an ontology on the music domain and DBpedia ontology. As a main outcoming, we have a set of manually validated complex correspondences, from which query patterns can be reused across the data sets described using those ontologies.

The rest of the paper is organised as follows. First, we introduce complex correspondences and query patterns ( §2). Then, we present the approach for query pattern rewriting that is based on the use of complex correspondences ( §3). Next, the experiments are discussed ( §4). Finally, we discuss related work ( §5) and conclude the paper ( §6).

Foundations

Complex correspondences

Matching two ontologies is the process of generating an alignment between them [START_REF] Euzenat | Ontology Matching[END_REF]. An alignment A is directional and refers to a source ontology O and a target ontology O ′ , denoted A O→O ′ :

Definition 1 (Alignment). An alignment A O→O ′ between two ontologies O and O ′ is a set of correspondences A O→O ′ = {c 1 , c 2 , ..., c n },
where each c i is a triple e i , e ′ i , r , where:

whether the correspondence is simple, then it relates one and only one entity (i.e., a class or a property) e i of O to one and only one entity e ′ i of O ′ (1:1);

or the correspondence is complex, and it involves one or more entities in a logical formulation (1:n,m:1,m:n), where e i refers to a subset of elements ∈ O, and e ′ i refers to a subset of elements ∈ O ′ , and these elements are related using the constructors of a formal language (First-Order Logic or Description Logics); -r is a relation, e.g., equivalence (≡), more general(⊒), more specific (⊑),

holding between e i and e ′ i ; -additionally, a value n (typically in [0,1]) is assigned to c i indicating the degree of confidence that the relation r holds between the e and e ′ .

The correspondence e i , e ′ i , r is unique in A O→O ′ . On the other hand, e i or e ′ i may be present in more than one correspondence c i . The alignment A O→O ′ is said complex if it contains at least one complex correspondence. In the rest of this paper, a correspondence c i , which is a triple e i , e ′ i , r (suffix notation), will be noted e i r e ′ i . For example, F ilm ⊑ W ork is a simple correspondence and asserts that F ilm in O is more specific than W ork in O ′ . On the other hand, we can have the following two complex correspondences :

∀x, Short F ilm(x) ≡ F ilm(x) ∧ duration(x, y) ∧ y ≤ 59 (1) ∀x, Biopic(x) ≡ F ilm(x) ∧ Celebrity(y) ∧ topic(x, y) (2)
(1) asserts that a Short F ilm in O is equivalent to a F ilm in O ′ whose duration is less than 59 minutes, and (2) asserts that a Biopic (or biographical film) in O is equivalent to a F ilm in O ′ whose the topic is about a famous person. We can either use First-Order Logic (FOL) or the constructors of Description Logics (DL) for expressing the complex correspondences. In FOL, a class corresponds to a unary predicate with one variable, a property to a binary predicate with two variables, and an instance to a constant. In DL, a class corresponds to a (atomic) concept, a property to a role, and an instance to an individual. We can equally transpose logical statements from DL to FOL, and conversely, as long as the DL fragment is always respected. In particular, we take advantage of the expressivity allowed by SHOIN , describing the following DL operators: ¬C (negation of concepts), C ⊓ C (intersection or conjunction of concepts), C ⊔ C (union or disjunction of concepts), ∃R.C (existential restriction), ∀R.C (universal restriction), ≤ nR (at most restriction), ≥ nR (at least restriction). For instance, the formula (1) becomes (3) and the formula (2) becomes (4) :

Short F ilm ≡ F ilm ⊓ ∃duration. ≤ 59 (3) Biopic ≡ F ilm ⊓ ∃topic.Celebrity (4)
In a (complex) correspondence formula expressed in FOL, a variable may occur in several entities in left and right operands. Intuitively, two classes referring to the same single variable are bound and are first connected by a simple correspondence (with a subsumption relation, otherwise there is no need for an additional complex correspondence to characterise the entities involved). For instance, the formulas (1) and ( 2) are consistent only if Court metrage ⊑ F ilm and Biopic ⊑ F ilm, respectively. The use of DL in (4) requires to explicitly assert the simple correspondence Biopic ⊑ F ilm first, as we do not know if Biopic is a specialisation or rather a generalisation of F ilm or Celebrity otherwise.

Query patterns

A pattern p O targetting an ontology O is composed of an RDF graph which is the prototype of a relevant family of queries. A pattern can be composed of several subpatterns sp i , such as p O = {sp 1 , sp 2 , ..., sp n }. Subpatterns are assigned minimal and maximal cardinalities, making these subgraphs optional or repeatable when generating the final SPARQL query. Formally, a query pattern can be defined as follows [START_REF] Pradel | Des patrons modulaires de requêtes sparql dans le système swip. 23es[END_REF]:

Definition 2 (Query pattern). Let G be a graph and v a vertex of the graph, we denote by G\v the graph deprived of the vertex v and all the arcs incident to the vertex. A query pattern p is a triple (G, Q, SP ) such as :

-G is a RDF connected graph that describes the general structure of the pattern and represents a family of requests; -Q is a subset of elements in G, called qualifier elements; these are typical of the pattern and will be taken into account during the association of the user request to the pattern in question. A qualifier element is either a vertex (class or data type), or an arc (object or data property) in G; -SP is the set of subpatterns sp in p such that ∀sp = (SG, v, card min , card max ) ∈ SP , we have:

• SG is a subgraph of G and v is a vertex of SG (and thus of G), such as G\v is not connected (v is a joint vertex in G, also called junction vertex) and admits SG\v as a connected component (i.e. all the vertices in this connected component belong to the subpattern subpattern's graph); • At least one vertex or an arc of SG is a qualifier element;

• card min , card max ∈ N et 0 ≤ card min ≤ card max ; are respectively the minimum and maximum cardinality of sp that define the optional and repeatable characteristics of sp.

Figure 2.2 shows an example of a query pattern which deals with the events, and the performers involved, where musical works have been performed (or conversely) with the corresponding artist(s) and release date. The pattern is composed of three subpatterns named live, artist and date. All of them are optional, and only the subpatterns live and artist are repeatable: it is considered that a musical work can have only one release date, but a musical work may be the work of several artists and can be performed many times.

Patterns rewriting approach

The rewriting approach takes as input a complex alignment A O→O ′ and a set

P ={p O 1 ,...,p O n } of query patterns p O i ,

and outputs a set

P ′ ={p O ′ 1 ,...,p O ′ n } of query patterns p O ′ j .
The intuition is that every subgraph from the input patterns has potentially a (complex) correspondence associating its entities to entities in the target ontology. We consider that the subpattern is the relevant unit of semantic information constituting the patterns. Each subpattern is ideally replaced with Fig. 1. Query pattern asking for events and their performers, where musical works have been performed (or conversely), with the corresponding artist(s) and release date.

an equivalent subgraph corresponding to a logical statement relating concepts and properties of the target ontology. This statement is the target part of the correspondence, if any in the alignment, in which the source part matches the initial subpattern. But the subpatterns and the correspondences in the alignment may not have the same granularity (correspondences can be either simple or can relate smaller subgraphs). Thus, we define an algorithm that is similar to a Depth-First Search algorithm (DFS) for traversing and searching graph data structures in the input query patterns. It starts at the largest subgraph, i.e. the subpattern, and recursively explores its subgraphs (i.e. subpattern > RDF triples > classes and properties), until a correspondence is found for the considered subgraph (in which case, the target graph is written to the subpattern being outputted) or a class or property is reached. If at the end of this process, there are entities that have not been translated, the whole subpattern will be discarded 1 . The operation is repeated for each subpattern in the input patterns.

The approach is inherently limited by the use of ontology alignment, which is itself an incomplete process. The subpattern is the indivisible expression of a need for information: it can be rewritten by chunks but if it is not fully rewritten at the end of the process, it is discarded. Thus, the conservation of the semantics of original patterns directly depends on the completeness of the input alignment (coverage of the source ontology, quality of correspondences, etc.). We consider that some loss of (semantic) information is acceptable, and that it can be filled with other techniques (for instance, by interacting with the user). However, it is out of the scope of this paper. Figure 3 illustrates the rewriting of the pattern depicted in Figure 2.2 (with the input alignment given later in §4.3, Table 1). The subpattern named live is rewritten to live', following the complex correspondence #6 in the alignment. The subpattern named artist is rewritten to artist', following the complex correspondence #2 in the alignment (in this case, only the first term of the disjunction artist ⊔ author ⊔ creator ⊔ musicComposer appears in the resulting subpattern, for the sake of simplicity and readability).

Finally, the subpattern named date could not be directly rewritten since there is no correspondence for this subgraph. Instead, the property release date is rewritten to releaseDate, following a simple correspondence, and the data type xsd:date remains xsd:date.

Preliminary experiments

In a first series of experiments, we used a set of simple correspondences for rewriting patterns. These correspondences come from a merge of alignments generated by OAEI 2012 matching systems (the reader can refer to [START_REF] Gillet | Réécriture de patrons de requêtes à l'aide d'alignements d'ontologies[END_REF] for details). Overall, 67% of the entities in the Music ontology were covered in the alignment. 25 out of 60 entities in the query patterns for this ontology could be replaced by a target entity (coverage of 41%). In terms of subpatterns, only 2 out of the 19 subpatterns could be fully rewritten using the alignment. Although we have found a handmade (reference) alignment between Music and DBpedia ontologies5 , we could not use it because it is mostly composed by correspondences linking classes only, using subsumption relations, and few equivalences could be inferred from them. Despite the fact that the quality of the alignment from the matchers was not measured, these first experiments highlighted the limitations in replacing individually the entities in the patterns. Nevertheless, we needed to accurately assess this deficiency and to know to what extent we could rewrite query patterns. It turned out that simple correspondences are not sufficient to capture all the meaningful relations between entities of two related ontologies.

Complex correspondences

Very few systems are able to find complex correspondences. First, we tried the tool described in [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF], which finds complex correspondences using a set of predefined patterns. Besides the two ontologies to align, this tool takes an alignment as input. We used the tool on the pair Music-DBpedia, with (i) the handmade alignment between Music and DBpedia ontologies, and (ii) the merged alignment from the matchers used in the preliminary experiments ( §4.2). In both cases, few correct correspondences could be identified. We tried then the successor of this tool described in [START_REF] Ritze | Linguistic analysis for complex ontology matching[END_REF], which benefits of natural language processing techniques instead of requiring an input alignment, and we obtained similar results.

Hence, we manually created a set of 28 complex correspondences (along 11 simple ones) for the pair Music-DBpedia, guided by the query patterns for Music 6 . A subset of them is presented in Table 1. The idea behind using complex correspondences is that every subgraph pattern has potentially a (complex) correspondence in the target ontology. Given that the subpattern is the relevant unit of semantic information constituting the patterns, we isolated them, and for each of them, we tried to find an equivalent logical statement relating concepts and properties of the target ontology. For constructing the complex correspondence set, we used as basis a set of simple correspondences (the left operand refers to an entity of the Music ontology, and the right operand refers to an entity of the DBpedia ontology): MusicalManifestation ⊑ MusicalWork, MusicalWork ≡ Musical-Work*, MusicArtist ≡ MusicalArtist*, Performance ⊑ Event, Performer ≡ Mu-sicalArtist, foaf:Group ⊐ Band, MusicGroup ≡ Band*, SoloMusicArtist ⊑ Mu-sicalArtist, Track ⊑ MusicalWork, Track ≡ Song, and Record ⊑ MusicalWork7 .

For each correspondence, we identified the complex correspondence patterns that characterise it, from the patterns proposed in the literature: Class 1. 12 out of 28 handmade complex correspondences between Music and DBpedia ontologies.

by Attribute Type [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF] (CAT), Class by Inverse Attribute Type [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF] (CAT-1), Class by Attribute Value [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF] (CAV), Attribute Value Restriction [START_REF] Scharffe | Correspondence patterns for ontology alignment[END_REF] (AVR), equivalent to CAV, Property Chain [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF] (PC), Aggregation [START_REF] Scharffe | Correspondence patterns for ontology alignment[END_REF] (AGR), equivalent to PC, Inverse Property [START_REF] Ritze | Linguistic analysis for complex ontology matching[END_REF] (IP), Union [START_REF] Scharffe | Correspondence patterns for ontology alignment[END_REF] (OR), and Intersection [START_REF] Scharffe | Correspondence patterns for ontology alignment[END_REF] (AND). Although no new pattern was discovered, stating that, for our case, the patterns proposed in the literature cover all types of generated correspondences, several of our correspondences are in fact compositions of them (Table 1). For instance, the left operand in the correspondence #4 is an assembly of the patterns CAV and CAT. In the scope of this paper, however, we do not define any algebra which would describe how patterns can be composed or associated to represent the structure of complex correspondences (definition of basic properties and laws such as associativity, commutativity and distributivity). We have also manually generated 52 multilingual complex correspondences (along 13 simple correspondences) for the Cinema and DBpedia ontologies. For instance, the correspondence expressing the relation between the artists that are awarded the Cesar Award in Cinema (source ontology) and DBpedia (target ontology) : Artiste ⊓ ∃estRecompenseA.CesarDuCinema ≡ Artist ⊓ ∃cesarAward(Award ⊓ ∃event.F ilmF estival).

Rewriting SPARQL queries and query patterns

From the set of complex correspondences for the pair Music-DBpedia and the query patterns for Music, we applied our approach ( §3) for rewriting Music patterns in terms of the DBpedia vocabulary. Before rewriting patterns, we evaluated the use of these correspondences for rewriting SPARQL queries. For doing so, we defined a set of rules for translating a complex correspondence pattern into RDF graph patterns (Table 2). These rules are intended to be used for guiding the process of SPARQL rewriting. Following these rules, we managed to rewrite the 25 first SPARQL queries from the benchmark training data in QALD 2013 8 . The training data include 100 natural language questions for MusicBrainz with the corresponding SPARQL queries, as well as the answers these queries retrieve. The queries have been rewritten in order to interrogate DBpedia.

ID Formal pattern SPARQL rewriting rule

CAT A ≡ ∃R.B ?x a A → { ?x R B } CAT-1 A ≡ B ⊓ ∃R-.T ?x a A → { ?x a B . ?y R ?x } CAV A ≡ ∃R.{...} ?x a A → { ?x R "..."ˆˆex:dataType } AVR A ≡ B ⊓ ∃R.{...} ?x a A → { ?x a B . ?x R SomeValue . } PC R ≡ P.(A ⊓ ∃Q) ?x R ?y → { ?x P A . A Q ?y } IP R-⊑ P ?x R ?y → ?y P ?x OR A ≡ B ⊓ (∃R.T ⊔ ∃Q.T) ?x a A → {?x a B . {B R ?y} UNION {B Q ?z}} AND A ≡ B ⊓ (∃R.T ⊓ ∃Q.T) ?x a A → {?x a B . ?x R ?y ; Q ?z .}
Table 2. Complex correspondence patterns and SPARQL rewriting rules.

As an example, consider the query in Table 3 asking if there are members of the Ramones who are not named Ramone (question #25) over MusicBrainz, and the same query rewritten for DBpedia. The MusicBrainz result answers false, while the DBpedia result asserts the opposite. The DBpedia request is not less correct: if we return the actual query solutions (SELECT) instead of testing whether or not the query pattern has a solution (ASK), we find that Clem Burke in DBpedia was a member of The Ramones under the name "Elvis Ramone", while the MusicBrainz data set directly refers to him with this alias. In fact, both sets of instances do not fully intersect and they are not necessarily/correctly interlinked 9 . From this point of view, 18 of the 25 rewritten queries are correct and consistent with the queries for MusicBrainz: they do not necessarily give the same results, but they do answer the same question. 3 of these 18 results give the same number of solutions with exactly the same literals. 5 out of the 7 remaining results give no solution at all (no instance). And finally, the 2 last results are not fully correct since the complex correspondences ahead are not correct themselves. For instance, M usicalM anif estation ⊓ ∃release type.live ⊑ M usicalW ork ⊓ ∃recordedIn.P opulatedP lace turns out to be erroneous since the albums which have been recorded in a recording studio are equally selectable within the property recordedIn: we wrongly thought it was reserved for live performances only. Thus, these results allowed us to validate our complex correspondences and remove those that prove to be incorrect.

ASK ASK WHERE {

WHERE { ?band foaf:name 'Ramones' .

?band foaf:name 'Ramones'@en . ?artist foaf:name ?artistname .

?artist foaf:name ?artistname . ?artist mo:member of ?band .

{?band dbo:bandMember ?artist} UNION {?band dbo:formerBandMember ?artist} . FILTER (NOT regex(?artistname,"Ramone")) FILTER (NOT regex(?artistname,"Ramone")) } } Table 3. DBpedia rewritten query (right) from MusicBrainz query (left). Namespace prefix bindings were ommitted (dbo refers to dbpedia and mo to music).

Next, we rewrote the Music query patterns in terms of the DBpedia vocabulary. Using the 11 simple correspondences and the 28 complex correspondences, we achieved a rewriting percentage of 90% of the Music patterns: on the 19 subgraphs (subpatterns) identified in the patterns for Music, we were able to transform 17 of them. For the Cinema patterns, we were able to rewrite 45 out of 51 subpatterns from the Cinema IRIT query patterns. Then, the patterns rewritten from Music were injected in the SWIP system along the DBpedia data set, in order to demonstrate the relevance of rewriting query patterns in the whole process. We managed to run five queries from QALD and originally intended to MusicBrainz. The generated SPARQL queries are (semantically) correct as long as (i) the correspondences involved do not apply any disjunction of terms, which is not currently supported in SWIP (in this case, only the most likely term is kept), and (ii) the source and target in the correspondences involved have the same information level (basically, equivalence).

Related work

Rewriting query patterns using complex correspondences is the novel aspect of this paper. With respect to complex correspondence generation, different approaches have emerged in the literature in the last years. A common approach is based on complex correspondence patterns [START_REF] Scharffe | Correspondence patterns for ontology alignment[END_REF][START_REF] Scharffe | Correspondence Patterns Representation[END_REF][START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF][START_REF] Ritze | Linguistic analysis for complex ontology matching[END_REF] ( §4.3). Walshe [START_REF] Walshe | Identifying complex semantic matches[END_REF] proposes refining elementary correspondences by identifying which correspondence pattern best represents a given correspondence. Following a different strategy, Qin et al. [START_REF] Qin | Discovering executable semantic mappings between ontologies[END_REF] propose an iterative process that combines terminological, structural, and instance-based matching approaches for mining frequent queries, from which complex matching rules (represented in FOL) are generated. Nunes et al.

[10] present a two-phase instance-based technique for complex datatype property matching, where the first phase identifies simple property matches and the second one uses a genetic programming approach to detect complex matches. Recently, Arnold [START_REF] Arnold | Semantic enrichment of ontology mappings: Detecting relation types and complex correspondences[END_REF] uses state-of-the-art matchers for generating initial correspondences that are further (semi-automatically) enriched by using linguistic, structural and background knowledge-based strategies. Although different strategies have been proposed, very few matchers for generating complex correspondences are available or use EDOAL, an expressive alignment language [START_REF] David | The Alignment API 4.0[END_REF], for representing them. With respect to query patterns rewriting, the problem can be seen, at a lower level of abstraction, as a problem of SPARQL rewriting. Correndo et al. [START_REF] Correndo | SPARQL Query Rewriting for Implementing Data Integration over Linked Data[END_REF] propose a set of SPARQL rewriting rules exploiting both (complex) ontology alignments and entity co-reference resolution. Zheng et al. [START_REF] Zheng | SPARQL Query Mediation over RDF Data Sources with Disparate Contexts[END_REF] propose to rewrite SPARQL queries from different contexts, where context mappings provide the articulation of the data semantics for the sources and receivers. Makris et al. [START_REF] Makris | Ontology mapping and SPARQL rewriting for querying federated RDF data sources[END_REF][START_REF] Makris | SPARQL-RW: transparent query access over mapped RDF data sources[END_REF] present the SPARQL-RW rewriting framework that applies a set of predefined (complex) correspondences. They define a set of correspondence types that are used as basis for the rewriting process (i.e., Class Expression, Object Property Expression, Datatype Property, and Individual ). However, the way the set of complex correspondences is established is not described. Our naive approach for rewriting query patterns is close to these SPARQL rewriting proposals in the sense of using complex correspondences. One of the difficulties is the lack of established ways for automatically identifying them. Although m:n complex correspondences are proposed at conceptual level, few concrete examples are available in the literature. Most of our correspondences are n:m. As most proposals, we start from a set of (automatically) discovered simple correspondences. Finally, our method is applied in an applicative context of rewriting patterns for a question answering system over RDF data.

Conclusions and future work

This paper has discussed the use of complex correspondences for rewriting query patterns, aiming at reusing query families across data sets that overlap. Although we could not fully evaluate the rewriting process mainly due to the fact that SWIP does not treat pattern disjunctions, we were able to validate our approach on a subset of manually validated complex correspondences. This opens several opportunities for future work. First, the structure of query patterns in SWIP could evolve so that they match the structure of the complex correspondences we have established. In particular, SWIP would benefit from the disjunction of subpatterns or specification of instances in patterns. Second, we plan to represent our complex correspondences using EDOAL. Third, we plan to formalise the composition of complex correspondence patterns, which are thereby the building blocks to obtain richer correspondences, following a grammar defining a set of rules for rewriting logical statements in FOL or DL. The grammar must define the properties of pattern precedence, transitivity, associativity, commutativity, and distributivity. Finally, we plan to propose an approach for (multilingual) complex correspondence generation, exploiting specially the ABox of ontologies.

Fig. 2 .

 2 Fig. 2. Example of query pattern rewriting.

#

In this case, the pattern is still connected, i.e. there is a chain connecting each pair of vertices.

http://musicontology.com/

http://ontologies.alwaysdata.net/cinema

http://wiki.dbpedia.org/Ontology?v=181z

http://knoesis.org/projects/BLOOMS/#Resources_for_Download

The resulting alignment do not cover all possible correspondences between Music-DBpedia, but a subset of them where entities appear in the query patterns.

[START_REF] Gillet | Réécriture de patrons de requêtes à l'aide d'alignements d'ontologies[END_REF] Correspondences with an asterisk were discovered using OAEI matchers.

Open challenge on Multilingual Question Answering over Linked Data: http:// greententacle.techfak.uni-bielefeld.de/ ~cunger/qald/index.php?x=task1&q=3

http://wiki.dbpedia.org/Interlinking?v=vn


Mari Carmen Suárez- Figueroa

Mouna Kamel
email: mouna.kamel@irit.frmpoveda@fi.upm.es

María Poveda-Villalón

Benefits of Natural Language Techniques in Ontology Evaluation: the OOPS! Case

Natural language techniques play an important role in Ontology Engineering. Developing ontologies in a manual fashion is a complex and time consuming process, which implies the participation of domain experts and ontology engineers to build and evaluate them. Natural language techniques traditionally help to (semi)-automatically build ontologies and to populate them. However, the general trends for evaluating ontologies are mainly expert reviewing, evaluating quality dimensions and criteria, and evaluating against existing ontologies and set of common errors. That is, the use of natural language techniques in ontology evaluation is not widely spread. Thus, in this paper we aim at the use of natural language techniques during the ontology evaluation process. In particular, we propose a first attempt towards a languagebased enhancement of the pitfall detection process within the ontology evaluation tool OOPS!.

Introduction

Developing ontologies manually is a complex and time consuming process, which involves both ontology engineers and domain experts. Natural language (NL) techniques have been traditionally used for extracting knowledge from texts to build semantic resources. In fact knowledge acquisition from text plays an important role in Ontology Engineering. It is divided into several steps, according to the "ontology learning layer-cake" [START_REF] Cimiano | Ontology Learning and Population from Text: Algorithms, Evaluation and Applications[END_REF]: (a) identifying and extracting terms, (b) eliciting concepts and relations linking concepts from these terms, (c) organizing concepts and relations into hierarchies, and (d) identifying axioms.

During the ontology building, a wide range of difficulties and handicaps can appear. These situations may have as consequence the inclusion of anomalies in the ontology. Thus, the ontology evaluation process plays a key role in ontology engineering developments. Currently, the general trends in ontology evaluation involve different approaches (e.g., the comparison of the ontology to a "gold standard" or the detection of common errors in the ontology). However, what seems to be less present in the ontology evaluation field is the intensive use of NL techniques. For example, some structural or naming errors in the ontology may be automatically pointed out with a linguistic analysis of concept labels. Thus, our intention in this paper is to aim at the use of NL techniques during the ontology evaluation process. In particular, we propose a first attempt of improving the pitfall detection methods implemented within OOPS! by means of NL techniques.

The remainder of this paper is structured as follows: Section 2 summarizes different NL techniques used in Ontology Engineering. Section 3 presents the relation between ontology evaluation and NL-based techniques. Section 4 briefly describes OOPS!. In Section 5 our proposal towards a language-based enhancement of the pitfall detection process within OOPS! is presented. Finally, Section 6 outlines some conclusions and future steps.

Natural Language Techniques in Ontology Engineering

NL techniques traditionally help on the (semi)automatic building of ontologies and on the population of ontologies with instances.

Most of the approaches for building ontologies from text, known as ontology learning methods, usually implement lexico-syntactic patterns (Hearts, 1992;[START_REF] Montiel | Using natural language patterns for the development of ontologies[END_REF], clustering methods or machine learning algorithms (essentially unsupervised) [START_REF] Poelmans | Formal concept analysis in knowledge discovery: a survey[END_REF], to exploit various linguistic clues. Some platforms exist and implement one or a combination of these methods using different NLP tools (term or relation extractors, parsers, etc.). Examples are Text2Onto [START_REF] Cimiano | Text2Onto -A Framework for Ontology Learning and Data-driven Change Discovery[END_REF], which discovers concepts and hyperonimic relations between concepts, thanks to lexico-syntactic patterns and associative rules automatically learned from examples and OntoLearn [START_REF] Velardi | Using text processing techniques to automatically enrich a domain ontology[END_REF], which uses Wordnet (Fellbaum, 1998) for identifying lexical relations.

Regarding the population of ontologies, tools like TEXCOMON [START_REF] Zouaq | Building Domain Ontologies from Text for Educational Purpos-es[END_REF] uses linguistic patterns for instance identification, using named entity recognition techniques.

Linguistic approaches have been also applied to ontology matching where [START_REF] Euzenat | Ontology Matching[END_REF] distinguish between language-based methods and methods which are based on linguistic resources, whereas the more general class of terminological approaches also includes string-based methods. We can mention the work by [START_REF] Ritze | Linguistic analysis for complex ontology matching[END_REF] that shows how complex matching can benefit from NL techniques.

Ontology Evaluation and Natural Language Techniques

Ontology evaluation process, which checks the technical quality of an ontology against a frame of reference (Suárez-Figueroa, 2010), plays a key role in ontology engineering projects.

To help developers during the ontology evaluation process, there are different approaches [START_REF] Sabou | Ontology (Network) Evaluation. Ontology Engineering in a Networked World[END_REF][START_REF] Poveda-Villalón | Validating ontologies with OOPS![END_REF]: (a) comparison of the ontology to a "gold standard", (b) detection of common errors from catalogues in the ontology, (c) use of dimensions and criteria for describing the quality and goodness of the ontology, (d) use of the ontology in an application and evaluation of the results, (e) comparison of the ontology with a source of data about the domain to be covered, and (f) evaluation by experts who check the ontology against the requirements.

In addition, ontology evaluation can be supported by NL techniques in several ways [START_REF] Gangemi | Ontology evaluation and validation: An integrated formal model for the quality diagnostic task[END_REF]:

• When the ontology directly supports information retrieval or text mining applications and thus concerns objects mentioned in texts.

• When a corpus of documents is available, NLP can be used to identify mentions of instances (i.e. occurrences in text) of classes and relations which are mentioned in the text. A corpusbased evaluation of the ontology can reveal important properties of the ontology that might not be discovered otherwise.

• When (semi)-automatic population of the ontology is performed, NLP can help in the identification of new senses of already known instances, for example because the instance is polysemous and/or ambiguous (e.g., "Washington" is a person and a location).

However, ontology evaluation approaches could take more advantage of NL techniques. In this sense, we propose here a first attempt towards a NL-based upgrade of OOPS!.

OOPS!: OntOlogy Pitfall Scanner!

OOPS!1 (Poveda-Villalón et al., 2012) is a webbased tool, independent of any ontology development environment, for detecting potential pitfalls that could lead to modelling errors. Currently, OOPS! provides mechanisms to automatically detect as many pitfalls as possible, thus it helps developers in the diagnosis activity, which is part of the ontology validation process.

OOPS! takes as input an ontology to be evaluated and a pitfall catalogue in order to produce a list of evaluation results. The current version of the catalogue2 consists on 35 pitfalls. Some examples are creating synonyms as classes, defining wrong inverse relationships, missing annotations, missing domain or range in properties, or defining wrong equivalent classes. Up to now, OOPS! detects semi-automatically a subset of 21 pitfalls related to the following dimensions: human understanding, logical consistency, modelling issues, ontology language specification and real world representation.

Towards a Language-based Enhancement of OOPS!

In this section we propose a first attempt towards a language-based enhancement of the pitfall detection process within the ontology evaluation tool OOPS!. To do this, we have reviewed the current catalogue of pitfalls in order to determine (a) which pitfalls, already implemented, could be detected in a better way by means of applying linguistic techniques and (b) which ones, not detected yet by OOPS!, could be implemented based on linguistic aspects.

Regarding the proposals for enhancing pitfalls already detected by OOPS!, we can mention the following ones:

• P2. Creating synonyms as classes: several classes whose identifiers are synonyms are created and defined as equivalent. Its detection could be improved by using linguistic resources such as WordNet and EuroWordNet, particularly by looking for the synonymy information of the class name.

• P3. Creating the relationship "is" instead of using ''rdfs:subClassOf'', ''rdf:type'' or ''owl:sameAs'': the "is" relationship is created in the ontology instead of using OWL primitives for representing the subclass relationship ("sub-classOf"), the membership to a class ("instance-Of"), or the equality between instances ("sameAs"). The detection could be enriched by creating specific language-dependent lexicosyntactic patterns to discover the use of 'is' and by using named entity recognition tools for characterizing the "instanceOf" relation.

• P5. Defining wrong inverse relationships: two relationships are defined as inverse relations when they are not necessarily. As first attempt, the implementation of this pitfall could be improved by creating specific lexico-syntactic patterns for direct/inverse relationship name structure.

• P7. Merging different concepts in the same class: a class is created whose identifier is referring to two or more different concepts (e.g., "StyleAndPeriod", or "ProductOrService"). As first attempt, its detection could be enhanced by creating specific language-dependent lexicosyntactic patterns and regular expressions to discover the use of 'and' or 'or' in the concept name.

• P12. Missing equivalent properties: when an ontology is imported into another, developers normally miss the definition of equivalent properties in those cases of duplicated relations and attributes (e.g., "hasMember" and "has-Member" in two different ontologies). The detection could be enriched by (a) using linguistic resources such as WordNet and EuroWordNet, specifically by looking for the synonymy information of the property name and (b) creating specific language-dependent lexico-syntactic patterns.

• P13. Missing inverse relationships: this pitfall appears when a relationship (except for the symmetric ones) has not an inverse relationship defined within the ontology. As first attempt, its implementation could be improved by creating specific lexico-syntactic patterns for direct/inverse relationship name structure (e.g., isSoldIn-sells; hasAuthor-isAuthorOf; hasParent-isParentOf).

• P21. Using a miscellaneous class: to create in a hierarchy a class that contains the instances that do not belong to the sibling classes instead of classifying such instances as instances of the class in the upper level of the hierarchy. This class is normally named "Other" or "Miscellaneous". As first attempt, its detection could be improved by creating a set of lexico-syntactic patterns that represent different ways of naming concepts that are usually miscellaneous entities.

With respect to those pitfalls not detected yet by OOPS!, we can propose the following ideas for their implementation based on NL aspects:

• P1. Creating polysemous elements: an ontology element whose name has different meanings is included in the ontology to represent more than one conceptual idea. As first approach, its detection could be implemented by (a) using linguistic resources such as WordNet and EuroWordNet, specifically by analyzing the different synsets in which the element name appears and (b) by analysing labels of neighbourhood concepts for disambiguation.

• P9. Missing basic information: information that is required and/or useful is not included in the ontology. As first approach and in certain situations, this pitfall could be implemented by using linguistic resources such as WordNet and EuroWordNet, specifically by analyzing the antonym information of the relationships name.

• P30. Missing equivalent classes: when an ontology is imported into another, classes with the same conceptual meaning that are duplicated in both ontologies should be defined as equivalent classes. As first step, this pitfall could be detected by using linguistic resources such as WordNet and EuroWordnet, specifically by looking for the synonymy information of the class name.

• P31. Defining wrong equivalent classes: two classes are defined as equivalent when they are not necessarily. As first step, this pitfall could be implemented by using linguistic resources such as WordNet and EuroWordNet, specifically by looking for the hyperonym information of the class name.

Conclusions and Future Work

In this paper, we have presented the first efforts towards a NL-based enhancement of the pitfall detection process within the ontology evaluation tool OOPS!. We have reviewed the 35 pitfalls in the OOPS! catalogue and analyzed which pitfall detections could be linguistically improved and which pitfalls could be implemented based on NL as first attempt. In summary, we have proposed the improvement of 7 pitfall detection processes and the automation of 4 pitfalls not detected yet by OOPS!. Thus, we have planned to enhance OOPS! with the NL techniques presented in this paper.

http://oeg-upm.net/oops/

http://www.oeg-upm.net/oops/catalogue.jsp

ACKNOWLEDGMENTS

This work has been supported by the Spanish project BabelData (TIN2010-17550).