Amalgamating Multiple Programming Paradigms in PROLOG

1. Introduction

Recently, several knowledge programming sys­ tems, such as [Bobrow83] have been proposed and implemented with multiple programming paradigms with the functional language Lisp. The paradigms supported in these systems so far are: object-oriented, rule­ oriented, data-oriented, and procedure-oriented ones. In these systems, most inference knowledge is expressed in a rule-oriented style with an "if-then" structure, and the target structure is expressed in hierarchically organized objects (or frames). They pro­ vide an embedded uniform inference mechanism, such as a forward and backward reasoning engine to reason on the target objects.

These systems have two basic problems in representing real-world knowledge. The first drawback is from having a uniform inference mechanism. This is because a uniform mechanism prevents the utilization of multiple inference strategies in an application. The second problem is that it is hard to read a knowledge base written in this style, because the inference rules are described separately from the target object network.

incorporates Flavor-like [Weinreb81) object-oriented programming with a multiple inheritance mechanism. However, its object-oriented programming is "added on", not "amalgamated", since its object implementation is just mimicking the one on Lisp based tools. For example, object types in the system are restricted to class and instance, and it is not allowed to treat rela­ tions among objects as Prolog relations. Therefore, the relation-oriented programming style is not positively supported.

Another way Is to express a semantic network in a set of Horn clauses and to use the Prolog interpreter as an inference mechanism [Koyama85]. Again, this per­ formance is limited, because an entire network is represented with only one predicate, so that every clause matching might cause the entire network search in the worst case.

Alternatively, objects may be expressed in a nested list structure [Lee86]. But this method can not utilize Prolog expressiveness and is not efficient.

In this paper, multiple knowledge programming paradigms are amalgamated in Prolog by the technique called meta-programming [Bowen82]. Additionally, it describes a new implementation of the Prolog based knowledge · programming system called PEACE (Pro log based Engineering AppliCations Environment). It is shown that PEACE efficiently supports a semantic net­ work knowledge representation realizing relation­ oriented programming as well as object-oriented pro­ gramming, data-oriented programming and rule-oriented programming amalgamated in Prolog.

2. Semantic Network Representation In PEACE

The ultimate goal of the authors' project was to realize a system which behaves like human experts in a diagnostic domain [Koseki87). To achieve this goal, it is necessary to represent various kinds of knowledge, such as design knowledge about the diagnosed equip­ ment, and maintenance technician's empirical diagnostic knowledge. To investigate what types of knowledge representations are suitable in this domain, a prototype system was developed, using a rule-based technique similar to the one described in [Shortliffe76]. There, it was found that representing diagnostic knowledge entirely in a rule-form was not natural and feasible. It was considered appropriate to incorporate the structural information of the target equipment. To represent such a kind of knowledge, network oriented representation is suitable.

To describe network-shape knowledge representations, recent knowledge programming systems provides the object-oriented (or frame-based) paradigm. In those systems, a knowledge network is described in hierarchi­ cal trees of objects. The objects are usually classified into class-objects , and instance-objects, and they are connected by the system-defined relations, such as class to instance , and super-class to class relations. Through these relations, an inheritance mechanism is provided. Still, it is not felt natural to classify real-world knowledge into these fixed object categories and the fixed relation categories. To represent various kinds of knowledge, such as signal paths along functional blocks of the diagnosed equipment, a more flexible system is needed which can describe a more flat network.

To meet this goal, PEACE was developed to describe a semantic network on the first-order predicate logic language Prolog. It is basically different from con­ ventional object-oriented (or frame-based) systems in three aspects.

First, there is no distinction among object types. That is, there is no distinction between class-object and instance-object, no distinction between class-method and instance-method, and so on. Instead, the system only provides a uniform object representation without any system-defined types. The role of an object is determined by how it is related to the other objects. For example, if an object is related to another object with instance-of relation, it is treated as an instance object, and the other object is treated as a class object.

Second, the user is allowed to define his own rela­ tion types in his problem domain and to add his own semantics to . them. That is, relations can be defined freely with their own inheritance specifications and inverse-relation definitions. Moreover, since the rela­ tions between objects are internally represented in Pro­ leg clauses, the user is allowed to express more com­ plex relations by providing Prolog rules.

Third, since it is constructed on Prolog which has a powerful backtracking and unification mechanism, the multiple programming paradigms can also utilize these features. For instance, slots and relations defined in an object can have multiple values which can be enumerated by backtracking.

To show how multiple programming paradigms can be amalgamated in Prolog language, let us see exam­ ple descriptions in PEACE. Figure 1 shows an example family network structure in a semantic network form. Each node corresponds to a physical object or concept. They are simply called object, because the system gives no distinction in regard to object types. Each arc between objects corresponds to a semantic relation between them. For instance, this network shows the facts that "Charlotte isa female", "Charlotte and Shirley are siblings", and "Andy's parent is Shirley, and so is Wayne's".

2.1. Object Description

In PEACE, a semantic network is repre§iented as a network of objects connected by directed binary rela­ tions. An object is represented with its name and a set of Prolog clauses describing the contents in the format:

object-name ::

relation-name # destination-object;

slot-name :slot-value;

slot-name :? slot-demon;

predicate-name( arguments);

predicate-name(arguments) ::- body.

Relation and slot can have basically similar effects, as long as both are used to point to another object. The difference is that relation can only point to objects and provide inheritance, automatic inverse-relation keeping, and user defined semantics as described in the following section (Relation oriented programming); whereas slot can contain any data, including complex Prolog structures and provide demon invocation as described in the other section (Data oriented program­ ming). Note that a slot demon is defined separately and can be inherited through relations separately from slot value.

Predicates defined in an object can be treated declaratively or procedurely, as ordinal Prolog predi­ cates can be. In other words, if they are interpreted declaratively, they can be considered to be facts and rules or axioms in an object's world. If they are inter­ preted procedurely, they can be considered equivalent to methods in the object-oriented languages, such as SMALL TALK-80 [Goldberg83).

2.2. Relation Description

Roles of a relation are described in an object (relation-object) with the relation name as the object name. For the example network in Fig. 1, the relation roles are described in Fig. 2 .

The parent and child relation objects describe the relation that "parent" has inverse-relation "child" and the relation "child" has inverse-relation "parent". That is, when 'Andy' has a parent 'Shirley' , 'Shirley' has a child 'Andy' at the same time. This description is inter­ preted when a relation is added to a network, and the bi-directional relation is kept at all times.

Currently, the following four kinds of inheritance specifications can be set up in relation-objects, so that the inheritance can be restricted to certain predicate names, slot names, and relation names by specifying the names in the argument.

$inherit_pred(predicate-name), ·

$inherit_ slot_ value( slot-name),

$inherit_slot_type(slot-name},

$inherit_relation( relation-name).

For example, in Fig. 2, the relation isa has inheri­ tance specifications which enable any predicates, any slot values, and any slot types to be inherited. The rea­ son is that, in these inheritance specifications, "_" in an argument denotes an anonymous value, which matches anything.

3. Multiple Programming Paradigms

Based on the semantic network representation described in the previous section, the system can pro­ vide the multiple programming paradigms. These para­ digms are: object-oriented, relation-oriented, data­ oriented, logic-oriented, and rule-oriented ones.

3.1. ObJect Oriented Programming

Figure 3 shows the object descriptions for the fam­ ily network in Fig. 1.

• :- 'Charlotte' ::

isa # female,

possesses # present_A;

possesses # present_B.

• :- 'Shirley' ::

isa #female;

sibling # 'Charlotte'.

• :- 'Andy'::
• isa #male; parent# 'Shirley'.
• :-Wayne'::

isa #male;

parent# 'Shirley'.

Fig. 3 Object Descriptions

The symbol "#" denotes a relation. With these descriptions, a simple query like

?- 'Andy'<- parent# X. {Who is Andy's parent?)

gives an answer,

X · 'Shirley'.

You may look at the content of 'Shirley' object by typ­ ing:

?- listobj('ShirleyJ.

And you can see that the system has created two child relations 'Andy' and Wayne' in 'Shirley' object. This is because the relation child is the inverse relation of parent as described in Fig. 2.

'Shirley' ::

sibling# 'Charlotte';

isa #female; child# 'Andy'; child# Wayne'.

Therefore, a query like

?- 'Shirley'<- child# X. (Who is Shirley's child?)

gives an answer,

X= 'Andy';

X· Wayne'.

Note that the multiple answers could be obtained simply by causing backtracking (hitting semi-colon).

Next, let us describe objects for female, male and human object, in Fig. 4.

• :-female::

isa #human;

sex(female);

height :? when_empty(160).

• :-male::

isa #human;

sex( male);

height :? when_empty(175).

• :-human::

disp_sex ::-origin<- sex(X), display(X), nl; weight :? (when_empty(X) ::- origin<- height : Y, X is Y- 115).

Fig. 4 Objects with methods and demons

The predicate sex is an example of the declarative usage of predicates. The query,

?- 'Shirley'<- sex(X).

generates the answer

X"" female

by the inheritance mechanism. When this query is invoked, the object interpreter (activated by "<-" opera­ tor) tries to satisfy the goal sex(X) predicate in the object 'Shirley'. Since the interpreter can not find it, it looks for relation descriptions of 'Shirley' and finds out the relation iss inherits the predicate sex, because isa object has $inherit_pred(_) which matches the goal $inherit_pred(sex). Then, it tries the goal sex(X) again in the female and succeeds in matching X with female.

The predicate disp_sex in human is an example of the procedural usage of predicates. It denotes a pro­ cedure (method) to print out the object's sex. The dummy object origin is used in it to point to the ori­ ginating object of the inheritance chain. For example, the query,

?- 'Shirley'<- disp_sex.

prints out the answer:

female.

After climbing up the inheritance chain of isa relations, it tries the goal disp_sex in human. In human, because origin is 'Shirley' in this case,

origin<- sex(X).

succeeds in matching X to female, and the word female is printed out.

3.2. Relation Oriented Programming

Since the directed binary relations between objects are internally represented as Prolog predicates, they can be used for relation-oriented programming.

A binary relation between objects:

'Andy'::

parent # 'Shirley'.

is internally represented as two Prolog facts, such as:

'Andy'(parent, 'Shirley'). parent('Andy', 'Shirley').

When Andy's characteristics are requested, that is, when the relation name "R" is unknown in the query:

?- 'Andy'<- R # X.

the interpreter searches the first kind of internal facts with a goal 'Andy'(R,X), and gives the result:

R =parent

X = 'Shirley'.

In this way, the number of matchings is restricted to the number of relations in the object and the search through the entire objects can be avoided.

On the other hand, when the relation name is known, it searches the second kind of facts with a goal parent(X,Y). Again, in this way, the search through the entire Prolog data base is avoided and the number of matchings is restricted to the number of related pairs for the relation in the worst case.

To search a set of the objects, by which relations can be expressed logically, only the Prolog rules to express its logic are to be added. For example, to express relations aunt and sister in the example family network, you should add two rules:

aunt(X,Z) :- parent(X, Y),sister(Y,Z). (Aunts are parent's sisters) sister(X, Y) :- sibling(X, Y), Y<-sex(female). (Sisters are any siblings who are female) The query like, ?- 'Andy'<- aunt# X. gives an answer, X= 'Charlotte'.

Using this feature, we can easily define inference rules pertaining to a certain relation. For example, a rule "A// of aunts give presents to their nephews" can be described as:

present_rule :- (aunt(X, Y), %for all of nephew·aunt pairs{X, Y) caii((Y <-possesses# P, %check if Y has a present P P <- instance_of #present, Y <-possesses#-= P, %get the present P from Y X<- possesses#+= P, %give the present P to x !)), fail;true).

The call operator is used to restrict the scope of the cut (!) operator. By executing this rule, Charlotte's presents are given to all of her nephews, Andy and Wayne. In this way, the relation-oriented programming can be accomplished nicely, in combination with the object­ oriented programming.

3.3. Data Oriented Programming

Slots can have demons. The system provides several kinds of demons: when_empty, referred, con­ strain, after_put, removed, and after_add. In the exam­ ple, a query,

?- 'Andy'<- height: X. gives an answer, X= 175

This is because when_empty demon in male worked since there was no height slot found in 'Andy' and isa inherits any slot types. A query,

?- 'Andy'<- weight : X.

gives an answer,

X=60

since when_empty demon in human calculates weight by subtracting 115 from its height as a default.

3.4. Logic Oriented Programming

Since the system i~ built Ol') the IOQic pro~rammipg language Prolog and preserves the features of the language, such as backtracking and a unification mechanism, all of the above mentioned programming paradigms can be incorporated in the logic program­ ming style.

For example, the setof predicate can be used nicely with object oriented programming. The query to get all of Charlotte's nephews,

?- setof(X, ( aunt(X, 'Charlotte') ,X< -sex( male)), S ).

3.5. Rule Oriented Programming

The Prolog interpreter itself works as a backward chaining rule interpreter with a backtracking mechan­ ism. To realize a forward chaining mechanism on Pro­ log is a relatively easy task. The simplest way to describe a rule with a Prolog clause is like:

fire_rule :- premise_1, premise_2, /,

conclusion_1, conclusion_2.

But the rule control mechanism must be written by the user. PEACE provides a special rule interpreter to give more flexible control. It interprets a set of rules described in a rule-object which has the format:

rule_set_name ::

$control(control_specification);

if premise

then conclusion;

The premise and the conclusion are described in PEACE and Prolog predicates. A Production system

can be realized using the semantic network as a work­ ing memory. The provided control specification types are do_1 , do_all , while_1, and while_all.

4. Implementation

PEACE is implemented on engineering work­ stations running standard Prolog interpreters and com­ pilers, including C-Prolog [Pereira84) and others.

The interpreter is realized with the meta­ programming technique (Bowen82, Miyachi84), known as the Prolog-in-Prolog technique, which is to write the Prolog interpreter in Prolog itself. This method is also used in realizing metaProlog (Bowen85). It gives great flexibility to the system implementation, but degrades execution performance. However, the degradation was permissible in building a diagnostic expert system (Koseki87].

Object descriptions are parsed when fed to the system and are stored as Prolog assertions. Slots, predicates, and relations pertaining to an object are internally represented as Prolog assertions with the same functor name as the object name, with different numbers of arguments. The multiple inheritance mechanism works interpretively so that dynamic addi­ tions of objects cause no troubles. Therefore, future efforts toward automatic knowledge acquisition may be relatively easy.

Since most of the Prolog compilers support the incremental compiling which enables it to compile a selected portion of a program, static objects which are never modified during execution can be compiled for speed up, without much effort to develop a special object-compiler. In addition, with the Prolog compiler's clause-indexing function [Bowen81 ], the time complexity for searching a predicate (including slot and relation) in an object may become constant.

A user-friendly interface is provided with a menu­ driven and mouse-driven environment on commonly­ used engineering workstations. Most of the basic operations including browsing the knowledge base network can be done by mouse operations. An exam­ ple user interface screen is shown in Fig. 5.

5. Conclusion

A way to amalgamate multiple programming para­ digms, such as relation-oriented, object-oriented, data­ oriented and rule-oriented ones, was shown with exam­ ples on a Prolog-based knowledge programming sys­ tem PEACE. By combining Prolog's logic programming capabilities, it was possible to achieve more flexibility in representing the real world knowledge than when using conventional knowledge representation systems.

The system has been successfully used in realizing an expert system in a diagnostic domain and has proved to be effective in representing various kinds of knowledge, such as target equipment structure and the diagnosis technician's empirical knowledge. In particu­ lar, the relation-oriented programming technique was effective in representing symptom-hypothesis relations and the structure of the diagnosed equipment (Koseki87].

ACKNOWLEDGEMENTS

The author thanks Shin-ichi Wada, the co-worker on the diagnostic expert system and also thanks Nobuyasu Wakasugi, Masaki Kondo, and Mitsugu Oishi for developing PEACE. He also expresses deep appre- . ciation to Hajimu Mori, and Satoshi Goto for continuous encouragement and support. Finally, he would like to thank Yasuo !washita of the Institute for New Genera­ tion Computer Technology for various kinds of support.