update content

[arxana.git] / latex / honey-demo.tex

%% honey-demo.tex - documentation for honey.el

%% Copyright (C) 2010 Raymond S. Puzio

%% This program is free software: you can redistribute it and/or modify
%% it under the terms of the GNU Affero General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% (at your option) any later version.
 
%% This program is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%% GNU Affero General Public License for more details.

%% You should have received a copy of the GNU Affero General Public License
%% along with this program.  If not, see <http://www.gnu.org/licenses/>.


\def\comment{;\it}
{\obeyspaces\gdef {\ }}
{\catcode`;=\active
 \gdef\lisp{\everypar={\tt}% 
\catcode`\#=12\catcode`;=\active\let;=\comment%
\tt\obeyspaces\obeylines}}%
%\openout1=honey-demo.el
\def\boxit#1{\hbox{\vbox{\hrule{\hbox{\vrule\kern2pt
 \vbox{\kern2pt\hbox{#1}\kern2pt}\kern2pt\vrule}}\hrule}\kern-2.5pt}}

\centerline{\bf Higher Order NEtwork Yarnknotter}
\centerline{\sl An introduction by example}

\beginsection Introduction

This document introduces the HONEY platform for networks by working
through examples, starting with the basics and gradually working up to
advanced features.  ``HONEY'' stands for ``Higher Order NEsted
Yarnknotter'' and is a system for creating, maintaining, and
interacting with higher-order nested semantic networks.  By ``higher
order'', it is meant that links can point to other links.  By
``nested'', it is meant that the nodes which make up a network may
contain other networks, which themselves may have nodes containing yet
other networks, etc., ad nauseam or ad infinitum, whichever comes
first.  In addition, all the links are bidirectional and no
fundamental distinction is made between links and nodes.  This
sophistication makes the package suitable as a platform to construct
knowledge bases for such advanced applications as hyperreal
dictionaries.

For convenience and flexibility, this package has been designed in a
modular and extensible fashion.  The basic functionality is provided
by a back-end which manages the data of the network.  In the
implementation described here, this data is stored in hash tables, but
one could instead have it stored in, say, a relational database or a
file system by writing a suitable back-end and using that instead.
For higher-level access to the data is mediated by means of a handful
of primitive commands and, as long as these commands behave similarly,
it does not matter to the end user how they are implemented or how the
data is represented internally.

Since these primitive command are, well, primitive, restricting
oneself to them would be quite a tedious way to interact with the
knowledge base except for basic maintenance operations.  Thus, on top
of the built-in layer, one would normally add a layer or two of
application packages which accomplish more sophisticated tasks such as
rendering documents or updating links en masse or implement different
types of documents as semantic nets.  In the interests of integrity of
the knowledge base and modularity with respect to its representation,
these routines should not access the underlying databases directly but
call upon the primitive access functions to do their bidding.  In a
finished application, one might even have several layers, say a middle
end which implements layered services upon the database and a
front-end which provides a user-friendly interface to these services.

The basic unit from which we will construct our networks is called an
``article''.  Articles are data objects which serve to encode both
links and nodes and are characterized by the following components:
\item{$\bullet$} Identifier
\item{$\bullet$} Source
\item{$\bullet$} Sink
\item{$\bullet$} Content

Each article has a unique identifier which the computer assigns to it
when it is entered into the database.  This identifier is used by the
access functions to refer to the article for subsequent operations.
Since talking about, say, article 12 pointing to article 5 is not
intuitive for most users, the system also has a mechanism for
assigning names to articles so that one could instead, say, refer to
``walrus'' pointing to ``mammal'' instead.

Source and sink are pointers to other articles and content is a place
in which to store a lisp object, which might be some text, or an
expression, or maybe a number or maybe something else depending on
what intends to represent with one's network and how one intends to
use it.  In particular, the content of an article can even be another
network constructed out of more articles.

In order to provide a foundation for building up networks, there is a
special article ``ground'' which serves as a foundation.  It is the
zero object of our system; its source and sink is itself and its
content is nil.  To enter an article which is meant as a node, we set
its source and its sink to ground.  We can also set the source to
ground and sink to a non-ground article or vice-versa; this provides a
means for creating ``stickies'' which attach directly to articles, a
construction for which we shall find use from time to time.

This system of articles each of which point to two other articles and
a ground article is similar to the cons cells of lisp, but expands the
paradigm in two important ways --- the cells carry content and the
links are bidirectional.  These differences allow the system under
consideration to accomplish things which would not be feasible with
plain old s-expressions.

Bidirectional linking means that the links are stored and accessed in
a manner which makes it no more costly to find and traverse links in
the backwards than the forward direction.  This is what makes it
practical to make links as mentioned above and done explicitly below.

Storing content in articles is what allows us to construct nodes.
While, in lisp, {\lisp(cons nil nil)} is certainly valid, it's not
terribly useful since it doesn't carry much information.  However,
when we can attach information to a cell, then each such object is
able to serve as a distinct carrier of information and can be quite
useful.  In the case of links, this room for extra information can be
used to do things like, say, specify what part of a story is being
considered in a link to a comment on a story.

\beginsection Getting Started

In this section, we will show how the system works by starting up an
instance, entering a simple example, and saving it.  

The first step is to load the Honey package.  We fire up Emacs in
lisp mode and type in the following command:
\smallskip
{\lisp
(load-file "honey.el")
  $\Rightarrow$ t}
\smallskip\noindent
Then we need to make a network with which to work.  We can do this
as follows:
\smallskip
{\lisp
(set-net (new-net root-level))
  $\Rightarrow$ 
(*network*
 1
 #<hash-table 'equal nil 2/65 0xa770c68>
 #<hash-table 'equal nil 1/65 0xa2f18c0>
 #<hash-table 'equal nil 1/65 0xa3fd678>
 #<hash-table 'equal nil 2/65 0xa710ad0>
 #<hash-table 'equal nil 2/65 0xa74eec8> 0)}
\smallskip\noindent
The command ``{\tt new-net}'' sets up the database for a new network
and initializes it.  The argument ``{\tt root-level}'' means that this
network resides at the fundamental level of the system as opposed to
residing within a node of some other network.  Finally, the command
``{\tt set-net}'' selects this net as the one to which the commands
for entering and viewing data will apply.  The output is the internal
representation of this network, which ``{\tt set-net}'' has passed
through for possible use by some other function.

Now, we can start entering data.  For our first example, we begin with
the following basic network of two nodes connected by a link which
expresses the fact that walruses are mammals:
$$
 \matrix{\lower3pt\boxit{\tt walrus} & 
 \hbox to 40pt{\rightarrowfill} & 
 \lower3pt\boxit{\tt mammal}}
$$
As we proceed, we will expand this to something non-trivial but first
the fundamentals.

In the example, there are two nodes, ``walrus'' and ``mammal''.  In
our system, nodes are represented by articles whose source and sink
are both ``ground''.  To construct these nodes, we will need the
identifier of the special article ``ground'', which we can find by
using the command ``label2uid'' :
\smallskip
{\lisp
(label2uid "ground")
  $\Rightarrow$ 0}
\smallskip\noindent
We proceed to construct the two articles using the command
``put-article'' as follows:
\smallskip
{\lisp
(put-article 0 0 "walrus")
  $\Rightarrow$ 2
(put-article 0 0 "mammal")
  $\Rightarrow$ 3}
\smallskip\noindent
The first two arguments of the command are the source and sink of the
article, respectively, which, in this case are both ground.  The third
argument is the content of the article, which we chose to be the
obvious text string.  The values returned are the identifiers of the
newly made articles, which we shall use in the next step.

The link from ``walrus'' to ``mammal'' will be represented by an
article whose source is ``walrus'' and whose sink is ``mammal''.
Using the values for identifier we noted above, this command to make
this article goes as follows:
\smallskip
{\lisp
(put-article 2 3 nil)
  $\Rightarrow$ 4} \smallskip

For our convenience, we will name our two nodes.  We do this using the
command ``label-article'' which takes the numerical identifier of the
article and the string by which we will refer to it as arguments:
\smallskip
{\lisp
(label-article 2 "walrus")
  $\Rightarrow$ 2
(label-article 3 "mammal")
  $\Rightarrow$ 3}
\smallskip\noindent
Just as we did above with ``ground'', so too we can now look up the
identifier of one of our nodes using the command ``label2uid''
{\lisp
(label2uid "mammal")
  $\Rightarrow$ 3}
\smallskip\noindent
Conversely, we can use ``uid2label'' to find the name of one of our
nodes from its numerical identifier:
\smallskip
{\lisp
(uid2label 2)
  $\Rightarrow$ "walrus"}
\smallskip\noindent

We may examine our network by using access functions to view the
content, source, and sink of articles:
\smallskip
{\lisp
(get-content 2)
  $\Rightarrow$ "walrus"
(get-source 4)
  $\Rightarrow$ 2
(get-sink 4)
  $\Rightarrow$ 3}
\smallskip\noindent
These can be combined with the previous commands to make for more
user-friendly interaction:
\smallskip
{\lisp
(uid2label (get-sink 4))
  $\Rightarrow$ "mammal"
(get-content (label2uid "walrus"))
  $\Rightarrow$ "walrus"}
\smallskip

Having entered our example net and performed a few operations on it, we
will now save it as ``simple-example'':
\smallskip
{\lisp
(setq simple-example (download-en-masse))
  $\Rightarrow$
((0 "ground" 0 0)
 (1 "article-type" 0 0)
 (2 "walrus" 0 0 . "walrus")
 (3 "mammal" 0 0 . "mammal")
 (4 nil 2 3))}
\smallskip\noindent
The result of this operation is a compact representation of our
network as a list of quintuplets of the form 
{\lisp (uid label source sink . content)}.  We can store this away in
a file or wherever for safekeeping and later use it to rebuild our
knowledge base.  To demonstrate how this goes, we will first use the
command ``reset-net'' which resets the net to the state in which it
was when newly created, removing everything added subsequently:
\smallskip
{\lisp
(reset-net)
  $\Rightarrow$ nil}
\smallskip\noindent
We can check that this command acts as advertised by calling
``download-en-masse'' once more:
\smallskip
{\lisp
(download-en-masse)
  $\Rightarrow$
((0 "ground" 0 0)
 (1 "article-type" 0 0))}
\smallskip\noindent
The walrus and the rest of what we typed in are gone, sure enough.  To
bring them back, we will use the command ``{\tt upload-en-masse}''
which takes a list of quintuplets generated by ``{\tt
download-en-masse}'' and constructs the database recorded therein:
\smallskip
{\lisp
(upload-en-masse simple-example)
  $\Rightarrow$ t}
\smallskip\noindent
When we ask about the nodes now, we see that the walrus has returned:
\smallskip
{\lisp
\smallskip\noindent
(uid2label (get-source 4)) $\Rightarrow$ "walrus"} 
\smallskip\noindent
To be sure, we can double check by comparing the saved value from
earlier with what we get by downloading now:
\smallskip
{\lisp
(equal simple-example (download-en-masse))
  $\Rightarrow$ t}

\beginsection Types, adding, and editing

Having seen how the basics go, we will now examine more features of
the fundamental system --- types of articles, primitive commands for
editing content, and mass addition of articles.

In a typical semantic network, the links and nodes have types which
are important for the semantics.  For instance, in our example, the
link would have type ``isa'' and the nodes might have type ``thing'':
$$
 \matrix{\mathop{\lower3pt\boxit{\tt walrus}}\limits_{\rm thing} & 
 \mathop{\hbox to 40pt{\rightarrowfill}}\limits^{\rm isa} & 
 \mathop{\lower3pt\boxit{\tt mammal}}\limits_{\rm thing}}
$$
In order to type articles in a systematic way which is easily
accessible to processes which depend on article type, we make use of
the special article {\tt article-type} (which is automatically created
by the system; e.g. see the output of {\tt download-en-masse} above).
To this special article are attached articles corresponding to the
different types; in our example these will include {\tt isa} and {\tt
thing}.  To record the type of a given article, we make a link from
the home node for the type to the article in question.

So we begin by making the home nodes for our types.  For convenience,
we combine article creation and labeling and use user-friendly names.
\smallskip
{\lisp
(label-article
 (put-article (label2uid "article-type")
              (label2uid "ground")
              nil)
 "isa-type")
  $\Rightarrow$ 5
(label-article
 (put-article (label2uid "article-type")
              (label2uid "ground")
              nil)
 "thing-type")
  $\Rightarrow$ 6}
\smallskip\noindent
Note that the source of these articles is {\tt ground} and that they
are attached to the main node {\tt article-type} by having it as their
sink.  This is an example of a ``stickie'' of the sort mentioned in
the introduction.  Such a construction is useful in cases like this
where we want to attach one article to another but don't need to have
a link between them as a separate object.

Whoopsie! we said the source was {\tt ground} and the sink was {\tt
article-type}, but when we look at what we told the machine, we got it
backwards:
\smallskip
{\lisp
(uid2label (get-source 5))
  $\Rightarrow$ "article-type"
(uid2label (get-sink 5))
  $\Rightarrow$ "ground"}
\smallskip\noindent
As it sometimes happens when writing exposition, your author has made
a serendiptious mistake which will be used for illustrating a point,
in this case how to edit articles.  Even more serendipitously, he has
made the mistake twice, providing an occasion to illustrate two
different methods.

The first method is to erase the incorrect article and enter it again
correctly.  To effect the erasure, we use the command {\tt
remove-article}:
\smallskip
{\lisp
(remove-article 5)
  $\Rightarrow$ nil}
\smallskip\noindent
Then we enter it again as it should have been:
\smallskip
{\lisp
(label-article
 (put-article (label2uid "ground")
              (label2uid "article-type")
              "isa")
 "isa-type")
  $\Rightarrow$ 7}
\smallskip\noindent
While we were at it, we took advantage of the occasion to put
something more interesting than {\tt nil} in the content slot.  Also
note that the new article now has uid 7 as opposed to uid 5 for the
one we deleted.  This, of course, is no surprise because there is no
reason to suppose that the machine would happen to assign the same
number to the new article as belonged to the deleted article it is
intended to replace.  Because, as yet, nothing links to this article,
this change of idntifying number does not have any effect and we can
refer to the new article using the same label.

The other way of rectifying the booboo is to change the source, sink,
and content of the erroneous article.  We carry this out by using a
trio of appropriately named commands, as illustrated below:
\smallskip
{\lisp
(update-source 6 (label2uid "ground"))
  $\Rightarrow$ ((6 . 0) (7 . 0))
(update-sink 6 (label2uid "article-type"))
  $\Rightarrow$ ((6 . 1) (6 . 0))
(update-content 6 "thing")
  $\Rightarrow$ (0 1 . "thing")}
\smallskip\noindent
Making the change this way ensures that the article retains the same
identifier.  As stated above, while this is unimportant for the
current example, it would be a different matter if there were other
articles pointing to the artice being edited since deleting it and
replacing it with a new article would mean losing those links.

Having straightened out this flap over the article types, we now
proceed to add types to our articles.  To do this, we make links from
our newly-created nodes isa-type and thing-type to the nodes to be
assigned types:
\smallskip
{\lisp
(put-article (label2uid "thing-type")
             (label2uid "walrus")
             nil)
  $\Rightarrow$ 8
(put-article (label2uid "thing-type")
             (label2uid "mammal")
             nil)
  $\Rightarrow$ 9
(put-article (label2uid "isa-type")
             4
             nil)
  $\Rightarrow$ 10} 
\smallskip\noindent
Note that, in the case of our link which states that a walrus is a
mammal, recording its type entails making a link to a link.


\beginsection Query and Search

\end

\hbox{\vbox{\hrule% upper side
\hbox{\vrule% left side
\kern3pt\vbox{\kern22pt% top marin
\hbox{walrus}\kern5pt %bottom margin
}\kern3pt % right margin
\vrule% right side
}\hrule%bottom side
\kern-5.5pt}}