Descriptions as Constraints in Object-Oriented Representation

1. INTRODUCTION

A form in LISP or a term in PROLOG can be viewed as a description, i.e. an expre~ sion which refers to an entity in a domain of discourse. Forms and terms are both de ­ finite descriptions . They are subject to two restrictions

• (i) The uniqueness condition : A desc~ tion may only denote a unique referent , i t cannot be ambiguous . For example , (Father John) is allowed because John can only have one father , but (Brother John) is not allowed because John may have more than one brother and it is therefore not clear which one is intended.
• (ii) The computability condition: when the referent of a description is needed during interpretation, it should be com­ putable. For example , the expression (Father John) must be computable when it is needed otherwise an error condition occurs .

Variables can also be viewed as descrip­ tions. Typically, the uniqueness and com­ putability conditions hold for then too a variable may have only one value (within a given environment of course) and the value should be retrievable when needed, otherwise an error condition (unbound variable) results.

Descriptions that may have more than one possible referent or whose referent is not computable at the time it is needed are called indefinite . We want to develop a system where definite as well as indefi ­ nite descriptions can be used.

For example, (Greaterthan 10), which de ­ notes an unknown number greater than 10, or (Divisor 12), which denotes a divisor

Luc STEELS Artificial Intelligence Laboratory Vrije Universiteit Brussel Pleinlaan 2 - 1050 Brussel (BELGIUM)

of 12, i.e. 1 ,2,3,4,6 or 12, are indefinite descriptions which would be allowed in the system . Note that the conjuction of (Grea­ terthan 10) and (Divisor 12) uniquely re­ fers to 12. In other words, the conjunction of indefinite descriptions may be definite .

A definite description provides a deter­ ministic method to compute the referent when needed . An indefinite description ex ­ presses a constraint on its referent. Com­ putation ~ith indefinite descriptions con­ sists of operations over constraints . For example , (Greaterthan 10) expresses the constraint that the referent has to satis­ fy the predicate (lambda (X)(> 10 X)) . (Divisor 12) introduces the constraint that the referent has to be a member of (1,2,3, 4,6,12). The predicate can be applied to filter members out of this set, so that th;; conjunction of the two descriptions yields 12 .

In recent years there have been some proposals that are relevant to this reseanh Concepts like lazy evaluation (Henderson and Morris , 1976), or futures (Hewitt ,1 977) make it possible to delay evaluation until needed or until sufficient information is available .

The concept of a logical variable as used in PROLOG (Kowalski , 1977) can be vie­ wed as a way to relax the computability condition, because a logical variable can be used even though its referent is not known or only partially known . Note however that a logical variable can be bound to only one object ~t the time, which would make it necessary to backtrack 5 times be ­ fore 12 yields a successful match in the previous example (but see Kornfeld, 1983).

Because the evaluatjon process needed to deal with indefinite descriptions re­ sembles techniques used to implement con­ st~aint propagation, there are some inte ­ resting relations to constraint languages as well (cf. Borning (1980) , Steele and Sussman (1980)

There are four motivations for studying indefinite descriptions . First they can be incorporated in ordinary programming lan­ guages, particularly in object - oriented languages in which definite descript i ons already play an important role . Second theyiects are T(top), NIL, and~ (bottom). can be incorporated in knowledge represen-~he domain ofT is the universe of discour­ tation languages, particularly in the re- ;e . The domain of NIL is the empty set . cent generation of description languages ~he domain of ~ is overdefined. When at a (see e . g . Winograd (1982), Attardi and :ertain point a subexpression refers to the Simi ( 1982)) . >verdefined object, then the whole expres- Third, because indefinite descriptions ;ion refers to the overdefined object . feature prominently in natural language, the relation between formal languages and natural languages promises to become more transparent. Finally, indefinite descrip­ tions can be used as a component of query languages for databases. It would make it possible that a user supplies constraints in the form of indefinite descriptions to refer to an object in the databas~. 3. DESCRIPTIONS BASED ON CONCEPTS

the description system is imposs~ble: In- ·ents 1 ,2 , 3 , 4 , 6 and 12. Divisor is a constead we only introduce some baslc l1nguistic constructs and mention some properties of the evaluation mechanism.

1 . DOMAIN VS . REFERENT

The first key idea is that we make a distinction between the domain of a des- :used with the propositional connectives cription and its referent. The referent is the element denoted by the description . :alculus. sen . For the description 'uneven' the domain is the set of uneven numbers and the referent is an element out of this Lntersection of the domains of d1 and d2 . set - although it is unknown which one. The domain of 'the brother of John' is equal to all brothers of John. The refe- i2. The referent of (dEither d1 d2) is an rent is one element out of this set.

The second type of descriptions is of ;he form <concept> or (<concept> <arg 1 > ... :arg >) for n > 1. A concept may either be L fuRction, in which case a unique referent :an be computed given referents as argu­ lents. For example, (+5 10) is a descrip­ ;ion with referent 15. But a concept need 1ot be a function. For example, (Divisor In this short paper a full treatment of 2) is a description with possible refe­ :ept but not a function .

4. DESCRIPTIVE CONNECTIVES

The descriptive connectives dAnd, dOr, LNot dEither and dAndnot are used to comJine,descriptions . Th~y should not be con1 sed to combine statements in predicate

The domain is the set of possible elements The descriptive connectives reflect setout of which the referent has to be cho- ;heoretic relations between the domains of ;he component descriptions . The referent Jf (dAnd d1 d2) is an element out of the rhe referent of(dOr d1 d2) is an element JUt of the union of the domains of d1 and ~lement of the domain of d1 or of the doThe distinction between domain and re- nain of d2 but not of both . The referent breviation of (dAndnot T d), i . e. dNot

ferent allows the construction of a clear of (dAndnot d1 d2) is an element out of set-theoretic semantics for a description the set-theoretic difference between the language . By making it possible ~o g~ve domains of d1 and d2 . (dNOT d) is an abpartial descriptions of the domaln, lt raises the expressive Power of the langu~indicates a set-theoretic difference with Also the explicit representation of con~ the domain of the all-description . Thus straints on the domain makes the deductlon (dNot female) 1 s equivalent to (dAndnot more powerful. Often ~e ~now a lot a?out T female). the domain of a des:r1pt1on but not 1ts It is easy to prove that T and NIL act refe~ent. By operatln~ at the level of as the identity and zero-element for these doma~ns, w~ c~n ~ometl~es reduce.the . connectives . Analogues exists also for the doma1n unt1l 1t lS a slngleton, l . e. untllother propositional laws such as De there is a unique referent ~eft . These Morgan , s. ' · points will be illustrated 1n the rest of the paper. First we introduce description

types .

2 . NAMES AND SPECIAL OBJECTS

The simplest form of a description is a name which uniquely indentifies an element in the domain of discourse. A name is an atom or a datastructure containing only names as elements. Sequences and sets are considered to be primitive datastructures . For example, J OHN , [ JOHN MARY JAMES ] and (JOHN MARY J AMES) are examples of names.

There are three special objects in the system . The undefined object or all - object, the null-thing or empty object , and the overdefined object. The names of these ob-

5. DESCRIPTIONS OF THE DOMAIN

There are a variety of things that couH bemow about the domain of a description. We want to have constructs that are able to express th i s partial information. Here are some examples

ENUMERATION OF THE POSSIBLE MEMBERS . An expression of the form (Element-of X . .. X expresses the constraint that the 1 n . X X referent has to be e1ther 1 ... or . For example, an alternative descr i pt~on for (Brother John) could be (Element-of George James).

PARTIAL ENUMERATION . A description of the form (INCLUD~ S X) expresses that the referent comes out of a domain that has X as a member . For example, if it is known that George is one of the brothers of John then (Includes George) is an alternative descript ion for (Brot her John) .

CARDINALITY OF DOMAIN . The description (Number -of X) with X an integer, indica­ tes that the cardinality of the domain is equal to X. For example , if it is known that John has two brothers, then (Br other John) can be descr ibe d as (Number - of 2) .

The deduction rules fo r the descriptive connect ives include rules for dealing with such domain descriptions . For exampl~ the referent of ( dAnd (Brother John) ( Frieni Frank)) , where (Brother John) is (Element­ of George James) and (Friend Frank) is (Element-of George Mary), is equal to George because George is the only element in the intersection of the domains of two descri ptions.

6 . VARIABLES

Variables are descriptions which start out as indefinite members of the universe and gradually assume their domain as con ­ straints accumulate . Variables are prece - ded by the symbo l and are lexically sco - ped within the expression in which they occur , although they may occur anywhere in the descript i on . For exampl e, in (dAnd Y 5) , or i ts e quivalent (dAnd 5 : Y), the referent of : Y wil l be equal to 5 . Varia ­ bles in the description system thus behave like logical variables .

1 . CONVERSE DESCRIPTIONS

If (Father George) i s a description for John , then (with Father John) is an alter ­ nat ive descri~tion for George . A descrip ­ tion of the form (with .~concept > <descrip­ t i on> is called a converse description, be­ cause it denotes the converse of a concept.

8 . EVALUATION

The goal of eval uation is to find the name o f the r eferent of a description , i . e . a value . When a description is def in ite , its referent can be computed and evaluation proceeds as ordinary appli cative evaluation When the description is i ndefinite , the result from evaluation is a collection of constraints on the referent, called a con­ straint cluster .

These constraints take the form of a predicate that the referent has to satisfy , gene rat o r s which coul d s tart e nume rati on of the domain if needed, and constraint s on the doma in such as a list of its members a list of the elements not in the domain, a partial list o f t he members, the cardi ­ nality of the doma in, etc .

The evaluator will attempt to proceed with the computation eve n though partial result s are constraint clusters . Deduction rules for the descr i pt i ve connectives operate over constraint clusters.

For example , if the constraint cluste rs of two descriptions contains predicates , then the constraint-cluster of the conjunc ­ tion of the two descriptions vill contain the AND-conjunct i on of the two predicates. Thus (dAND (Greaterthan 10) (Lessthan 5)) results in ((Predicate (lambda (x)(and (>X 10)(< X 5))))) .

Th~ evaluation process will also aLLerupL to apply functions to constraint clusters . For example , when an explicit domain is known, computations can be performed by mapping the function . For example , ( + (ele ­ ment - of 1 2)(element - of 3 4)) is equa l to (element -of 4 56) .

Note however that it is possible to spe ­ cify descriptions whose referent will not be computable because it would require the introduction of much more knowledge . For example, the description (dAnd Even Prime) has only one r eferent , namely 2 , but this cannot be determined from knowing predica­ tes o r generators on the component descr i p­ tions themselves .

9. CONCLUSION

We argued fo r the introduction of inde ­ finite descriptions , sketched some lingu i s­ tic constructs and briefly indicated a possible evaluation .