Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!harpo!seismo!hao!hplabs!sri-unix!Dave.Touretzky@CMU-CS-A
From: Dave.Touretzky@CMU-CS-A@sri-unix.UUCP
Newsgroups: net.ai
Subject: NETL
Message-ID: <4443@sri-arpa.UUCP>
Date: Thu, 18-Aug-83 05:16:00 EDT
Article-I.D.: sri-arpa.4443
Posted: Thu Aug 18 05:16:00 1983
Date-Received: Wed, 24-Aug-83 01:09:48 EDT
Lines: 59

I am a graduate student of Scott Fahlman's, and I've been working on
NETL for the last five years.  There are some interesting lessons to
be learned from the history of the NETL project.  NETL was a
combination of a parallel computer architecture, called a parallel
marker propagation machine, and a representation language that
appeared to fit well on this architecture.  There will probably never
be a hardware implementation of the NETL Machine, although it is
certainly feasible.  Here's why...

The first problem with NETL is its radical semantics:  no one
completely understands their implications.  We (Scott Fahlman, Walter
van Roggen, and I) wrote a paper in IJCAI-81 describing the problems
we had figuring out how exceptions should interact with multiple
inheritance in the IS-A hierarchy and why the original NETL system
handled exceptions incorrectly.  We offered a solution in our paper,
but the solution turned out to be wrong.  When you consider that NETL
contains many features besides exceptions and inheritance, e.g.
contexts, roles, propositional statements, quantifiers, and so on, and
all of these features can interact (!!), so that a role (a "slot" in
frame lingo) may only exist within certain contexts, and have
exceptions to its existence (not its value, which is another matter)
in certain sub-contexts, and may be mapped multiple times because of
the multiple inheritance feature, it becomes clear just how 
complicated the semantics of NETL really is.  KLONE is in a similar 
position, although its semantics are less radical than NETL's.
Fahlman's book contains many simple examples of network notation
coupled with appeals to the reader's intuition; what it doesn't
contain is a precise mathematical definition of the meaning of a NETL
network because no such definition existed at that time.  It wasn't
even clear that a formal definition was necessary, until we began to
appreciate the complexity of the semantic problems.  NETL's operators
are *very* nonstandard; NETL is the best evidence I know of that
semantic networks need not be simply notational variants of logic,
even modal or nonmonotonic logics.

In my thesis (forthcoming) I develop a formal semantics for multiple 
inheritance with exceptions in semantic network languages such as
NETL.  This brings us to the second problem.  If we choose a
reasonable formal semantics for inheritance, then inheritance cannot
be computed on a marker propagation machine, because we need to pass
around more information than is possible on such a limited
architecture.  The algorithms that were supposed to implement NETL on
a marker propagation machine were wrong:  they suffered from race
conditions and other nasty behavior when run on nontrivial networks.
There is a solution called "conditioning" in which the network is
pre-processed on a serial machine by adding enough extra links to
ensure that the marker propagation algorithms always produce correct 
results.  But the need for serial preprocessing removes much of the 
attractiveness of the parallel architecture.

I think the NETL language design stands on its own as a major
contribution to knowledge representation.  It raises fascinating
semantic problems, most of which remain to be solved.  The marker
propagation part doesn't look too promising, though.  Systems with
NETL-like semantics will almost certainly be built in the future, but
I predict they will be built on top of different parallel
architectures.

-- Dave Touretzky