Uses, improvements and extensions of Prolog+CG :
Case studies

Adil Kabbaj1, Bernard Moulin2,
Jeremi Gancet2 , David Nadeau2, Olivier Rouleau2

1 INSEA, Rabat, Maroc, B.P. 6217

 

2 Université Laval, Computer Science Department
Québec, Québec, Canada G1K 7P4

Abstract.  Prolog+CG is a CG-Based logic programming language which integrates Prolog, the manipulation of conceptual graphs (CGs), Java and object-oriented constructs. It provides a powerful development environment for the creation of knowledge-based applications and their integration on the web. Java provides object-oriented capabilities allowing the development of multi-platform applications. Object-oriented Prolog provides the full power of an object-oriented logic programming language and CGs provide the expressive power of an advanced knowledge representation language. This paper presents the recent extensions that have been added to Prolog+CG and illustrates some typical uses of the environment for the development of various applications.

 

Note: This paper has been published in ICCS’01 Proceedings by Springer-Verlag:

1   Introduction

The language Prolog+CG has been developed by A. Kabbaj [2, 3] in order to extend the Prolog language in two main directions : a conceptual extension allowing the representation of goals with conceptual graphs (CGs) and the manipulation of simple and compound CGs (type hierarchy, operations on conceptual graphs, etc.); an object oriented extension allowing the manipulation of objects (object specification, inheritance mechanisms, etc.).

Recently, Prolog+CG has been extend to include a natural and powerful interface with Java. This integration benefits from the fact that both the Prolog+CG language and its development environment are implemented using Java. Hence and thanks to this new interface, Prolog+CG can be called from a Java code and inversely, Java classes can be manipulated from a Prolog+CG program.

The integration of Java, object-oriented Prolog and the manipulation of CGs provides a powerful development environment for the creation of knowledge-based applications and their integration on the web. Java allows the development of multi-platform applications as well as the capabilities of object-oriented languages. Object-oriented Prolog provides the full power of a logic programming language well suited for natural language processing, inference and symbolic manipulations. CGs provide the expressive power of an advanced knowledge representation language (advanced semantic nets, type hierarchy, schemas, notion of context, etc.). During the past six months an intensive and productive collaboration between A. Kabbaj and the other authors has enabled the development of new extensions to Prolog+CG which are strengthening the integration of its three language paradigms and providing new capabilities. This paper reports on the authors' experience using Prolog+CG language and its development environment. Some aspects of the language and its environment have been refined, some bugs have been identified and fixed and several extensions have been suggested and implemented.

The paper is organized as follows. Section 2 reports on the extension of Prolog+CG which allows calling a Prolog+CG program from a Java program. Section 3 illustrates the expert system mode available in Prolog+CG. Section 4 reports on the extension of Prolog+CG which enables the call of applications from a Prolog+CG program. Section 6 presents the extension of Prolog+CG which allows the use of Java code : creation of an instance of a class, accessing attributes and calling methods of instances or classes. It also illustrates how these extensions can be used in a natural language processing context. Section 6 and 7 present two other case studies. Section 8 discusses future orientations, and the potential use of Prolog+CG for the development of advanced applications.

Other extensions of Prolog+CG, such as types hierarchy operations and operations on simple and compound CGs with sets and co-references are described in [4].

Figure 1 shows a snapshot of the new Prolog+CG environment : the main frame is a split pane that can be used to edit a program (in the top pane) and to interact with the interpreter (in the bottom pane). Prolog+CG 2.5 provides also a visual debugger which shows the construction/deconstruction of the inference tree (Figure 1) and an “inspection” feature which allows the user to have a detailed description of the inference tree node (Figure 1, the window at the bottom) or to have the value of a variable. More details on the new Prolog+CG environment is provided through the Help menu and the site : www.insea.ac.ma/CGTools/PROLOG+CG.htm

2   Calling Prolog+CG from Java programs

The Prolog language provides powerful reasoning and symbolic manipulation capabilities, but it is not well suited to implement the interface functionalities (windows, menus, link to data bases, etc.) that object-oriented languages provide. Hence, a good development strategy consists in using each Prolog+CG programming paradigm to implement the functionalities that it best supports. It is recommended to develop programs using Java and to call the Prolog+CG modules when it is appropriate. This section presents a set of primitives that Prolog+CG 2.5 provides in order to call Prolog+CG modules from Java programs. The use of these primitives is illustrated using a simple example.

 

 

Figure 1: The new Prolog+CG 2.5 Environment

 

Four primitives are used to exploit a Prolog+CG program from a Java program

 

ü         void LoadFile(String fileName) :   “fileName” is the name of a Prolog+CG program. The role of this primitive is to load a Prolog+CG program contained in the file “fileName”.

ü         Vector  Resolve(String Quest [, boolean convertResult] [, boolean ExpertSystemMode]) : the parameter “Quest” is the request that Prolog+CG should resolve and the two other arguments are optional :

·           “convertResult”, if it is specified, is a boolean that indicates if the returned result should be converted to String or to be returned as Java objects. This argument is set to true (i.e. convert to String) by default.

·           “ExpertSystemMode”, if it is specified, is a boolean that indicates if Prolog+CG should behave like an expert system shell or like a Prolog interpreter. This second argument is optional and it is set to false by default.

The primitive goal Resolve/31 returns all the solutions in a Vector of hashtables; one solution being represented by a hashtable. Since a solution is a set of couples <VariableIdentifier, VariableValue>, it is natural to represent it as a hashtable with VariableIdentifier as a key. To get the value of a variable in a solution, one has to use the hashtable method “get(key)” where key stands for a variable identifier.

ü         void SaveFile(String fileName) : saves the current program in the Prolog+CG file “fileName”.

ü         void PurgeMemory() : deletes the current Prolog+CG program from memory.

 

Example :

Assume that we have a Prolog+CG program “FamilyRelations.plgCG” which contains, among other things, the following facts and rules :

[Man : John]-fatherOf->[Man : Peter].                     

[Woman : Deborah]-motherOf->[Man : Peter].

[Man : John]-fatherOf->[Woman : Clara]. 

[Person : x]-parentOf->[Man : y] :-

          [Person : x]-fatherOf->[Man : y].

[Person : x]-parentOf->[Woman : y] :-

          [Person : x]-motherOf->[Woman : y].

 

From a Java program, we can assert new facts and retract existing facts from the above Prolog+CG program and we can ask questions and get answers. Here is an example:

//PrologPlusCG is implemented as a Java Package

import  PrologPlusCG.PrologPlusCGFrame; 

public void example() {

          ... any Java code

          // Load a Prolog+CG File

          LoadFile(“FamilyRelations.plgCG”); 

          ... any Java code

          // Resolve a question

          Vector  solutions  =  Resolve(“[Person : x]-parentOf->[Person : y].”);

          // Make access to the solutions and to their content

          Hashtable solution;

          String valX, valY;

          For (Enumeration e = solutions.elements(); e.hasMoreElements(); ) {

             // Make access to a solution

             solution = (Hashtable) e.nextElement();

             // Make access to the variable’s value for the solution

             valX = (String) get(“x”);

             valY = (String) get(“y”);

             // Make use of the variable’s value

          };

           // Assert a new fact in the Prolog+CG program

          Resolve(“asserta([Man : Marc]-fatherOf->[Man : Clark],     ()).”);

          // Save the current program in a new file

          SaveFile(“FamilyRels1.plgCG”);

          // Purge the current program from the memor

           PurgeMemory();

 

The four primitives “LoadFile”, “Resolve”, “SaveFile” and “PurgeMemory” are “external” primitives of Prolog+CG and constitute the interface from Java to Prolog+CG : they are used in a Java Program to make use of a Prolog+CG program. These simple external commands may look like details but they are a tremendous step forward in making the Prolog+CG language a concrete development tool. The interface inability to convey a sense of usability and user-friendliness has long been a major obstacle in using logic programs in real end-user developments.

 


(a) an input screen                                                (b) output screens                          

 

Figure 2 : front/end interface for a Prolog+CG program

For instance, it is not unusual to have many lines of Prolog code to enter before making a useful query. In addition, a lot of parameters in these lines of code are very sensible to error and require that the user know the program's internal workings fairly well to be able to get any valuable information from the system. In addition, the answer has the typical Prolog form (an output list) and it is sometimes very hard to read. The output list (i.e. the solution) is neither sorted alphabetically nor numerically. Finally, if the user wants additional information on one of the listed items, an additional query is necessary. All these considerations find an elegant solution using the Java/Prolog+CG interface.  We have used this interface to develop a simple Prolog+CG program (Figure 2). The front/end interface has been implemented using Java and the reasoning part using Prolog+CG. The input screen (Figure 2.a) offers lists and slider bars and actually writes in the Prolog+CG program four assertions for the user, using his selections. A results-screen (Figure 2.b) then presents the output list which can be sorted using any criteria. Additional information on a given list item can be obtained with the simple press of a button (Figure 2.b). Using this example, we wanted to emphasize the importance of having interfaces between languages thus allowing each to be used for what it is best at. 

3   The Expert System Mode of Prolog+CG

Prolog+CG 2.5 provides two resolution modes : a Prolog-like resolution which is the default mode and an expert system shell mode. In the first mode, when a goal is not a primitive nor a defined goal, the resolution process assumes that it is false. In the expert system mode however, the resolution process asks a question to the user in order to establish the truth of such a goal and it records it (using an assert operation).

 

Example : A excerpt from a simple expert system about animal classification

Universal > Object, Animal, Person, Action, State, Attribute.

Object > Hair, Meat, Teeth, Claw, Eye.

Animal > Mammal, Carnivore, Cheetah.

Person > Man.

Action > Eat.

State > Belong.

Attribute > Color, Component, Tawny, Dark, Pointed, Forward.

Man = Robert.

Animal = Yala.

[Animal : x]-is->[Carnivore] :-

[Eat] -

       -obj->[Meat],

-agnt->[Animal : x].

[Animal : x]-is->[Carnivore] :-

  [Animal : x]-poss->[Teeth]-attr->[Pointed],

  [Animal : x]-poss->[Claw].

[Belong] -

     -bnfcre->[Man : Robert],

     -pat->[Animal : Yala] -

              -colorOf->[Color]-attr->[Tawny],

              -poss->[Teeth]-attr->[Pointed];.

After the compilation of this example, the user can set the expert system mode to “on” by activating, from a Prolog+CG menu, the action “Build/Expert System Mode”. Here is an excerpt from the interaction that took place :

?- [Animal : Yala]-is->[Cheetah], /.

==> The goal  : [Animal : Yala]-poss->[Hair] cannot be infered from what is known, so

==> Is it true that : [Animal : Yala]-poss->[Hair] ? tape y (for yes) or n (for no) : y.

As a side effect of the whole interaction, the following facts are added to the database

[Animal : Yala]-poss->[Hair].

[Eat] -

   -obj->[Meat],

   -agnt->[Animal : Yala].

[Animal : Yala]-partOf->[Component]-attr->[Dark].

 

The expert system mode of Prolog+CG can be exploited from a Java program by using the primitives described in Section 3. In this case, the third argument of the primitive “Resolve/3” should be used and should be set to “true”.

To make the expert system mode of Prolog+CG a kernel for a complete expert system shell we are implementing the explication capability (i.e. respond to Why/How/What questions).

4   Calling applications from a Prolog+CG program

Prolog+CG 2.5 provides two primitives which allow calling an executable application from a Prolog+CG program. This is another way to make use of Prolog+CG 's capabilities to work as a component of a larger system.

ü         exec(ExecFileName) : starts the execution of the application “ExecFileName” and continues the current resolution.

ü         execAndWait(ExecFileName) : starts the execution of the application “ExecFileName” and waits for its termination. Then it resumes the current resolution of the Prolog+CG program.

 

Example :

 ex1 :-

  eq(x, 45),

  exec("Synergy.exe"),

  write("Continue without waiting for the end of Synergy..."), /.

 ex2 :-

  eq(x, 45),

  execAndWait("Synergy.exe"),

 write("Continue after the end of Synergy ..."), /.

5  Using Java code from Prolog+CG

Prolog+CG 2.5 provides several primitives allowing the use of Java code and providing access to object-oriented capabilities. Indeed, new Java objects can be created, used and destroyed from a Prolog+CG program. These objects are considered as “global objects” of a Prolog+CG program.

This section presents these primitives and briefly illustrates their use.

ü         new(NewObjectIdent, JavaClass, ConstructorArguments) : this primitive goal enables the creation of a new Java object. It corresponds to the following Java instruction :

JavaClass NewObjectIdent = new JavaClass ConstructorArguments;

ü         destroy(ObjectIdent) : this primitive goal destroys the Java object identified by “ObjectIdent”.

ü         destroyAll  : this primitive goal destroys all the Java objects that have been created in the current program.

ü         get(Data, AttributeIdent, ObjectIdent) : this primitive goal can be used to get the value of the attribute "AttributeIdent" of the object "ObjectIdent". The value is then unified with the first argument "Data".

ü         set(Data, AttributeIdent, ObjectIdent) : this primitive goal can be used to set "Data" as the value of the attribute "AttributeIdent" of the object "ObjectIdent".

ü         execMethod(Data_Or_void, JavaClass_Or_ObjectIdent, MethodIdent, MethodArguments) :

this primitive goal can be used to call a method "MethodIdent", of a Java class (in the case of a static method) or of a Java object with the argument list "MethodArguments". If the method is of type void then the first argument of the primitive execMethod should be the keyword "void". If the first argument of execMethod is a global variable (a new feature in Prolog+CG), then the result of the method is assigned to the variable, otherwise the returned value is unified with the first argument of execMethod.

 

An application that calls Java code : SHRDLU-PCG

To illustrate the expressive power of Prolog+CG and to show its usefulness for the development of natural language processing applications, we developed SHRDLU-PCG, a reformulation in Prolog+CG of some aspects of the classic SHRDLU program [10]. In the Prolog+CG program (see below), one can note the natural use of CG as a data structure, beside term and list, and also the very use of variables in CG : a variable can hold for a CG, a concept, a concept type, a referent, a co-referent, a concept description (or value) and a relation. This flexibility is very important from a programming perspective.

SHRDLU-PCG also illustrates how Java classes (and their attributes and methods) can be used from a Prolog+CG program.

SHRDLU-PCG simulates a very restricted natural language dialog between a user and a robot that operates in a block-world. The robot can create, move, push and pop 3D blocks. The robot is able to “understand” declarative, imperative and interrogative sentences and to react accordingly. The 3D animation that results from such a dialog is monitored thanks to the “cooperation” of the Prolog+CG program SHRDLU-PCG with a Java3D program which provides the capability to create a 3D canvas, to fill it with 3D objects (cube, cylinder, sphere, pyramid) and to do some actions on them.

First, let us consider how the semantic analysis of a sentence and especially the analysis of an imperative sentence is carried out. Examples of imperative sentences are “create a red pyramid pyramid4.”, “push the red pyramid on the big cube.” and  “move the blue sphere at the left of cube1.”.

As the components of the sentence are analyzed, CGs that represent their semantic meaning are constructed and then joined. This dynamic construction of CGs is in itself an important feature of Prolog+CG.

 

// lexicon(Word, SyntaxicCategory, TypeOrCGCanon)

lexicon("push", verb, [Push]-

               -obj->[Object],

                -on->[Object]     ).

lexicon("create", verb, [Create]-obj->[Object]-colorOf->[Color]).

Lexicon("sphere", noun, Sphere).

Verb(V, _CGCanon) :- lexicon(V, verb, _CGCanon).

// Syntax of imperative-sentence = Verb  NP  Complement.

// Complement = [Prep  NP].

imperative_sentence((V|P1),

[Proposition : G]-mode->[Modality : imperative]) :-

   Verb(V, G_V),

   NP(P1, P2, E_NP1, S1),

   eq([T_Verb]-obj->E_N_G1, G_V),

   maximalJoin(G_V, E_N_G1, S1, E_NP1, G1_S1, _),

   complement(P2, T_Verb, G1_S1, G).

 

Comment on Verb/2 : checks if V is a verb, if so, return the canon of the verb.

Comment on imperative_sentence/2 :

imperative_sentence(P, G) receives a sentence P, as a list of words, and produces a CG G that represents its meaning. It starts by recognizing the verb and then the noun phrase. The canon of the verb (G_V) is then joined with the CG corresponding to the noun phrase (S1). This maximal join should satisfy however the following constraint : the concept that represents the head of the noun phrase has to be joined with the concept that represents the object of the verb. So we have to locate these two concepts in the two CGs respectively and then we have to consider them as “entry concepts” for the maximal join in question; this later should start by the join of the two entry concepts.

The entry concept for the CG G_V that represents the semantic meaning of the verb is located by the following goal :  eq([T_Verb]-obj->E_N_G1, G_V).

To understand the effect of the above goal, let's consider this request :

?- eq(G_V,[Create]-obj->[Sphere:sphere1]), eq([T_Verb]-obj->E_N_G1, G_V).

{G_V = [Create]-obj->[Sphere:sphere1], T_Verb = Create,

E_N_G1 = [Sphere:sphere1]}

As a result of the above unification eq/2, the variable “E_N_G1” refers to the concept in G_V that represents the object of the verb. Note how the variable “T_Verb” stands for the type of the concept and the variable “E_N_G1” stands for the whole concept.

The defined goal NP/4 : NP(P1, P2, E_NP1, S1) returns the graph S1 that represents the meaning of the noun phrase as well as the entry concept E_NP1 in S1.

After the analysis of the verb and the noun phrase, the maximal join of their semantic representations is done, producing a CG G1_S1 and then, the semantic analysis of the complement is initiated. If the complement is specified, its semantic representation will be computed and then joined with the CG  G1_S1. A detailed description of maximalJoin and other CG operations in Prolog+CG is given in [4].

After the semantic analysis of an imperative sentence, the “robot” will consider its meaning as an order to be executed. Hence and as a result of such an execution, the knowledge of the “robot” will change (for instance, the position of an object has to be modified) as well as the 3D animation that shows the visual simulation of the robot behavior. The following Prolog+CG code shows how all these aspects are related.

Shrdlu :-

  new(aShrdlu_Canvas3D, "PrologPlusCG.Shrdlu_Canvas3D", ()),

  read_sentence(_sentence),

  ShrdluDialog(_sentence), /.

ShrdluDialog(("end", ".")) :- /.

ShrdluDialog(_sentence) :-

  Semantic_Analysis(_sentence, _CG),  

  _CG,

  read_sentence(_s),

 ShrdluDialog(_s), /.

 

Comment on the main goal Shrdlu : this goal initiates the 3D simulation as well as the restricted natural language dialog. In particular, it specifies a call to the primitive goal “new” in order to create an instance of the defined Java 3D class Shrdlu_Canvas3D. Such a creation will involve, among other actions, the display of a frame that contains a “robot” (Figure 3.a).

 

Comment on the goal ShrdluDialog : in the above definition of “ShrdluDialog” goal, note how the meaning of the sentence (i.e. the CG “_CG” that results from the semantic analysis of “_sentence”) is put as a goal to be interpreted. Thus, in the case of an imperative sentence, the goal-variable “_CG” will be bound to the following CG :  [Proposition : G]-mode->[MODALITY : imperative] 

 

The proposition G (the variable G will be bound to a CG) is interpreted as an order that should be satisfied. Here is the Prolog+CG rule that naturally formulates this interpretation :

[Proposition : G]-mode->[MODALITY : imperative] :- G.

Each order is then executed according to its semantic interpretation. For instance, the order to create an object with a specific name and color is defined as follows : first assert the existence of the object in the data base, then create a physical object in the 3D canvas. Each kind of object (Cube, Sphere, Pyramid) is created by a corresponding method in the defined Java class “Shrdlu_Canvas3D”.

[Create]-obj->[T_Obj : _IdObj]-colorOf->[Color: C] :-

   asserta(object([T_Obj : _IdObj]-colorOf->[Color :     C]), ()),

   execMethod(void, “PrologPlusCG.Shrdlu_Canvas3D”,

          T_Obj, (_IdObj, C)), /.

6   A simple natural language analyzer for English sentences

Prolog is a popular language for the development of natural language processing (NLP) applications. CGs are well-suited for the semantic representation of NL sentences. Having both Prolog and CG manipulation mechanisms integrated in a single environment provides a powerful platform for NLP. We present the results of a preliminary investigation of Prolog+CG's potential for NLP. We selected a NL analyzer for English written in Prolog [1] and we reprogrammed it using Prolog+CG. The resulting program was much more concise and readable thanks to the CG manipulation mechanisms and to CGs' expressive power.

We built the lexicon as a lexical type hierarchy composed of lexical categories and elements. Here is the top-level of this hierarchy illustrated on a simple example:

                               universalGram > verb, noun, determiner.

                               verb > transitive, intransitive, copular.

                               noun > commonNoun, properNoun.

                               determiner > detSing, detPlur.

                               detSing > a, the, that, this.

                               detPlur > the, these.

                               commonNoun > dog, cat , ...

                               transitive > eat, chase,  … 

                               intransitive > sleep, ...

Such a representation is well-structured, clearer and shorter than the standard Prolog predicates used to represent lexical entries such as:

                               lexicon(dog, commonNoun).

                               lexicon(cat, commonNoun).

                               lexicon(eat, verb)…

For the semantic analysis, we naturally used a concept type hierarchy which can be expressed in a Prolog+CG program in a very concise way (no need of Prolog predicates for that). Here is part of our simple example:

                               universalSem > animate, inanimate...

                               animate > animal, human.

                               inanimate > object, plant.

                               animal > carnivorous, vegetarian, omnivorous.

We also used CGs to represent conceptual schemas in a very legible and concise way compared to the equivalent Prolog entries. For example, expressing the property that "carnivorous eat meat" is a simple Prolog+CG entry:

                               mySem ( [carnivorous]<-subj-[eat]-obj->[meat] ). 

 

The program performs semantic analysis in two steps. The first step consists in building the CGs corresponding to the analysed sentence in parallel with the syntactic analysis. When the program finds a syntactic pattern which matches the NL entry, a "high level CG" is built using the syntactic concepts (Verb, Noun, Adjective, etc.) and relations (Subj, Obj, Attr, etc.). When all the parts of a sentence have been analysed, the resulting CGs can be easily joined in order to create the graph corresponding to the whole sentence, thanks to Prolog+CG's graph manipulation operations such as the maximalJoin primitive. For example, applying the maximalJoin primitive on the two following parts which result from the analysis of the sentence's noun-phrase and verb-phrase portions :

[verb]-obj->[meat]-attr->[adjective]  and  [dog]<-subj-[eat]-obj->[noun]

we get the following CG:   [dog]<-subj-[eat]-obj->[meat]-attr->[adjective]

It is clear that developing the equivalent program in pure Prolog would require much more effort. Hence, thanks to Prolog+CG graph manipulation mechanisms and to few instructions integrated in the syntactic part of the NLP analyser, we get the results of the syntactic analysis in the form of CGs.

The second step of the semantic analysis consists in performing the semantic validation of the CGs obtained after the syntactic analysis. The idea is to isolate different parts of a resulting CG and to check if they match conceptual schemas contained in the system's knowledge base. For example, from the graph:

                               [dog]<-subj-[eat]-obj->[meat]-attr->[tasty]

the program extracts two graphs

                               [dog]<-subj-[eat]-obj->[meat]      and         [meat]-attr->[tasty]

and checks if they are compatible with schemas contained in the knowledge base.

In this program we have explored only few NLP mechanisms. We think that almost all knowledge levels of a NL analyser could be encoded thanks to CGs mechanisms, from the morphological level to the semantic level, including lexical and syntactic levels. This point will be the subject of a forthcoming paper. Prolog+CG's graph manipulation mechanisms and CGs' expressive power greatly improve the construction of NLP applications, providing more concise, legible and efficient programs.

7 Evaluation of the semantic similarity between two CGs

We explored the interest of using Prolog+CG to develop a program aiming at evaluating the semantic similarity between two CGs. For example such a program can be useful to search similar cases in a case base [6].

Let’s consider for instance these two CGs :

          CG1 : [Eat]-            CG2 : [Eat]-

          -agnt->[Monkey]         -agnt->[Human]

          -obj->[Banana]          -obj->[Vegetable]

          -mnr->[Fast].                 -col->[Green].

We can observe two main differences between CG1 and CG2. First, there is a semantic distance between corresponding nodes. For example, the agent of eating in CG1 is a “monkey” and  “human” in CG2.  These two concepts are linked by their common super-type “Animal” in the type hierarchy. We can also observe that the global structures of the two CG’s are dissimilar.

Several authors proposed similarity algorithms which make use of these differences [7, 8, 9, 11]. The evaluation of semantic distance is called surface similarity while the evaluation of maximal common structure is called structure similarity. Maher's Absolute Distance (d) and Yang et al.'s Degree Of Inheritance (DOI) are useful to evaluate the semantic distance between two concepts. We have written a Prolog+CG program that compute both.

Poole and Campbell [9] presented a complete structure similarity algorithm in their publication. PROLOG+CG's advanced knowledge manipulation capabilities allow us to directly find the common generalization of two CGs using the generalize  primitive : generalize(_CG1, _CG2, _CommonStructure).

Applied to our example, the program finds the following CG and the associated semantic distances.

           [Animal]<-agnt-[Eat]-obj->[Comestible].

           dMonkey,Human = 2     DOIMonkey,Human = 0

           dEat,Eat = 0        DOIEat,Eat = 0

           dVegetal,Banana = 3         DOIVegetal,Banana = 1

An overall similarity percentage can be deduced from these information according to specific domain constraints.

In 1999, Nadeau developed this program using WinProlog. The program had 360 lines of code. The program's new version, written in Prolog+CG, has only 74 lines of code. Again, we found that Prolog+CG offers a greater expressive power than pure Prolog, greatly improving the legibility and conciseness of the programs.

8   Future Works and Conclusion

Prolog+CG is a CG-Based logic programming language; CGs play the same role as terms, i.e. they are used to represent goals and data structures. Moreover, Prolog+CG provides several primitive goals to manipulate concept type hierarchy and CGs [4].

As illustrated in this paper, Prolog+CG 2.5 integrates not only object-oriented Prolog and CG formalism, but also Java technology. It then offers a great potential for the development of a large variety of applications.

Because Prolog+CG is based on an interpreter written in Java, it is slower than commercial Prolog systems such as WinProlog. We are confident that Prolog+CG's performance will significantly improve during the coming year. However, the system's current performance is already quite reasonable for the development of prototype systems, and Prolog+CG's offers such a rich prototyping environment for the development of knowledge-based applications. More and more applications are developed using Java. Prolog+CG enables developers to integrate some kind of intelligence in such applications, taking advantage of the expressive power of CGs and the reasoning capabilities of Prolog. It will be easy to create modules that handle ontologies (using the CG type hierarchy and CGs as concept schematas), sub-systems that provide some natural language capabilities, components that provide all sorts of reasoning capabilities using structures expressed in CGs.

Many specialized libraries are available in C++. We plan to develop in the coming year a link between Prolog+CG and C++ in order to take advantage of the functionalities provided by such libraries. With this link to C++, Prolog+CG will become a very powerful platform for the development of applications integrating object-oriented components and knowledge-based systems taking advantage of the expressive power of CGs and the reasoning capabilities of Prolog.  

Acknowledgments

Special thanks from A. Kabbaj to B. Moulin who suggested and pushed such an intensive and productive collaboration. Special thanks also from A. Kabbaj to the other authors who contributed strongly, by their critics and requests, to the extension of Prolog+CG. Finally, thanks to Issam Alloul who developed the Java3D program for the SHRDLU-PCG application.

References

1. Bee-gent Software agent environment (Toshiba):

 http://www2.toshiba.co.jp/beegent/index.htm

2. Gal A., Lapalme G., Saint-Dizier P., Somers H.(1991) Prolog for Natural Language Processing, Wiley Professional Computing editions.

3. Kabbaj A. (1996), Un système multi-paradigme pour la manipulation des connaissances utilisant la théorie des graphes conceptuels, Ph. D. Thesis, Université de Montréal, Canada.

4. Kabbaj A., Janta-Polczynski M. (2000), From PROLOG++ to PROLOG+CG : A CG Object-Oriented Logic Programming Language, in Conceptual Structures : Logical, Linguistic, and Computational Issues, Ganter B. and G. W. Mineau (eds.), Springer, LNAI 1867, 540-554.

5. Kabbaj A., The impact of sets and co-references on CG operations in Prolog+CG 2.5, Submitted to ICCS'2001

6. Kolodner J. (1993) Case-Based Reasoning, Morgan Kaufmann.

7. Maher P.E. (1993) A similarity measure for conceptual graphs, International journal of intelligent systems, Vol 8, No. 8, 1993, 819-837.

8. Myaeng H. , Lopez-Lopez A. (1992) Conceptual graph matching : a flexible algorithm and experiments, Journal of experimental and Theoretical Artificial Intelligence, Vol 4, April-June, 107-126.

9. Poole J., Campbell J.A. (1995) A novel algorithm for matching conceptual and related graphs, Conceptual structures: applications, implementation and theory, In G. Ellis et al. (eds.), Springer Verlag Lecture notes in Artificial Intelligence 954, 293-307.

10. Winograd T. (1972), Understanding Natural Language, Academic Press, NY.

11. Yang G-C., Choi Y.B. and Oh J.C. (1993) CGMA : A novel conceptual graph matching algorithm, Conceptual structures : theory and implementation, In H.D. Pfeiffer, T.E. Nagle (eds.), Springer Verlag Lecture notes in Artificial Intelligence754, 252-261.


1 Resolve/3 means a predicate with identifier Resolve and three arguments (i.e. arity 3).