The Amos Project: An Approach to Reusing Open Source Software

Software development is currently one of the most important and strategic activities for any country; the creation of new software packages and tools is now at the heart of many technological advances. This is not only an issue for businesses, but also for the citizens and the users who request new functionalities and services to be delivered using software systems. However, a proper reutilization of open source code-not at the level of whole programs, but at the level an implementor perceives code-has, in our opinion, not yet been achieved.

There is an extensive literature on components, software frameworks, and such, and even some research work on the integration of legacy code into new systems. However, finding appropriate components is a prerequisite in order to reach this point. Presently, the only way to do this is by extensive search through software libraries. Current research on software matching which tries to address and solve some of the aforementioned problems is focused on two aspects:

In (mili95), an extensive summary of recent research works on the software matching field are analyzed and classified. Following that article, our approach can be classified as an extended lexical-descriptor frame-based approach, where the strict tabular-based approach of adding semantics to dictionary words is extended with a more flexible ontology that is in general tree-based. Also in the same review there is a comparison of various retrieval strategies and it is shown that a benefit of lexical based approaches like the one proposed is that they are capable of high recall and precision, and are not constrained by limitations of current theorem provers or formal specification methods. We believe that this approach is also substantially better suited to implementation using tried-and-true technologies like logic programming.

The core of the project is the development of an ontology for Open Source code, able to describe code assets, and the implementation of an indexical search based on the descriptions of each of the instantiations of this ontology. At the end of the project, this search engine and the ontology will be made available, together with a sample, middle-size database of packages and a WWW interface for making queries and for adding new package descriptions. The database can be used both as an initial example, for companies willing to use Amos in their work, and as a demonstration of the capabilities of the approach of the project.

The ontology provides an underlying tree structure which adds semantics (and more information) to the database contents, and instantiations of the ontology provide descriptions of packages. The dictionary is an unordered set of terms which are used to describe the items in the database of package descriptions. The dictionary is updated by adding the terms necessary to describe new items in the database, until a sufficiently rich set of terms appear in the database. Therefore, dictionary entries will grow quite quickly at the beginning of the project (or, in general, at the beginning of any instantiation thereof), and change very slowly in a more advanced stage. Synonyms (different wordings that represent the same concept) and generalizations can be associated to any element in the dictionary. Synonyms are useful for users in whose field of knowledge a particular term is applied to some concept; generalizations are used to broaden a search when the more specific term yielded no matching description.

The search engine is in charge of matching the user input, which consists of a series of terms from the dictionary, with a set of packages whose descriptions fulfill the user query. The set of returned packages should cover as much as possible the user's request. In the search process, the needs of some packages (i.e., packages which in turn need other packages) are taken into account to return a set of components as self-contained as possible. It is possible, however, that some query term, either initially entered by the user or generated while performing the search, remain unmatched. Measures of optimality can be used to choose among different search possibilities.

The user interacts with the matching engine and the database by means of an easy-to-use WWW-based interface. The interface provides access to dictionary terms, allows constructing a query, and returns the names of matching packages. The figure below shows a high-level view of the architecture and of the interaction among the basic parts of the system.

The ontology is a set of structured, tree-like commented "slots" that are used to store facts about source code packages in general. This is unlike other common uses of ontologies in that we will use it not only to structure information, but also to perform reasoning (in the form of search) on them, by means of a matching engine. Most ontology definitions are done nowadays using XML-based languages and representations like DAML+OIL (fensel01_oil,horrocks01_daml_oil). We have chosen a different approach, because we did not foresee a lengthy work on the ontology itself and we preferred to have and easy-to-understand, easy-to-parse, human-readable description of the project. In addition to that, the reasoning part will be performed by a matching engine created with the Ciao Prolog (ciao-novascience) programming environment, with which parsing the ontology files generated withing the project would be easy.

We have striven to be compliant with existing standards (still scarce at the moment). The most developed is the IEEE 1420.1 BIDM standard (group93_model_bidm,information95_data_model_reuse), and we tried to follow it with some extensions from the NHSE working group on Software Repositories. In particular, the fields for the certification property have been added to our package descriptions. These may be useful and applicable in specific fields like aerospace or health care.

We expect the ontology to change very slowly with time. We believe that, after the first year of the project, the ontology itself will be quite complete and static. Of course, the package database and the dictionary can grow continuously, but it is unlikely that new, significant concepts will emerge after the initial work so that a change in the tree itself is required.

For this reason, and to facilitate the initial work, we have adapted a very simple ontology description language that is simply an enumeration of classes. Attributes are stated in lines:

 <x>.<y>:                <z>                        (type):a:b

which means that in class <x> the modifier <y> has value <z> and type (type), and has minimum and maximum cardinalities a and b, respectively. If either a or b are not present, then absence of constraints is assumed. If <x>.<y> are repeated, it means that equilevel classes or representation are added. There is no assumption of any ordering among the ontology fields. This simplified representation allows using common Unix text tools to process it, and it is relatively easy to read and transform into other representations. Common types, such as string, date, and others, are part of already existing RFD standards (see, for example, http://www.w3.org/TR/xmlschema-2/ , for a definition of standard datatypes). There are some data whose contents can be further structured (e.g., URLs), but which we will represent using a flat structure (e.g., a string), as we will process them as a whole.

As an example to illustrate the ontology description, here is a small brief from the in-progress snapshot of the ontology:

 ontology.name:          AMOS
 ontology.version:       0.2
 ontology.status:        unpublished
 ontology.author:        Carlo Daffara, AMOS project
 ontology.authoremail:   cdaffara@conecta.it
 ontology.affiliation:   Conecta srl
 ontology.affiliation:   AMOS project
 ontology.description:   this is the base ontology for the AMOS project.
                         it aims to capture schemas and constraints for the
                         representation of open source code packages and
                         the ancillary data about them.
 ontology.comment:       work in progress
 ontology.language:      english, EN
 ontology.class:         asset
 ontology.class:         assetElement
 ontology.class:         user
 ontology.class:         organization
 ontology.class:         certification
 ontology.class:         dictionaryItem
 ontology.class:         dictionary

 organization.description:  this is the main class for expressing
                            users, organizations, etc.
 organization.subClassOf:   none
 organization.property:     name      (string):1
 organization.property:     email     (string):1
 organization.property:     telephone (string)
 organization.property:     webpage   (string)
 organization.property:     notes     (string)

 user.description:          based on organization
 user.subClassOf:           organization
 user.property:             affiliation (organization)

 dictionaryItem.description:  holds the individual terms of the
                              dictionary, including sinonyms and
                              specializations.
 dictionaryItem.subClassOf:   none
 dictionaryItem.property:     dictionaryentry (string):1
 dictionaryItem.property:     sinonyms        (string)
 dictionaryItem.property:     generalization  (dictionaryItem)

 // generalization are linked dictionary entry for relaxed attribution
 // of an item. Eg. SQL database --> database

 dictionary.description:      holds the entire dictionary
 dictionary.subClassOf:       none
 dictionary.property:         entries     (dictionaryItem):1

Two fields have special importance to perform searches: the one which expresses the requirements of a package, and the one which expresses what capabilities are provided by a package.Both are simply expressed as lists of dictionary items. Initial user requirements are satisfied by selecting packages whose offered capabilities match those expressed by the user; in turn, requirements by these selected packages are treated similarly.

Apart from fulfilling package requirements (i.e., some package might need some other capabilities in order to function properly), special attention is payed to input/output chainability of packages: in order to express the ability of a package output to be combined with others which require these as input, we need to be able to express package input data at the ontology level (i.e., by providing special fields, which may be empty to denote input/output data) or at the dictionary level (i.e., by selecting specific keywords to denote input/output).

We have chosen to denote input/output chaining by adding special tags to the requirements and capabilities of a package: stream(PostScript) in the requirements part will denote that some asset will accept a stream-in the abstract sense-of PostScript to perform some processing. This needs a special treatment during the search phase, since, in principle, these streams exist only as an intermediate data connection between two packages, while other properties are simply additive (e.g., if some package provides mathematical routines, then this capability remains present for the whole project). But, in return for that special considerations, descriptions of packages will become more homogeneous.

The search engine is in charge of locating an assembly of packages able to fulfill a set of user requirements, expressed using terms from the dictionary. Each open source package has two main sets of terms associated: a list of capabilities which the package gives and a list of requirements which the package needs.

Requirements and capabilities can be associated to the preconditions and postconditions in the realm of plan generation, or to premises and consequences in the first order logic world. The knowledgeable reader may appreciate the similarity with multiheaded Horn clauses. A noticeable difference is that in our case postconditions, or capabilities, are added to the ''state of the world'', except for the case of the special stream() tag referred to in the Section The Ontology and the Dictionary. Therefore, a package A can need several capabilities a, b, c, ... (i.e., preconditions), and provide several other capabilities ''m, n, o, ... (i.e., postconditions). We will write this as A^{a, b, c}_{m, n, o}'', putting preconditions at the top and postconditions at the bottom.

A very schematic matching algorithm is as follows:

     R := <initial requirements>     -- What the user wants
     F := EmptySet             -- What has been fulfilled so far
     P := EmptySet             -- Packages used so far
     do  -- Invariant: Intersection(R, F) = EmptySet
        select A^p_q such that Intersection(q, R) != EmptySet
        F  := Union(F, q)
        R  := Union(Difference(R, q), Difference(p, F))
        P  := Union(P, {A})
     until <no A^p_q can change R>
     return P and R

The intuition behind the algorithm is that as long as R has any requirement satisfiable by packages in the database, a new package is (nondeterministically) selected, and the requirements needed by this package (except for those which were already satisfied) are to be taken into account. For the sake of simplicity, the algorithm above does not take into account the special stream() tag for data streams, which only survive one chaining, and it does not take into account generalization of packages. All capabilities the selected packages provide are incrementally added to the set F of fulfilled capabilities, which helps to cut down search, as only the really unfulfilled preconditions are added to the set R of requirements at any step. The select keyword expresses a non-determinism in the selection of packages, which means that several choices of packages are possible at every iteration of the loop. Also, the process may end without having matched all the requirements (either initially entered by the user, or generated by an intermediate package selection).

The selection is expected to use heuristics aimed at approximating some kind of optimality in the final results. For example, the user might want to try different heuristics for a given project, namely: minimizing the number of packages |P|; minimizing the number of programming languages in the final set of packages; minimizing the number of final features |F| which had to be fulfilled; minimizing the number of unmatched characteristics |R| at the end of the algorithm; etc.

Optimality measures are often based on global considerations which need a completely generated plan. Optimal chainings can or course be returned by selecting all possible package sets and ordering them afterward. However, it is very possible that this number is very large, and therefore computationally prohibitive, and therefore we will resort to an approximation using local heuristics. For example, in order to minimize the number of packages in the final result, it seems sensible to choose at each step a package A^p_q which reduces R as much as possible. This eager strategy might however not yield optimal results, as it does not take into account how many preconditions p are introduced in the system.

Since it is likely that several packages A^p_q meet the conditions imposed by a local heuristic rule, we want to make proviso for several plans to be returned, so that the user is presented with different package assemblies. All of these plans try to optimize some global optimality measure, and the user will be able to select the one which (s)he deems more appropriate. Additionally, the plans shown to the user will (optionally) contain explanations as to what package was selected at each stage, and why, so that there user does not feel confronted to a black box whose internal underpinnings are unknown.

The basically symbolic nature of all the operations performed, and the fact that there is an implicit non-determinism in the search, makes logic languages clear candidates to implement a more evolved form of the above algorithm. We expect that the ease of programming in logic languages (exemplified by Prolog) will be of much help in prototyping, modifying, and tuning the algorithm above until the final tool is deployed. The implicit non-determinism of Prolog will alleviate the work of keeping track of the non-explored branches, and resuming them when needed.

The Prolog system to be used will be Ciao Prolog, which is a robust, mature, state-of-the-art, next-generation Prolog system, with a good programming environment featuring an automatic documentation generator, a module system which the compiler takes advantage of to keep track of inter-modular dependencies, and a rich set of libraries, including (remote) database access, WWW access and page generation, etc. Ciao Prolog is currently freely available for testing and use.

The user interface will be based on WWW, since we want the tool to be remotely accessible. Actually, two different interfaces will coexist: one addressed to users who only want to consult the database in order to build a new project, and another one for administrators who want to add new packages to the knowledge base. In the former case, special permissions are needed: making this interface completely open will create the risk of populating the dictionary with unneeded (or even inaccurate) terms, which would eventually result in lack of accuracy in the search process.

We have described summarily the motivation and internal structure of Amos, a project funded by the E.U. Esprit Programme which addresses the reuse of Open Source code assets. It is based on designing an ontology to describe source code; the available descriptions will be used by a matching engine, written in Ciao Prolog, to satisfy user requirements. Interaction with the system will happen through a WWW interface, also written in Ciao Prolog. We believe that the tool will be useful not only as a proof of concept, but also as a practical part of organizations whose everyday work focuses on building software projects based on creating or modifying source code pieces.

In the current state, the ontology is being finished, and a preliminary matching engine is being built in order to foresee possible scalability problems, to asses the completeness of the ontology, and to investigate feasible heuristics. We plan to develop a prototype interface in short which will allow us to introduce a preliminary set of packages and to assess the effectiveness of the technology.

Cooperating and exchanging information and experiences with other that may find our work useful, like the CoopX ( http://coopx.eu.org/ ) project, is also part of the future work. We also look forward to use the ontology and results of the project as basis for a more widely available standard, and that the matching engine (which will be released under the GPL at the end of the project) will be included both in vertical, specialized sites (like mathematical software repositories, or sites for astronomical software) but also in common developer sites like SourceForge and FreshMeat.

If the same data format and engine is used at several sites with (partially) open databases, a possible future work line would be to improve the search engine in order to cooperate in a user-transparent fashion with other search engines in order to achieve more precise results thanks to the sharing of information spread across different databases.