Page Numbers: Yes First Page: 1
Heading:
June 14, 1977 12:16 PM [IVY]<KRL>document>sys-imp
Status: Continually changing, but hopefully up to date. This version has not been updated (except for adding this line) since May 24 and needs working over
An outline of what needs to be done for the KRL-1 implementation
This is an attempt to fill in one more level of detail on what needs to be done in implementing KRL-1. The estimates as to how much work is needed for each part are very rough. First I will sketch out the major parts of the system and what they do, then fill in the details of each of the jobs to be done.
1. The basic operations of the system.
Summary of the major components (these labels are further explained where they appear in italics in the text)
I/O
Reader
Parser
Cataloguing
Printer
Editor
Dump and Load
Running
Scheduling
System events
Interpreter
Access Compiler
Compiler
Run-time routines
General Interpreter
Incorporator (memory -> belief converter)
Inferencer
Strategy
Anchorer (belief -> memory converter)
Interfacers
Activation of responses to system events
recognizing
interfacing
scheduling
The code which we will write will support two basic kinds of system operation, I/O and running.
I/O includes reading text strings which represent KRL-1 units and programs, printing internal structures as text strings, and dumping and loading on secondary storage in a not necessarily human-readable form. The input operation includes the activity of a parser and a cataloguing of a subset of the information contained in meta-descriptions (e.g. about further specification, triggers, functionals, etc.) into a form which allows the interpreter to run efficiently without having to repeatedly examine the units. For interactive use, the I/O system includes an editor which allows the user to modify the knowledge base, and which is interfaced with the cataloguing system to keep things up to date.
Three different kinds of support are needed for running KRL-1 programs: a basic scheduling mechanism which provides agendas for user-written functions; a system event mechanism for handling exceptions and data-driven processing (previously signals, traps and triggers); and an interpreter which executes KRL-1 commands for performing matching, seeking, and describing. KRL-1 commands are included as steps in the INTERLISP functions which are used as KRL-1 programs. They include the match/seek/describe commands which are executed by the interpreter, and process creation and control commands which are handled by the scheduling mechanism. The interpreter operates in two modes: there is a general interpreter which supports the full semantics of KRL-1 and can be used for complex inferencing, and there is the access compiler which operates once on a KRL-1 command, providing direct code (which makes use of a set of compiler run-time functions) to carry out the desired operations without going through full-scale interpretation each time the command is run.
A KRL-1 command for the interpreter includes a description of a process to be carried out which has the following general outline. There are goals to be achieved, such as: deciding whether a certain set of beliefs is inferrable from the stored memory structures; finding an anchor in the memory structure which corresponds to some entity; or adding additional memory structures which embody some set of beliefs. As the interpreter runs, it maintains an active context of beliefs, some of which may be initially specified in the command, some of which are derived from looking at stored memory structures, and some of which are the results of inferences.
The steps carried out by the interpreter can be thought of as an interweaving of several basic activities: incoporating beliefs from existing memory structures (memory level to belief level conversion); drawing inferences based on the set of beliefs already in the active context, leading to new beliefs; strategy decisions as to which activities should be done in what order to achieve the desired goals; activation of responses associated with system events; and anchoring of beliefs into new memory structures (belief level to memory level conversion). In addition, there are interpreter interfaces needed to get the initial information from the command, and to package the results in the appropriate manner to return them (as LISP values) to the program which included the command.
The activation of system events includes three parts: recognizing that an event has occurred for which there is some kind of response; interfacing by setting up a description of the relevant parts of the current context in a form which allows them to be accessed by the responding program; scheduling the carrying out of the response with appropriate priorities, ordering, etc.
2a. The data structures of the system -- function.
The data structures can be classified along two orthogonal dimensions -- function and form. I will first classify them by function.
Summary of the data structures (functional)
Declarative knowledge base
KRS levels
Message level
Intermediate level
Memory structures
Belief structures
Catalogue
Declarations
Functional definitions
Event-response pairs
Category and further-specification hierarchies
Procedural Knowedge base
Programs
Event-response pairs
Current system state
Agendas
Process descriptions
Interpreter state
Goals
Active context
Event descriptions
A first loose division is between those which represent the declarative knowledge base, those which represent the procedural knowledge base, and those which represent the current system state.
The declarative knowledge base is structured along the lines of KRS, with different structures for the different levels. There are message structures which represent the strings (and spacing) of text as read in or printed out. These are the structures which are stored on the standard INTERLISP files, and which are handled by the editor interface. There are intermediate structures which are produced in parsing and used in the cataloguing operations. These are transitory, generated during parsing or printing, and thrown away when that task is complete. There are memory structures which are the basic mechanism for storing knowledge in KRL-1. Finally there are belief structures which are created in the interpretation process, and are transitory, lasting only as long as the specific interpretation process which created them.
In addition to these basic structures, there is a catalogue which is a compilation of information derived from the other structures, used to make various operations more efficient. It includes: Category inclusion, functional defintions, further specification hierarchies, event-response pairs (see below), changing value declarations, and compaction declarations (see below).
The procedural knowledge base can be divided into two major parts: programs and event-response pairs. A program is an INTERLISP expression or function which may contain KRL-1 commands. An event-response pair is a combination of a description of a system event with a program to be carried out (with appropriate interfacing) whenever an event fitting that description occurs. Most such pairs are expressed as triggers or traps in units, or as part of a high-level description of processes. The set of pairs in the knowledge base is collected by the cataloguing operation, and compiled into a data structure which makes recognition efficient.
The current state of the interpreter includes the active context (described above as a transitory declarative structure). It also includes the agendas with their processes and the interlinking between them. The descriptions associated with these proceses will include global information (e.g. the current world, processing resources, etc.). The set of interpreter goals will also be available as a data structure for use in making strategy decisions. Whenever a system event triggers a response, an event description is created for use in interfacing.
2b. The data structures of the system -- form.
Summary of the data structures (forms)
Basic INTERLISP structures
Static -- lists, strings, numbers, etc.
Programs -- Expr forms, compiled code
Explicit description structures
Compact description structures
Specialized record structures
The data structures used to implement the abstractions described above can be grouped into four categories: basic INTERLISP data structures; explicit description structures; compacted description structures and specialized record structures.
The basic INTERLISP structures (lists, strings, data types, records) form the basis for implementing everything else. They are intermixed into the other structures (e.g. using a string as a value of a slot). KRL-1 programs are written as INTERLISP programs, which means they have a form as a list structure, and other forms as arrays (compiled code). They may contain embedded description structures as part of their data and as part of the specification of KRL-1 commands.
Explicit description structures correspond in a direct way to the conceptual notions of memory structure which form the basis for the semantics of KRL. They are built up out of data structures which correspond to the various descriptor types and structural objects (units, anchors, slots, etc.). In a simple implementation (like that of KRL-0) they would be thought of as simply being the KRL data structures and would be implemented using INTERLISP structures (using appropriate record declarations). In this implementation, they are bootstrapped in a different way (see below).
Compacted description structures are a specialized implementation of a subset of the allowable KRL-1 descriptor forms. They can be thought of as records (in the sense of the record package) which are interpreted as descriptions (through declarations entered as meta-descriptions of the associated units). This makes it possible to use the same interface (through Match, Seek, Describe, etc.) for general descriptions and these specialized ones, and thereby makes it possible for the system objects (e.g. event descriptions, process descriptions, agendas, etc.) to be treated as through they had full KRL descriptions, without paying an unacceptable overhead. In fact, it makes it possible to bootstrap, using compacted description structures as the implementation for the explicit description structures (see the memo on compaction).
In order to use this compaction, the declarations and knowledge about their interpretation must be used by those parts of the system which deal with memory structures (i.e. the incorporation and anchoring from the general interpreter, and the run-time (and possibly also the compile-time) routines of the access compiler). In the current plan, most of the structures described above by their function (e.g. agendas, process descriptions, interpreter goals, etc.) will be implemented in compacted descriptions.
If the compaction system were fully developed, there would be no need to have other specialized INTERLISP structures (record and data type declarations), since the compaction mechanism would take over the full function of the record package, dealing with access functions, data types, etc. In this go-round of implementation, we do not intend to put in all of these features, sticking with only the most basic record facilities. Therefore it may be necessary to implement some of the data structures (e.g. the active context, the catalog of system event-response pairs) using the record package in the usual way, taking advantage of various opportunities to gain efficiency. This also allows these parts to be implemented independently of the access compiler. Note: It may be useful to do this by having a facility to include your own record declarations along with a declared unit, thereby leaving the programmer the choice of using the access compiler or direct access functions.
3. The programming tasks.
In describing the set of tasks to be done, I am leaving out basic design, but including detailed design such as the choice of data structures, and specification of interfaces. The tasks do not break up along the program/data division used above, since typically a single task includes both designing the data structures and writing the code which uses them. Data structure design in many cases will consist of writing the appropriate units and compaction declarations, while in some cases it will mean dealing more directly with the record package, or special secondary storage manipulation. Many of the tasks can be best thought of as specification rather than implementation, since they involve specifying a set of conventions to be used by other components.
Outline of the tasks
Basic Memory Structure
Abstract specification of the memory structures
Implementation of primitive access to memory structures (extended address package)
Specification of the standard compaction declarations
Specification of intermediate level structures
I/O programs
Specification of the syntax
Implementation of the reader and parser
Specification of catalogue structures
Implementation of the cataloguer
Implementation of the printer
Implementation of an editor interface (using message level structures)
Programs for running
LISP interface
Specification of the run-time LISP-KRL interface (for passing values back and forth)
Implementation of the run-time LISP-KRL interface
Specification of standard descriptions for higher constructs (categories, sets, worlds, changing values)
Process
Specification of the standard agenda and process descriptions
Specification of the scheduler commands
Implementation of scheduling and agenda manipulation
Specification of the standard system events
Specification of the standard trigger and trap attachments
Implementation of system event activation
Implementation of discrimination trees
Interpreter
Specification of the standard interpreter commands and arguments
Specification of the standard interpreter process descriptions
Specification of the active context structures
Specification of the interpreter rules (incorporation and inference)
Specification of the interpreter goals
Specification of meta-descriptions used by the interpreter (e.g. to decide on uniqueness)
Implementation of the incorporator
Implementation of the inference processes
Implementation of the anchoring process
Specification of a set of basic interpreter modes and strategies
Implementation of standard strategies for the interpreter
Access Compiler
Specification of the cases handled by the access compiler
Implementation of the access compiler compile-time routines
Specification of the access compiler run-time routines
Implementation of the access compiler run-time routines
Abstract specification of the memory structures: This includes deciding how to represent anchors, descriptors, units, slots, etc. It has two components: creating the units and creating the compaction (and/or record) declarations which correspond to them.
Status: basically done, some cleaning up to do
Estimated Time: 1-3 days
Responsibility: Henry
Implementation of primitive access to memory structures (extended address package): The memory structures will be implemented using secondary storage. The mechanisms for this will be invisible to the user (e.g. hidden in the access functions associated with the corresponding records). The storage system needs to be designed, and implemented.
Status: Some design done
Estimated Time: 2-3 weeks
Responsibility: Ron, with help from Henry
Specification of the standard compaction declarations: This includes deciding how to implement low-level KRL-1 data objects such as sequences using LISP objects such as lists.
Status: Most of the design done
Estimated Time: 1-2 days
Responsibility: Danny & Terry
Specification of the syntax: Thisis described in the document on KRL-1 syntax, but there are a few minor changes and the we need to design a syntax for constructor forms
Status: Done except for minor changes and constructor forms
Estimated Time: 2-4 days
Responsibility: Henry
Specification of intermediate level structures: These are the structures used in parsing and printing
Status: Fully done as record structures, no units written, some changes need to be made to reflect minor changes in definition
Estimated Time: 1-2 days for changes, units to be done later
Responsibility: Henry
Implementation of the reader and parser:
Status: Done, some changes need to be made to reflect minor changes in definition
Estimated Time: 1-2 days for changes
Responsibility: Henry
Specification of catalogue structures:
Status: Mostly done as record structures. Needs to be cleaned up and put into unit structures. Some things not yet catalogued may need to be added. Additions or changes to design of categories may need to be done.
Estimated Time: 1-2 days
Responsibility: Danny
Implementation of the cataloguer:
Status: Basically running. Needs to be finished and extended to reflect changes in the specifications.
Estimated Time: 3-5 days
Responsibility: Danny
Implementation of the printer: We eventually need to be able to produce message level structures from memory structures. This is a non-trivial job. The current printer goes from intermediate level to message level. I am not sure exactly how this fits into the editing and filing issues. We need some discussion.
Status: one kind of printer running. We need a discussion of just what has to be there.
Estimated Time: 1/2 day discussion + ???
Responsibility: Ron with help from Henry
Implementation of an editor interface (using message level structures): As I currently understand it, we plan to edit by going back to the message level (characters and spacing) and reparse on leaving the editor. The reparsing includes updating the catalog. I believe this is basically done, but don’t know how it interacts with the display stuff.
Status: Running in some form, need to clarify interaction with display stuff and with cataloguing (e.g. removing obsolete entries).
Estimated Time: ???
Responsibility: Ron with help from Henry & Mitch
Specification of the run-time LISP-KRL interface (for passing values back and forth): This includes the "bang" descriptor, which allows lisp values to be filled into a command before it is executed, and the LISP descriptor which allows bindings to be made during interpretation. It also overlaps with the specification of arguments and values for the match/seek/describe family of commands.
Status: We have worked out all the basic ideas but need to organize them, clean it up and write it up
Estimated Time: 1-3 days
Responsibility: Danny & Terry
Implementation of the run-time LISP-KRL interface: This includes the code which fills arguments into a command at run-time, which sets up bindings, etc.
Status: Nothing done
Estimated Time: 1-2 weeks
Responsibility: Henry with help from Danny
Specification of standard descriptions for higher constructs (categories, sets, worlds, changing values): This is a large and open-ended task. We will have to do it incrementally, filling in those parts which are needed for doing the other specifications. Unfortunately, it is important to do those pieces in a style which fits in with the ultimate expansions, so it is a little hard to do piecemeal.
Status: Lots done for sets, but needs changes; categories need a little design, and detail; worlds are thought through, but lots of detailed design decisions remain, changing values are thought through, but some design remains.
Estimated Time: 2-4 weeks (incrementally)
Responsibility: Terry
Specification of the standard agenda and process descriptions: This includes units and appropriate declarations for all of the objects manipulated in control. At a first level, it includes the primitives for agendas and processes, but it can expand to deal with higher level control structures.
Status: A first pass has been done
Estimated Time:
Responsibility: Mitch and Martin
Specification of the scheduler commands: The activities of the scheduler will be control by giving KRL-1 commands (i.e. a KRL description of what is to be done, included in LISP with a special syntax, currently "$"). The set of general units for describing scheduler activities needs to be written, then functionals need to be defined which correspond to the standard cases (i.e. the ones the system will actually be able to do in the earliest implementation).
Status: Some design has been done. Needs to be systematized
Estimated Time: 3-5 days
Responsibility: Mitch with help from Terry
Implementation of scheduling and agenda manipulation: The programs which actually carry out the scheduler commands and maintain the process context. These may include some kind of compile-time (first execution time) manipulations on the commands, producing LISP code like the access compiler. This may be instead of or in addition to general interpretation of the commands at run time.
Status: Some design and coding has been done. More needed
Estimated Time: 1-3 weeks
Responsibility: Mitch
Specification of the standard system events: There will be a set of event descriptions which the sytem will actually be able to catch when they happen. This includes the old traps, triggers, and signals, but needs to be extended and unified.
Status: Some design has been done. More needed
Estimated Time: 3-5 days
Responsibility: Terry
Specification of the standard trigger and trap attachments: The standard triggers are actually a combination of two things -- a description of the event which should set them off, and a description of the process which should then be carried out. For servants like ToFill, this includes describing events within the interpreter. We know basically what is needed, but they need to be carefully defined.
Status: Some design has been done. More needed
Estimated Time: 3-5 days
Responsibility: Terry
Implementation of system event activation: The code which actually checks the catlog to see if there is something to be triggered, sets up the interfaces, schedules the response, and does something with the result if necessary.
Status: Needs more design at all levels, plus implementation
Estimated Time: 1-3 weeks
Responsibility: Danny with help from Mitch and Terry
Implementation of discrimination trees: The current plan is to implement system event recognition with a kind of discrimination tree.
Status: Mitch has been working on it, but I’m not sure of current status
Estimated Time: 1-2 weeks
Responsibility: Mitch with help from Leo?
Specification of the standard interpreter commands and arguments: This includes two levels: defining the units which have the right semantics, and creating the functionals for the standard combinations (the ones which will be hanlded in the early implementation).
Status: We have basically worked it out, but need cleanup and detail
Estimated Time: 1-3 days
Responsibility: Danny with help from Terry
Specification of the standard interpreter process descriptions: This includes two levels: defining the units which have the right semantics, and creating the functionals for the standard combinations (the ones which will be hanlded in the early implementation).
Status: Only vague thoughts. We will start with only the simplest ones
Estimated Time: 1-3 days
Responsibility: Terry with help from Danny
Specification of the active context structures: We need a formalization of the boxes and arrows I drew on the board. This is basically a matter of putting into units the decisions which have already been represented in the graphics.
Status: only general ideas so far
Estimated Time: 3-5 days
Responsibility: Terry with Martin
Specification of the interpreter rules (incorporation and inference): We need a formalization of the boxes and arrows manipulations I demonstrated on the board. This is basically a matter of carefully writing up things which are sketched out in written form already.
Status: Most of the thinking done. Some vague scribbles exist
Estimated Time: 3-5 days
Responsibility: Terry with Martin
Specification of the interpreter goals: Need a formalization of how the interpreter keeps track of what it is trying to do.
Status: only general ideas so far
Estimated Time: 3-5 days
Responsibility: Terry with David
Specification of meta-descriptions used by the interpreter (e.g. to decide on uniqueness): The notions of default, obligatory vs. optional element, criteria for deciding on whether a mapping exists, etc. are all part of the meta-description. We need a standard set which will be recognized by the initial version of the interpreter.
Status: It is stuff which we have thought through but not formalized, so a fair deal of organization is needed
Estimated Time: 3-5 days
Responsibility: Terry with Danny
Implementation of the incorporator: This is the code which takes memory structures and produces corresponding belief structures
Status: Nothing done
Estimated Time: 1-2 weeks
Responsibility: Martin
Implementation of the inference processes: The code which actually carries out the inference steps. The hard part of this is the bookkeeping needed to know when an inference is possible (it is the job of the strategy component do decide whether it should be done). This is closely related to some of the issues in keeping a parsing chart, and recognizing when new process activations are possible.
Status: Nothing done
Estimated Time: 2-4 weeks
Responsibility: Martin with help from Leo?
Implementation of the anchoring process: This is the inverse of incorporation. Selected belief structures are entered into the description structures. The hard part is accounting for worlds, etc. and for what is already there in the anchor into which the information is being entered. The old issues of folding, etc. come up here. In addition, it must be interfaced with the interpreter’s process descriptions for doing consistency checking as part of a Describe.
Status: Nothing done
Estimated Time: 2-4 weeks
Responsibility: Henry
Specification of a set of basic interpreter modes and strategies: In order to actually carry out a match, seek, etc. decisions must be made at each step of the interpreter. This is an open-ended problem, leading into all the grand and glorious issues of hypothesis formation, multi-processing, frames, etc. etc. However, a subset is needed for the most basic kinds of matching, seeking, and consistency checking.
Status: Nothing done
Estimated Time: 2-4 weeks
Responsibility: David with Terry
Implementation of standard strategies for the interpreter: The actual implementation of the strategies involves maintaining approriate processes and agendas within the interpreter, dealing with notifications, etc.
Status: Nothing done
Estimated Time: 2-4 weeks
Responsibility: David
Specification of the cases handled by the access compiler: A subset of the commands to the interpreter will be handled by access compiling. This subset needs to be specified early, so they can be used in implementing the other parts of the system.
Status: Basically done, needs to be written up
Estimated Time: 1-2 days
Responsibility: Danny
Implementation of the access compiler compile-time routines: Rich already has a basic set running. These will gradually be extended to handle more of the different possible commands.
Status: Basically done for one subset, may need to be extended
Estimated Time: 1-2 weeks (incrementally as extensions come up)
Responsibility: Rich
Specification of the access compiler run-time routines: The run-time routines need to handle the actual memory structures (including the difference between compacted and explicit descriptions).
Status: Need to be finished
Estimated Time: 1-2 days
Responsibility: Danny
Implementation of the access compiler run-time routines: These are what the access compiler compiles into combinations of.
Status: Not written
Estimated Time: 3-6 days
Responsibility: Rich with Danny