kif
genesereth@cs.Stanford.EDU (Michael R. Genesereth)
Message-id: <9312152011.AA25350@Sunburn.Stanford.EDU>
Date: Wed, 15 Dec 1993 12:10:31 -0800
To: interlingua@ISI.EDU
From: genesereth@cs.Stanford.EDU (Michael R. Genesereth)
X-Sender: mrg@sunburn.stanford.edu (Unverified)
Subject: kif
Cc: perlis@cs.umd.edu
Folks,
Well, there has been some lively discussion on this mailing list of late; and I
have read the exchange with considerable interest. I think that most of the key
points have already been raised; but, in my role as editor of the KIF document,
I wanted to emphasize a few of these points.
(1) First of all, an historical note on the issue of first-order vs higher-order
logics. Rich Fikes and I brought this issue before the interlingua committee in
its meeting of July 1992. In that meeting we outlined the relative advantages
and disadvantages of first-order and higher-order semantics and asked the
committee for a decision.
The principal benefit for higher order semantics was seen to be the power to
represent complex concepts (like transitive closure and circumscription) that
could not be represented in first-order without the danger of non-standard
models.
The disadvantages were seen as (1) a loss of compactness and completeness and
(2) the necessary introduction of typed variables and all of the
difficulties and
confusion they engender in practical settings.
Into this argument was injected the point that, while nonstandard models of
things like transitive closure are a problem for knowledge REPRESENTATION, they
are irrelevant to knowledge INTERCHANGE. The same conclusions can be drawn
whichever semantics one chooses! Pat Hayes recently made this point in his
responses to Fritz Lehman.
Given this point and the disadvantages of higher order semantics, the committee
voted to adopt a first-order semantics until and unless someone could discover a
significant problem with this approach to knowledge interchange.
I think we need to look carefully at Fritz Lehman's examples to determine
whether
any are sufficient examples to warrant a change to this decision. I, for one,
plan to study these examples over the next few weeks and either produce
renditions in KIF -or- suggest needed modifications to the semantics. But,
so far
as I can see after a brief look, none appear to warrant such a change, so
long as
we continue to concentrate on knowledge interchange.
(2) As to the issue of apparent higher order constructs in a language with
first-order semantics, I would like to refer you to the literature of
mathematical logic. For those of you unfamiliar with how one can give a first
order semantics to a language with second order syntax, you should look at the
treatment of second order languages in Herb Enderton's book entitled ``A
Mathematical Introduction to Logic''. In this particularly lucid account,
Enderton distinguishes between general semantics and absolute semantics, the key
difference being whether the relational quantifiers range over all
relations on a
universe of discourse or whether the quantifiers range over those relations
in a particular set of relations. In the latter case, it can be shown that the
semantics is effectively first-order, i.e. the logic remains compact and
semidecidable.
(3) The problem of set paradoxes is discussed in the KIF speification itself, at
least briefly. The treatment follows that of vonNeumann Godel and Bernays, who
show that there is a model for the basic axiom schemata given in the spec.
Given
that there is a model for any set of sentences, there can be no paradoxes
(which,
you will recall, are effectively self-contradictory sentences).
If anyone is interested, I can also give the rationale for why we chose the
slightly more complicated vonNeumann set theory over the apparently simpler
Zermelo Frankel set theory. Hint: think about how you would define the
lambda and
kappa operators in ZF.
(4) The problem of metalevel paradoxes is also mentioned in the specification,
though in this case the discussion is even briefer. There are numerous ways to
eliminate the metalevel paradoxes popularized by Montague. Kripke (Journal of
Philosophy 1975) gives an axiomatic approach based on Kleene's strong
three-valued
logic. Feferman (Journal of Symbolic Logic 1984) provides a simpler
axiomatization. Feferman's version is essentially equivalent to the one
described
by Perlis (AIJ 1986). Perlis's version is the one used in KIF. Perlis's
article
on self-reference proves that the axiom schema true(p)<=>p* is consistent
with any
theory not containing any occurrences of the true predicate. In other
words, the
semantics is not paradoxical, though one can write sentences that turn out to be
false.
The committee also considered a few weaker axiomatizations, which are not
included in the current specification. These can still be incorporated in
future
editions by naming additional true-like predicates, each with different axiom
schemata.
Those interested in these isues should look at the book ``Truth and Modality
for Knowledge Representation'' by Ray Turner (MIT Press), especially his
proof of
the equivalence of the KIF axiomatization to a variation of that described by
Kleene.
To summarize, we can be pretty well assured that the basic APPROACH taken in KIF
is safe from paradox. The semantic basis for KIF has been documented, reviewed,
and published in the mathematical and ai literature for years. We have not
innovated here in any semantic way; we have just standardized notation.
However,
(1) we must continue to study the spec to be sure that no silly mistakes were
made. Moreover, (2) we must continue to study some of our decisions to
determine
that these are the things we WANT in a language for knowledge interchange.
(And,
in so doing, we must be careful not to confuse knowledge interchange with
knowledge representation. The criteria are different.)
In conclusion, I would like to point out that the members of the Interlingua
committee have done a lot of work on this spec, as have the outside reviewers.
And more work is being done all of the time -- to refine the language, to
document
it, and to use it. This is no slapdash effort. I am personally gratified
to see
so much discussion on the mailing list. However, I would like to encourage
us to
concentrate on constructive criticism. The best questions are those based
on uses
of the language, accompanied by specific examples (like Lehman's list).
The best
kinds of criticisms are those that are based on proven difficulties,
together with
specific alternatives in the spirit of the language (like Gruber's criticisms
eraly on in the effort and Sowa's more recent recommendations for extended
quantifiers). I think we would all also welcome comparative studies (e.g.
between
kif's semantics and that of attardi and simi). The point of publishing the spec
was to elicit just such discussion. If we work together constructively, I think
we can produce a language that we can live with and that will serve the industry
well as it begins to begins to support greater degrees of knowledge interchange.
mrg
PS: Unfortunately, I will be away from my email for the next two weeks. So, if
you respond to this note, please do not be dismayed if you do not hear from me
for a while. I will respond when I get back in the new year.