Programmer's ROM - The Computer Language Library/programmersrom.iso/ada/ai/alspuser.doc

Text File | 1988-05-03 | 85.5 KB | 3,499 lines

                         C2 Support Software in Ada(R)




                                 User's Manual









                                 SAE-DC-85-R002


                                 March 17, 1986








                      Software Architecture & Engineering
                        1600 Wilson Boulevard, Suite 500
                           Arlington, Virginia 22209










           (R) Ada is a registered trademark of the U.S. Government -
                            Ada Joint Program Office














          1.  Preface


          This document represents the final delivery of CDRL A003
          (User's Manual) for Contract N66001-85-C-0039 ("C2 Support
          Software in Ada") between Software Architecture & Engineer-
          ing, Inc. (Software A & E) and Naval Ocean Systems Center
          (NOSC), 271 Catalina Blvd, Building A-33, San Diego, CA
          92152.

          The C2 Support Software in Ada to be provided by
          Software A & E consists of a generic package, the AI Data
          Types package, which provides the necessary facilities to
          emulate the capabilities commonly used in Artificial Intel-
          ligence (AI) applications but not directly supported in Ada.
          These facilities are:

          (1)  Definitions of the primary data object to be used
               throughout this package, the symbolic expression.

          (2)  Symbolic expression operators.  These include functions
               and procedures for creation, selection, manipulation
               and destruction of symbolic expressions.

          (3)  Packages which define generic AI objects generally
               found useful in AI applications:  patterns, rules and
               rulebases.

          This manual will consist of six sections.  Each of the first
          four sections will document one of the four data type pack-
          ages: Symbolic_Expressions, Patterns, Rules and Rulebases.
          The fifth will provide an explanation of how to use the AI
          Data Types package including restrictions on instantiating
          the package and a description of the necessary parameters
          for instantiation.  The final section will describe the com-
          pilation and use of the demonstration program provided with
          the package.





























          2.  Symbolic Expressions

          2.1.  Syntax


          The following is a Backus-Naur Form (BNF) representation of
          the syntax of symbolic expressions:


              Symbolic_Expr ::= Atomic_Expr | Non_Atomic_Expr | Null_S_Expr

              Atomic_Expr ::= Literal  | Variable

              Literal ::= User defined, supplied by package instantiation.

              Variable ::= '?' Variable_Name

              Variable_Name ::= String_Literal

              Non_Atomic_Expr ::= '(' Component {',' Component} ')'

              Component ::= Symbolic_Expr

              Null_S_Expr ::= '(' ')'



          As can be seen from the above syntax specification, there
          are three types of symbolic expressions:  atomic expres-
          sions, non-atomic expressions and the null component.

          Atomic expressions are defined as being either literals or
          variables.  An atomic literal is supplied by the user as a
          result of package instantiation.  This literal can be a
          value of any predefined or user-defined Ada enumeration,
          numeric, record, array, access or private type.  For pur-
          poses of discussion, literals based on enumeration or
          numeric types will be referred to as simple atomic literals.
          Those based on record, array, access or private types will
          be called complex atomic literals.  While complex atomic
          literals can be simulated using non-atomic expressions, in
          cases where dynamic data structures are not necessary (the
          data structures used do not grow and shrink with time) or
          where additional data encapsulation is required, using com-
          plex atomic literals will result in more efficient implemen-
          tations.  The only values which an atomic literal may not
          take on are values of a task type or any limited private
          type due to the fact that equality and assignment are not
          defined for these types.

          The other type of atomic expression is a variable.  A vari-
          able consists of a one-character prefix ('?') and a string
          literal indicating the name of the variable.  Variables are


                                       2










          used primarily for pattern matching purposes which will be
          discussed at length in the AI Object Packages section.

          Examples of atomic expressions:

              1234                    - integer literal
              122.34                  - floating or fixed point literal
              "bcd"                   - string literal
              `(46, 22, 33, 97, 134)  - array of integers
              `(July, 4, 1986)        - record
              ?x                      - variable


          Note that the some type of character must be used to distin-
          guish between an atomic expression whose representation
          includes parentheses from a non-atomic expression.  The
          choice of this indicator is user-specified.

          Non-atomic expressions are composite expressions consisting
          of a left ('(') and right (`)`) non-atomic delimiter and one
          or more components.  Each component of a non-atomic expres-
          sion is a symbolic expression.  Thus, a symbolic expression
          is a recursive data type and it is possible to nest non-
          atomic expressions within one another to any desired depth.

          Examples of non-atomic expressions:

              ('a', 'b', 'c', 13678)
              ('(1, 2, 3, 10, 46), "foo", (Apr, 12, 1983))
              ((("bar")))
              (("abc", "def"), ("ghi", "jkl"))


          The final type of symbolic expression is Null_S_Expr.
          Null_S_Expr is a special constant symbolic expression which
          denotes the null component and serves primarily as a
          representation of an empty non-atomic expression.
          Null_S_Expr cannot be placed in either of the two previous
          categories because it is the only symbolic expression which
          is treated as both an atomic and a non-atomic expression.
          Null_S_Expr is represented as a left and right non-atomic
          delimiter enclosing white space ('('')').

          2.2.  Symbolic Expression Operators


          The following is a list of the available symbolic expression
          operators categorized by their functionality.  Each entry
          contains an interface specification, description and a list
          of restrictions on use and possible exceptions which can be
          raised.  The parameters of the subprograms in the examples
          are representations of the variables supplied to the subpro-
          grams, not the parameters themselves.


                                       3










          2.2.1.  Storage Management Routines

          2.2.1.1.  Free

          Interface:

              procedure Free (S_Expr_Arg : in out S_Expr);


          Description:
               Because symbolic expressions are dynamic objects, their
               storage must be managed.   Free provides a way of deal-
               locating storage from a symbolic expression which is no
               longer in use.  It is HIGHLY recommended that this pro-
               cedure be called for each symbolic expression declared
               locally in a block, procedure or function before exit-
               ing that local scope.

          Restrictions:
               None.

          Examples:

                   procedure X (Var : in S_Expr) is
                      SE : S_Expr;
                   begin
                      -- Process SE;

                      Free (SE);
                   end X;



          2.2.1.2.  Return_And_Free

          Interface:

              function Return_And_Free (S_Expr_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Return_And_Free is another storage management function
               which is to be used when returning a value from a func-
               tion to insure that its storage is later reclaimed.
               When returning a value of type S_Expr from a function,
               Return_And_Free should be called and the value returned
               from Return_And_Free should be returned directly.  Once
               again, it is HIGHLY recommended that this convention be
               followed to avoid inefficient use of and possible
               exhaustion of available storage space.




                                       4










          Restrictions:
               None.

          Examples:

                   function X (Var : in S_Expr) return S_Expr is
                      SE : S_Expr;
                   begin
                      -- Process SE;

                      return Return_And_Free(SE);
                   end X;











































                                       5










          2.2.2.  Creation Routines

          2.2.2.1.  Create_Atomic_Literal

          Interface:

              function Create_Atomic_Literal (Literal_Arg : in Atomic_Literal)
                 return S_Expr;


          Description:
               Create_Atomic_Literal returns an atomic expression con-
               taining the specified Literal_Arg.

          Restrictions:
               None.


          2.2.2.2.  Create_Atomic_Variable

          Interface:

              function Create_Atomic_Variable (Name : in String)
                 return S_Expr;


          Description:
               Create_Atomic_Variable returns an atomic expression
               containing an atomic variable with the specified Name.

          Restrictions:
               None.


          2.2.2.3.  Prefix

          Interface:

              function Prefix (First_Value : in S_Expr;
                               Rest_Value  : in S_Expr := Null_S_Expr)
                 return S_Expr;


          Description:
               If the second argument is atomic, Prefix returns an
               expression, X, such that First (X) = First_Value and
               First (Rest (X)) = Rest_Value.  Otherwise, it returns
               an expression, Y, such that First (Y) = First_Value and
               Rest (Y) = Rest_Value.

          Restrictions:
               None.



                                       6










          Examples:

               Prefix  () ()    ==> (())
               Prefix  a ()     ==> (a)
               Prefix  () a     ==> ((), a)
               Prefix  () (a)   ==> ((), a)
               Prefix  a b      ==> (a, b)
               Prefix  a (b)    ==> (a, b)
               Prefix  (a) b    ==> ((a), b)
               Prefix  (a) (b)  ==> ((a), b)



          2.2.2.4.  &

          Interface:

              function "&" (S_Expr_Arg1, S_Expr_Arg2 : in S_Expr)
                 return S_Expr;


          Description:
               "&" returns Null_S_Expr if both its arguments are
               Null_S_Expr.  Otherwise, "&" returns a non-atomic
               expression which contains as components:

               (1) S_Expr_Arg1 and S_Expr_Arg2, if both are atomic
               expressions.

               (2) the components of S_Expr_Arg1 appended with
               S_Expr_Arg2, if S_Expr_Arg1 is a non-atomic expression
               and S_Expr_Arg2 is an atomic expression.

               (3) S_Expr_Arg1 appended with the components of
               S_Expr_Arg2, if S_Expr_Arg1 is an atomic expression and
               S_Expr_Arg2 is a non-atomic expression.

               (4) the components of S_Expr_Arg1 appended with the
               components of S_Expr_Arg2, if both are non-atomic
               expressions.

          Restrictions:
               None.

          Examples:

               () & ()          ==> ()
               () & a           ==> (a)
               () & (a)         ==> (a)
               a & b            ==> (a, b)
               a & (b)          ==> (a, b)
               (a) & (b)        ==> (a, b)
               (a, b) & (c, d)  ==> (a, b, c, d)


                                       7










          2.2.3.  Component Selection Routines

          2.2.3.1.  First

          Interface:

              function First (Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               First returns the first component of Non_Atomic_Arg.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expr is raised.

          Examples:

               First ((), a, b)   ==> ()
               First (a, b, c)    ==> a
               First ((a), b, c)  ==> (a)



          2.2.3.2.  Rest

          Interface:

              function Rest (Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               If Non_Atomic_Arg is a non-atomic expression containing
               only one component, Rest returns Null_S_Expr.  Other-
               wise, Rest returns a non-atomic expression which con-
               tains all components of Non_Atomic_Arg except the
               first.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Rest (a)          ==> ()
               Rest (a, b, c)    ==> (b, c)
               Rest (a, (b, c))  ==> ((b, c))





                                       8










          2.2.3.3.  Nth

          Interface:

              function Nth (Non_Atomic_Arg : in S_Expr;
                            Position       : in Positive)
                 return S_Expr;


          Description:
               Nth returns the Position-th component of
               Non_Atomic_Arg.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.  Position must be a valid position within
               Non_Atomic_Arg.  If not, the exception Invalid_Position
               is raised.

          Examples:

               Nth (a, (b), c)  1  ==> a
               Nth (a, (b), c)  2  ==> (b)
               Nth (a, (b), c)  3  ==> c



          2.2.3.4.  Last

          Interface:

              function Last (Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Last returns the last component of Non_Atomic_Arg.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Last (a, b, c)      ==> c
               Last (a, b, (c))    ==> (c)
               Last (a, (b, (c)))  ==> (b, (c))






                                       9










          2.2.3.5.  Nth_First

          Interface:

              function Nth_First (Non_Atomic_Arg : in S_Expr;
                                  Repetitions : in Positive)
                 return S_Expr;


          Description:
               Nth_First returns the result of calling the function
               First Repetitions times each time using the result of
               the previous call as the argument for the new itera-
               tion.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.  Also, if the function First cannot be called
               Repetitions times with a non-atomic argument each time,
               the exception Invalid_Repetitions is raised.

          Examples:

               Nth_First (((a)), b, c)  1   ==> ((a))
               Nth_First (((a)), b, c)  2   ==> (a)
               Nth_First (((a)), b, c)  3   ==> a



          2.2.3.6.  Nth_Rest

          Interface:

              function Nth_Rest (Non_Atomic_Arg : in S_Expr;
                                 Repetitions : in Positive)
                 return S_Expr;


          Description:
               Nth_Rest returns the result of calling the function
               Rest Repetitions times each time using the result of
               the previous call as the argument for the new itera-
               tion.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.  Also, if the function Rest cannot be called
               Repetitions times with a non-atomic argument each time,
               the exception Invalid_Repetitions is raised.




                                       10










          Examples:

               Nth_Rest (a, b, c) 1  ==> (b, c)
               Nth_Rest (a, b, c) 2  ==> (c)
               Nth_Rest (a, b, c) 3  ==> ()


















































                                       11










          2.2.4.  Comparison Operators

          2.2.4.1.  Is_Null

          Interface:

              function Is_Null (S_Expr_Arg : in S_Expr)
                 return Boolean;


          Description:
               Is_Null returns True if S_Expr_Arg is equal to
               Null_S_Expr.

          Restrictions:
               None.

          Examples:

               Is_Null ()       ==> TRUE
               Is_Null (())     ==> FALSE
               Is_Null a        ==> FALSE
               Is_Null ((), a)  ==> FALSE



          2.2.4.2.  Is_Atomic

          Interface:

              function Is_Atomic (S_Expr_Arg : in S_Expr)
                 return Boolean;


          Description:
               Is_Atomic returns True if S_Expr_Arg is an atomic
               expression.

          Restrictions:
               None.

          Examples:

               Is_Atomic ()       ==> TRUE
               Is_Atomic a        ==> TRUE
               Is_Atomic (())     ==> FALSE
               Is_Atomic ((), a)  ==> FALSE
               Is_Atomic (a, b)   ==> FALSE







                                       12










          2.2.4.3.  Is_Non_Atomic

          Interface:

              function Is_Non_Atomic (S_Expr_Arg : in S_Expr)
                 return Boolean;


          Description:
               Is_Non_Atomic returns True if S_Expr_Arg is a non-
               atomic expression.

          Restrictions:
               None.

          Examples:

               Is_Non_Atomic ()       ==> TRUE
               Is_Non_Atomic a        ==> FALSE
               Is_Non_Atomic (())     ==> TRUE
               Is_Non_Atomic ((), a)  ==> TRUE
               Is_Non_Atomic (a, b)   ==> TRUE



          2.2.4.4.  Is_Variable

          Interface:

              function Is_Variable (S_Expr_Arg : in S_Expr)
                 return Boolean;


          Description:
               Is_Variable returns True if S_Expr_Arg is an atomic
               variable.

          Restrictions:
               None.

          Examples:

               Bind (AV, Create_Atomic_Variable("var1"));
               Is_Variable AV ==> TRUE



          2.2.4.5.  Is_Equal

          Interface:

              function Is_Equal (S_Expr_Arg1, S_Expr_Arg2 : in S_Expr)
                 return Boolean;


                                       13










          Description:
               Is_Equal returns True if S_Expr_Arg1 and S_Expr_Arg2
               are equal. Two atomic expressions are equal if they
               contain equivalent literals or equivalent variables.
               Two non-atomic expressions are equal if each component
               of the expression is equal.

          Restrictions:
               None.

          Examples:

               Is_Equal () ()          ==> TRUE
               Is_Equal a a            ==> TRUE
               Is_Equal a b            ==> FALSE
               Is_Equal a (a)          ==> FALSE
               Is_Equal () (())        ==> FALSE
               Is_Equal (a, b) (a, b)  ==> TRUE





































                                       14










          2.2.5.  Manipulation Routines

          2.2.5.1.  Reverse_S_Expr

          Interface:

              function Reverse_S_Expr (Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Reverse_S_Expr returns a non-atomic expression with the
               top-level components of Non_Atomic_Arg in reverse
               order.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Reverse_S_Expr (a, b, c)       ==> (c, b, a)
               Reverse_S_Expr ((a, b), c, d)  ==> (d, c, (a, b))



          2.2.5.2.  Flatten

          Interface:

              function Flatten (Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Flatten returns a non-atomic expression which has as
               components all atomic components of Non_Atomic_Arg and
               all atomic components of all non-atomic expression
               within Non_Atomic_Arg.  That is, Flatten removes all
               internal parentheses from Non_Atomic_Arg.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Flatten ((a), (b, (c, ((d)), e)))  ==> (a, b, c, d, e)
               Flatten (())  ==> ()




                                       15










          2.2.5.3.  Delete

          Interface:

              function Delete (S_Expr_Arg, Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Delete returns a copy of Non_Atomic_Arg with all top-
               level occurrences of S_Expr_Arg removed.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Delete a (a, b, (a), a, c)  ==> (b, (a), c)
               Delete a (b, b, (a), c, c)  ==> (b, b, (a), c, c)



          2.2.5.4.  Replace

          Interface:

              function Replace (S_Expr_Arg1, S_Expr_Arg2,
                                Non_Atomic_Arg : in S_Expr)
                 return S_Expr;


          Description:
               Replace returns a copy of Non_Atomic_Arg with all top-
               level occurrences of S_Expr_Arg1 replaced by
               S_Expr_Arg2.

          Restrictions:
               Non_Atomic_Arg must be a non-null, non-atomic expres-
               sion.  If not, the exception Atomic_Expression is
               raised.

          Examples:

               Replace a b (a, b, (a), a, c)  ==> (b, b, (a), b, c)
               Replace a b (b, b, (a), c, c)  ==> (b, b, (a), c, c)








                                       16










          2.2.6.  Set Operators

          2.2.6.1.  Is_Member

          Interface:

              function Is_Member (S_Expr_Arg,
                                  Non_Atomic_Arg : in S_Expr)
                 return Boolean;


          Description:
               Is_Member returns True if S_Expr_Arg is a top-level
               component of Non_Atomic_Arg.

          Restrictions:
               Non_Atomic_Arg must be a non-atomic expression.  If
               not, the exception Atomic_Expression is raised.

          Examples:

               Is_Member a (a, b, c)    ==> TRUE
               Is_Member a (b, c, d)    ==> FALSE
               Is_Member a ((a), b, c)  ==> FALSE



          2.2.6.2.  And (Intersection)

          Interface:

              function "And" (Non_Atomic_Arg1,
                              Non_Atomic_Arg2 : in S_Expr)
                 return S_Expr;


          Description:
               "And" returns a non-atomic expression which contains as
               components only those components which are both in
               Non_Atomic_Arg1 AND Non_Atomic_Arg2 with no duplicates.

          Restrictions:
               Non_Atomic_Arg1 and Non_Atomic_Arg2 must both be non-
               atomic expressions.  If not, the exception
               Atomic_Expression is raised.

          Examples:

               (a, b, c) And (a, d, e)     ==> (a)
               (a, b, c) And (a, b, b, e)  ==> (b, a)





                                       17










          2.2.6.3.  Or (Union)

          Interface:

              function "Or" (Non_Atomic_Arg1,
                             Non_Atomic_Arg2 : in S_Expr)
                 return S_Expr;


          Description:
               "Or" returns a non-atomic expression which contains as
               components all components which are either in
               Non_Atomic_Arg1 OR Non_Atomic_Arg2 with no duplicates.

          Restrictions:
               Non_Atomic_Arg1 and Non_Atomic_Arg2 must both be non-
               atomic expressions.  If not, the exception
               Atomic_Expression is raised.

          Examples:

               (a, b, c) Or (a, d, e)     ==> (c, b, e, d, a)
               (a, b, c) Or (a, b, b, e)  ==> (c, e, b, a)



          2.2.6.4.  - (Difference)

          Interface:

              function "-" (Non_Atomic_Arg1,
                            Non_Atomic_Arg2 : in S_Expr)
                 return S_Expr;


          Description:
               "-" returns a non-atomic expression which contains as
               components all those components of Non_Atomic_Arg1
               which are not contained in Non_Atomic_Arg2 with no
               duplicates.

          Restrictions:
               Non_Atomic_Arg1 and Non_Atomic_Arg2 must both be non-
               atomic expressions.  If not, the exception
               Atomic_Expression is raised.

          Examples:

               (a, b, c) - (a, d, e)     ==> (c, b)
               (a, b, c) - (a, b, b, e)  ==> (c)





                                       18










          2.2.6.5.  Xor (Excluded Union)

          Interface:

              function "Xor" (Non_Atomic_Arg1,
                              Non_Atomic_Arg2 : in S_Expr)
                 return S_Expr;


          Description:
               "Xor" returns a non-atomic expression which contains as
               components all those components of Non_Atomic_Arg1
               which are not contained in Non_Atomic_Arg2 and all
               those components of Non_Atomic_Arg2 which are not con-
               tained in Non_Atomic_Arg1 with no duplicates.

          Restrictions:
               Non_Atomic_Arg1 and Non_Atomic_Arg2 must both be non-
               atomic expressions.  If not, the exception
               Atomic_Expression is raised.

          Examples:

               (a, b, c) Xor (a, d, e)     ==> (b, c, d, e)
               (a, b, c) Xor (a, b, b, e)  ==> (c, e)






























                                       19










          2.2.7.  Input/Output Routines

          2.2.7.1.  Get

          Interface:

              procedure Get (Input_File : in File_Type;
                             S_Expr_Result : in out S_Expr);

              procedure Get (S_Expr_Result : in out S_Expr);


          Description:
               Get reads a symbolic expression from either the speci-
               fied or the current default input file.

          Restrictions:
               The following exceptions may be raised based on the
               error in the input:   Extra_Separator,
               Missing_Separator, Invalid_Variable_Name and
               Improper_Input.  The first three are self-explanatory,
               the last is raised upon any error condition not handled
               by the other three.


          2.2.7.2.  Put

          Interface:

              procedure Put (Output_File : in File_Type;
                             S_Expr_Arg : in S_Expr);

              procedure Put (S_Expr_Arg : in S_Expr);


          Description:
               Put writes a symbolic expression to either the speci-
               fied or current default output file.

          Restrictions:
               None.














                                       20










          2.2.8.  Miscellaneous Operators

          2.2.8.1.  Bind

          Interface:

              procedure Bind (Current_Value : in out S_Expr;
                              New_Value : in S_Expr);


          Description:
               Bind assigns the value of New_Value to Current_Value
               freeing the structure originally associated with
               Current_Value in the process.

          Restrictions:
               None.


          2.2.8.2.  Length

          Interface:

              function Length (S_Expr_Arg : in S_Expr)
                 return Natural;


          Description:
               If S_Expr_Arg is an atomic expression, Length returns
               0.  Otherwise, Length returns the number of components
               in S_Expr_Arg.

          Restrictions:
               None.

          Examples:

               Length a          ==> 0
               Length ()         ==> 0
               Length (a, b, c)  ==> 3



          2.2.8.3.  Return_Atomic_Literal

          Interface:

              function Return_Atomic_Literal (Atomic_Arg : in S_Expr)
                 return Atomic_Literal;


          Description:
               Return_Atomic_Literal returns the Atomic_Literal


                                       21










               extracted from the given Atomic_Arg.

          Restrictions:
               Atomic_Arg must be a non-null, atomic expression.  If
               not, the exception Non_Atomic_Expression is raised.
               Atomic_Arg must be a literal.  If not, the exception
               Not_A_Literal is raised.


          2.2.8.4.  Set_Variable_Tag

          Interface:

              procedure Set_Variable_Tag (Atomic_Arg : in S_Expr;
                                          New_Tag : in Natural);


          Description:
               Sets the tag of the given variable to the given number.
               A variable tag is used to rename a variable to make it
               distinct from other variables with the same name.

          Restrictions:
               Atomic_Arg must be a non-null, atomic expression.  If
               not, the exception Non_Atomic_Expression is raised.
               Atomic_Arg must be a variable.  If not, the exception
               Not_A_Variable is raised.

          Examples:

               Bind (AV, Create_Atomic_Variable("var"));
               Put (AV);  ==> var
               Set_Variable_Tag (AV, 1);
               Put (AV);  ==> var1
               Set_Variable_Tag (AV, 0);
               Put (AV);  ==> var



          2.2.8.5.  Return_Variable_Name

          Interface:

              function Return_Variable_Name (Atomic_Arg : in S_Expr)
                 return String;


          Description:
               Returns the name associated with the given variable.

          Restrictions:
               Atomic_Arg must be a non-null, atomic expression.  If
               not, the exception Non_Atomic_Expression is raised.


                                       22










               Atomic_Arg must be a variable.  If not, the exception
               Not_A_Variable is raised.


          2.2.8.6.  Return_Variable_Tag

          Interface:

              function Return_Variable_Tag (Atomic_Arg : in S_Expr)
                 return Natural;


          Description:
               Returns the tag associated with the given variable.

          Restrictions:
               Atomic_Arg must be a non-null, atomic expression.  If
               not, the exception Non_Atomic_Expression is raised.
               Atomic_Arg must be a variable.  If not, the exception
               Not_A_Variable is raised.


          2.2.8.7.  Associate

          Interface:

              function Associate (Key, A_Table : in S_Expr;
                                  Search_Position : Positive:= 1)
                 return S_Expr;


          Description:

               A_Table is of the form:
               ((a11 a12 ... a1n) (a21 a22 ... a2n) ... (am1 am2 ... amn))


               Associate returns the first component of A_Table which
               has a component in the Search_Position-th position
               which Is_Equal to the symbolic expression Key.

          Restrictions:
               A_Table must be a non-null, non-atomic expression.  If
               not, the exception Atomic_Expression is raised.

          Examples:

               Associate a ((a, b), (b, a), (a, d))    ==> (a, b)
               Associate a ((a, b), (b, a), (a, d)) 2  ==> (b, a)
               Associate c ((a, b), (b, a), (a, d))    ==> ()





                                       23










          2.2.8.8.  Associate_All

          Interface:

              function Associate_All (Key, A_Table : in S_Expr;
                                      Search_Position : Positive:= 1)
                 return S_Expr;


          Description:

               A_Table is of the form:
               ((a11 a12 ... a1n) (a21 a22 ... a2n) ... (am1 am2 ... amn))


               Associate_All returns a non-atomic expression which
               contains as components all components of A_Table which
               have a component in the Search_Position-th position
               which Is_Equal to the symbolic expression Key.

          Restrictions:
               A_Table must be a non-null, non-atomic expression.  If
               not, the exception Atomic_Expression is raised.

          Examples:

               Associate_All a ((a, b), (b, a), (a, d))    ==> ((a, b), (a, d))
               Associate_All a ((a, b), (b, a), (a, d)) 2  ==> ((b, a))
               Associate_All c ((a, b), (b, a), (a, d))    ==> ()


























                                       24










          3.  Patterns

          3.1.  Pattern Variables, Patterns and Pattern Matching

          A pattern is a data object derived from symbolic expressions
          which is used primarily in the operation of pattern match-
          ing.  It consists of a pattern template which can be any
          symbolic expression and a variable binding context which is
          a symbolic expression of the form of the A_Table argument to
          the Associate routines described in the Symbolic Expressions
          section.  A pattern which has a null template and null bind-
          ing context is said to be a null pattern.  A constant,
          Null_Pattern, has been defined to represent this pattern.
          Examples of pattern templates:

              ()
              ?x
              a
              (a, b, c)
              (?x, 1983))
              (hit, ?x, ?z)
              ((hit, ?x, ?z), (hurt, ?z))


          Examples of variable binding contexts:

              ()
              ((?x, a))
              ((?x, John), (?z, Joe))


          The primary operation on patterns is pattern matching.  Pat-
          tern matching consists of comparing two patterns to see if
          they are equivalent or can be made equivalent.

          If the original symbolic expressions (from which the two
          patterns being compared were made) contain only atomic
          literals, the pattern matching operation only involves
          determining if the corresponding components in each pattern
          are equal.  If so, the patterns match.

          However, if either of the original symbolic expressions con-
          tain variables, the pattern matching operation is quite dif-
          ferent.  When a variable is encountered in either pattern
          during a matching operation, the corresponding component in
          the other pattern is bound to the variable.  Binding a com-
          ponent, the bound value, to a variable involves placing a
          copy of the bound value in the entry of the variable binding
          context for the variable.

          Once a pattern variable is bound, the bound value is used
          throughout the remainder of the matching process.  Any sub-
          sequent instances of the bound variable are replaced by its


                                       25










          bound value.  If a variable is bound to a literal, the sub-
          sequent instances of the variable are replaced by that
          literal.  If, however, one variable is bound to another, the
          subsequent instances of the first variable are replaced by
          the literal to which the second variable is bound.  If the
          second variable has not been bound yet, subsequent instances
          of the first variable are replaced by the second.  When the
          second variable becomes bound to a literal, all instances of
          both variables will be replaced by the same literal.  If the
          matching process completes with no inconsistent bindings
          (two possible literal values for the same variable) being
          found, the patterns are said to match.

          The following is a list of the available pattern operators.
          The parameters of the subprograms in the examples are
          representations of the variables supplied to the subpro-
          grams, not the parameters themselves.






































                                       26










          3.2.  Patterns Routines

          3.2.1.  Is_Null

          Interface:

              function Is_Null (Pattern_Arg : in Pattern)
                 return Boolean;


          Description:
               Determines if Pattern_Arg is a null pattern.


          3.2.2.  Is_Equal

          Interface:

              function Is_Equal (Pattern1, Pattern2 : in Pattern)
                 return Boolean;


          Description:
               Determines if Pattern1 is equal to Pattern2.  Two pat-
               terns are equal if their instantiated templates match.
               An instantiated template is a symbolic expression in
               which all variables in the template have been replaced
               by the values to which they are bound in variable bind-
               ing context. (See the description for function Instan-
               tiate below.)

          Examples:

               Bind (P1, Create_Pattern ( (?x, b, ?z) ))
               Bind (P2, Create_Pattern ( (?x, b, ?z) ))
               Is_Equal (P1, P2)  ==> TRUE
               Bind (P1, Create_Pattern ( (a, b, c) ))
               Bind (P2, Create_Pattern ( (?x, b, ?z) ))
               Is_Equal (P1, P2)  ==> FALSE
               Bind (P1, Create_Pattern ( (a, b, c) ))
               Bind (P2, Create_Pattern ( (?x, b, ?z),
                                          ((?x, a), (?z, c)) ))
               Is_Equal (P1, P2)  ==> TRUE



          3.2.3.  Create Pattern

          Interface:

              function Create_Pattern (Template : in S_Expr;
                                       Bindings : in S_Expr := Null_S_Expr)
                 return Pattern;


                                       27










          Description:
               Creates a pattern. The first argument represents the
               pattern template while the second forms the variable
               binding context.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ()

               Bind (P, Create_Pattern ( (?x, b, ?z),
                                         ((?x, a), (?z, c)) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ((?x, a), (?z, c))



          3.2.4.  Tag_Variables

          Interface:

              procedure Tag_Variables (Pattern_Arg : in Pattern;
                                       Tag : in Natural);


          Description:
               Tags all variables within Pattern_Arg with the value of
               Tag thus providing a way of making patterns unique.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Tag_Variables (P, 1)
               Get_Template (P) ==> (?x1, b, ?z1)
               Get_Bindings (P) ==> ()

               Bind (P, Create_Pattern ( (?x, b, ?z), ((?x, a), (?z, c)) ))
               Tag_Variables (P, 1)
               Get_Template (P) ==> (?x1, b, ?z1)
               Get_Bindings (P) ==> ((?x1, a), (?z1, c))



          3.2.5.  Get_Template

          Interface:

              function Get_Template (Pattern_Arg : in Pattern)
                 return S_Expr;





                                       28










          Description:
               Returns the symbolic expression representing the pat-
               tern template for Pattern_Arg.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Get_Template (P) ==> (?x, b, ?z)
               Bind (P, Create_Pattern ( (?x, b, ?z), ((?x, a), (?z, c)) ))
               Get_Template (P) ==> (?x, b, ?z)



          3.2.6.  Get_Bindings

          Interface:

              function Get_Bindings (Pattern_Arg : in Pattern)
                 return S_Expr;


          Description:
               Returns the binding context for Pattern_Arg which is an
               S_Expr interpreted as a set of pairs, where each pair
               is an S_Expr whose First component is an atomic S_Expr
               such that Is_Variable is True, and whose Rest component
               is the value bound to the variable.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Get_Bindings (P) ==> ()
               Bind (P, Create_Pattern ( (?x, b, ?z), ((?x, a), (?z, c)) ))
               Get_Bindings (P) ==> ((?x, a), (?z, c))



          3.2.7.  Set_Bindings

          Interface:

              function Set_Bindings (Pattern_Arg : in Pattern;
                                     Bindings : in S_Expr)
                 return Pattern;


          Description:
               Sets the variable binding context for Pattern_Arg to
               Bindings.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))


                                       29










               Get_Bindings (P) ==> ()
               Bind (P, Set_Bindings ( P, ((?x, a), (?z, c)) ))
               Get_Bindings (P) ==> ((?x, a), (?z, c))



          3.2.8.  Instantiate

          Interface:

              function Instantiate (Pattern_Arg : in Pattern)
                 return S_Expr;


          Description:
               Returns the symbolic expression representing the pat-
               tern template for Pattern_Arg with all occurrences of
               variables replaced by the values to which they are
               bound.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Instantiate (P)  ==> (?x, b, ?z)
               Bind (P, Set_Bindings ( P, ((?x, a), (?z, c)) ))
               Instantiate (P)  ==> (a, b, c)



          3.2.9.  Match

          Interface:

              procedure Match (Pattern1, Pattern2 : in out Pattern;
                               Is_Match : out Boolean);


          Description:
               If the patterns associated with Pattern1 and Pattern2
               can be made identical by variable substitution,
               Is_Match will be True and the variable binding contexts
               of Pattern1 and Pattern2 will contain the variable
               bindings; otherwise, the binding contexts will remain
               unchanged and Is_Match will be False.

          Examples:

               Bind (P1, Create_Pattern ( (a, b, c) ))
               Bind (P2, Create_Pattern ( (?x, ?y, ?z) ))
               Match (P1, P2, Is_Match)  ==> Is_Match = TRUE
               Get_Bindings (P1) ==> ()
               Get_Bindings (P2) ==> ((?x, a), (?y, b), (?z, c))
               Instantiate (P1) ==> (a, b, c)


                                       30










               Instantiate (P2) ==> (a, b, c)

               Bind (P1, Create_Pattern ( (?x, b, ?z) ))
               Bind (P2, Create_Pattern ( (a, ?y, b) ))
               Match (P1, P2, Is_Match)  ==> Is_Match = TRUE
               Get_Bindings (P1) ==> ((?x, a), (?z, c))
               Get_Bindings (P2) ==> ((?y, b))
               Instantiate (P1) ==> (a, b, c)
               Instantiate (P2) ==> (a, b, c)

               Bind (P1, Create_Pattern ( (?x, b, c) ))
               Bind (P2, Create_Pattern ( (a, ?y, d) ))
               Match (P1, P2, Is_Match)  ==> Is_Match = FALSE
               Get_Bindings (P1) ==> ()
               Get_Bindings (P2) ==> ()
               Instantiate (P1) ==> (?x, b, c)
               Instantiate (P2) ==> (a, ?y, d)



          3.2.10.  First

          Interface:

              function First (Pattern_Arg : in Pattern)
                 return Pattern;


          Description:
               Returns a pattern consisting of the first component of
               the template of Pattern_Arg along with its full vari-
               able binding context.

          Restrictions:
               The template for Pattern_Arg must be a non-null, non-
               atomic expression.  If not, the exception
               Atomic_Template is raised.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ()
               Bind (P, First (P))
               Get_Template (P) ==> ?x
               Get_Bindings (P) ==> ()

               Bind (P, Create_Pattern ( (?x, b, ?z), ((?x, a), (?z, b)) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ((?x, a), (?z, b))
               Bind (P, First (P))
               Get_Template (P) ==> ?x
               Get_Bindings (P) ==> ((?x, a), (?z, b))


                                       31










          3.2.11.  Rest

          Interface:

              function Rest (Pattern_Arg : in Pattern)
                 return Pattern;


          Description:
               Returns a pattern consisting of the rest component of
               the template of Pattern_Arg along with its full vari-
               able binding context.

          Restrictions:
               The template for Pattern_Arg must be a non-null, non-
               atomic expression.  If not, the exception
               Atomic_Template is raised.

          Examples:

               Bind (P, Create_Pattern ( (?x, b, ?z) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ()
               Bind (P, Rest (P))
               Get_Template (P) ==> (b, ?z)
               Get_Bindings (P) ==> ()

               Bind (P, Create_Pattern ( (?x, b, ?z), ((?x, a), (?z, b)) ))
               Get_Template (P) ==> (?x, b, ?z)
               Get_Bindings (P) ==> ((?x, a), (?z, b))
               Bind (P, Rest (P))
               Get_Template (P) ==> (b, ?z)
               Get_Bindings (P) ==> ((?x, a), (?z, b))



          3.2.12.  Bind

          Interface:

              procedure Bind (Current_Value : in out Pattern;
                              New_Value : in Pattern);


          Description:
               Assignment operation for patterns.


          3.2.13.  Free and Return_And_Free

          Interface:

              procedure Free (Pattern_Arg : in out Pattern);


                                       32










              function Return_And_Free (Pattern_Arg : in Pattern)
                 return Pattern;


          Description:
               Dynamic object deallocation operations for patterns.
               The conventions followed for deallocating symbolic
               expressions should also be followed when using pat-
               terns.


          3.2.14.  Get and Put

          Interface:

              procedure Get (Input_File : in File_Type;
                             Pattern_Result : in out Pattern);
              procedure Get (Pattern_Result : in out Pattern);
              procedure Put (Output_File : in File_Type;
                             Pattern_Arg : in Pattern);
              procedure Put (Pattern_Arg : in Pattern);


          Description:
               Input/output operations for patterns.  Get reads a pat-
               tern template (from the given input file or the current
               default input file) and creates a pattern with the tem-
               plate and a null binding context.  Put prints the
               instantiated pattern template for the given pattern to
               the given output file or the current default output
               file.
























                                       33










          4.  Rules

          4.1.  Description of Rules

          A rule is a specific type of pattern.  Rules differ from
          general patterns in that a rule's template contains two sym-
          bolic expressions which represent the (possibly null)
          antecedent and (possibly null) consequent of a rule.   The
          variable binding contexts for rules take the same form as
          those for patterns.

          There are four types of rules: facts, queries, rules and the
          null rule.  A fact is a rule with a null antecedent and
          non-null consequent.  A query is a rule with a non-null
          antecedent and null consequent.  A rule has both a non-null
          antecedent and  non-null consequent.  The null rule has both
          a null template and null binding context and is represented
          by a defined constant, Null_Rule.  Examples of rule tem-
          plates:

              ((), ())                       -- null template
              ((), (hurt, ?z))               -- fact
              ((hit, ?x, ?z), ())            -- query
              ((hit, ?x, ?z), (hurt, ?z))    -- rule


          4.2.  Rule Routines

          4.2.1.  Create_Rule

          Interface:

              function Create_Rule (Antecedent,
                                    Consequent,
                                    Bindings : in S_Expr := Null_S_Expr)
                 return Rule;


          Description:
               Creates a rule composed of the given components.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Get_Template (R) ==> ((hit, ?x, ?z), ())
               Get_Bindings (R) ==> ()

               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Get_Template (R) ==> ((), (hurt ?z))
               Get_Bindings (R) ==> ((?z, John))

               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))


                                       34










               Get_Template (R) ==> ((hit, ?x, ?z), (hurt ?z))
               Get_Bindings (R) ==> ((?z, John))



          4.2.2.  Tag_Variables

          Interface:

              procedure Tag_Variables (Rule_Arg : in Rule;
                                       Tag : in Natural);


          Description:
               Tags all variables within Rule_Arg with the value of
               Tag thus providing a way of making rules unique.


          4.2.3.  Antecedent

          Interface:

              function Antecedent (Rule_Arg : in Rule)
                 return Pattern;


          Description:
               Returns the antecedent of the given rule along with the
               complete binding context for the rule.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Bind (P, Antecedent (R))
               Get_Template (P) ==> (hit ?x, ?z)
               Get_Bindings (P) ==> ()

               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Bind (P, Antecedent (R))
               Get_Template (P) ==> ()
               Get_Bindings (P) ==> ((?z, John))

               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))
               Bind (P, Antecedent (R))
               Get_Template (P) ==> (hit, ?x, ?z)
               Get_Bindings (P) ==> ((?z, John))








                                       35










          4.2.4.  Consequent

          Interface:

              function Consequent (Rule_Arg : in Rule)
                 return Pattern;


          Description:
               Returns the consequent of the given rule along with the
               complete binding context for the rule.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Bind (P, Consequent (R))
               Get_Template (P) ==> ()
               Get_Bindings (P) ==> ()

               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Bind (P, Consequent (R))
               Get_Template (P) ==> (hurt ?z)
               Get_Bindings (P) ==> ((?z, John))

               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))
               Bind (P, Consequent (R))
               Get_Template (P) ==> (hurt ?z)
               Get_Bindings (P) ==> ((?z, John))



          4.2.5.  Is_Null

          Interface:

              function Is_Null (Rule_Arg : in Rule)
                 return Boolean;


          Description:
               Determines if Rule_Arg is a null rule.


          4.2.6.  Is_Equal

          Interface:

              function Is_Equal (Rule1, Rule2 : in Pattern)
                 return Boolean;





                                       36










          Description:
               Determines if Rule1 is equal to Rule2.  As in the Pat-
               terns package, two rules are considered equal if their
               instantiated templates are equivalent.


          4.2.7.  Is_Query

          Interface:

              function Is_Query (Rule_Arg : in Rule)
                 return Boolean;


          Description:
               Determines if the given rule is a query.  A query is a
               rule which has a non-null antecedent and null conse-
               quent.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Is_Query (R)  ==>  TRUE
               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Is_Query (R)  ==>  FALSE
               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))
               Is_Query (R)  ==>  FALSE



          4.2.8.  Is_Fact

          Interface:

              function Is_Fact (Rule_Arg : in Rule)
                 return Boolean;


          Description:
               Determines if the given rule is a fact.  A fact is a
               rule which has a null antecedent and non-null conse-
               quent.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Is_Fact (R)  ==>  FALSE
               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Is_Fact (R)  ==>  TRUE
               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))
               Is_Fact (R)  ==>  FALSE


                                       37










          4.2.9.  Is_Rule

              function Is_Rule (Rule_Arg : in Rule)
                 return Boolean;


          Description:
               Determines if the given rule is a general rule.  A gen-
               eral rule is a rule which has a non-null antecedent and
               a non-null consequent.

          Examples:

               Bind (R, Create_Rule ( (hit, ?x, ?z), () ))
               Is_Rule (R)  ==>  FALSE
               Bind (R, Create_Rule ( (), (hurt ?z), ((?z, John)) ))
               Is_Rule (R)  ==>  FALSE
               Bind (R, Create_Rule ( (hit, ?x, ?z), (hurt ?z),
                                      ((?z, John)) ))
               Is_Rule (R)  ==>  TRUE



          4.2.10.  Get_Template

          Interface:

              function Get_Template (Rule_Arg : in Rule)
                 return S_Expr;


          Description:
               Returns the symbolic expression representing the rule
               template for Rule_Arg.


          4.2.11.  Get_Bindings

          Interface:

              function Get_Bindings (Rule_Arg : in Rule)
                 return S_Expr;


          Description:
               Returns the binding context for Rule_Arg which is an
               S_Expr interpreted as a set of pairs, where each pair
               is an S_Expr whose First component is an atomic S_Expr
               such that Is_Variable is True, and whose Rest component
               is the value bound to the variable.





                                       38










          4.2.12.  Set_Bindings

          Interface:

              function Set_Bindings (Rule_Arg : in Rule;
                                     Bindings : in S_Expr)
                 return Rule;


          Description:
               Sets the variable binding context for Rule_Arg to Bind-
               ings.


          4.2.13.  Instantiate

          Interface:

              function Instantiate (Rule_Arg : in Rule)
                 return S_Expr;


          Description:
               Returns the symbolic expression representing the rule
               template for Rule_Arg with all occurrences of variables
               replaced by the values to which they are bound.


          4.2.14.  Match

          Interface:

              procedure Match (Rule1, Rule2 : in out Pattern;
                               Is_Match : out Boolean);


          Description:
               If the patterns associated with Rule1 and Rule2 can be
               made identical by variable substitution, Is_Match will
               be True and the variable binding contexts of Rule1 and
               Rule2 will contain the variable bindings; otherwise,
               the binding contexts will remain unchanged and Is_Match
               will be False.


          4.2.15.  Bind

          Interface:

              procedure Bind (Current_Value : in out Rule;
                              New_Value : in Rule);




                                       39










          Description:
               Assignment operation for rules.


          4.2.16.  Free and Return_And_Free

          Interface:

              procedure Free (Rule_Arg : in out Rule);
              function Return_And_Free (Rule_Arg : in Rule)
                 return Rule;


          Description:
               Dynamic object deallocation operations for rules.  The
               conventions followed for deallocating symbolic expres-
               sions should also be followed when using rules.


          4.2.17.  Get and Put

          Interface:

              procedure Get (Input_File : in File_Type;
                             Rule_Result : in out Rule);
              procedure Get (Rule_Result : in out Rule);
              procedure Put (Output_File : in File_Type;
                             Rule_Arg : in Rule);
              procedure Put (Rule_Arg : in Rule);


          Description:
               Input/output operations for rules.  Get reads a rule
               template from the given file or current default input
               file creating a rule with the read template and a null
               binding context.  Put prints the instantiated rule tem-
               plate to the given file or the current default output
               file.

          Restrictions:
               In the Get routines, the input template must contain
               exactly two components, one for the antecedent, the
               other for the consequent.  If not, the exception
               Invalid_Rule_Format is raised.











                                       40










          5.  Rulebases

          5.1.  Definition of Rulebase

          A rulebase is an indexed collection of rules representing
          facts and general rules.  A rulebase which has no rules is
          said to be null.  A constant, Null_Rulebase, represents the
          null rulebase.   A rulebase template is a symbolic expres-
          sion containing the templates of all rules in the rulebase.
          Examples of rulebase templates:

              (((), ()),
               ((), (hurt, John)),
               ((hit, ?x, ?z), (hurt, ?z))
              )

              (((loves, ?x1, ?y1), (friends, ?x1, ?y1)),
               ((wife, ?x2, ?y2), (loves, ?x2, ?y2)),
               ((), (wife, Mary, John)),
               ((), (loves, Mary, Joe)),
              )


          NOTE: Variable names are global to the entire rulebase.  If
          it is necessary to limit the scope of a variable to a single
          pattern, use the rule function Tag_Variables to make the
          rule unique with respect to other rules in the rulebase
          before adding the rule to the rulebase.

          The three primary operations performed on rulebases are
          assertion (adding a fact or general rule to a rulebase),
          retraction (deleting a fact or general rule from a rulebase)
          and deductive retrieval (examining the rules in a rulebase
          to determine the answer to a supplied query).

          The retrieval operation involves an operation known as back-
          ward chaining.  The antecedent of the supplied query is
          matched against the consequents of the entries in the
          rulebase.  If the entry is is a fact and the match succeeds,
          the instantiated query antecedent is added to the result.
          Otherwise, if the entry is a general rule and the match
          succeeds, the antecedent of the general rule involved in the
          match is recursively passed to another invocation of the
          retrieval operation.  This backward chain continues until a
          fact is found which matches the current query (in which case
          the bindings found during the chaining process are used to
          instantiate the original query which is then added to the
          result) or until a match cannot be found.  The symbolic
          expression containing the instantiated queries is then
          returned.





                                       41










          5.2.  Rulebase Routines

          5.2.1.  Is_Null

          Interface:

              function Is_Null (Rulebase_Arg : in Rulebase)
                 return Boolean;


          Description:
               Determines if the given rulebase is empty (contains no
               rules).


          5.2.2.  Is_Equal

          Interface:

              function Is_Equal (Rulebase1, Rulebase2 : in Rulebase)
                 return Boolean;


          Description:
               Determines if two rulebases are equivalent.   Two rule-
               bases are equivalent if they contain the same set of
               rules.  NOTE:  The rules in the two rulebases do not
               have to be in the same order to be considered
               equivalent.


          5.2.3.  Create_Rulebase

          Interface:

              function Create_Rulebase (Template : in S_Expr)
                 return Rulebase;


          Description:
               Creates a rulebase with a template based on the given
               symbolic expression.


          5.2.4.  Get_Template

          Interface:

              function Get_Template (Rulebase_Arg : in Rulebase)
                 return S_Expr;





                                       42










          Description:
               Returns a symbolic expression representing the template
               for the given rulebase.


          5.2.5.  Assert

          Interface:

              procedure Assert (Rule_Arg : in Rule;
                                Rulebase_Arg : in out Rulebase);


          Description:
               Adds a rule to the specified rulebase.

          Example:

               Bind (RB, Null_Rulebase)
               Get_Template (RB) ==> ()
               Assert ( RB, ((), (wife, Mary, John)) )
               Get_Template (RB) ==> (((), (wife, Mary, John)))
               Assert ( RB, ((wife, ?x2, ?y2), (loves, ?x2, ?y2)) )
               Get_Template (RB) ==> (((), (wife, Mary, John))
                                      ((wife, ?x2, ?y2), (loves, ?x2, ?y2)))



          5.2.6.  Retract

          Interface:

              procedure Retract (Rule_Arg : in Rule;
                                 Rulebase_Arg : in out Rulebase);


          Description:
               Deletes a rule (if it exists) from the specified
               rulebase.

          Example:

               Bind (RB, Null_Rulebase)
               Get_Template (RB) ==> ()
               Assert ( RB, ((), (wife, Mary, John)) )
               Get_Template (RB) ==> (((), (wife, Mary, John)))
               Assert ( RB, ((wife, ?x2, ?y2), (loves, ?x2, ?y2)) )
               Get_Template (RB) ==> (((), (wife, Mary, John))
                                      ((wife, ?x2, ?y2), (loves, ?x2, ?y2)))
               Retract ( RB, ((), (wife, Mary, John)) )
               Get_Template (RB) ==> (((wife, ?x2, ?y2), (loves, ?x2, ?y2)))




                                       43










          5.2.7.  Retrieve

          Interface:

              function Retrieve (Rule_Arg : in Rule;
                                 Rulebase_Arg : in Rulebase)
                 return S_Expr;


          Description:
               Returns a symbolic expression containing instantiated
               versions of the rules which matched the input Rule_Arg.

          Example:

               Create_Rulebase (RB,
                                (
                                 (((loves, ?x1, ?y1), (friends, ?x1, ?y1)),
                                  ((wife, ?x2, ?y2), (loves, ?x2, ?y2)),
                                  ((), (wife, Mary, John)),
                                  ((), (loves, Mary, Joe)),
                                 )
                                ))
               Retrieve (RB, ((friends, Mary, ?x), ()) )  ==>
                  ((friends, Mary, Joe), (friends, Mary, John))



          5.2.8.  And (Intersection), Or (Union), - (Difference) and
          Xor (Excluded Union)

          Interface:

              function "And" (Rulebase1, Rulebase2 : in Rulebase)
                 return Rulebase;
              function "Or"  (Rulebase1, Rulebase2 : in Rulebase)
                 return Rulebase;
              function "-"   (Rulebase1, Rulebase2 : in Rulebase)
                 return Rulebase;
              function "Xor" (Rulebase1, Rulebase2 : in Rulebase)
                 return Rulebase;


          Description:
               These operations treat rulebases as sets returning the
               appropriate combination of rules.


          5.2.9.  Bind

          Interface:

              procedure Bind (Current_Value : in out Rulebase;


                                       44










                              New_Value : in Rulebase);


          Description:
               Assignment operation for rulebases.


          5.2.10.  Free and Return_And_Free

          Interface:

              procedure Free (Rule_Arg : in out Rulebase);
              function Return_And_Free (Rule_Arg : in Rulebase)
                 return Rule;


          Description:
               Dynamic object deallocation operations for rulebases.
               The conventions followed for deallocating symbolic
               expressions should also be followed when using rule-
               bases.


          5.2.11.  Get and Put

          Interface:

              procedure Get (Input_File : in File_Type;
                             Rule_Result : in out Rulebase);
              procedure Get (Rule_Result : in out Rulebase);
              procedure Put (Output_File : in File_Type;
                             Rule_Arg : in Rulebase);
              procedure Put (Rule_Arg : in Rulebase);


          Description:
               Input/output operations for rulebases.   The Get rou-
               tines create a rulebase with a rulebase template based
               upon the symbolic expression read from the given or
               current default input file.  The Put routines print the
               rulebase template for the rulebase out to the given or
               current default output file.













                                       45










          6.  Using the AI Data Types Package

          6.1.  Instantiating the Package

          In order to use the AI Data Types package, it must first be
          instantiated with five parameters.  The first parameter is
          the type which defines the possible values of the atomic
          expressions.  This may be any predefined or user-defined Ada
          type with the exception of limited private and task types.
          Note: The atomic expression type can be defined as a
          discriminated record type to allow the use of different
          types within one symbolic expression.  This user-supplied
          type will be referred to as type Atomic_Literal within the
          package and will be treated as a private type.

          The second parameter, Is_Equal, is a function which defines
          equality between two values of type Atomic_Literal.

          The third parameter, Lookahead, is a character which is used
          to communicate between the input routine provided by the
          user when instantiating the package and the input routine
          used to read the AI data types.  A specific protocol must be
          used when accessing the Lookahead character.

          (1)  The Lookahead character must be the first character
               examinined by any Get routine using it.

          (2)  After reading it, the Lookahead character must be set
               to a blank.

          The fourth parameter, Get, is a function which will allow
          input of type Atomic_Literal to be read from a specified
          input file.  This routine must follow the above protocol
          when accessing the Lookahead character and must stop reading
          input if a non-atomic suffix or separator character and set
          the value of Lookahead with this character.

          The fifth parameter, Put, is a procedure which will accept
          values of type Atomic_Literal and write them to a specified
          output file.

          6.2.  Accessing the Various Packages

          Once the AI Data Types package is instantiated all data
          objects and functions of all packages except the Rulebase
          package are available via a with/use rule for the appropri-
          ate package.  The Rulebase package is a generic package
          requiring two parameters:

          (1)  An enumerated type by which the database may be indexed
               for efficient access.




                                       46










          (2)  A function which accepts a parameter of type Rule and
               returns a unique value of the enumerated type used to
               index the database.




















































                                       47










          7.  The AI Data Types Demonstration

          Because it is helpful to experiment with the functions in
          the AI Data Types package, a demonstration program has been
          provided.  This program effectively tests and demonstrates a
          large number of functions from each of the packages in the
          AI_Data_Types package.  It is hoped that this program will
          help programmers to resolve questions about the facilities
          and become familiar and proficient with the subprograms
          found in these packages.

          7.1.  Compiling the AI Data Types Demonstration   To create
          the AI Data Types Demonstration, five files are needed.
          These are:

             aitypesdemo.ada  -- The demonstration program, AITypesdemo.
             aitypesimp.ada   -- The generic package implementation for
                                 the AI_Data_Types package.
             aitypesspc.ada   -- The generic package specification for
                                 the AI_Data_Types package.
             instimp.ada      -- The package implementation for the
                                 Inst_Facilities package, a collection
                                 of facilities needed to instantiate
                                 the AI_Data_Types package for use by
                                 the demonstration program.
             instspc.ada      -- The package specification for the
                                 Inst_Facilities package.


          Creating the demonstration simply involves compiling the
          files in the following order:

             1. aitypesspc.ada
             2. aitypesimp.ada
             3. instspc.ada
             4. instimp.ada
             5. aitypesdemo.ada


          and then invoking the appropriate object code linker to
          create the executable program, which should be named
          aitypesdemo.

          Upon running the program, the user will be prompted with a
          menu requesting which package of the AI_Data_Types package
          the user would like to demonstrate.  Choosing the appropri-
          ate number will start the demonstration program for that
          package.

          After choosing the AI package to be demonstrated, the names
          of subprograms specific to the current AI package and their
          arguments can be entered at the prompt.  After hitting
          <RETURN>, the given arguments will be processed by the


                                       48










          chosen subprogram and the result displayed on the following
          line.  The user will then be prompted for the next input.

          A few general notes will be helpful here.

          (1)  A list of programs provided by the current AI package
               demonstration can be obtained by entering "help" at the
               prompt.

          (2)  To terminate the current demonstration, enter "quit".
               Upon leaving the current demonstration, the user will
               be asked if another demonstration is desired.  Answer-
               ing "y" will cause the initial menu to be redisplayed,
               answering "n" will terminate the program completely.

          (3)  The names of the subprograms do not have to be in any
               specific case.  Entering the subprogram name in all
               lower-case letters will suffice.

          (4)  The parameters to the subprograms should be separated
               by blanks, no commas are needed or allowed between
               parameters.

          (5)  Extra input on the command line will be ignored.

          (6)  If the program seems to be waiting, chances are that a
               parameter or a closing parenthesis has been omitted.
               Consulting the user's manual will help solve the first
               problem, counting parentheses will help solve the
               second.

          The following sections will describe the specifics of each
          of the AI package demonstrations.

          7.2.  Using the Symbolic Expressions Demonstration   The
          following operations are available for testing in the Sym-
          bolic Expressions demonstration:

          Append         Help           Is_Variable  Prefix         Set_Differ
          Associate      Is_Atomic      Last         Quit           Set_Or
          Associate_All  Is_Equal       Length       Replace        Set_Xor
          First          Is_Non_Atomic  Nth_First    Reverse_S_Expr
          Flatten        Is_Null        Nth_Rest     Set_And


          Please note the difference in names between those facilities
          represented by a single character operator in the User's
          Manual (e.g "&") and the name used for this subprogram in
          the demonstration (e.g Append).  Another point of note is
          that default parameters are not supported in this demonstra-
          tion, all parameters for functions such as Prefix (both sym-
          bolic expressions) and the Associate functions (two symbolic
          expressions and a numeric search position) are required to


                                       49










          be entered by the user.  A helpful starting point for using
          this demonstration would be to enter those examples provided
          in the User's Manual and verifying the result.  The demons-
          tration would take the following form:

                 ...

          -> first (a, b, c)
             a
          -> rest (a, b, c)
             (b, c)
          -> append (a, b) (c, d)
             (a, b, c, d)
          -> prefix (a) (b)
             ((a), b)

                 ...


          7.3.  Using the Patterns Demonstration   The following
          operations are available for testing in the Patterns demons-
          tration:

          Create_Pattern1  Free2          Help          Is_Null2  Set_Bindings1
          Create_Pattern2  Get_Bindings1  Instantiate1  Match     Set_Bindings2
          First1           Get_Bindings2  Instantiate2  Quit      Tag_Variables1
          First2           Get_Template1  Is_Equal      Rest1     Tag_Variables2
          Free1            Get_Template2  Is_Null1      Rest2


          In the patterns demonstration, two patterns are declared.
          These can be operated upon by using the appropriate subpro-
          gram suffixed by the number of the patttern to be manipu-
          lated.  All subprograms suffixed by a "1" operate on pattern
          one, while those suffixed by a "2" operate on pattern two.
          Those subprograms without numeric suffixes (with the excep-
          tion of Help and Quit) are binary operations with operate on
          both patterns (inputs after these subprogram names will be
          ignored).  The best way to start this demonstration is to
          create two patterns and then match them.  The output of the
          match routine will help to show the operation of a number of
          the Patterns subprograms.  The following is an example:

               ...

          -> create_pattern1 (?x, b, ?z)
             (?x, b, ?z)
          -> create_pattern2 (a, ?y, c)
             (a, ?y, c)
          -> match
             Initial Template of Pattern1: (?x, b, ?z)
             Initial Bindings of Pattern1: ()
             Initial Template of Pattern2: (a, ?y, c)


                                       50










             Initial Bindings of Pattern1: ()
             Result of Match:  TRUE
             Final Template of Pattern1:   (?x, b, ?z)
             Final Bindings of Pattern1:   ((?z, c), (?x, a))
             Final Template of Pattern2:   (a, ?y, c)
             Final Bindings of Pattern2:   ((?y, b))
             Instantiation of Pattern1:    (a, b, c)
             Instantiation of Pattern2:    (a, b, c)

               ...


          Please note that a variable binding context cannot be asso-
          ciated with patterns when calling Create_Patterns functions
          in this demonstration.  The bindings can only be set by
          calls to the Set_Bindings functions.

          7.4.  Using the Rules Demonstration   The following opera-
          tions are available for testing in the Rules demonstration:

          Antecedent1   Free1          Help          Is_Null1   Match
          Antecedent2   Free2          Instantiate1  Is_Null2   Quit
          Consequent1   Get_Bindings1  Instantiate2  Is_Query1  Set_Bindings1
          Consequent2   Get_Bindings2  Is_Equal      Is_Query2  Set_Bindings2
          Create_Rule1  Get_Template1  Is_Fact1      Is_Rule1   Tag_Variables1
          Create_Rule2  Get_Template2  Is_Fact2      Is_Rule2   Tag_Variables2


          The Rules demonstration is similar to the Patterns demons-
          tration.  Two rules have been declared and can be operated
          upon by calling the appropriately numbered facilities.  The
          notes regarding the matching process and the association of
          binding lists mentioned for the Patterns demonstration
          applies equally to the Rules demonstration.

          7.5.  Using the Rulebase Demonstration   The following
          operations are available for testing in the Rulebase demons-
          tration:

          Assert1           Get_Template1  Quit       Retract2
          Assert2           Get_Template2  Rb_And     Retrieve1
          Create_Rulebase1  Help           Rb_Differ  Retrieve2
          Create_Rulebase2  Is_Equal       Rb_Or
          Free1             Is_Null1       Rb_Xor
          Free2             Is_Null2       Retract1


          Two rulebases have been declared in the Rulebase demonstra-
          tion and, as in the other demonstrations, can be operated
          upon by calling the appropriately numbered facilities.
          Functions without numeric suffixes (with the exception of
          Help and Quit) are binary operations which operate upon the
          current contents of the two rulebases.  Rulebases may be


                                       51










          constructed by calling the Create_Rulebase routines with a
          rulebase template, by using the Assert routines to incremen-
          tally add facts and rules or by a combination of the two
          methods.  After constructing the appropriate rulebases, the
          rulebases can be queried by calling the appropriate Retrieve
          function with an applicable query.  The following example
          demonstrates the incremental construction of a rulebase and
          the retrieval of the results of a query:

               ...

          -> assert1 ((loves ?x1, ?y1), (friends, ?x1, ?y1))
             (((loves ?x1, ?y1), (friends, ?x1, ?y1)))
          -> assert1 ((wife ?x2, ?y2), (loves, ?x2, ?y2))
             (((loves ?x1, ?y1), (friends, ?x1, ?y1))
              ((wife ?x2, ?y2), (loves, ?x2, ?y2)))
          -> assert1 ((), (wife, Mary, John))
             (((loves ?x1, ?y1), (friends, ?x1, ?y1))
              ((wife ?x2, ?y2), (loves, ?x2, ?y2))
              ((), (wife, Mary, John)))
          -> assert1 ((), (loves, Mary, Joe))
             (((loves ?x1, ?y1), (friends, ?x1, ?y1))
              ((wife ?x2, ?y2), (loves, ?x2, ?y2))
              ((), (wife, Mary, John))
              ((), (loves, Mary, Joe)))
          -> retrieve1 ((friends, Mary, ?x), ())
             ((friends, Mary, Joe),
              (friends, Mary, John))

               ...

























                                       52