The Design Of A System For Designing Knowledge Representation Systems

James L. Weiner Computer Science Department University of New Hampshire

ABSTRACT

The use of abstract data types as a basis for designing experimental knowledge representation systems is discussed. Abstract data types are shown to have features in common with several diverse representation formalisms (e.g. semantic networks, frames and KLONE). For example, abstract data types have notions analogous to concept, subconcept and inheritance. The relatively small conceptual distance between abstract data types and knowledge representation formalisms make them an ideal vehicle for implementing such formalisms.

I INTRODUCTION

Representation of knowledge is of primary im­ portance to programs dealing with real world situ­ ations. There have been several attempts to derive an appropriate formalism that would help to minimize the. problems in this difficult area. There have been just as many resulting methodo­ logies, offering widely different solutions: Frames [Minsky, 1975], Semantic Networks [Quillian, 1968], KRL [Bobrow and Winograd, 1977], First­ Order Logic [Hayes, 1977], and KLONE [Brachman, 1979]. These different methodologies are based on fundamentally different assumptions about the nature of knowledge, each with convincing claims for its precedence. In order to compare these assumptions it would be necessary to find a common basis of representation. We contend that the dif­ ferent formalisms can all be expressed in logic combined with abstract data types, and that this proves to be a useful and informative tool for designing knowledge representation systems.

Logic with abstract data types (ADTs) offers a solid foundation that already includes many of the facilities built into knowledge representation languages. It also allows a system to be built that combines features from different formalisms, providing an ideal testing ground for purposes of comparison; There are also inherent advantages in the choice of logic with ADTs. By writing programs in logic, especially clausal logic [Kowalski, 1980], we have both a mathematical semantics or specification and an operational semantics that allows us to execute that specification. ADT's have the same advantage, whether defined algrebrai­ cally [Zilles, 1975, Goguen, Thatcher and Wagner, 1977] or model-theoretically [Nourani, 1980, Van Emden and Maibaum, 1980]. This allows the builder of the knowledge base to concentrate on defining concepts independently of how they might be im- Martha Palmer Computer and Information Science Department University of Pennsylvania plemented or executed, and thus allows the designer of the system to concentrate on issues of know­ ledge representation, rather that programming. ADTs have the advantage of providing a powerful tool for structuring the masses of knowledge required in modelling even the most trivial situa­ tion.

The rest of this paper demonstrates the usefulness of this approach. Examples are given using an extension of PROLOG [Warren, 1977] that supports ADTs. This extension is based on the languages HOPE [Burstall, MacQueen and Sannella, 1980] and OBJ [Goguen and Tardo, 1979] with most of the syntax taken from HOPE. A similar exten­ sion was proposed by Van Emden and Maibaum (1980).

II SEMANTIC NETWORKS

We view semantic networks as a combination of logic and ADTs. This view differs slightly from a view held by many, notably Hayes (1977), which states that semantics networks are equivalent to a set of assertions in First-Order Logic and that the only value they have is as syntactic sugar for those assertions. In this view, the network in Figure 2-la would be equivalent to the assertions in Figure 2-lb and the network in Figure 2-lc would be equivalent to the assertions in Figure 2ld.

Although this view sheds important light on the status of semantic networks as a formalism, it ignores their value as an important structuring technique. That is, one can also view Semantic Networks as both a structure and a set of rules for interpreting that structure independent of the specific nodes or arcs an instance of a network contains.

In our view, a Semantic Network can most clearly be represented as an ADT. The ADT defines the structure of the network and defines operations which interpret that structure.* To understand how one might go about defining a Sematic Network using ADTs, consider the following:

1. data semantic net(alpha,beta) mkksn (set n;de(alpha)#set arc(alpha,beta))
2. data node (alpha) == mknode (alpha)
3. data arc (alpha,beta) == mkarc (node(alpha)#node(alpha)#beta)

A Semantic Network is defined in (1) as consisting of a set of nodes (defined in (2)) of some type alpha and a set of arcs (defined in (3)) of type alpha and beta (which are the type of the node and of the label respectively). Alpha and~ are variables ranging over types. Data definitions such as (1) are used to introduce a new data type along with the constructors which create elements of that type. mksn ("make semantic network") is a function** which takes-s;ts-of nodes-and sets of arcs between these nodes and constructs a semantic network from them. A definition of a parameterized type, such as (1), is not really a type, but a type constructor . It constructs different sorts of semantic nets, depending on the type (or types) supplied as a parameter. For example, if we define mary, sam, ~. john and lisa as persons:

1. data person == mary ++ sam ++ judy ++ john ++ lisa

and mother and father as relations between members of a family:

(S)data family_relationships ·· mother ++ father

we can then define a family network as in:

• (6)data family net mkfn(semantic net(person, family_r;lationships))

which defines a type of semantic network whose nodes are of the type person (where judy, sam etc. are constants of that type) and whose arcs are labelled by family relationships (where mother and father are constants of that type).

Now, since we defined a semantic net as really a constructor of semantic nets, we can use it to define a simple form of partitioned network [Hendrix, 1979). To do this, we simply view a partitioned semantic net as a network whose nodes

*Given this view, one could, in turn, argue that an ADT is also just syntactic sugar for a set of as­ sertions, but this becomes like arguing that one should not program in a high level language. Since it is equivalent to a Turing machine. **Our extended PROLOG provides a functional inter­ face.

are themselves networks. For example, if we

define:

1. data neighbor_relation ·· neighbor and then
2. data neighbor net ·· mksn(semantic-net(family net, neighbor=relation))-

We have a network whose arcs are labelled by the neighbor relation, and whose nodes are networks of families. This could be used to answer a query like "Who is the youngest person in John's neigh boring family."

To actually complete the definition we would have to define operations to interpret the network. These, of course, are lengthy and will not be given here.

In the definition given above, we have tried to be consistent with the way semantic networks are traditionally defined. A slightly different formulation would be to distinguish different sorts of arcs, not by their labels, but by their type. To do this, we need to introduce a corre­ spondence between notions used to describe ADTs and notions used to describe semantic networks. Corresponding to concept is, of course ~. to subconcept subtype, and to inheritance the notion of coercion: a function that takes an object of one type and returns an object of another type. Using these notions, father arc and mother arc can be defined as subtypes of arc as follows: -

1. data arc ·· mkarc(father arc) ++ mkarc(mother=arc)

assuming mother arc and father arc were previously

defined.

Using this formulation, any operation on arcs will apply to both father arcs and mother arcs, by having the system automatically coerce an object of type mother or father arc to type arc.

We can also get rid of arcs altogether by treating them as operations whose source type is the type of the node at the arc's tail, and whose target type is the type of the node at the arc's head (we would also have to include some environ­ ment). Thus, instead of incorporating knowledge about mother and father through the arcs and the rules which interpret them, we incorporate it through the semantics of the corresponding opera­ tion. For example, we could define general opera­ tions corresponding to mother and father as:

father: person, environment ~ person mother: person, environment ~ person

along with a set of clauses which define how, given a person, his/her mother or father could be

determined.

What we get by doing this is essentially a Frame-like representation. In the next section we will see how Frames can also be represented by

ADTs.

III~

In this section, we will show how ADTs can be used to implement Frames, by comparing a definition o f a date frame, written in KRL, a frame-based language, with a definition of a date ADT written i n our extended PROLOG.

First, consider the definition of date in KRL ( t aken from [Bobrow and Winograd, 1977]) [date month name (when filled reset-day) day (bounded integer 1-31) year integer (to fill assume 1975)

A date consists of three slots, month, ~. and year which are to be filled by a-;;;;, an integer be tween 1 and 31 and an integer respectively. Att ached t o the month and year slots are procedures which are to be automatically activated when their associated conditions are satisfied. These proce­ dures must contain a great deal of task specific i nformation such as the number of months in a year, days in a month etc. The procedure attached to the month slot will reset the ~ slot back to 1 whenever the month slot is filled, and the procedure attached to the year slot will return the integer 1975 whenever the slot is referenced

before it is filled. Now consider the definition of a date ADT. First, we need to define a year, a month-date and a day ADT. (10) data month name = 2 january ++ febuary ++ march ++ ;pril ++ may ++ june ++ july ++ august ++ september ++ october ++ november ++ december (11) data year mkyear(num) (12 ) data day =s mkday(num) ++ out-of-bounds The function mkday which takes a number and r eturns a day is a hidden function; it is not accessible to the user. Instead, the user inter­ faces to the type ~ thru a function ~ declared as: day:num -+ day and de fined by the following clauses: day(n) < day(n) < = day(n) < = mkday(n) if n =<31, n >= 1 out-of-bounds if n > 31 out-of-bounds if n > 1

which restrict the user to defining a day numbered be tween 1 and 31. More specifically, these clauses say that if the number passed to the function ~ is between 1 and 31 then a day corresponding to t hat number is returned (mkday(~)) otherwise~­ of-bounds is returned, which indicates the appro­ priate error.

Using these definitions, we can define date

as: (13) data date == mkdate(month_name#day#year) To cr eate a dat.e, the user uses a function date declared as :

date: month name -+ date to take a month name and return a date. The other functions-which update and access a date

are: get- month: date -+ month name put-month: month_name, date -+ date get-year: date -+ year put-year: year,date -+ date get-day: date -+ day put-day : day,date -+ date The semantics of date are given by the following rules or clauses:

(14) date(mn) <= mkdate(mn,mkday(l),mkyear(l975)) (15) get-day(mkdate(dm,dd,dy)) <= dd (16) put-day(d,mkdate(dm,dd,dy)) <= mkdate(dm,d,dy) (17) get-month(mkdate(dm,dd,dy)) <= dm (18) put-month(mn,mkdate(dm,dd,dy)) <= mkdate(mn,mkday(l),dy) (19) get-year(mkdate(dm,dd,dy)) <= dy (20) put-year(y,mkdate(dm,dd,dy)) <= mkdate(dm,dd,y)

Rule 14 creates a new date, rules 15, 17 and 19 select from a date the day, month name and year respectively, and rules 16, 18 ;nd 20 update the day, month name and year respectively and re­ turn a new dat; with those parts updated.

The work done by the attached procedures in the KRL definition is done by rules 14 and 18. Rule 14 will cause the year 1975 to be returned if the date is not updated before it is referenced . For example, get-year(mkdate (july))) will return 1975 but get-year(put-year(mkyear(l977), mkdate (july))) will return 1977. Rules 14 and 18 will reset the day when the month_name is filled. An advantage of the ADT definition is that we can represent knowledge about defaults, such as that the default year is 1975, and knowledge about what is implied by an action, such as that the day is to be reset to 1 when the month directly with the clauses without having to resort to an additional mechanism, as is the case in KRL.

In this section we have shown how Frames can be represented by ADTs. This should not be seen as detracting from the importance of Frames or KRL, since their importance is not as a system, but as a theory of knowledge representation which empha­ sizes ideas like prototypes and multiple des:rip­ tions.

In the next section we will consider th~ need for a methodology for building up a knowledge base, and whether one developed for knowledge representation can be used for ADTs and vice versa.

IV METHODOLOGY

Regardless of the formalism used, a knowledge representation system must embody a methodology for adding to its knowledge base. If not, the system will eventually be overcome with the complexity of the knowledge needed to model the situation at hand. One system whose main contri­ bution is such a methodology, which it calls an epistemology because of the broader context it is working in, is KLONE.

The KLONE methodology is based on concepts and their interrelationships. Concepts consist of roles (parts of the concept) and structural descrip­ tions (relationships between the parts). The essence of the KLONE methodology is the ability to build up knowledge by generalization and speciali­ zation. For example, once we have defined course with roles instructor and students, we can spe­ cialize it to the subtype service course which results in specializing, in turn, ~t and teacher fillers of those roles. One could, of course, go in the other direction, and first define service course and then course. Differentia­ tion is another type of special~n. First we define instructor and then differentiate it into two subroles: lab instructor and lecturer.

In this section we will attempt to separate out the KLONE methodology from its implementation by showing how we can apply the methodology to the design of ADTs. In some ways, we can view KLONE as a user's interface to the design of ADTs where KLONE is the source language and ADTs are the target language of some translator.

The interrelationships we are concerned with here are

1. Subordination between concepts such that one concept is a subconcept (or super­ concept) of another.
2. Individuation of a concept by another. For example, the concept Babe Ruth is an individual concept from the set repre­ sented by the generic concept baseball star.
3. Restriction on the type of object that can fill a role of another.
4. Differentiation of a role into subroles.
5. Satisfaction, or the relation between a role of a generic concept and one of its individual concepts such that the filling of one is the same as filling of the other. For example, a toll may require 50 cents, but this requirement may be satisfied, instead, by 3 quarts of chop suey.

The arcs have the following interpretation -­ arcs of the form A superc ~ indicate that B is superconcept of A, arcs of the form A ind ~ indicate that A is an individual concept of generic B, arcs of the for A V/R B indicate that the filler of role A must be oftype-B, arcs of the form A satisfies B indicate that role A satisfies role B, arcs of the form A diff B indicate that A is a subrole of B, and, flnally,-arcs of the form A role ~ indicate that B is a role of A.

Consider the KLONE description in Figure 4-1

Now let's define some of the ADTs that cor­ respond to the above KLONE description. Starting with ~. we see that it has roles instructor and students, and that instructor is differentiated into roles lab instructor and lecturer. Now to define a corresponding ADT for ~. we need to know how to construct it. That is, what parts come together to form a course. These parts are, of course, the different roles. Therefore, one way to define the ADT course is as:

data course ·· mkcourse(teacher#teacher# list student)

where one teacher is the lab instructor and the other is the lecturer. Roles also indicate that we need corresponding operations which access and update them.

The differentiation links indicate that we need operations which allow you to select out only those teachers which are lecturers and those which are lab instructors. One way to differentiate between these objects is to type them (or in this case subtype them). We can define instructor as:

1. data instructor ·· mkinst(lab instructor) ++ mkinst(lecturer)
2. data lab_instructor ·· mklab(teacher)
3. data lecturer .. mklec(teacher)

which says that instructors are either lab in­ structors or lecturers.

The above definition may appear odd, since the fact that instructors consist of teachers is specified twice, once in the definition of lab instructors and once in the definition of lecturer, rather than specifying it only once in the defini­ tion of instructor and letting "inheritance" pass it down. The problem is that the data definition not only specifies knowledge at the conceptual level, but, at the implementation level, specifies how to construct it. For which, like any function in any programming language, we need to know what its parameters are and their order. This informa­ tion, although necessary at some level, is proba­ bly not necessary at the level in which the user interacts with the system; this gives another reason for needing some interface, whether or not it is KLONE. Now we can change the definition of course appropriately.

*Note that this network would only let a sin2le graduate student be a teaching assistant. Although clearly contrived, this allowed us to include a satifaction link without over complicating the net­ work.

(24)data course ==

mkcourse(instructor#instructor#list student)

The KLONE description above actually implies a di fferent definition, because courses (in our very limited description) consist only of service courses. Therefore, the ADT should be defined as:

• (25)data course ·z mkcourse(service course)
• (26)data service course ~= mkcourse(te~ching_assistant# teaching_assistant#list freshman)

Of course, the operations on course can still be applied to service course, because the system will automatically coerce a service course into a course. For example, assume we have an operation to select out the lecturer from a course, declared

as:

get_lecturer: course ~ instructor

When it is applied to an object of type service ~ it will return an instructor who is a lecturer who is, in turn, a teaching assistant.

Nothing has to be added to handle restriction links if the value of the restricted role is just a subtype of the value of the unrestricted role. If not, all that has to be done is for additional clauses to be added to the definition of the operations corresponding to the role. A similar situation occurs for satisfaction links.

The additional clauses to implement a satis­ faction link define a mapping between objects of one role and objects of another. Given operations that select the id from a teacher and the student id from a graduate student, declared as:

get-id: teacher get-student-id: ~ employee# graduate student ~ social_s;curity#

We can then add the following clause to define the mapping frqm the role student id to id:

ge t-id(grad) <= ss#toempU(get-student-id(grad))

whe re grad is a graduate student which is coerced t o t eacher before being applied to get-id and s s#toemp# is a function which changes social security numbers to employee numbers.

ADTs also come with their own methodology for building up knowledge which allows existing types to be combined and enriched to produce new types ([Goguen, Thatcher and Wagner, 1977, and Nourani, 1980]). Although this methodology is not as specific and directed as the KLONE methodology, it is important, because it guarantees that the new types are well-defined if the old ones were.

We have tried to show that the methodology provided by KLONE can be accommodated by using ADTs and therefore one can view KLONE simply as an interface to such an ADT system. This has the advantage that we can decouple the concerns of the methodology from its implementation.

V SUMMARY AND CONCLUSIONS

In this paper we have tried to demonstrate the usefulness of developing a system for know­ ledge representation that is based on a foundation of ADTs and logic. This foundation is strong enough to allow other systems supporting various formalisms for knowledge representation to be built upon it.

The advantages of this approach are many, including: easing the problem of implementing a system by providing a base, allowing several formalisms to be supported by one system, and, finally, providing a common language with which to compare representations in the different formal­ isms.

To demonstrate the usefulness of our appro­ ach, we have shown that two competing formalisms (Frames and Semantic Networks) can be supported by a system such as we propose, and that our founda­ tion is consistent with a methodology for adding to a knowledge base which is already in use.

Several objects and situations have been modelled in a system designed along the proposed lines of this paper and run in our extended PROLOG. These include, a blocks world, a company world, and the largest one; an ATN and a lexicon for that ATN (following [Woods, 1979]).

ACKNOWLEDGEMENTS

We are indebted to Joe Goguen for sharing his insights into the nature of Abstract Data Types. We would also like to thank Rod Burstall and Farshid Nourani for discussions about issues related to this paper, Gabrial Barta, Eugene Freuder and Chris Mellish for comments on the structure of this paper, and Barbara Layne for preparation of this paper.