Presenting a workable compromise between the rigid structures of Prolog,and the chaos of hypertext.
Bev and Bill Thompson are directors at Knowledge Garden Inc., Nassau N.Y The have written extensively about AI systems and are the authors of KnowledgePro, KnowledgeMaker, and MicroExpert.
If you look at the conference proceedings of the American Association for Artificial Intelligence, you'll see the papers broken down into categories such as AI architectures, cognitive modeling, knowledge representation, machine learning, and knowledge acquisition. The key words here are architecture, modeling, representation, and machine learning. The interest of much AI work has been to mimic human intelligence through the design of structures that let machines store and manipulate knowledge.
The users of AI systems, on the other hand, are interested in a totally different aspect of the problem. The lure of AI to corporations, scientists, educators, and individual authors is in the ability to communicate expertise via the medium of the computer. The current interest in hypertext systems represents another approach to the use of the computer to communicate complex knowledge. Because the ability to build structures is necessary in order to turn information and data into knowledge, any scheme that hopes to manipulate knowledge must be built around powerful but flexible structural concepts.
When we began our design project, which eventually became the language KnowledgePro, our goal was to build a system in which the focus was on the communication of expertise as opposed to its representation. This may sound like a meaningless distinction, but the switch in perspective affects the complexion of the system. In any design process, the designers are forced to make compromises. In saying that we would emphasize communication, we meant that when we made design decisions, we would compromise on the side of ease of use and expressive power rather than code efficiency.
In this article we will describe a structure called a topic that is the basic structural and storage unit used in KnowledgePro. A topic is a simple, uniform structure that provides both data representation and control. Topics serve many purposes; they can behave as procedures, functions, variables, system commands, and hypertext nodes. We'll discuss how topics support backward chaining, inheritance, and list processing as well.
Topics As Procedures
In its most basic incarnation, a topic is very much like a procedure in a language such as Pascal. It begins with a declaration of its name and parameters and ends with an end statement. Between the beginning and the end, a series of program statements are included, Example 1 page 41, shows an example of several nested topics.
Example 1: Fragment of a KnowledgePro program, or knowledge base.
topic 'which language'
ask ('What #mlanguage#m do you want to know more about ?',want,
[Pascal,C,Lisp,Prolog])
do (?want).
topic language.
window ().
say('
Some people make a distinction between AI and "conventional"
programming languages. Though individual languages certainly
differ, for the most part, an AI language is one that was
developed at a place where they happened to be doing AI.')
close_window().
end. (* language *)
topic Pascal
say ('
When using Pascal to solve "AI types" of problems, you usually
have to design low-level routines to implement linked
list structures.').
end. (* Pascel *)
(* topics for C, Lisp and Prolog would go here*)
end. (* ehich language*)
Before discussing the topics in this example, we should say a few words about KnowledgePro syntax. KnowledgePro statements consist of the name of the command followed by a set of parentheses that enclose any parameters to be passed to the command. Each command ends with a period. Several of the most commonly used commands also have shorthand notations that make them more natural to express. Strings that include spaces or delimiting characters are enclosed within single quotes. Words included between (* and *) are comments.
KnowledgePro programs are called knowledge bases. All commands in the knowledge base are associated with an undeclared topic called !main. Topics nested within !main are executed in one of two ways: directly using a do command or through a mechanism called backward chaining. Using the do command is just like executing a procedure in C or Pascal. The command can be written using the uniform notation that uses the name of the command:
do (`which language').
or with a format more familiar to C and Pascal programmers:
`which language')).
In either case parameters can be passed to the topic much as in C or Pascal.
Backward Chaining
Backward chaining is a technique used in PROLOG and by rule-based expert system shells. In a "conventional" programming language, when you use a variable that hasn't yet been assigned a value, the value of the variable is unpredictable. In a language that uses topics, there are no variables as such. The topic serves not only as a structural unit but also as the unit of storage. Values can be both assigned to and retrieved from a topic. The dual nature of the topic makes it possible for an unassigned value to cause the execution of a topic in an effort to find its value.
As an example, suppose we change the first line of the knowledge base in Example 1 to read:
if ?`more about languages' is yes
then do (`which language').
and we add the following topic:
topic `more about languages'.
ask (`Do you want to know more about languages ?`,
more about languages',
[Yes,No]).
end. (* more about languages*)
Here, the ? is a shorthand notation for the value_of command, so this expression can also be written as value_of (`more about languages'). value of requests & value for the topic more about language and, not finding a value, causes the commands associated with the topic more about languages to be executed. This topic contains an ask command that uses three parameters: the question, the name of the topic in which the answer is saved, and optionally a list that will place a menu of options on the screen. In this example the answer to the question is saved in a topic that already exists, If the topic selected was one that was not defined in the knowledge base, it would be created.
If a statement containing ?`more about languages' is encountered again in the knowledge base, it will not trigger the execution of the ask command but will merely retrieve the value of the topic, of course, a topic can be considerably more complex than the one shown in the example. A topic whose execution as been triggered by the ? operator could trigger the execution of other topics either directly or through backward chaining.
Topics As Variables
The ? operator retrieves the value from a topic. A topic may be assigned a value either as the result of executing commands nested within itself, or it may be assigned a value as the result of another topic's actions.
Along with values and associated procedures, topics have a series of properties that describe the number and kinds of values they may take on. By default, topics are unrestricted in the number and kinds of values that may be assigned to them. It is possible, however, to restrict topics to a range of numerical values, to a limited number of values, or to members of a set of specified legal values.
Topics may be predefined in the knowledge base or created on the fly. This has the advantage of allowing the creation of complex structures at run time. For example, the statements:
ask(Which cat do you wish to choose ?`,cat-name, [Figaro,Flo, Babe]). ?cat_name = `needs a new flea collar.'
will produce a menu of choices and allow the user to choose one or several names. For each name chosen, a topic will be created if it doesn't exist and the topic will be assigned a string.
Designers of structured languages tell us that all data structures should be predefined and strongly typed. A reason often cited for this is that programs designed in this way are easier to debug and maintain. Actually, debugging and maintenance are functions of the programming environment. Strong typing and predefinition of data structures make the design of efficient compilers easier because at run time the program contains the location and type of most of its data structures. Languages that create structures at run time are dependent on efficient search routines to find structures.
Rules
In the jargon of expert systems, an if.. .then statement is called a rule. Rules can be expressed in the form shown earlier but can also share the formal notation of all KnowledgePro commands. The rule in our example has the following internal representation:
rule(eq(?('more about languages'), yes), delay)[do `which language')])).
delay is used to prevent the second half of the rule from evaluating until the first part is evaluated and returns a Boolean value of T.
As you might suspect from looking at the example, system commands are themselves topics defined internally but behave in all other ways like user-defined topics. In an application the internal topics can be overridden by defining a topic with the same name within the knowledge base or by using a topic written in another language and included in an external library. The same technique can be used to create new topics that extend the language.
Hypertext and Topics
Returning to the example in Example 1, let's look at the first line in the topic which language:
ask (Which #mlanguage#m would you like to know more about?', want, [Pascal,C,Lisp,Prolog]).
We've already described how the ask command works, but if you look closely, you'll notice that the text of the question includes the word language enclosed within the characters #m. This notation is used to define a hypertext node. Any text marked in this way is displayed on the screen in inverse video (or in any color selected by the application designer). The user of the application can use a function key or a mouse to move among highlighted concepts. When a concept is selected, the topic of the same name--for example, language--is executed. The commands, window, close_window, and say are self-explanatory. Here, window and close_window use default values, but they can also include parameters that specify title, color, size, and location of the windows selected.
If no topic with the same name can be found, the system will next search for a topic called mark and, if it finds it, will pass the hypertext phrase to mark as a parameter. Example 2, page 41, shows an example of one way in which this feature is used. In the knowledge base in Example 2, all the text threaded to hypertext nodes is stored in an external data file called thread.fil. When the say command displays its message, the Lisp and list structures are highlighted, but no topics with these names are defined. If the user selects one of these--for example, Lisp--the topic mark is executed and passed Lisp as a parameter. The first line in mark assigns a value to the topic text, which is also created at this time. The value assigned is the result of the read command.
Example 2: Using the default topic mark with hypertext.
say ('One of the powerful features of #mLisp#m is the ability
to easily manipulate #mlist structures#m'),
topic mark (find),
text = read (;(threads.fil', concat ('/', ?find), '/ednd').
window ().
say (?text)
close_window ()
end. (* mark *)
read uses three parameters: the name of the file to read, where to begin reading, and where to stop reading. The command concat returns /Lisp, which is the result of concatenating the character / onto the value of the topic find. All text following this string and up to the string /end is assigned to the topic text. A window is opened; the value of text, which might be several pages long, is displayed; the window is closed; and control returns to the statement from which the hypertext was selected.
Nested Topics and Inheritance
Topics can be nested inside other topics to form a hierarchy, which allows you to package pieces of a knowledge base into self-contained units. A topic defined within another topic is normally accessed only from within that topic. Normally, KnowledgePro searches for a topic by examining the topics defined within the current topic. If none of these is the one being sought, it examines the parent topic to see if the topic is defined there. KnowledgePro doesn't look at topics nested within those defined at the parent level. Nested topics are normally invisible from the outside; they are only found through the hierarchical search process. The search continues up the hierarchy until the topic is found or the topic main is examined.
Example 3, page 41, shows an example of a nested topic. If dog is referenced outside of animal, it won't be found unless the full name animal:dog, which defines its location in the hierarchy, is specified. The hierarchical structure allows topics to inherit values from other topics. Example 3 shows a knowledge base that describes some properties of some common animals. The command animal (). will display the following message:
A dog has 4 legs. A cat has 4 legs. A bird has 2 legs.
Example 3: Nested topics showing how values are inherited.
topic animal
;legs = 4. (* The default number of legs for an animal *)
dog (). (* These commands are used for initialization *)
cat ().
bird ().
say ('
A dog has ',?dog:legs,' legs.
A cat has ',?cat:legs,' legs.
A bird has ',?bird:legs,' legs.')
topic dog.
end. (* dog *)
topic cat.
end (* cat *)
topic bird.
:legs =2. (* override the default *)
end (* bird *)
end (* animal *)
The default value for legs is set to 4. The topics dog, cat, and bird are then executed. Of these topics only bird contains an override value. The before the name legs in this topic tells KnowledgePro that this legs is a local topic, not the one defined in animal. Because this topic doesn't exist, it is created. When a value is sought for each of these items in the say statement, both dog:legs and cat:legs are assigned the default value of 4 because no override was specified.
List Processing
Lists are integral to all topics. Each parameter passed to a topic is actually a list. For example, the first parameter of an ask command is the question. So far, you've seen questions made of simple text expressions; however, because each parameter can be a list, more complex displays can be created, as in this example:
ask (['The total cost is $', ?price ?'number of items', 'How will you pay?'], pay,[Check,'Credit card']).
Here, the question is a list containing three items: a literal string, the result of multiplying the value of the topic price by the value of the topic number of items, and a final literal string.
Turning back for a moment to Example 1, you can see another example of the use of lists. The response to the question What language do you want to know more about? can include more than one item from the list of menu items [Pascal,C,Lisp,Prolog]. The answers selected are stored as a list that is assigned to the topic want. Let s say that the answers selected were C and Prolog. When the command do (?want). is executed, each topic in the list assigned to want will be executed, so the first topic, C, will be performed and then the topic Prolog will be executed.
Lists enable you to manipulate groups of related items. In one knowledge base we examined recently, the designer had a long set of rules with each rule having only one conditional clause, as in this example:
if ?lot is K10
then item is 3A62.
if ?lot is A22
then item is 6H77.
...
topic lot.
ask ('What is the lot number on the remaining section ?',lot, [K10,A22,...]).
end.
This entire set of rules, no matter what its length, could have been expressed in four lines using lists:
lot_list is [K10,A22,...] item_list is [3A62,6H77,...]. ask (What is the lot number?', lot,?lot_list). item is element (?item_list, where (?lot_list, ?lot)
When the question is displayed, the contents of the topic lot_list are displayed on the menu. The item selected-for example, 6H77-is assigned to the topic lot. The evaluation of the last line begins by finding where the value selected, 6H77, is located in the list lot_list. The value 2 is returned as the result of the where command. Next, the element command returns the second item of the list contained in item_list and this value is assigned to the topic item.
Many other list-handling commands are necessary for a high-level symbolic language. These include commands such as first, last, and rest (similar to the LISP commands car, last, and cdr) that let you tear apart lists. KnowledgePro also includes commands for combining, comparing, and constructing lists in a variety of ways.
Summary
The flexibility of the hypertext and the directness that comes with procedural control make it possible for people with little or no programming experience to sit down and easily express their expertise. At the same time, techniques such as backward chaining, inheritance, and list handling enable it to be used in complex symbolic computational problems. With languages built around these types of structures, it becomes possible to design applications that allow program control to be shared by both the designer and the user of the system, surpassing the rigidity of the current expert system technology and the free-form environment of hypertext media.
Readers interested in seeing a sample of the KnowledgePro environment can obtain a run-time version from CompuServe: go PCVEN (data library 8). Several free demo programs, including TextPro (a program for writing and reading short hypertext documents), are available. Source code is included with the demos so you can get an idea of how topics work.