Some thoughts on K.I.F.

sowa@watson.ibm.com
Message-id: <9105080122.AA00127@venera.isi.edu>
Date: Tue, 7 May 91 21:21:19 EDT
From: sowa@watson.ibm.com
To: SRKB@isi.edu, INTERLINGUA@isi.edu
Subject: Some thoughts on K.I.F.

I was not able to attend the KR'91 conference in Boston, but I heard
some second-hand reports about the discussions on the SRKB effort.
The loudest and clearest message seemed to be that people did not want
to see it called a "standards" project.  I had some concerns myself,
which I decided to express in this note to the SRKB committee.

My main concern is that I don't believe we have fully considered all
the requirements for the Knowledge Interchange Format.  A KIF that is
intended for knowledge interchange is very different from an ordinary
knowledge representation language.  For any given system, you can design
a clean, simple inference engine and a KR language that drives it.  Then
you can tell the users to take it or leave it.  If they want some feature
that isn't in your language, they have to do without it, code around it,
or find some other system that gives them what they want.  But a KIF
isn't designed for human users.  That puts more stringent requirements
on the language, because current computer systems aren't as flexible
as humans.

In my talk at Pajaro Dunes, I mentioned the work I once did on a common
intermediate language for compilers.  We initially tried to develop a
high-level intermediate language that would be close to the semantics of
all the conventional high-level languages.  But it turned out to involve
a nightmare of special cases for each language -- we couldn't make do
with less than the union of all the languages, and the amount of overlap
between them was much less than we had hoped to find.  The only approach
that really turned out to be successful was to adopt a very low-level
language, essentially a stylized machine language with an open-ended
number of registers.

First-order logic is certainly low-level for a knowledge representation
language.  It is what I call "the assembly language of knowledge
representation."  Since that is essentially the current proposal for KIF,
there is some hope that all other KR languages can be compiled into it.

But there is a big difference between a target language for a compiler
and an interface language designed for conversions.  Suppose that you
have two source languages A and B.  If you map both into KIF, you are
mapping both of them from a more expressive level to a low-level
first-order logic:

    A -> KIF   and   B -> KIF.

Going from a high-level to a low-level language can be done by a fairly
easy kind of macro expansion.  But if you are trying to use KIF to map
between A and B, you also have to handle the task of decompiling from
a low-level KIF to a high-level A or B:

    A -> KIF -> B   and   B -> KIF -> A.

Decompilers are much harder to write than compilers -- largely because
they have to recognize that a scattered sequence of low-level operators
is intended to represent some high-level function.  Sometimes a clever
decompiler can do that for special cases, but the general case is
theoretically unsolvable.  For these reasons, I don't believe that a
low-level KIF can be adequate.  Instead, KIF must be a very expressive
language that is essentially a superset of all the others.

To illustrate the point, I'd like to give some examples.  The first
one concerns the need for a sorted logic, which I was arguing for at
Pajaro Dunes.  Most KR languages support a type or sort hierarchy,
such as

   BIRD < ANIMAL < LIVING-THING < ENTITY

Each < symbol in that ordering maps into a first-order formula of the
following kind:

   (Ax)(bird(x) -> animal(x)).

This maps the higher-level sorted logic to an unsorted KIF.  But
if you want to translate KIF to a sorted logic or a semantic net as
the target language, the decompiler would have to search for formulas
of that kind and map them back into the symbol < or its equivalent.
But suppose the decompiler found the following formula:

   (Ax)(bird(x) -> flies(x)).

How would the decompiler know that BIRD was intended to be a type in
the original language, but that "flies" represents a verb that is not
supposed to be a type?  Perhaps it might not make a difference whether
"flies" is treated as a type or as a one-place predicate.  But in some
systems, the type hierarchy has a privileged status: i.e. there are no
exceptions to BIRD < ANIMAL, but there may be exceptions to birds flying.

As another example, consider the extended quantifiers "exactly-one"
and "unique".  Since they occur fairly often, some KR languages have
built-in features for them.  Consider the following sentence represented
in a sorted logic with the "exactly-one" quantifier and in a low-level
first-order logic:

   Every person has exactly one mother.

   (Ax:person)(Exactly-one y:woman) mother_of(x,y).

   (Ax)(Ey)(person(x) -> (woman(y) & mother_of(x,y)
      & (Az)(mother_of(x,z) -> z=y))).

Uniqueness is even harder to express with conventional quantifiers:

   Every person has a unique social security number.

   (Ax:person)(Unique y:number) ssno(x,y).

   (Ax)(Ey)(person(x) -> (number(y) & ssno(x,y)
      & (Az)(ssno(x,z) -> z=y) & (Aw)(ssno(w,y) -> w=x))).

These are two of the simplest sentences you might find that use the
quantifiers "exactly-one" and "unique".  In more complex examples, it
may be extremely difficult to analyze the low-level formulas in order
to determine whether or not they were supposed to express one of the
high-level quantifiers.

As an exercise for the reader, try expressing "most".  This is not a
fuzzy quantifier like "many", since it has a precise meaning.  But
expressing it requires an operator for accumulating and counting all
the instances for which a predicate is true.  Then converting to another
language requires a way of recognizing when that counting operator is
being used to express "most".  And speaking of fuzziness, what should
we do about mapping between two different systems that use fuzzy logic
or fuzzy set theory?  Just say that we don't like it?

When you're implementing a compiler or translator from a given language,
you don't have the right to pick and choose the features you like or find
easy to implement.  You've got to accept the source language exactly as
defined.  French chefs (at least at the top restaurants) have a slogan:
"Il faut honorer le menu."  If it's on the menu, you must support it.

John Sowa