A CLASSIC to KIF Exercise
Richard Fikes <pwtc!fikes@labrea.stanford.edu>
Date: Fri, 19 Oct 90 17:44 PDT
From: Richard Fikes <pwtc!fikes@labrea.stanford.edu>
Subject: A CLASSIC to KIF Exercise
To: interlingua@venera.isi.edu
Cc: pwtc!Fikes@labrea.stanford.edu
Message-id: <19901020004413.9.FIKES@peso.tc.pw.com>
Folks,
In order to move our interlingua work forward and to make our net
interactions more productive, I would like for us to do some small scale
translation experiments and use them as a focus for our discussions. To
get the process going and to illustrate what I have in mind, I have
prepared the following report on an exercise I recently conducted
involving hand translating a small CLASSIC knowledge base into KIF. The
exercise is incomplete in that I have not discussed the more difficult
translation task, namely from KIF into CLASSIC. However, it is a start
and has already brought up several issues which I discuss in the report.
I encourage you to comment on this exercise and to try one yourself.
Richard
TRANSLATING CLASSIC IN KIF
The following is an exercise in using KIF 2.0. I have attempted to
translate into KIF the sample CLASSIC knowledge base given in the paper
"Living with CLASSIC: When and How to Use a KL-ONE-Like Language" by
Brachman, McGuinness, Patel-Schneider, and Resnick.
I have enclosed in ">>>>> <<<<<" comments that I thought are of
particular interest.
CLASSIC
The declarative portion of CLASSIC is quite compact (read elegant). The
significant parts of the grammar are as follows:
<concept-definition> ::= (DEFINE-CONCEPT <concept-name> <concept-expr>)
<concept-expr> ::= THING | CLASSIC-THING | HOST-THING | <concept-name> |
(AND <concept-expr>+) | (ALL <role-expr><concept-expr>) |
(AT-LEAST <positive-integer><role-expr>) |
(AT-MOST <non-negative-integer><role-expr>) |
(SAME-AS <attribute-path><attribute-path>) |
(TEST-C <fn><arg>*) | (TEST-H <fn><arg>*) |
(ONE-OF <individual-name>+) | (PRIMITIVE <concept-expr><index>) |
(DISJOINT-PRIMITIVE <concept-expr><group-index><index>) |
(FILLS <role-expr><individual-name>+)
<individual-expr> ::= <concept-expr>
<role-expr> ::= <mrole-expr> | <attribute-expr>
<mrole-expr ::= <symbol>
<attribute-path> ::= (<attribute-expr>+)
<attribute-expr> ::= <symbol>
KIF DEFINITIONS
I am assuming a facility in KIF for substitutional and analytical
definitions as proposed by Schubert in July. In particular, I am
assuming as a syntax for analytical definitions one of Len's
recommended forms as described below.
I define later an "arity" relation for use in the definitions of
functions and relations. Thus, one of the sentences in a defrelation or
defunction can be an arity expression.
DEFRELATION
(defrelation <relconst> <sentence>*)
Meaning:
<relconst> is defined to be a relation;
The sentences, which would typically contain references to
<relconst>, are true by definition.
Example:
(defrelation bachelor (arity bachelor 1)
(<=> (bachelor $x) (and (man $x) (unmarried $x))))
DEFUNCTION
(defunction <funconst> <sentence>*)
Meaning:
<funconst> is defined to be a function;
The sentences, which would typically contain references to
<funconst>, are true by definition.
Example:
(defunction paternal-grandfather
(arity paternal-grandfather 1)
(= (paternal-grandfather $x) (father (father $x))))
DEFOBJECT
(defobject <objconst> <sentence>*)
Meaning:
<objconst> is defined to be an object;
The sentences, which would typically contain references to
<objconst>, are true by definition.
Example:
(defobject id (= (f $x id) $x) (= $x (f $x id)))
>>>>> I am ambivalent about this "explicit" syntax versus the "implicit"
syntax that is in the current KIF reference manual. This syntax
requires fewer forms (i.e., "defprimrelation" is not needed). It also
allows one to define functions with an implication rather than a
bi-conditional (i.e., "primitive" functions) without requiring an
additional form in the language. It has the drawback of being more
cumbersome for human use. Comments? <<<<<
BASIC CONSTANTS
>>>>> I found it desirable to add to the basic constants in KIF
relations and functions to define sets (i.e., member, setof, and
cardinality) as described below.
I assumed the monotonic version of setof. (Which does not seem crucial
to this exercise.) I am unsure about the "provable" versus "true"
issue, but it seems we face that issue throughout the language, not just
in setof. <<<<<
RELATIONS
(member <object> <set>) -- <object> is a member of <set>.
FUNCTIONS
(setof <variable> <sentence>) -- The set consisting of all objects for
which <sentence> is true when the object is substituted for
<variable> in <sentence>. Note, this is the monotonic version; i.e.,
all objects for which <sentence> is true as opposed to provable.
(cardinality <set>) -- The number of elements in <set>.
STANDARD NON-BASIC CONSTANTS AND EXPRESSIONS
Just as is true of COMMON LISP, I expect there will be a set of standard
definitions that will become a part of KIF, even though they are
"non-basic" in the sense that they can be defined in terms of more basic
constants.
The only general definitions I needed were "disjoint" for sets and the
arity relation described above.
RELATIONS
(defrelation disjoint (arity disjoint 2)
(<=> (disjoint $s1 $s2)
(forall $x (not (and (member $x $s1) (member $x $s2))))))
>>>>> Note we could define a version of "disjoint" that takes 2 or more
arguments as follows:
(defrelation disjoint
(=> (disjoint @ss) (>= (length (list @ss) 2))))
(<=> (disjoint $s1 $s2 @ss)
(or (and (> (length (list @ss) 0))
(disjoint $s1 $s2) (disjoint $s1 @ss)
(disjoint $s2 @ss)))
(and (= (length (list @ss) 0)) (disjoint $s1 $s2)
(forall $x
(not (and (member $x $s1) (member $x $s2))))))
(defrelation arity
(=> (arity @args) (= (length (list @args)) 2))
(<=> (arity $x $i)
(or (and (relationp $x)
(=> ($x @args) (= (length (list @args)) $i)))
(and (functionp $x)
(=> (exists $y (= ($f @args) $y))
(= (length (list @args)) $i))))
>>>>> Note that in the definition of arity I am quantifying over a
relation or function and using the quantified variable in the relational
or functional position. Adding that capability to KIF eliminates many
of the annoying situations in which one needs to use quote. I have
assumed that capability throughout this note. Mike has done some
investigating of the ramifications of allowing such quantification and
his initial impression is that it does not cause any problems. Comments
welcome. <<<<<
NOTES ON A CLASSIC -> KIF TRANSLATOR
I have found it convenient to posit a set of KIF definitions
specifically for use with CLASSIC knowledge bases. These definitions
would be included at the beginning of the translated knowledge base, or
by reference if we provide that facility in KIF. I motivate each of
them in the discussion below and list all of them at the end of this
note.
DEFINE-CONCEPT
CLASSIC concepts correspond to unary relations in KIF. A CLASSIC
concept definition therefore translates into a defrelation sentence. If
the concept expression is a PRIMITIVE or DISJOINT-PRIMITIVE expression,
then the sentence inside the defrelation is an implication. Otherwise,
the sentence inside the defrelation is a bi-conditional. In either
case, most of the action is in the translation of the <concept-expr>.
Note that the translator will need to create a variable and pass it to
the translator of the concept expression (e.g., $x in "(defrelation foo
(<=> (foo $x) ...)").
As a convenience, I used Schubert's metadef facility for substitutional
definitions to create the following definitional forms that do not
require the implication or bi-conditional.
(metadef (def-concept $$c ($$x) @@ce)
(defrelation $$c (arity $$c 1) (<=> ($$c $$x) @@ce)))
(metadef (def-prim-concept $$c ($$x) @@ce)
(defrelation $$c (arity $$c 1) (=> ($$c $$x) @@ce)))
(metadef (def-disjoint-prim-concept $$c $$g ($$x) @@ce)
(def-prim-concept $$c ($$x)
(disjoint-concept $$c $$g) @@ce))
The relation disjoint-concept is used in the above to indicate that the
concept is disjoint from each of a given set of concepts (i.e., $$g). I
defined that relation as follows:
(defrelation disjoint-concept (arity disjoint-concept 2)
(<=> (disjoint-concept $x $g)
(and (member $x $g)
(forall $s (=> (and (member $s $g) (not (= $s $x)))
(disjoint $s $x))))))
AND
AND translates in a straightforward manner into a sequence of KIF
relational sentences. E.g., given $x as the concept expression
variable,
(and white-wine full-bodied-wine) -> (white-wine $x) (full-bodied-wine $x)
ALL
ALL translates into an implication whose consequent is the translation
of an arbitrary concept expression. E.g., given $x as the concept
expression variable,
(all son (and gentleman scholar)) ->
(forall $s (=> (son $x $s) (and (gentleman $s) (scholar $s))))
For convenience in expressing the typical case where the value
restriction is a concept, I defined an "all-fillers" relation in KIF as
follows:
(defrelation all-fillers (arity all-fillers 3)
(<=> (all-fillers $x $r $vr) (=> ($r $x $v) ($vr $v)))
"(all-fillers x r vr)", means that "all r's of x are vr's", where x
is an object, r is a role (i.e., a binary function), and vr is a
concept being used as a value restriction (i.e., a unary relation).
So, for example, given $x as the concept expression variable,
(all region california-region) ->
(all-fillers $x region california-region)
AT-LEAST
AT-LEAST translates in a straightforward manner assuming a basic
"cardinality" function in KIF. I have defined the following relation to
enable a succinct translation:
(defrelation at-least-fillers (arity 3)
(<=> (at-least-fillers $x $r $nr)
(>= (cardinality (setof $y ($r $x $y))) $nr))
E.g., given $x as the concept expression variable,
(at-least 1 grape) -> (at-least-fillers $x grape 1)
AT-MOST
Similarly for AT-MOST. E.g., given $x as the concept expression
variable,
(at-most 1 grape) -> (at-most-fillers $x grape 1)
SAME-AS
SAME-AS translates in a straightforward manner. E.g., given $x as the
concept expression variable,
(same-as (wine) (guest favorite-wine)) ->
(=> (wine $x $y)
(exists $z (and (guest $x $z) (favorite-wine $z $y))))
TEST-C
>>>>> The CLASSIC TEST-C and TEST-H forms raise some issues. First,
there is the need to distinguish "classic" concepts from "host"
concepts. As I understand those ideas, a classic concept is one
subsumed by CLASSIC-THING and a host concept is one subsumed by
HOST-THING. To express that distinction, I have defined the following
relations:
(defrelation nec-a-subsumes (arity 2)
(<=> (nec-a-subsumes $c1 $c2) (nec-a (=> ($c2 $x) ($c1 $x)))))
(defrelation classic-concept (arity 1)
(<=> (classic-concept $c) (nec-a-subsumes CLASSIC-THING $c)))
(defrelation host-concept (arity 1)
(<=> (host-concept $c) (nec-a-subsumes HOST-THING $c)))
Note the use of Schubert's "nec-a" in the definition of
"nec-a-subsumes". The intent is that one concept (i.e., unary relation)
nec-a-subsumes another only if the implication given is a logical
consequence of the domain assertions implicit in definitions.
A second issue raised by these tests which I have no solution for is
that the tests can return "unknown" as well as "true" or "false". I
don't know what to do about that in the KIF translation. I have ignored
it for now. <<<<<
For example, given $x as the concept expression variable,
(test-c foo) -> (and (classic-concept $x) (eval `(foo ,$x)))
TEST-H
See discussion of TEST-C. For example, given $x as the concept
expression variable,
(test-h evenp) -> (and (host-concept $x) (eval `(evenp ,$x)))
ONE-OF
ONE-OF translates in a straightforward way into a disjunction. E.g.,
given $x as the concept expression variable,
(all body (one-of full medium)) ->
(forall $y (=> (body $x $y) (or (= $y full) (= $x medium))))
FILLS
FILLS translates straightforwardly. E.g., given $x as the concept
expression variable,
(fills grape chardonnay) -> (grape $x chardonnay)
MISCELLANEOUS
>>>>> In order to support the defining of CLASSIC attributes (i.e.,
functional binary relations) and roles (i.e., binary relation), I
defined the following relations:
(defrelation def-attribute (arity 1)
(<=> (def-attribute $a)
(defrelation $a ($x $y) (forall $z (at-most-fillers $z $a 1)))))
(defrelation def-role (arity 1)
(<=> (def-role $a)
(defrelation $a ($x $y))))
CLASSIC has a limited form of forward chaining inference rules. Those
rules translate straightforwardly into a KIF implication. I have made
no attempt to capture the notion that CLASSIC uses them for forward
chaining only. <<<<<
WINE AND MEAL KNOWLEDGE BASE
The following is the KIF translation of the sample knowledge base given in
the paper assuming the definitions given above.
; Define attributes (i.e., roles that have at most one value).
(def-attribute color)
(def-attribute body)
(def-attribute flavor)
(def-attribute sugar)
(def-attribute region)
(def-attribute maker)
; Define roles
(def-role grape)
(def-role drink)
(def-role food)
; Define value restriction concepts and individuals to be used in further
; definitions.
(def-disjoint-prim-concept wine-property classic-thing-1 ($wp)
(classic-thing $wp))
(def-disjoint-prim-concept wine-color wine-property-1 ($wc)
(wine-property $wc))
(wine-color white)
(wine-color rose)
(wine-color red)
(def-disjoint-prim-concept wine-body wine-property-1 ($wb)
(wine-property $wb))
(wine-body light)
(wine-body medium)
(wine-body full)
(def-disjoint-prim-concept wine-flavor wine-property-1 ($wf)
(wine-property $wf))
(wine-flavor delicate)
(wine-flavor moderate)
(wine-flavor strong)
(def-disjoint-prim-concept wine-sugar wine-property-1 ($ws)
(wine-property $ws))
(wine-sugar sweet)
(wine-sugar off-dry)
(wine-sugar dry)
(def-disjoint-prim-concept wine-region wine-property-1 ($wr)
(wine-property $wr))
(wine-region napa-valley)
; Define the other topmost concepts.
(def-disjoint-prim-concept consumable-object classic-thing-1 ($co)
(classic-thing $co))
(def-disjoint-prim-concept meal classic-thing-1 ($m) (classic-thing $m))
(def-disjoint-prim-concept edible consumable-object-1 ($e)
(consumable-object $e))
(def-disjoint-prim-concept potable-liquid consumable-object-1 ($pl)
(consumable-object $pl))
(def-disjoint-prim-concept seafood edible-1 ($s) (edible $s))
(def-disjoint-prim-concept shellfish seafood-1 ($s) (seafood $s))
(def-disjoint-prim-concept fish seafood-1 ($f) (seafood $f))
; Define wine-grape and some instances of it.
(def-disjoint-prim-concept wine-grape edible-1 ($wg)(edible $wg))
(wine-grape chardonnay)
(wine-grape semillon)
; Define the concept of a wine.
(def-prim-concept wine ($w)
(potable-liquid $w)
(at-least-fillers $w color 1)
(all $w color wine-color)
(at-least-fillers $w body 1)
(all $w body wine-body)
(at-least-fillers $w flavor 1)
(all $w flavor wine-flavor)
(at-least-fillers $w sugar 1)
(all $w sugar wine-sugar)
(at-least-fillers $w region 1)
(all $w region wine-region)
(at-least-fillers $w grape 1)
(all $w grape wine-grape)
(at-least-fillers $w maker 1)
(all $w maker winery))
; Define some subcategories of wines.
; A white wine is a wine whose color is white.
(def-concept white-wine ($ww) (and (wine $ww) (color $ww white)))
; A full-bodied wine is a wine whose body is full.
(def-concept full-bodied-wine ($fbw) (and (wine $fbw) (body $fbw full)))
; A chardonnay-wine is a wine with exactly one grape, which is
; Chardonnay.
(def-concept charonnay-wine ($cw)
(and (wine $cw) (=> (grape $cw $g) (= $g chardonnay))))
; Now assert some rules about Chardonnay wines.
; Chardonnays are always white
(=> (chardonnay-wine $cw) (color $cw white))
; Chardonnays are always either full- or medium-bodied wines.
(=> (chardonnay-wine $cw)
(=> (body $cw $b) (or (= $b full) (= $b medium))))
; Chardonnays are not delicate.
(=> (chardonnay-wine $cw)
(=> (flavor $cw $f) (or (= $f strong) (= $f moderate))))
; Create and describe some individual wines.
(and (chardonnay-wine forman-chardonnay)
(body forman-chardonnay full)
(flavor forman-chardonnay moderate)
(sugar forman-chardonnay dry)
(maker forman-chardonnay forman))
(and (wine kalin-cellars-semillon)
(grape kalin-cellars-semillon semillon)
(body kalin-cellars-semillon full)
(flavor kalin-cellars-semillon strong)
(sugar kalin-cellars-semillon dry)
(maker kalin-cellars-semillon kalin-cellars))
; Define some primitive food-types.
(def-disjoint-prim-concept oyster-shellfish shellfish-1 ($os)
(shellfish $os))
(def-disjoint-prim-concpet non-oyster-shellfish shellfish-1 ($nos)
(shellfish $nos))
; Create some instances of food.
(oyster-shellfish oysters)
(non-oyster-shellfish crab)
; Describe the properties of a meal.
(def-prim-concept meal ($m)
(and (at-most-fillers $m food 1) (at-least-fillers $m drink 1)
(at-most-fillers $m drink 1) (all-fillers $m drink wine)))
; Define some concepts that allow recognition of meal-types, which will
; be antecedents of rules constraining wines.
(def-concept seafood-meal ($sm)
(and (meal $sm) (all-fillers $sm food seafood)))
(def-concept shellfish-meal ($sm)
(and (meal $sm) (all-fillers $sm food shellfish)))
(def-concept oyster-shellfish-meal ($osm)
(and (meal $osm) (all-fillers $osm food oyster-shellfish)))
; Assert rules pertaining to meal-types.
(=> (seafood-meal $sm) (all $sm drink white-wine))
(=> (shellfish-meal $sm)
(=> (drink $sm $d)
(and (body $d full)
(=> (flavor $d $f) (or (= $f moderate) (= $f strong))))))
(=> (oyster-shellfish-meal $osm) (=> (drink $osm $d) (sugar $d sweet)))
; Create a specific meal with oysters and food.
(and (meal meal-256) (food meal-256 oysters))
GENERAL CLASSIC DEFINITIONS
The following are the full set of definitions discussed above made
specifically for CLASSIC knowledge bases.
(defobject THING)
(defobject CLASSIC-THING)
(defobject HOST-THING)
(defrelation disjoint-concept (arity 2)
(<=> (disjoint-concept $x $g)
(and (member $x $g)
(forall $s (=> (and (member $s $g) (not (= $s $x)))
(disjoint $s $x))))))
(metadef (def-concept $$c ($$x) @@ce)
(defrelation $$c (arity 1) (<=> ($$c $$x) @@ce)))
(metadef (def-prim-concept $$c ($$x) @@ce)
(defrelation $$c (arity 1) (=> ($$c $$x) @@ce)))
(metadef (def-disjoint-prim-concept $$c $$g ($$x) @@ce)
(def-prim-concept $$c ($$x)
(disjoint-concept $$c $$g) @@ce))
(defrelation nec-a-subsumes (arity 2)
(<=> (nec-a-subsumes $c1 $c2) (nec-a (=> ($c2 $x) ($c1 $x)))))
(defrelation classic-concept (arity 1)
(<=> (classic-concept $c) (nec-a-subsumes CLASSIC-THING $c)))
(defrelation host-concept (arity 1)
(<=> (host-concept $c) (nec-a-subsumes HOST-THING $c)))
(defrelation all-fillers (arity 3)
(<=> (all-fillers $x $r $vr) (=> ($r $x $v) ($vr $v)))
"(all-fillers x r vr)", means that "all r's of x are vr's", where x
is an object, r is a role (i.e., a binary function), and vr is a
concept being used as a value restriction (i.e., a unary relation).
(defrelation at-least-fillers (arity 3)
(<=> (at-least-fillers $x $r $nr)
(>= (cardinality (setof $y ($r $x $y))) $nr))
(defrelation at-most-fillers (arity 3)
(<=> (at-most-fillers $x $r $nr)
(=< (cardinality (setof $y ($r $x $y))) $nr))
These two relations provide a convenient shorthand for number
restrictions.
(defrelation def-attribute (arity 1)
(=> (def-attribute $a)
(defrelation $a (arity 2) (forall $z (at-most-fillers $z $a 1)))))
An attribute is a role that can take at most one value.
(defrelation def-role (arity 1)
(=> (def-role $a)
(defrelation $a (arity 2))))