Languages and metalanguages
Message-id: <>
Date: Sat, 16 Nov 91 12:59:08 EST
Subject: Languages and metalanguages

Your comments and questions are very well taken, and I'm sure that
a lot of other people have similar questions.  Following are my
comments on your comments:

> I have a few questions left over from your presentation last Friday,
> and the meeting at KSL last Tuesday.  Since the overall goal is to make
> the IRDS standards and the knowledge sharing effort languages as
> compatible as is possible, I wanted to be sure I had a clear vision of
> the IRDS proposal.

First, I must emphasize that the ANSI proposal for the IRDS conceptual
schema is still very much work in progress.  The only thing that is down
in writing is a 20-page working paper that will be presented to ISO.
(I sent a copy of that paper without the diagrams to SRKB and INTERLINGUA
mailing lists on October 18.)

For conceptual graphs, the starting point for most implementations has
been my 1984 book, but almost everybody who has worked with them deviates
>From the book in one way or another.  In recent papers, I have stayed
fairly close to the book, but I have added some extensions and have
clarified some points that were not clear in the book.  So the term
"conceptual graph" or the abbreviation CG is very much a moving target.

KIF is also a moving target, and it should continue to move as more
people start to work with it and add more requirements.  Therefore,
I will use NKIF for the "normative KIF" that we would like to make an
ANSI and ISO standard at some point in the future, say 1995.  I will
use NCG for the "normative conceptual graphs" that we would like to
define as semantically equivalent to NKIF.

> Could you let me know if the following are correct statements?

> 1) The second-order constructs of conceptual graphs, as used in IRDS,
> can all be expressed, although less compactly, in first order logic.

The general CG notation was designed as a semantic representation for
natural language, and it therefore allows almost any kind of mixture of
modal, intensional, and higher-order forms that occur in unrestricted
natural language.  NKIF and NCG are likely to be much more disciplined.

In my talk on Friday, I said that I prefer to use first-order logic as
much as possible.  Therefore, I would like to treat second-order logic
as a version of first-order logic whose domain of discourse is some other
first-order system.  As an illustration, following is a second-order
conceptual graph that says that the relation mother-of is a one-to-many,
irreflexive relation (this is in the linear notation for conceptual
graphs, which uses brackets for the boxes and parentheses for the

     [Relation: mother-of]-
          (CHRC)->[Cardinality: <1,many>].

ATTR is the attribute relation and CHRC is the characteristic relation.
Informally, you can say that ATTR is used with adjectives and CHRC with
nouns, although I have a more formal characterization of the distinction.
The formula operator phi translates this graph to the following formula
in predicate calculus:

     (Ex)(relation(mother-of) & irreflexive(x) & cardinality(<1,many>)
          & attr(mother-of,x) & chrc(mother-of,<1,many>)).

This formula says that there exists an instance of irreflexivity x, the
relation mother-of has x as an attribute, and it has a characteristic
cardinality <1,many>.

Note that this formula looks like first-order logic.  In fact, it
is a formula in an easily decidable logic with only conjunction and
existential quantifiers.  What is odd is its domain of discourse,
which includes constants like "mother-of" and "<1,many>" and
quantification over weird things like instances of irreflexivity.

In pure first-order CGs, we can say that mother-of is irreflexive
by a rule of the following form:

     IF    [Person: *x]->(Mother-of)->[Person: *y]
     THEN  [*x]-(^=)-[*y].

This says that if person x is the mother of person y, then x is not
equal to y.  (The asterisk distinguishes variables from constants.
In the pure graph form, you don't need any variables at all, and even
in the linear form, the number of variables is usually less than in the
corresponding formula in predicate calculus.)  I define IF and THEN
as macros for nested negative contexts, as in C. S. Peirce's logic.
Therefore, this graph maps to the following formula:

     ^(Ex)(Ey)(person(x) & person(y) & mother-of(x,y) & ^( x/=y)).

which is equivalent to

     (Ax)(Ay)((person(x) & person(y) & mother-of(x,y)) -> x/=y).

Note that Peirce's conventions allow you to use existential quantifiers
in the IF-clause instead of transforming them into universals in front
of the formula.  In most cases, this gives you a more natural English
reading for the graphs.

We still need some way to relate the second-order graphs to the
first-order graphs.  That can be done by an IF-THEN rule with the
second-order graph in the antecedent and the first-order graph in
the consequent:

     IF    [Relation: *r]->(ATTR)->[Irreflexive]

     THEN  [IF    [*x]->(rho *r)->[Person: *y]
            THEN  [*x]-(^=)-[*y]].

Note the Greek letter rho.  It represents an operator that maps
constants of type Relation in the second-order graphs into
relations in the first-order graphs.  I prefer to use lower-case
for constants in second-order graphs and upper case for relations
in first-order graphs.  Therefore, you could define

     Mother-of = rho mother-of.

The rule that relates the metalanguage to the target language belongs
to a metametalanguage whose domain is the union of the domains of the
target language and the metalanguage.  It also includes the operators
rho and tau for mapping individuals in the metalanguage to relations
and types in the target language.  Unrestricted use of rho and tau could
lead to an extremely complex undecidable system.  But if you restrict
them to rules of this form, you get simple translation rules for deriving
the first-order formulas from the second-order ones.

> 2) The logic expressed in IRDS includes integers, +, *, and
> exponentiation, so even though it is first order, it is not
> semi-decidable.

What makes Peano's axioms undecidable is the axiom of induction,
which is not first order.  You can have a restricted theory in which
you introduce arithmetic operators and functions one at a time as
you need them, but you allow induction only in the metalanguage, not
the target language.  Such a language could be decidable, but you
would have to go to the metalanguage if you wanted to add any new
functions and operators.

> 3) KIF includes some higher-order constructs which can not be reduced
> to f.o.l., to encode various closed-world assumptions, inheritance with
> exceptions, etc.  I assume these operations can not be directly
> expressed in IRDS?  This mismatch in expressiveness  will complicate
> interoperability between the two standards.

We must include all these features in the IRDS.  There are database
systems in use today that have null values, defaults, and open-world
assumptions with truth values {T, F, Unknown}.  The IRDS must be able
to describe them.

I attended John McCarthy's talk at CSLI on Nov. 7, where he discussed
contexts as first-class objects.  I like that approach very much.  I
think that you can use it to axiomatize theories in which the truth
values of the metalanguage are very different from the truth values of
the target language.  For example, you could have a metatheory with the
truth values {T,F} whose domain of discourse includes a set {T',U',F'},
which happens to be the truth values of the target language.  But you
would not identify T=T' or F=F'.

> If there is indeed a mismatch in expressiveness between IRDS and KIF,
> then we could extend IRDS to include the extra constructs, but this
> would mean sacrificing the good computational properties of IRDS in
> order to include constructs which are extraneous to its main mission
> -- defining dictionaries, constraints, etc. Alternately, we could
> accept a partial mapping for the KIF --> IRDS translation, with the
> usual idea that unexpressible constructs show up as structured
> comments.  Just making sure the mapping is clean on the appropriate
> subset of KIF would be a great boon to both standards, I think.

I think that we would like to have good computational properties in
both the IRDS and KIF.  But you may have to state rules for the kinds
of things that allow a nice tractable system and those things that
lead you into an intractable swamp.

Since the goal of CGs is to represent anything that anyone might say
in natural language, they must be able to represent all kinds of
absurdities and paradoxes.  But there should be criteria that warn you
when you approach a danger zone.  There are many decidable subsets of
logic that can be determined by syntactic checks.  When you go beyond
those subsets, the system might allow you to say what you want, but give
you a warning message:  "You have just said something that might be lead
to a paradox."  The system wouldn't have to prove that your statement
was indeed paradoxical; it could just say that violations of the rules
for using rho and tau might lead you into trouble.  If you are really
looking for trouble, the system should warn you, but let you do what
you want.