-This paper discusses an application of intelligent software agents and ontologies to solve the problem of semiautomatic porting of Java programs. We have designed a system for aiding users to adapt Java code in a type- and meaning-safe way, when an application has to migrate to new libraries which are not fully compatible with the legacy ones. To achieve this, we propose an approach based on an integration of the two type-theoretic notions of subtyping and type isomorphism with ontology matching. While the former notions are needed to ensure flexible adaptation in the presence of typesafety, the latter supports the user to preserve the meaning of names that appear in the program to be adapted. Intelligent agents control the different components of the system and interact with other agents in order to provide the final user with the semi-automatic porting service he/she required.
Migrating a Java program p that uses library l into a corresponding program p0 that uses library l0 in a semiautomatic way is an open problem for which no satisfying solution has been found yet.
One aspect that must be considered while facing this problem, and that makes it hard to solve, is that migration must be type-safe. Replacing method m defined by l and used in program p by m0 defined in l0, thus leading to a new program p0, is a legitimate operation only if no type inconsistencies are raised by this replacement. If the functionality of m and m0 is the same no type problems will arise. But what should it happen in case of a difference in the type returned by m and m0, or in the type of some of their parameters, or in their number and order? The most conservative approach would be to give up, and to consider the migration possible only if elements of l used by p have corresponding elements in l0 whose type is identical or isomorphic.
However, this is a very restrictive choice with little motivation: type identity or isomorphism between elements of l and the corresponding elements of l0 may be relaxed by requiring that the type 0 of e0 in l0 is a subtype of the type of e in l, for a suitable definition of the subtype relation. This requirement allows a type-safe replacement of e in p with e0 in p0.
For example, R. Di Cosmo, F. Pottier and D. Re´my propose
an efficient decision algorithm for subtyping recursive types
modulo associative commutative products that demonstrates
the feasibility of using subtyping instead of type isomorphism,
when translating a program into another [
The limitation of their work, that we want to overcome by exploiting intelligent agents and ontologies in our system, is that they abstract from the names of classes, methods and attributes and just consider safe matching between types. Since there may be a large number of type correspondences < , 0 > that preserve type-safety, re-introducing names of classes, methods and attributes into the algorithm that matches libraries’ elements may help in removing those correspondences that, even if type safe, are not “meaning-safe”. Correspondences between names of methods and attributes are also needed during the translation process where type correspondences are not enough.
Assume that we would like to port p from l to l0. For simplicity, the problem can be reduced to the following example scenario: p is the program
and l is defined as follows: c l a s s AttributeList e x t e n d s Object { String getName( i n t i){...} } where Object and String are the usual predefined classes defined in the standard package java.lang.
The library l0 to which p has to be ported contains the following class declarations: c l a s s Attributes e x t e n d s Object { i n t getLength(){...} String getLocalName( i n t index){...} String getAttributeType( i n t index){...} }
The approach discussed in [
What we would like to have, instead, is the set of correspondences f<AttributeList, Attributes>, <getName, getLocalName>g. This set cannot be obtained by just checking the type compliance of String getName(int) with int getLength(), String getLocalName(int), and String getAttributeType(int).
In fact, while getLength is not type compliant with getName, both getLocalName and getAttributeType are. However, we expect that the right correspondence is that between getName and getLocalName, due to the intended meaning of their names.
It is here that ontologies come into play: assuming that an “ontology matching algorithm” can devise the correspondences between ontology elements (classes, properties, relationships, individuals) that better respect their intended meaning, and assuming that from a Java library, an ontology carrying the intended meaning of the library elements can be extracted, we propose to extract ontologies o and o0 from l and l0, and to run a matching algorithm on them.
And it is here that agents come into play: the system that we have designed consists of complex components that must provide different kinds of services (type and ontology extraction, type and ontology matching, filtering of the matching results, assisted extraction of the translation function, actual translation) either to the final user or to other system’s components. In order to make our system as flexible as possible, we associate an intelligent agent with each component. The agent controls the component and interacts both with other agents and with the user.
The output of the type and ontology matching algorithms, controlled by a Type Matching Agent and by an Ontology Matching Agent respectively, will be combined by a Filtering Agent in order to produce a type- and meaning- safe matching relation. A human user assisted by a Function Extraction Assistant Agent will disambiguate multiple possible matchings in order to identify a match function which will finally be used by a Translation Agent to translate p into p0.
Continuing the example above, p0 would be
String name = atts.getLocalName(0); where Attributes = match(AttributeList) and getLocalName = match(getName). Thanks to the match function, the translation from p to p0 can be fully automatized.
The aim of this paper is to discuss a multiagent system that exploits type and ontology matching techniques to make automatic migration of Java programs possible. The paper is organized in the following way: Section II describes the architecture of our multiagent system and Sections III and
agents in detail. Section V concludes and highlights future directions of work.
The purpose of our multiagent system, depicted in Figure 1, is to provide the service of computing a match function between the elements of two Java libraries l, l0 given in input either by a human user or by any other software application, by exploiting interactions among the different agents belonging to it1. If the user (agent, software application) wants the additional service of performing the translation of a Java program p that uses library l into a Java program p0 that uses l0, the match function can in turn be given in input to the Translation Agent which computes a translation p0 of p driven by match.
The match function is obtained in the following way: ontologies o and o0 are extracted from libraries l and l0 respectively. In a similar way, collections of types t and t0 are extracted from l and l0.
The Ontology Matching Agent interacts with a set of Simple Ontology Matching agents (SOMi in Figure 1), each in charge of running one specific ontology matching algorithm chosen from a pool of existing ones (see Section IV, last paragraphs). The Ontology Matching Agent may decide to demand the ontology matching service to the SOM agent that has the lowest workload, to the one that seems more suitable to correctly match ontologies o and o0 according to quality of service criteria or efficiency needs, or to any other SOM agent according to some policy including running all the available ontology matching algorithms and either merging the obtained results or selecting one of them based on ex-post analysis2. At the end, the Ontology Matching Agent obtains from one or more SOMs the alignments (namely, the sets of correspondences) a1, a2, ..., an between o and o0 and merges them or selects the most preferred alignment among them if it is the case. The Type Matching Agents behaves in the same way, controlling a set of Simple Type Matching agents (STMj in Figure 1) each in charge of running a specific type matching algorithm on t and t0 to get tm. The type match tm is used for selecting only those correspondences in a that are type safe. We name this activity “filtering”.
Filtering, whose responsibility is given to the Filtering Agent, still does not ensure that we obtain a set of correspondences that is a function: it might still be a relation, because more than one correspondence involving e 2 l is both typeand meaning-safe.
The user is involved in the loop for making the relation output by the Filtering Agent turn out into a match function: if many correspondences are possible for an element e 2 l, the user will be asked to make his/her choice among them. Another information must be integrated into the match function, namely, for any method m 2 l, which injection must be applied on its parameters p1; :::; pn in order to obtain 1Currently, some agents belonging to the MAS such as type matching and filtering agents have little decisional power and autonomy, so they could be collected into a single sequential process, simplifying the system design. However, we expect that these agents may be equipped with a higher degree of intelligence in a future version of the system. Hence, we model them as agents even if, in the current version, they are just service providers.
2Alignments can be compared according to their precision and recall. Unfortunately, computing precision and recall of an alignment between o and o0 is only possible if a reference alignment for o and o0 has already been developed by hand. In fact, precision is defined as the number of correctly found correspondences with respect to a reference alignment divided by the total number of found correspondences and recall is defined as the number of correctly found correspondences divided by the total number of expected correspondences. The higher the precision and recall, the better. If no reference alignment exists, only quantitative features of the alignment such as dimension, number of correspondences with the same first element, etc, can be considered to decide whether one alignment is “better” than another one. the tuple p1; :::; pk, k n whose ordered elements can be used as parameters for m0 2 l0, where m0 = match(m). Also in this case, the user may be required to make a choice if more injections are possible. For example method m1(c1, int, String) in l might be type- and meaningsafely replaced by m2(int, String, c1) in l, but a permutation of its parameters is required when actually translating p that uses m into p0 that uses m0.
The match function (which is indeed a family of functions working either on elements of l, or on tuples of elements of l) is needed by the Translation Agent.
Of course, it might also happen that the Filtering Agent cannot achieve its goal because there are some elements in l for which no corresponding element in l0 has been found and thus no match function from l to l0 can be computed. The user will be involved in this case too: the Filtering Agent will inform him/her that no type and meaning-safe matching was possible for some elements, and the result of the filtering stage will be shown to him/her. Even if no automatic translation of p will be possible due to the impossibility to generate a match function, the user might find the result of the Filtering Agent useful for driving his/her hand-made translation.
If, thanks to the human intervention, a match function has been defined, the automatic translation of p into p0 can be performed by the Translation Agent, leading to the desired output, namely program p0.
In the sequel of this section, each agent is shortly presented. Agents that deal with ontologies are discussed in more detail in the next sections.
The Ontology Extraction Agent takes one Java library as input and returns an ontology that models the structure of the library in term of its classes, their subclass relationships, their methods and attributes. This agent, described in Section III, must operate on both l and l0 in order to obtain o and o0 respectively.
The Type Extraction Agent takes one Java library as input
and returns a collection of types following S. Jha, J. Palsberg
and T. Zhao’s proposal [
The service offered by the Ontology Matching Agents is returning an alignment of the two ontologies taken in input. This agent is responsible for the “meaning-safety” of the matching between elements of l and elements of l0; it will take the ontologies o and o0 extracted from l and l0 respectively as input and will return an ontology alignment a between them. As we will discuss in Section IV, many ontology matching algorithms and tools exists: we will integrate the most relevant ones into our system by implementing, for each of them, a SOM agent that provides an interface towards the algorithm/tool. The Ontology Matching Agent will coordinate the activity of SOM agents
Once the collections of types induced by l and l0 have
been extracted, a type-safe matching between them must be
computed. The algorithm we will use for this activity is
inspired by that proposed by R. Di Cosmo, F. Pottier and
D. Re´my in [
In order to find a matching between the elements of l and
those of l0 that is both type-safe and that takes the meaning
of names of methods, attributes and classes into account, as
well as their structural relationships, we need to filter elements
of a by taking the type-safe correspondences contained in tm
into account. A Filtering Agent that implements the algorithms
described in [
In the general case the output of the Filtering Agent, tsa (for type safe alignment), will not be deterministic enough to be used for translating a program p that uses l into the corresponding program p0 that uses l0. There might be elements of l that can be matched to more than one element in l0 taking both types and meaning into account, and no algorithm could automatically determine the right choice. Once most of the work has been done and the subset tsa of elements(l) elements(l0) has been generated, the Function Extraction Assistant Agent comes into play and interacts with the user in order to complete the definition of the match function that will drive the translation from p to p0. The task of the user mainly consists in making choices among a set of possibilities provided by the Filtering Agent, in order to constrain a relation to become a function. The user is also asked to define the right operations to be performed on parameters of m 2 elements(l) in order to obtain a tuple of parameters suitable for the corresponding method m0 2 elements(l0).
Of course there might be elements of l for which no type safe matching into a corresponding element of l0 exist, and this would mean that tsa could never become a function, and that the system has nothing left to do. The user can benefit from knowing tsa, but he/she has to perform the translation from p to p0 by hand.
In case a the match function has successfully been
extracted, the Translator Agent can provide its translation service
by taking a function match and a program p and returning a
program p0 following the rules defined in Section 7 of [
This section describes the algorithm for automatically extracting an OWL ontology from a Java library exploited by the Ontology Extraction Agent. In case more ontology extraction algorithms should be implemented, the Ontology Extraction Agent might coordinate interface agents towards all or some of them, in the same way as the Ontology Matching and Type Matching agents do.
In order to explain how the extraction algorithm works, we need to provide some details on the subset of OWL that we will use for representing ontologies corresponding to Java libraries. We have designed the extraction in order to make this subset as small as possible. In particular, it is a proper subset of OWL Lite.
a) Data Types: Data Types used in OWL ontologies are those defined by the XML Schema specification, http://www. w3.org/TR/xmlschema-2/: decimal represents the subset of the real numbers, which can be represented by decimal numerals; integer is derived from decimal by fixing the number of decimal digits to 0, and disallowing the trailing decimal point. This results in the standard mathematical concept of the integer numbers. Neither decimal nor integer have a direct counterpart in Java primitive data types. long is derived from integer by setting the maximum value to be 9,223,372,036, 854,775,807 and the minimum one to be -9,223,372,036,854,775,808 (both included); it corresponds to the long Java primitive data type. int is derived from long by setting the maximum value to be 2,147,483,647 and the minimum value to be 2,147,483,648 (both included); it corresponds to the int Java primitive data type. short is derived from int by setting the minimum admissible value to -32,768 and the maximum admissible value to 32,767 (both included); it corresponds to the short Java primitive data type. byte is a short ranging between -128 and 127 (both included); it corresponds to the byte Java primitive data type. float is patterned after the IEEE single-precision 32bit floating point type; it corresponds to the float Java primitive data type. double is patterned after the IEEE double-precision 64bit floating point type ; it corresponds to the double Java primitive data type. boolean has the value space required to support the mathematical concept of binary-valued logic: ftrue, falseg; it corresponds to the boolean Java primitive data type. OWL primitive data types do not include char, which is the only Java primitive data type with no direct correspondence. However, since char is a finite-valued type type, it may be easily represented as an OWL class with a finite number of instances, as a set of integers with a maximum cardinality (the owl:maxCardinality built-in OWL property may be used to this aim), or in other straightforward ways. Instead, OWL primitive data types include for example string, date, time that correspond to some extent to the String, Date, Time classes provided by java.lang and java.sql packages, respectively.
Since OWL provides no data type corresponding to void, we assume that an OWL class named Void is defined in a namespace that we abbreviate with myns, and that it corresponds to the void type specifier in Java.
b) Namespace: Namespaces are inherited by OWL from XML. XML namespaces provide a simple method for qualifying element and attribute names used in XML documents by associating them with namespaces identified by URI references. A standard initial component of an ontology includes a set of XML namespace declarations that provide a means to unambiguously interpret identifiers and make the rest of the ontology presentation much more readable.
c) Class: A class defines a group of individuals that belong together because they share some common properties. The OWL class element, identified by owl:Class, is a subclass of the RDFS class element, rdfs:Class. The rationale for having a separate OWL class construct lies in the restrictions on OWL DL (and thus also on OWL Lite), which imply that not all RDFS classes are legal OWL DL classes.
d) Subclass: Class hierarchies may be created by making one or more statements that a class is a subclass of another class. This can be achieved by using the rdfs:subClassOf element defined by RDFS.
e) Property: Properties have originally being defined in RDF and can be used to state relationships between individuals (object properties, owl:ObjectProperty) or from individuals to data values (data type properties, owl:DatatypeProperty). Both object and data type OWL properties are subclasses of the RDF class rdf:Property.
The algorithm that we describe in this section has been designed for working under the assumption that names of methods and attributes of the classes in a class library are all different. The absence of name clashes between classes is given for granted, since a class library cannot include two classes with the same name. Even under the assumption that different classes with no inheritance relation among them define different methods, a preprocessing stage must be performed on the library in order to deal with method overriding. In fact, we cannot prevent subclasses from overriding methods defined in superclasses, but this leads to a violation of our assumption on disjoint names of methods. We deal with this situation by just removing the overridden method from all the subclasses that override it. This gives us two advantages: 1) the assumption under which the algorithm works is respected; 2) we avoid that a method m defined by class c may be matched to m0, and the same method m overridden by a subclass of c is matched to m00 6= m0.
The basic ideas underlying the extraction algorithm are: The Java library l corresponds to a single OWL ontology lo named after the library name and defined in a namespace lns.
Java classes belonging to l correspond to OWL classes belonging to lo; the identifier of the OWL class coincides with the name of the Java class it corresponds to. If the Java class sc extends c, then the OWL class corresponding to c (that we name owl(c) for our convenience) is defined as a subclass of the OWL class corresponding to sc.
Since properties of an OWL class are inherited by its subclasses, the Java methods and attributes of class c are translated into OWL properties with identifier identical to their name and domain owl(c). This allows them to be inherited by owl(c)’ subclasses for free. The range of a property corresponding to a Java attribute is defined as the attribute’s type; that of a property corresponding to a method is a pre-defined OWL class named myns:MethodF.
Our assumption of absence of clash names is very strong, but it allows us to describe the basic ideas underlying the algorithm in a clear and understandable way, discarding the technical details raised by name clashes. The reason for this assumption is that we translate all the elements (classes, attributes, methods) of the class library into corresponding elements of a unique OWL ontology. Unfortunately, an OWL ontology cannot include properties with the same name, even if their domain and range are different as it should happen with methods, parameters and attributes with the same name but different functionality.
In the real case, where name clashes between methods, parameters, and attributes may occur, two solutions have been devised.
1) Instead of translating the entire Java library into an OWL ontology, each Java class c should be translated into an OWL ontology o defined within a namespace ns created starting from c in a way that ensures its uniqueness. Methods and attributes of class c, as well as the methods’ parameters, should be translated into properties of the ontology o within the namespace ns. The usage of different ontologies defined in different namespaces should allow us to identify each element of a Java class in a unique way, and thus to overcome the problem of name clashes (using the same identifier in different namespaces is, of course, admitted). The ontology corresponding to the Java class c should import all the ontologies corresponding to translations of Java classes referenced in c, and thus a pre-processing phase should be added to the extraction algorithm. The Java library l should be translated into an ontology that just imports all the ontologies corresponding to the Java classes belonging to l.
The main drawback of this approach, besides a much more complex extraction algorithm, is that few implemented matching algorithms that the Simple Ontology Matching Agents, SOMs, should interface take namespaces correctly into account. 2) The Java library should still be translated into a single OWL ontology, but clashing names should be modified during their translation in order to obtain an ontology “clash-free”.
Here, the drawback is that the modification of names would result into poorer performances of the ontology matching algorithms. If, for example, method m in the library l has been translated into m14 in ontology o because of a name clash, and method m in library l0 has been translated into m37 in ontology o0, again because of a name clash, the confidence in the correspondence < m 2 o; m 2 o0 > would turn out to be lower than the confidence in the correspondence < m14 2 o; m37 2 o0 > for most matching algorithms, because of the syntactic difference between the two names.
The following paragraphs describe the extraction of the OWL elements starting from the Java library elements and provide examples.
A Java class c that extends no class corresponds to an OWL class c (Table I).
A Java class sc that extends a class c different from Object corresponds to an OWL class sc defined as a subclass of c (Table II).
An attribute a of class c whose type is a basic type t with a corresponding data type in XML corresponds to an OWL datatype property whose ID is a, whose domain is c, and whose range is the XML data type that corresponds to t (Table III).
An attribute a of class c whose type is the class c0 defined in the Java library corresponds to an OWL object property whose ID is a, whose domain is c, and whose range is c0 (Table IV).
Since we are not interested in representing the functionality of a method m in the ontology, we treat methods in the same way as attributes with the only difference that their range is always an OWL class defined in our namespace, and named "myns:MethodF". The domain of a method is the OWL class representing the Java class it belongs to (Table V).
The Ontology Matching Agent will coordinate Simple Ontology Matching Agents, each interfacing towards some existing algorithm and/or tool (for example those mentioned at the end of this section, but others might be considered).
In the recent past, the second author of this paper together
with other colleagues from the University of Genova designed,
implemented and tested a FIPA compliant Ontology Agent for
JADE [
In this section, we shortly review the state of the art of
ontology matching systems and algorithms towards which
Simple Ontology Matching Agent will interface. We draw
inspiration from [
An alignment of ontologies o and o0 is a set of correspondences between entities of o and o0, and a matching process is a function f which takes two ontologies o and o0, a set of parameters p and a set of oracles and resources r, and returns an alignment A between o and o0.
Two of the dimensions according to which matching techniques can be classified are the level (element vs structure) and the way input information is interpreted (syntactic vs external vs semantic).
Element-level matching techniques compute alignments by analyzing entities in isolation, ignoring their relations with other entities. Structure-level techniques compute alignments by analyzing how entities appear together in a structure.
Element-level techniques include, among others:
String-based techniques, that measure the similarity of
two entities just looking at the strings (seen as mere
sequences of characters) that label them. They include
substring distance, Jaro measure [
constraints being applied to the definitions of entities, such as types, cardinality of attributes, and keys.
rithms which consider only the specialization relation. Model-based techniques that handle the input based on its semantic interpretation (e.g., model-theoretic semantics). Examples are propositional satisfiability (SAT) and description logics (DL) reasoning techniques. public class Bike <owl:Class rdf:ID="Bike"/> public class MountainBike extends Bike <owl:Class rdf:ID="MountainBike">
<rdfs:subClassOf rdf:resource="Bike"/> </owl:Class>
Syntactic techniques interpret the input in function of its sole structure following some clearly stated algorithm.
External techniques exploit auxiliary (external) resources of a domain and common knowledge in order to interpret the input.
Semantic techniques use some formal semantics (e.g., model-theoretic semantics) to interpret the input and justify their results. In case of a semantic based matching system, a further distinction between exact algorithms (that guarantee a discovery of all the possible correspondences) and approximate algorithms (that tend to be incomplete) may be done.
Many implemented matching systems and algorithms exist.
If we just consider those listed in the “Project” section of the
Ontology Matching portal, http://www.ontologymatching.org/
projects.html, we may count about thirty of them. These
systems and infrastructures are very different one from another.
Many of them have been carefully analyzed and compared in
[
Just to cite some very recent systems, HMatch [
CtxMatch [
The Alignment API [
AUTOMS-F [
... public BikeFeatr getFeatr() {
...
}
}
<owl:ObjectProperty rdf:ID="setFeatr">
<rdfs:domain rdf:resource="Bike"/>
<rdfs:range rdf:resource="myns:MethodF"/>
</owl:ObjectProperty>
<owl:ObjectProperty rdf:ID="getFeatr">
<rdfs:domain rdf:resource="Bike" />
<rdfs:range rdf:resource="myns:MethodF"/>
</owl:ObjectProperty>
individual ontology mapping methods. Towards this goal,
AUTOMS-F provides a highly extensible and customizable
application programming interface. AUTOMS [
Finally, automatic matching techniques that exploit “Upper
Ontologies”, namely general ontologies that deal with
concepts that are the same across different domains, have been
implemented and analyzed in [
In this paper we have described a multiagent system that,
once implemented, should allow a user to semi-automatically
porting a Java program p that uses library l to a program p0 that
uses l0 in a type-safe and “meaning-safe” way. To the best of
our knowledge, no previous attempts of exploiting agents and
ontologies for facing porting and migration problems exist.
We devise some similarity between our proposal and the
Natural Programming Project, http://www.cs.cmu.edu/ NatProg/,
working on making programming languages and environments
easier to learn, more effective, and less error prone. The
report [
The contribution of this paper is twofold. On the one hand,
we have designed the multiagent system’s architecture; on the
other hand, we have either identified existing algorithms to
integrate in the agents when possible, or designed new ones (the
ontology extraction algorithm described in this paper and the
algorithms implemented by the Filtering and the Translation
agents described in [
The first activity we will carry out in the very near future is the implementation of the algorithms that, at this stage, are only designed. In parallel to the implementation of these algorithms, the choice of the most suitable algorithms and tools to be accessed by Simple Ontology Matching Agents will be made.
Once all these components will be available and tests will be performed over them, a prototype demonstrating the feasibility of our approach will be created in JADE.
The authors acknowledge the anonymous reviewers for their thoughtful and constructive suggestions.
This work has been partially supported by MIUR EOS DUE - Extensible Object Systems for Dynamic and Unpredictable Environments, and by the CINI-FINMECCANICA Iniziativa Software project.