Production System - adds an OPS5-like system to C.

Implemented as a C preprocessor

Bernard Thirion, Institut de Recherche Polytechnique, 1992

Related languages
OPS5 => Edison   Implementation

  • "Edison, A Unix and C Friendly Rete Based Production System", B. Thirion, view details Abstract: This document introduces the architecture and the implementation of a rule based system especially devised to be integrated in the C and UNIX world. Built around the Edison knowledge description language and its translator, the environment features an inference engine using the Rete algorithm as well as a trace mechanism and a debugger. The who set can be used in full autonomy to design an expert system, or it can be integrated into a wider application as a software component. We shall describe the Edison language, its translation, the development environment and the performances of our production system.

    Various systems integrating a knowledge representation language and an inference engine, running in more or less elaborate environments have been around for a while. These environments are used as generator or kernel of expert systems. OPS51 is one of the first production systems available and operational in the industry. It owes its success both to its efficient filtering - thanks to the Rete algorithm 2 - and to its use for implementing the R1/XCON 3 expert system which deals with the configuration of VAX TM computer systems.

    Whereas more and more computer applications require a combination of declarative and procedural techniques, many expert system kernels have proved to remain closed - e.g. LISP based. Future development environments will depend on their integration into a common operating system (e.g. UNIX) and also to their interface with conventional languages such as C. To solve this integration problem, two strategies have been put forward depending on whether their base is a
    declarative language with a bridge to conventional languages, or whether their base is an imperative language with declarative extensions. The first approach consists in using a declarative system and opening it to other languages. C5 can be considered as a typical example of this procedure, as it is compatible with OPS5, but has been re-written into C and allows access to this language in the rule conclusions. The second approach consist in expanding a conventional language by adding declarative facilities as well as an inference engine; such are Modula-Prolog and AdLog - adding a Prolog layer onto respectively Modula-2 and Ada languages - or XC which is a declarative extension of the C++ language.
    Our environment goes into the second category, since it adds an OPS inspired declarative aspect to the C language. The aim of the environment is to endow a C programmer with the possibilities of an expert system kernel while keeping to a minimum the learning difficulties of a new formalism. A pre-processor translates Edison declarations into C language and an inference engine - implemented with the Rete algorithm - gives them their impetus.
    Further in our study, we shall first give a brief reminder of OPS type production systems, then we'll give a short introduction on the Rete algorithm. We shall then proceed with an analysis of our knowledge description language and of the implementation of our system, especially for the translation principle. Lastly, we shall indicate a few performances. Extract: The EDISON Language
    Edison is the name of the language describing the knowledge relevant to our system. Its syntax could be compared to
    that of the C language. The overall aspect of a source file reminds of the aspect of LEX or YACC files as found in the
    UNIX world. The source features a specific central part, framed by a prologue and an epilogue containing any user code.
    /* any user C code
    /* declaration of fact structure */
    /* declaration of production rules */
    declaration of initial facts
    /* any user C code */
    Prologue or epilogue may accept any C code, more particularly such as constant, type, variable, function, and file inclusion
    declarations. For instance:
    typedef enum (take, drop, wait, relax) tasks;
    typedef enum (inTheHeap, inTheHand, inTheBox) places;
    The declaration part
    The reserved word DECLARATIONS introduces this part which allows to define the structure of object (or fact) classes
    being handled; the syntax here is very similar to that of C:
    ROBOT { ~ a Robot has a name and a task to perform
    char name[20];
    tasks task;
    BRICK { /* a Brick has a size and is in a given place
    int size;
    places place;
    RECTANGLE { /* a Rectangle is defined by
    double top, left, bottom, right;
    void (* draw ) ();
    four values and can be drawn */
    /* a Square is defined by
    top, left, width;
    The production part
    its position and its width ./
    The reserved word PRODUCTIONS introduces this part which features the rules as condition conjunctions (leaving out
    the && logic operator) followed by an action. Each condition gives the name of the class of the searched fact as well as an
    expression to be satisfied under the form of a C condition, the comma being equivalent to the && operator. The conclusion
    is conventional C code. An alias mechanism permits to identify the facts matching the premises so as to allow using them
    in the action part. The following Edison source gives the rule allowing to take the biggest brick of the heap:
    ROBOT ($task == take)
    ($place == inTheHeap)
    ($place == inTheHeap, $size > Ssize)
    ("I have found the biggest brick, with a %d size", $size);
    (, place = inTheHand);
    TakeTheBigestBrick is the name of the rule.
    Sattribute is a notation giving access to a fact attribute.
    ROBOT ($task == take) filters an instance of class ROBOT whose task is to take an object.
    BRICK ($place == inTheHeap) filters an instance of class BRICK, the fact is identified by the alias.
    The last condition indicates that there must be no brick in the heap larger than the brick.
    The action part features not only any C code with the alias option, but also three specific instructions allowing to
    modify the working memory. The ADD instruction allowing to create a new fact, the MODIFY instruction allowing to
    modify a fact and the REMOVE instruction allowing to delete a fact. For instance:
    removeI 1 legalRect angles :
    RECTANGLE (Sleft > Sright I L $bottom > Stop)
    REMOVE () ;
    doObjectMut at ion :
    RECTANGLE ($right - $1eft == Stop - Sbottom)
    ADD (SQUARE, $1eft = $1eft,
    Stop = $top,
    $width = $right - $1eft
    REMOVE () ;
    The initial facts part
    The reserved word FACTS introduces this part which features the declaration of possible initial facts under the
    CLASS NAME (attribute values) form, as in the example:
    RECTANGLE ($1eft = i0, Sright = 50, Stop = I00, $bottom = 5)
    SQUARE ($1eft = 50, Stop = 50, $width = 30)
    BRICK ($place = inTheHeap, $size = i00)
          in SIGPLAN Notices 27(01) January 1992 view details