Dave.Touretzky@CMU-CS-A@sri-unix.UUCP (08/18/83)
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
Fahlman@CMU-CS-C.ARPA@sri-unix.UUCP (08/19/83)
From: Scott E. Fahlman <Fahlman@CMU-CS-C.ARPA> I've only got time for a very quick response to Alan Glasser's query about NETL. Since the book was published we have done the following: 1. Our group at CMU has developed several design sketches for practical NETL machine implementations of about a million porcessing elements. We haven't built one yet, for reasons described below. 2. David B. McDonald has done a Ph.D.thesis on noun group understanding (things like "glass wine glass") using a NETL-type network to hold the necessary world knowledge. (This is available as a CMU Tech Report.) 3. David Touretzky has done a through logical analysis of NETL-style inheritance with exceptions, and is currently writing up his thesis on this topic. 4. I have been studying the fundamental strengths and limitations of NETL-like marker-passing compared to other kinds of massively parallel computation. This has gradually led me to prefer an architecture that passes numers or continuous values to the single-bit marker-passing of NETL. For the past couple of years, I've been putting most of my time into the Common Lisp effort -- a brief foray into tool building that got out of hand -- and this has delayed any plans to begin work on a NETL machine. Now that our Common Lisp is nearly finished, I can think again about starting a hardware project, but something more exciting than NETL has come along: the Boltzmann Machine architecture that I am working on with Geoff Hinton of CMU and Terry Sejnowski of Johns-Hopkins. We will be presenting a paper on this at AAAI. Very briefly, the Boltzmann machine is a massively parallel architecture in which each piece of knowledge is distributed over many units, unlike NETL in which concepts are associated with particular pieces of hardware. If we can make it work, this has interesting implications for reliable large-scale implementation, and it is also a much more plausible model for neural processing than is something like NETL. So that's what has happened to NETL. -- Scott Fahlman (FAHLMAN@CMU-CS-C)