# Daneel Pang's Ontolingua paper

Tom Gruber <Gruber@sumex-aim.stanford.edu>
Full-Name: Tom Gruber
Message-id: <2870816529-5881409@KSL-Mac-69>
Date: Fri, 21 Dec 90  17:02:09 PST
From: Tom Gruber <Gruber@sumex-aim.stanford.edu>
To: ontolingua@sumex-aim.stanford.edu
Subject: Daneel Pang's Ontolingua paper

Enclosed is a paper by Daneel Pang, who was a MS student who
implemented a first version of ontolingua for Epikit, LOOM, and KIF.
In addition to making the routine stuff like define-class work, he
explored some extensions motivated by the needs of our port of DME off
of Cyc.

I am sending this to describe the first-cut syntax that he implemented
and to introduce some of issues involved in extending the language to
support productions and possible worlds.  I don't view the latter
capability as designed, much less implemented, but Pang did a good bit
of thinking on what might be done.

The laper is in LaTeX format, but requires a doublespace.sty file.  If
you don't have this file, let me know and I'll send it to you.  Be
warned that the paper is long, because of spacious formatting.

--tom
% -*- Mode:TeX -*-
\documentstyle[11pt, doublespace]{report}

\begin{document}

Where $w\entails\psi$ means that $\psi$ is true in $w$, and
$w\proves\psi$ to mean that, given $w$, the system can conclude $\psi$.
Thus, the semantics which describe inclusion and the effect \ttonto expects
are:
\begin{itemize}
\item[P1:]$$\entails\psi\;\mbox{\em iff}\;\psi\in G\;\mbox{OR}\;\proves\psi$$
\item[P2:]$$\entails\neg\psi\;\mbox{\em iff}\; \neg\psi\in G\;\mbox{OR}\;\proves\neg\psi$$
\item[P3:]$$\entails(\psi\andl\phi)\;\mbox{\em iff}\; \entails\psi\;\mbox{AND}\;\entails\phi$$
\item[A1:]$$\entails\poss\psi\implies\psi$$
\item[A2:]$$\entails(\poss\psi\;\andl\;\poss(\psi\implies\phi)) \implies\poss\phi$$
\item[R1:] from $\proves\psi$ and $\proves\psi\implies\phi$ infer $\proves\phi$.
\end{itemize}
This closely parodies the Kripke's possible world semantics, except for the
use of the $\poss$ instead of the $\nec$ operator.
The consequences of the definitions are:
\begin{itemize}
\item
Where we need to prove $\psi$, we will attempt to prove it first in the
current world, where it fails, we shall try to prove it via it's accessible
worlds.
\item
In trying to prove $\psi$ in the accessible worlds, wherein we encounter the
rule $\entails\phi\implies\psi$, we will attempt to prove $\phi$ from the
current world again.
\item
This may be recursively done.
\item
It may be possible to conclude both $\psi$ and $\neg\psi$ so long as
$\entails\poss^{n}\psi$ some $n$ and
$\entails\poss^{m}\neg\psi$ some $m$.\footnote{$\poss^{m}$ is the $\poss$
operator applied $m$ times.}
\item
Because of the order and direction of search, the nearest'' results and
rules will be utilized before the further ones.
This behaviour is inherently conducive to refinement down the children, since
the more refined results will be utilized.
\end{itemize}
The last item makes the entire inclusion'' method fragile, since to ensure
that the knowledge base does not have a contradiction (both proving $\psi$
and $\neg\psi$), none of the included partitions may contradict any other
partition.
This method of doing possible worlds is thus limited, but it is still an
important and useful mechanism to have and model.

\section{Dimensions}

In the building of possible worlds, be it for simulation or because it is
part of the knowledge that these possibilities'' exist parallel to ours if
only in our minds for analysis, it is recognized that there is a large
base of knowledge that is shared across some possibilities'' and other sets
which are shared across another set, where the intersection of these may be
one or several worlds.

It was thought interesting to analyze the pattern of sharing,\footnote{the
sharing here is the sharing of some facts inside of a system across
partitions and different thus from sharing entire knowledge bases between
users}  and with the help of the DME project, the following first
approximations were concluded:
\begin{itemize}
\item
If we consider each state or knowledge base that is analyzed that is
consistent'' and complete'' for the purpose of which the knowledge base
was produced as a world, it is hardly true that the entire world's knowledge
is shared.
\item
Of each world, there are some subset of knowledge which is shared amongst
some worlds and some other subset which are shared amongst yet others.
If we call the world which is included the parent world, and the other the
child world ({\em ie} the child world can see some part of the parent world),
we may analyze this as there being several types of parent-child branches,
with the particular subset being shared defining the type of branching.
\item
Sharing is sometimes not pure copying since it is often that the subsequent
sharing would add more facts to which may be shared by other worlds to
follow.  Using the terminology developed in the previous point, we may state
that each child may choose to refine and add onto the part that it shares
with it's parent before passing it down to its child.
\end{itemize}
With regards to the fact that the world is subdivided into those which are
shared along each branch and that the branches normally correspond to the
dimension'' (time dimension, possibility dimension and some such), we so
name these subsets.

These dimensions then are the portions of a world which is shareable by other
dimensions in other worlds.
The information that is shared must be able to function under the fragile
conditions specified in the previous section,
{\em ie} that it is not possible to both prove $\psi$ and $\neg\psi$ in any
2 worlds accessible'' from any world.

The limitation implies an inability to deal properly with nonmonotonicity via
this inclusion mechanism, except via non-inclusion ({\em ie} the parts which
contradict each other should thus not be placed in the partition), but is
still a useful mechanism.

It has a well defined formalism, and, given the capability to be in'' any
particular partition, one may control the efficiency of search by guiding and
directing the parents and ancestors to search.
The order of search is current world/dimension, the parents are searched
according to the order of inclusion.  A somewhat depth-first'' nature is
thus duplicated.
Thus, utilizing this particular nature, one may direct the direction of
search across these worlds and dimensions.

Therefore, a world then is a knowledge base which may be partitioned into
dimensions where each dimension may be shared and may share the knowledge of
another dimension(s) from other world(s).  These worlds are thus
dimension accessible'' from this world and $R$ is the
dimension accessibility'' relation.
The knowledge shared may be refined down the hierarchy but may not be

\section{Possible World Operators}

Unfortunately, the implication of the previous section is that there is no
possible world operator which works across these worlds in \ttonto as yet.
Therefore, \onto may choose to adopt yet another keyword, the keyword
{\bf true\_in} to achieve that.

The suggested syntax for the {\bf true\_in} operator is
\asisblock{
(true_in (<type> <accessibility reln>) <onto logic sentence>)
}
In as much as {\bf KIF} seems to wish to avoid this second order like
sentence, the expanded'' form might be used for the {\tt <onto logic
sentence>} portion of this syntax\footnote{for an example of the expanded''
form refer to the form inside the {\bf KIF} {\bf true} keyword in the example
in the discussion on the command {\bf tellm}}, thus the following may appear
in a knowledge base:
\asisblock{
(<= (= time (1+ \$t)) (true_in (necessarily backward) (list '= 'time \$t)))
}
Thus, {\tt type} may be one of {\tt necessary}, {\tt possibly} or a possible
world operator deemed necessary.
And the accessibility relation would denote the graph to which the worlds are
linked.\footnote{To achieve this, one may need to define a $(accessible\; R\; W_1\; W_2)$ type of relation as well, which states that $W_1$ may access
$W_2$ via the accessibility relation $R$}
In the given example, it states that utilizing the backward accessibility
relation, if all the values of {\tt time} of the previous worlds is
{\tt \$t}, then this world must be the world at time {\tt \$t+1}.

Currently, it is possible to utilize a production to achieve some subset of
such behavior ({\em ie} define a specialize {\bf true\_in} operator), but that
is an application of production that is, at best, temporary, if not a
perversion.

Thus, \ttonto (along with {\bf KIF} and several others) does not have a good
notation for possible world operator, and the {\bf true\_in} operator so
suggested is primitive but adequate for now, but is as yet unimplemented nor
supported.   This should be the next urgent step in the continued \ttontons.

\section{World Commands}

There are several world related commands available in the \ttontons.
However, these will probably be changed to accommodate the new ideas better,
and so will not be included here.
Again, the online documentation should provide adequate guide.
The commands available to date are
{\bf define-world},
{\bf perform-in-world},
{\bf perform-local-world},
{\bf perform-switch-world}, and
{\bf query-find-world}.
The functional dual of these are named as is similar to the other commands.

\chapter{Conclusion}

Again, it is stressed that \ttonto is a first attempt implementation of which
we are sure will contain misconceptions, mistranslations or other such.
However, the basic premise and idea, the \onto is sound and an important one.
Therefore, where in there is a failure or incompletion in the part of the
\ttontons, let the corrections be made and argued.
Where in there are refinements and conceptual changes needed for \ontons, let
the pages burn.

There are still several issues and items which should have been included and
discussed, but unfortunately, time constraints are upper most at this moment,
and it is hoped that this be a draft for a better document to come.

The forge is ready, the sword unfinished, may the first hammer hit be
resounding.

\appendix
\chapter{Acknowledgements}
My sincere thanks to Professor Tom Gruber for allowing me the chance to
undertake such a task and to provide numerous hours of refinement on my crude
ideas.  Thanks also to James Rice who provided the bulk of support in the
implementation that is \ttontons, without whom \ttonto would have probably
been an unfathomable mess.

My gratitude also to Yumi Iwasaki, Low Chee Meng, Alon Y. Levy who provided
information and critique essential to my constant work.

Lastly, my appreciation goes to Darlene M Gong, whose mental support and
incessant care made life bearable and allowed me to push on.

\end{document}