D-SCRlPT: A Computational Theory of Descriptions

1. Introduction

1.1 Ways of Representing Knowledge

Methods advocated for repres entin~ knowledg e in artifici a l intelli gence prog r ams have included lol'; i c al statements 0 1cCarthy, Sandewall), semantic net\~or k s (Quillian, Schank), and procedures (Hewitt, Sussman and ~kDermott). All these approaches sh<1re one fundamental concept, the notion of pred ic a tion. That is, the basic data structure in each system is some representation of a predicate appl led to objects. In this respect, the various systems are more or less equivalent. But this basic idea must be extended to handle problems of qu antification and knowledge about know led~ e. llere the systems do diffe r. l~e wi 11 ar gue, though, that these differences result from the descri ptive apparatus used in the particular systems being compared, rather than from an inherent a dvantage of, say, procedures ove r declaratives or vice versa.

Advocates of PLANNER (e. g . Winograd , p , 215) have argued that the predicate calculus cannot represent .b.ID:£ a piece of knowledl'!;e should be used . But this is true only of the first-or der pred i cate calculus. In a hir.her­ order or non-ordered declarative language, statements coul d be made which woul d tell a t heorem prover how other statements are to be used . PLANN ER, on the other hand, has no way of directly stating an existenti a l quantification, but this doe s not mean that procedural langua ges are necessarily incapable of hand ling that prob lem.

Our belief, then, is that the type of system used to repres e nt knowledge is uni mportant, so long as it has sufficient expres s ive power. This paper pre sents an attempt at such a system, the language 0SC RIPT . . As the name implies, the most inter esting feature of 0-SCRIPT is its powerful formal ism for descriptions, which enables it to represent statements that are problematical in other systems. No position will be ta ken as to what k ind of language 0SCRIPT is. Since it is intended to answer questions by ma k ing deductions from a data base , it can be t hought of as a theo rem prover. Since it oper a tes by comparing expressions li ke the data-base languages of PLANNER and CONNIVER, it can be thought of as a pattern-matching langua ge. And since It Is Turing univers a l and, In fact, includes the 1 ambda calculus, it can be thought of as a prog r amming language .

Robert c. ~l oor e llassachusetts Institute of Technolo ~ y Cambridge, Massachusetts

1.2 Problems in Representing Knowledge

Before presenting the details of 0SCRIPT, we will tr y to give some idea of the type of problem it is designed to solve . A classic problem Is that of representing opaque contexts. An opaque context is one which does not allow substitution of referentially equivalent expressions or does not allow existential quantification. For example the ver b "want" creates an opaque context:

(1.1) John wants to marry the prettiest girl.

This s entence is ambi guous. either: It can mean

(1. 2) John wants to ma rry a specific g irl who also happens to be the prettiest.

or:

(1 . 3) John wants to marry whoever is the prettiest g irl, although he may not know who that is.

Unde r the first interpretation we can substitute any phrase which refers to the same person for "the prettiest girl". That is, if the pretti est g irl is named "Sally Sunshine", from (1.2) we can infer:

(1.4) John wants to marry a specific girl who also happens to be named Sally Sunshine.

We cannot make the corresponding inference from (1.3). It will not be true that:

(1.5) John wants to marry whoever is named ' Sall y Sunshine, although he may not know who that is.

Because of this property, (1.2) is called the transparent reading of (1.1) and (1.3) Is called the opaque reading . It is almost always the case that sentences having an opaque read ing are ambir,uous with the other reading being transpar ent.

To illustra te blocking of existential quantification, consider:

(1.6) John wants to marry a blonde.

Again the sentence is ambiguous, meaning either:

(1.7) John wants to marry a specific girl, who also happens to be a blonde.

or:

(1.8) John has no particular g irl in mind, but he wants whoever he does marry to be a blonde.

We can existentially quantify over the first read ing but not the second. We can Infer:

(1.9) Ther e exists someone whom John wants to marry.

from (1.7), but not from (1.8).

Another problem is the occurrP.nce of descrirtive phrases in sentences involving time reference. In the sentence:

(1.10) The President has been married since 194 5.

the phrase "the President" refers to an individual. In the sentence:

(1.11) The President has lived in the ~lhite I louse s i nee 1800.

"the President" refers to each Presi dent in turn.

Another type of sentence where the reference of a phrase depends on time is i 11 us trated by:

(1.12) John met the President in 1960.

This sentence is ambiguous, but unlike (1.11), each interpretation refers to only one person. The ambiguity is v1hether "the Pres I dent" refers to the President at the time (1.12) is asserted, or the President in 19GO.

Representing knowledge about knowledge raises some interesting issues. For instance, in:

(1.13) John knows Bill's phone number.

how is John's knowledge to be represented? In John's mind it might be something 1 ike:

(1.14) (PH O~I F:-NUM BILL 987-6543)

So, (1.13) might be:

(1.15) (KNO\·/S JOHN (PHONE-NU~1 BILL 987-6543))

The trouble with (1.15) is that it includes too much information. Not only does it say what (1.13) says, it also says what the number .u_. The difficulty is to refer to a piece of information without stating it.

For all these types of sentences, D­ SCRIPT provides representations which allow the correct deductions to be made. Further, it provides separate representations for each meaning of the ambiguous sentences, and these representations are related in a way that explains the ambiguity.

2. The D-SCRIPT Language

2.1 D-SCRIPT Expressions

D-SCRIPT contains the following types of expressions:

1. constants

2. variables

3. forms

4. 1 is ts

A constant is any alpha-numeric (i.e.~ letters or numbers) character string (e.g. "FOO", "BLOCK5"). A variable is any alpha­ numeric character string prefixed by "?" (e.g. "?X"). A form is any sequence of expressions enclosed in angle-brackets (e.g. "<X Y ?Z>"). A 1 ist is any sequence of expressions enclosed in parentheses (e.g. "(FOO A <BARB C>l").

D-SCRIPT observes the convention that all functions, predicates, and operators evaluate their arguments. The rules for evaluating expressions are largely adapted from LISP. In fact, D-SCRIPT variables and forms are treated just like LISP atoms and lists, respectively. Rather than introducing "QUOTE", however, we use constants and lists to represent pre­ defined items. To state our rules formally:

1. A constant evaluates to itself.
2. A variable evaluates to the expression which it has been assigned.
3. The value of a form is the result of applying Its first element to the values of its remaining elements. This will not be defined in general, but only for those expressions which represent meaningful operations in D-SCRIPT. One such case is that of lambda-expressions. A lambda­ expression is represented in D-SCRIPT by a form containing the constant "LA~1 BDA", followed by a list of variables, followed by an expression (e.g. "<LM1BDA (?X ?Y) <TIMES ?X ?Y»"l. A form whose first element is a lambda-expression is evaluated in the same way as a corresponding LISP expression. The result is the value of the body of ~e lambda-expression, with the values of the arguments assigned to the corresponding variables. For Instance, assuming 11 + 11 has the usual meaning, "«LAMBDA (?X) <+ 2 ?X» 3>" has the same value as"<+ 2 3>", which is "5". ~Je will introduce other types of forms whose value is defined when we explain the representation of statements.
4. A 1 i st evaluates to a form with identical structure, except that free variables are replaced by their values. If "?X" has previously been assigned the value "A", then "(LAMBDA (?Y) (FOO ?X ?Y)) will evaluate to "<LAMBDA (?Y) (FOO A ?Yl>".

It is worth noting that the way lambda­ expressions and 1 ists are defined makes it very easy to write functions which construct complex forms. For example, consider "<LAMBDA (?X) (FOO (BAR (GRITCH ?X)))>". The result of applying this to "Z" is "<FOO (BAR (GRITCil Zll>". A comparable LISP function would have to be built up with "CONS"'s to achieve this result.

2.2 Representing Knowledge in D-SCRIPT

The most basic statements are those which express simple predication. A statement of this kind is represented in D-SCRIPT by a form whose first element is a constant representing the predicate and whose other elements are constants representing the objects of the predicate. For example:

(2.1) The sun is a star.

(2.2) BlockA Is on BlockB.

coul d be represented as:

(2.3) <STAR SUN> (2.4) <ON BLOCKA BLOCKB>

A simple statement about a statement, such as:

(2.5) John believes the sun is a star.

would be:

(2.6) <BELIEVE JOHN (STAR SUN)>

The important thing to notice about (2.6) is that the embedded statement is represented by a list. This is because we need an expression whose ~ is ( 2. 3) to be consistent I'll th the convention that predicates (in this case, "believe") evaluate their ar guments.

To represent more complex statements, two types of extensions are needed. The sim~ler of these is the addition of logical connectives. D-SCRIPT uses "OR", "AND", " ~!OT", and "I MPL IES" to stand for the obvious lop;ical operations. As in (2 .6 ) the embedded statements are expressed as 1 ists. So:

(2.7) If the sun is a star, then BlockA is on BlockB.

would be represented by:

(2.8) < 1 ~ 1 PLIES (STAR SUN) (ON BLOCKA BLOCKB) >

This notation reflects the f act that in D­ SCRIPT, lop;ical connectives operate on the statements themselves rather than on their truth-values. "1~1PLIES", then, is not computed as a Boolean function, but rather is computed by asserting that its first argument is true, and attempting to prove its second argument.

The other extension required for complex statements, and the one that is most important to our theory, is the use of descriptions. There are three types of descriptions in D­ SCRIPT; existential descriptions, universal descriptions and definite descriptions. A description is a form whose first element is "SOME" (existential), "FVERY" (universal), or "TilE" (def inite); whose second element is a list containing a variable; and whose third element is an expression whose value is a statemen t. Descriptions represent the corresponding types of natural langua p; e descriptive phrases:

( 2. 9) a b 1 oc k every number the Table

<SOME (?X) (BLOCK ?X)> <EVERY (?Y) (NUM ?Y)> <TilE (?X) (TABLE ?X)>

Some examples of sentences containinr. descriptive phrases and their representations are:

(2.10) The king is fat. <FAT <THE (?X) (KING ?X) »

(2.11) John owns a dog. <OWN JOHN <SOME (?X) (DOG ?Xl>>

(2.12) Every boy likes Santa Claus. <LIKE <EVERY (?X) (BOY ?X) > SANTA>

Notice that when descriptions appear in statements, they are 1 eft as forms. This is because, unlike embedded statements, we are talking about the objects to which the descriptions refer (i.e. their values) rather than the descriptions themselves.

The notation we have used so far is not sufficient to express statements containing mo re than one occurrence of the same description. In the sentence:

(2.13) Every boy either loves Santa Claus or hates hi m.

the phrase "every boy" is the subject of both "loves" and "hates". vie cannot use the following representation though:

(2.14) <OR (LOVE <EVERY (?X) (BOY ?X)> SANTA) (HATE <EVERY (?X) (BOY ?X)> SANTA)>

because this means:

(2.15) Either every boy loves Santa Claus or every boy hates Santa Claus.

which, of course, is quite different. We can overcome this difficulty by using lambda­ expressions. We will represent (2.13) by:

(2.16) << LAMBDA (?X) (OR (LOVE ?X SANTA) (HATE ?X SANTA)) ) <EVERY (?Y) (BOY ?Y)> >

This can be read as something 1 ike "the predicate X is true of every boy," where the pred icate X is "loves Santa Claus or hates hi m."

We have a similar situation with respect to the scope of quantifiers. It is not clear whether:

(2.17) <GREATER <SOME (?X) (NUM ?X) > <EVERY (?Y) (NUM ?Y)>>

represents:

(2.18) For every number there is some larger number.

or:

(2.18) Ther e is some number which is large r than every number.

We will have to arbitrarily choose a rule to d isambiguate (2.17), but by usin~ lambda­ expressions we can avoid the difficulty. (2.18) can be represented by:

(2.20) <<LAMBDA (?X) (GREATER <SOME (?Y) (NUM ?Y)> ?X) > <FVERY (?Z) (NUM ?Z)> >

and (2.19) can be repre~ented by:

(2.21) <<LAMBDA (?X) (GREATER ?X <EVERY (?Y) ( NUM ?Y)>)>

<SOME (?Z) (NUM ?Z)>>

Analyzing these expressions in the same way as (2.16) will show that they have the correct meaning.

It should be apparent that existential and universal descriptions in D-SCRIPT serve exactly the same function as the quantifiers of the predicate calculus. In view of this, it may be asked why we have used a different notation. one reason is that our notation makes it possible to write expressions whose structure more closely resembles the sentences they r epresent. Hopefully this makes them more intelli g ible. The more important reason, though, is that having a single expression for a description makes it easier for an interpreter to manipulate it.

2.3 Formal Semantics of D-SCRIPT

The previous two sections outlined the syntax and informal semantics of D-SCRIPT. This section attempts to show how a program could be written that would interpret D-SCRIPT statements in accord with their intuitive meaning. The details of this will be somewhat sketchy. One reason for this Is that choosinp, proof strategies and using heuristic information are complicated problems that we cannot claim to have solved. Secondly, creating a theorem prover is not our main goal. What we are trying to do Is to show the sort of descriptive system necessary to represent the information contained In natural language statements. The purpose of this section Is to establish that our notation for that system Is "well-founded".

The program we have in mind would take a statement as its input and determine from its data base whether the statement is true. For statements which are simple predications, the program looks for another statement in the data base which matches the first statement. The statement whose truth is being determined will be ·called the "test statement"; the statement In the rlata base to which it is being compared 1-1111 be called the "tar p;e t statement". To prove a complex statement, the program would break It down into Its components and process them according to the semantics of the operators involved . Similarly, a complex target statement must be broken down to its components for processing, but the rules are different. So, in explaining the semantics of complex expressions, analyses will be given for their use both In test statements and In tar get statements.

Two basic statements match if their corresponding elements match. In general, expressions which are not statements match whenever their values are identical. A variable which has not been assigned a value matches any expression, and is assigned that expression's value. These rules apply to both test statements and target statements. As an example, suppose "S" has been assigned to "?X", "?Y" is unassigned, and "+"has its usual meaning. Then "<FOO 5 ?Y>" will match "<FOO ?X<+ 3 4»" and "7" will be assigned to "?Y".

We will not give a complete deductive procedure for lor. ical connectives. It is a well understood problem and is not of primary importance in the phenomena we wish to explain. But to suggest the kind of procedur e we have in mind, consider 11 1\ND" and "IMPLP'S". In handl lng these expressions the distinction between test statements and target statements comes through. To prove " <AND ..11. ~>" both ..11. and ~ must: be proved; but in miltch i ng something against "<M!D ..11. ~>", the match succeeds if either ..11. or~ matches. "<l t>lPLIES ..11. ~>" is true if In a hypothetical state where ..11. is asserted, ~can be proved. A test statement will match a target statement "< H1Pll ES ..11. ~> " if the test statement matches ~ and ..11. can be proved. "OR" and "NOT" are somewhat more complicated but can be handled in much the same way.

The really important part of our deductive procedure is the treatment of descriptions. Definite descriptions are the si mplest. "<THE (?X) ( . ·· ?X ·.. )>" evaluates to the constant which when assigned to "?X"

makes "< ··· ?X .·· >" true. If there is not such a constant or if there is more than one, the value of the description Is undefined. For exafllple, If "LESS" means "arithmetically less than", then "<FOO 3>" matche:;:

(2.22) <FOO <THE (?X) (AND (LESS ?X 4) (LESS 2 ?X)) »

This rule for evaluating definite descriptions applies to both test statements and target statements.

For existential and universal descriptions, there is again a difference between test statements and target statements. In a test statement, an existential · description matches anything that makes the body of the description true. That is, " <FOO <SOME (?X) (BAR ?Xl»" matches "<FOO A>" if "<BAR ?X>" is true when "?X" Is assigned "A". For the case of a target statement, the evaluation is more difficult. If we know that "Some bar is foo," we could simply give it a name and continue. But giving a name would imply that we know~ bar is foo, which is not true. Instead we can create a name and say that .it the new name were the name of the object that Is asserted to exist, then anything which we can prove about the new name is true of the object. We do this by creating a hypothetical state of the data base In which, If the new name is "G999", we assert "<BAR G999>". The target statement then becomes "<FOO G999>". Another way of putting this is that "<SOME (?X) (BAR ?X)>" evaluates to "G999", with the side effect of creating a hypothetical state of the data base in which " <BAR G999>" Is asserted. When the hypothesis is discharged, the new name becomes undefined, and we are not in danger of supposing that we know what the name of the object is.

The treatment of universal descriptions is the exact dual of that for existential descriptions. In a test statement, we know that whatever we can prove about an arbitrarily selected member of a class is true of every member of ~e class. So just as we did for existential target statements, we set up a hypothetjcal state, produce an arbitrary unique name; and assert that it is a member of the class. Analogously to what we said before, "<EVERY (?X) (FOO ?Xl>" evaluates to, say, "Glll" 1-lith the side effect of creating a hypothetical state In which "<FOO Glll>" is asserted. Also in duality with existential descriptions, In a target statement a universal description matches anything which makes its body true. For example, "<FOO A>" matches " <FOO <EVERY (?X) (BAR ?X)»" if "<BAR ?X>" is true when "?X" is assigned "A".

Now we can see why lambda-expressions are important for representing Information in D­ SCRIPT. Evaluating existential and universal descriptions sometimes has the side effect of changing the data b~se. later we will introduce other expressions which also do this. If we have other descriptions In the statement, we need to be able to control whether they are evaluated In the old data base or the new. By "lambda-fying" a statement we can bring one or another description to the outside and force it to be evaluated first. In this way we can control the order In which expressions are evaluated. A detailed example of this will be given in section 3.3.

In this brief summary, we have given the barest outlines of a deductive procedure. We have not discussed any of the complex interactions among these logical operators. But hopefully we have laid a sufficient foundation to talk about the issues that are the real point of this paper.

3. Solution to Representation Problems Using D-SCRIPT

3.1 Descriptions in Opague Contex s

In general, descrirtive phrases in opaque contexts are subject to more than one interpretation. Furthermore, at least one of the interpretations seems not to behave according t o normal rules of log ical manipulation. Look ing more closely, opaque context s primarily occur in the complement constructions of verbs 1 ike "want", "believe", "knovl'', etc. These verbs all have the property of describing somebody 1 s model of the worl d. Wh~n we say:

(3.1) John wants to marry Sally.

what we mean is that in John's model of the wo r 1 d, the state :

<3.2) John is married to Sally.

Is considered desirable. The ambiguity of descriptive phrases arises from the question of whethe~ the descriptive phrase is to be evaluated in our model of the world or the model of the subject of the sentence. To illustrate this, recall the sentence:

(3.3) John wants to marry the prettiest g irl.

In D-SCRIPT, the opaque reading is represented by:

(3.4) <WANT JOHN (MARRY JOHN <THE (?X) (PR ~ TTI EST ?X) >)>

The reason that there are restrictions on substituting other expressions for " <HIE (?X) (PRETTIEST ?X) >" is that the statement which actually contains this description, i.e.:

(3.5) <!>lARRY JOHN <THE (?X) (PRETTIEST ?X)»

is part of John's world model. If in our program we represent John's world model by a separate data base, then the expressions which may be substituted are those which are equivalent in that data base, not in the main data base which represents our world model.

To represent the transparent read ing of (3.3), we must take the description outside the scope. of John's model. We can do this with a lambda-expression:

(3.6) « LMlBOA (?X) (\·/ANT JOl iN (MARRY JOHN ?X)) > <THE (?Y) ( PRFTTIFST ?Y)>>

This says that the statement we get by eyaluatjng the description in our model and substituting that value for "?X" in:

(3.7) <MARR~ JOHN ?X>

is marked as a desirable state in Joi1n 1 s world model.

The analysis Is analogous for existential descriptions. The two readings of:

(3.8) John wants to marry a blonde.

can be represented by:

(3.9) <WANT JOHN (MARRY JOHN <SOME (?X) (BLONDE ?X))))

for the opaque reading, and by:

(3.10) << LAMBDA ( ?X ) (WANT JOHN (MARRY JOHN ?X)) > <SOME (?Y) (BLONDE ?Y)))

for the transparent reading. (3.9) means:

(3.11) John wants there to be a blonde that he marries.

and (3.10) means:

(3.12) There is a blonde that John wants to marry.

So the reason we can't make a "there Is ... " paraphrase of (3.9) is that rather than being an existential statement, It Is an assertion ~an existential statement.

3.2 Descriptions in time contexts

In order to discuss the next set of examples, we need a way to represent time. The basic fact here is that any predicate can be made to vary with time. Even those that we choose to consider eternal can be alleged to depend on time, e.g.:

(3.13) Two used to be greater than three.

To account for this in first-order logic, we would have ro make time an expl lclt parameter of every predicate symbol. Instead, we will represent time by a context-structyred data base (McDermott). By this we mean that the data base will be broken down into a series of sub-data bases, or contexts, each of which represents the state of the world at some particular time. This can be efficiently implemented, as it is In CONNIVER (Sussman and McDermott) by specifying each context by recording the differences between It and Its predecessor. '

To use this kind of data base, we need a special predicate "T-A-T" which takes as Its parameters a statement and the name of a time context. " <T-A-T~ .t.>" means statement ~ Is True At Time .t.. The formal semantics of "T-A­ T" are that it attempts to deduce~ in the time context named by .t.. We also need to be able to generate references to time contexts. For instance, the phrase:

(3.14) when Washington was President

would be represented by the description:

(3.15) <THE (?I) (1-A-T (PRES WASHINGTON) ?I)>

Finally we need the one-place predicate "TIME" to make quantified statements about time. We would represent:

(3.16) Three is always greater than two.

(3.17) <T-A-T (GREATER 3 2) <FVF:RY (?T) (Tit.oF ?T)»

Given this notation for ti~e, we can solve the associated problems which we raised earlier. As in the case of opaque contexts, the solution depends on whether a description is evaluated in the context in which a statement is made or the context which the statement is about. Recalling the previous examples:

(3.18) The President has been married since 19115.

is represented by:

(3.19) <<LANBDA (?X) (T-A-T (MARRIED ?X) <EVERY (?T) (AFTER ?T 1945) >) > <THE (?Y) (PRES ?Y)»

In (3.19) the use of ~e lambda-expression puts the description "<THF (?Y) (PRFS ?Y)>" outside the time construction, so it is evaluated in the context in which the statement is made. On the other hand:

(3.20) The President has lived in the ~lhite House since 1800.

is represented by:

(3,21) <T-A-T (LIVE-It1 <THE (?X) (PRES ?X)> W- 11) <EVERY (?T) (AFTER ?T 1800) >>

llere the description is inside the time construction and is not evaluated until the time description has been instantiated. The analysis is the same for:

(3.22) John met the President in 19GO.

except that in this case the time reference is definite. One interpretation is g iven by:

(3.23) <T-A-T Ct1EET JOHtl <TilE (?X) (PRES ?X)> 1960>

and the other is ~iven by:

(3.24) <<LAMBDA (?X) (T-A-T (NEET JOHN ?X) 1960) > <THE (?Y) (PRFS ?Y) >

3.3 Knowledge about Knowledge

One of the questions we raised in the beginning 1-Jas how to represent:

0.25) John knov1s Bill's phone number.

If we knew the number we coul d represent 0.25) by:

(3,26) <KtlOI'I JOHN (PI!OtlE-NUfl BILL _AAK) )

where .AAK is the number. ~Je do know one description of the number, namely "Dill's phone number". If we substitute this into (3.2G), however, we get a trivial statement:

(3.27) <KtlO~·I JOHN (PJIONE-NU~l BILL <TilE (?X) (PHONE-NU1'1 BILL ?X) >) >

(3.28) John knows that Dill's phone numb e r is Bi11 1 s phone number.

What we neerl to do is to remove the occurrence of the description from John's w6rld model into our world model. Once again, we c an do this with a lambda -expression:

(3.29) << LAMBDA (?X) (V-NOVI JOliN (PI!ONE-NUt·1 BILL ?X)) > <TilE (?X) (PHONE-NUt.-1 BILL ?X)»

This says that if we were to evalua te the description "Gill's phone number" an.d stick the result in (3.26), we would correctly describe John's knowledge.

To see the difference between (3.27) and (3.29), suppose we know that Bill has a phone number, and we know that John knows that Bill has a phone number. These facts are represented by:

(3.30) <PHOtiE-t!Ut1 BILL <S0~1 E (?X) 0!Ut1 ?X)»

(3.31) <KN0\'1 JOHN (PIIONE-NU~1 BILL <SOt 'F: (?X) (NU f'-1 ?X) >) >

Siven this, we can prove (3.29) from itself. ~!otice that in D-SCRIPT this is non-trivi a l. Complex statements are never proved by simply looking to see if they are in the Ja ta base. Rather, they are broken down to their basic components and these components are processed accordin~ to the semantics of the operators comb in i nr. them. In the case of "K~!O~I " the semantics are to shift the proof to the data base of the person doing the knowing. So even to prove a statement from itself, the semantics really have to work.

In trying to prove (3.29) the lambda­ expression r71akes us first evaluate "<THE (?X) (PHOrJE-NUt·1 GILL ?X) >". \~e do this by trying to find a match for " < PIIONE-NU ~ I BILL ?X> ". If we don't know Gill's phone number we can't do this directly, (3.30), however, entitles us to create a hypothetical state in which some arbitrary constant, say "G777" is asserted to be Gill's number. So to prove (3.29), we

attempt to prove:

(3.32) <KN0\·1 JOliN (PIJONE- NUM BILL G777)>

with the hypothesis:

(3.33) <PHONE-NU~' BILL G777>

To prove (3.32) from (3.29) we process (3.29) much the same as before. This ti me , however, we already have (3.33) in the data base; so "<TIIF (?X) ( PIIOI!E-NU~1 GILL ?X) >" evaluates to "G777" directly, Our proof then reduc e s t o proving (3.32) from itself, which reduce s a P; a i n to p r o v i n g ( 3 · 3 3 ) f rom i t s e l f i n the data base which represents John's world model. (3.33) is a basic statement, so it can be inferred from itself immediately, and the

entire proof succeeds.

Now suppose instead that we were trying to prove (3.29) from (3.27). The proof would be the same down to the point where we generated the subgoal of proving (3.32). To prove this from (3.27), we have to prove

(3. 33) from:

in the context of John's world model. But this time we cannot use (3.33) when we evaluate the description, bec<JUSe (3.33) is asserted only in o4r world model, and the evaluation is ta~ing place in John's. What will happen is that 0.31l will be used to ~enerate another arbitrary constant (e.~. "G888 11 ) in John's v10rld model. ~/e vlill then try to prove (3.33) from:

(3.35) <PIIOtiE-NUr, BILL G883>

Since "S777" does not ma tch " G888", the proof f a i 1 s.

.. 4. Future ~iork

In this paper we have presented a formal lan~uage for the representation of knowledge. We have shown how information which is difficult to express in other formal isms can be expressed in our language. And we have suggest~d how a deductive progra~ could be designed to answer questions In our language. Cle a rly, the next step in this research is to buil d that deductive prog ram.

There are several reasons why this would be a worthwhile project. For one, A. I. deductive systems seem to fall into tvJO extreme categories. On the one hand, pred icate-calculus theorem provers restrict themselves to first order languages. Procedural systems such as PLANNER, on the ot her hand, use pattern matching schemes which are genera l enough to process higher order statements, but they are ~ ~eneral that they say nothing about the meaning of those stat ements. Implementing D-SCRIPT would create a system somewhere In between - one that would embody systematic know led~e about some types of higher order statements.

Beyond this, the particular types of knowledge we have discussed seem to be especially important for A.l. There is still much work to be done, but if we can pror;~am a deductive system to treat "T-A-T" and "K N 0 ~/ 11 in the way we have proposed, we will have ta ken a first step towa~d s creating programs ~1hich can think about thinking.