back2roots/padua/padua.7z/padua/lang/ops5c.lzh/OPS5c/ops5c.doc

Text File | 1990-05-23 | 114.2 KB | 3,037 lines

                              OPS5c User's Guide

                                Version 1.08a

                        For the Amiga Personal Computer







                             Bernie J. Lofaso, Jr.











































                               Table of Contents

       1.  Introduction.............................................4
         1.1  What is OPS5c?........................................4
         1.2  OPS5 History..........................................4
         1.3  Production Systems Overview...........................5
       2.  Working Memory...........................................9
         2.1  Class Declarations....................................9
         2.2  Working Memory Element Structure......................9
         2.3  Vector Attributes....................................10
       3.  Rules...................................................12
         3.1  Rule Structure.......................................12
       4.  The LHS.................................................13
         4.1  Condition Elements...................................13
         4.2  Variables............................................13
         4.3  Quoting..............................................13
         4.4  Predicates...........................................14
         4.5  Conjuctions..........................................14
         4.6  Disjunctions.........................................15
         4.7  Negated Condition Elements...........................15
         4.8  Element Variables....................................16
       5.  The RHS.................................................17
         5.1  Element Designators..................................17
         5.2  RHS Patterns.........................................17
         5.3  Pre-defined Functions................................18
            5.3.1  genatom.........................................18
            5.3.2  litval..........................................18
            5.3.3  substr..........................................18
            5.3.4  compute.........................................18
            5.3.5  accept..........................................19
            5.3.6  acceptline......................................19
         5.4  RHS Actions..........................................19
            5.4.1  make............................................20
            5.4.2  remove..........................................20
            5.4.3  modify..........................................20
            5.4.4  write...........................................21
            5.4.5  bind............................................21
            5.4.6  cbind...........................................21
            5.4.7  call............................................22
            5.4.8  halt............................................22
            5.4.9  openfile........................................22
            5.4.10  closefile......................................22
            5.4.11  default........................................22
       6.  Conflict Resolution.....................................24
       7.  OPS5 Programming........................................26
       8.  Top Level Commands......................................29
         8.1  include..............................................29
         8.2  run..................................................30
         8.4  ppwm.................................................30
         8.5  wm...................................................30
         8.6  cs...................................................31
         8.7  strategy.............................................31
         8.8  pbreak...............................................31
         8.9  dump.................................................31












         8.8  size.................................................31
       9.  The OPS5c System........................................32
         9.1  Installing OPS5c.....................................32
         9.2  Differences from OPS5................................32
         9.3  Compiler Switches....................................34
         9.4  Run-Time Switches....................................35
         9.5  Interfacing With External Code.......................35
            9.5.1  Data Types......................................36
            9.5.2  The Result Element..............................37
            9.5.3  Interning and String Spaces.....................37
            9.5.4  Functions Versus Actions........................39
       10. References..............................................40

       Appendix A - Dollar Library Description.....................41
       Appendix B - String Library Description.....................44

       Index.......................................................45














































       OPS5c User's Guide


       1.  Introduction

       1.1  What is OPS5c?

            OPS5c is a  compiled  version  of  the  OPS5  expert  system
       language originally developed at Carnegie-Mellon University.   It
       belongs to a class of languages which are referred  to  as  rule-
       based (or production-based) expert  systems.   In  such  systems,
       knowledge  is  expressed  as  a  set  of   rules   (also   called
       productions).   These   rules are meant to express some deductive
       statements which may be used as applicable in solving  a  problem
       requiring an expert level of  performance.   If  you  have  never
       programmed in a rule-based language, expect  to  spend  a  little
       time  "getting  up  to  speed".   The   methodologies   used   in
       programming  such  systems  are   considerably   different   from
       programming in conventional programming languages.   This  manual
       should serve as a brief overview of the operation  of  production
       systems (PS's) in general and the OPS5c programming  language  in
       particular.  There are several good texts that you  may  want  to
       consult  in  order  to  get  better  acquainted  with  production
       systems and several are specific to the OPS5 language.


       1.2  OPS5 History

            OPS5  is  part  of  a  family  of  languages  developed   at
       Carnegie-Mellon University  by  Charles  Forgy,  John  McDermott,
       Allen  Newell,  and  Michael  Rychener  in  the  mid-70's.    The
       inference engine used by  OPS5  is  based  on  the  RETE  pattern
       matching algorithm developed  by  Charles  Forgy.   The  original
       systems were written in Lisp.  They read in OPS5 source code  and
       produced  an  intermediate  pseudo-code  which  could   then   be
       interpreted by the OPS5  inference  engine.   Much  of  the  OPS5
       language semantics indicate the underlying Lisp language used  in
       coding the first system.  Another version of OPS5 was written  in
       a language called BLISS.   The  BLISS  system  runs  considerably
       faster  than  the  original  interpreted  Lisp   but   had   some
       limitations  not  present  in  the  Lisp  version.   More  recent
       versions have been written in Common Lisp which  run  many  times
       faster than the original Lisp version, partially  due  to  better
       Lisp coding and probably to some extent due  to  greater  variety
       and power of the  data  structures  and  functions  available  in
       Common Lisp.  The most recent version  of  OPS5  from  CMU  is  a
       system called ParaOps which  compiles  OPS5  source  directly  to
       machine language.  While being considerably faster than  previous
       OPS5 versions the ParaOps system is very machine specific  as  it
       produces assembly language as its output.
            The OPS5c system was designed to accept a language as  close
       to the OPS5 language definition as possible.  As with  the  BLISS
       version of OPS5, some language  features  were  not  implemented.
       OPS5c  is,  however,  approximately  98%  true  to  the  language
       definition and the features missing are not likely to  be  missed
       by most OPS5 programmers.  Unlike previous  systems,  OPS5c  uses
       the  TREAT pattern matching algorithm  developed  by  Dr.  D.  P.


                                     - 4 -






                                                      OPS5c User's Guide


       Miranker.  In general, the TREAT algorithm has shown  to  be  the
       superior algorithm in most cases.  The OPS5c  compiler  takes  as
       input  an  OPS5  source  program  and  produces  code  in  the  C
       programming language as output.  This code is then  compiled  and
       linked with a run-time library module to  produce  an  executable
       of the OPS5 program.  The main emphasis of this  system,  besides
       OPS5 source code  compatibility,  is  speed.   Whenever  a  speed
       versus space trade-off was encountered during system design,  the
       option  producing  the  fastest  execution  was   almost   always
       selected (within reason of course).  A limited amount of  testing
       on small programs done in December 1988  showed  that  the  OPS5c
       system showed a 30-120% speed  advantage  on  benchmark  programs
       over the then fastest known OPS5 system.   Additional  speed  and
       space  improvements have been  made  to  the  system  since  that
       preliminary testing occurred.  Additional benefits of  OPS5c  are
       that it may be interfaced with other languages  (primarily  C  at
       the moment).  The main disadvantage to OPS5c  is  that  it  often
       produces large executables.  It is not recommended  for  machines
       with less than 1 Meg. of RAM unless only small rule  systems  are
       used.


       1.3  Production Systems Overview

            In   describing   production   systems   in   general,   the
       descriptions will be of systems which have architectures  similar
       to OPS5.  OPS5 terminology will be used as much  as  possible  so
       that  any  reference  to  external   materials   will   be   more
       understandable to the reader.
            As previously mentioned, production  systems  consist  of  a
       set of rules, each of which consists of  two  parts.   These  are
       the antecedent, more commonly known as the left-hand side  (LHS),
       and the consequent, more commonly known as  the  right-hand  side
       (RHS).  The LHS can be thought  of  as  a  series  of  conditions
       which when all are true simultaneously, make  the  rule  eligible
       to "fire".  A rule may fire  when  all  its  LHS  parts,  called
       condition  elements  (CEs), are true and it has been selected  as
       the correct rule to fire.  In  firing,  the  rule  instructs  the
       system to perform one or more actions as indicated  by  the  RHS.
       The determination of when a rule may fire as well as what  effect
       it's actions have when  it  does  fire  is  dictated  by  working
       memory (WM).
            Working  memory is  best  thought  of  as  a  set  of  facts
       maintained by OPS5.   These  facts  take  the  form  of  discrete
       records  similar  to  structs  in  the  C  language.   Each  such
       structure belongs to a  'class'.  Each class may have attributes,
       which act as data slots, defined for it.  Declarations  of  valid
       classes and their attributes must precede the  rules  definitions
       in the OPS5 source file.  A typical declaration might be:

            (literalize person name age height weight)

       We  could  then  begin  creating  instances  of  this  class   to
       represent individual  facts.   Even  with  only  one  such  class


                                     - 5 -






       OPS5c User's Guide


       definition we might want to represent a set of facts such as:

            (person ^name John ^age 23 ^height 69 ^weight 165)
            (person ^name Mary ^age 18 ^height 62)
            (person ^name Mark ^age 18)

       Each such instance is called a  working memory element (WME).  It
       is these elements which are matched against the patterns  of  the
       LHS of each rule.  When a rule is fired, statements  in  the  RHS
       may add to, remove  from,  or  modify  the  contents  of  working
       memory.
            In general, a production system executes a cycle of  phases.
       The phases of  a  PS  cycle  are  MATCH, CONFLICT RESOLUTION, and
       ACT.  The MATCH and ACT phases we have mentioned  earlier.   They
       corresponding to matching patterns of the LHS to  working  memory
       elements and performing the actions of the RHS  when  a  rule  is
       selected to fire.  The intermediate phase,  CONFLICT  RESOLUTION,
       determines how a rule is selected amongst many possibilities  for
       firing.  After the system has performed MATCH  against  the  LHSs
       of all rules, there may either be more than one rule which has  a
       LHS match or a rule could have one or more ways  of  producing  a
       match.  The first case should be very obvious.  It  simply  means
       that the facts supporting more than one rule  firing  exist.   It
       is up to CONFLICT RESOLUTION to decide which rule  will  fire  on
       the current cycle.  In the second case, we may  find  that  there
       exists more than one way of matching WMEs to the LHS  of  one  or
       more rules.  As an example, given the three WMEs above,  the  LHS
       of a rule such as

            (person ^age > 20)
            (person ^age < 20)

       could be matched in two ways.  We  can  form  a  pair  using  the
       first and second WMEs or we can form a pair using the  first  and
       third WMEs.  Each combination of valid mapping  of  WMEs  to  the
       CEs of a rule constitutes what is called an  instance.  OPS5 will
       calculate all the instances it can,  then  select  one  instance,
       and hence the rule  that  it  corresponds  to,  to  fire  on  the
       current cycle.  As we shall later see, instances may be  created,
       but are never guaranteed to be selected to be fired.  Other  more
       appropriate instances may be created during the  MATCH  phase  or
       it is possible for instances to be destroyed.  At any  moment  in
       time, if  we  were  to  stop  the  system  and  examine  all  the
       instances we would  refer  to  this  set  of  instances  as  the
       conflict  set.   The  CONFLICT  RESOLUTION  phase  examines   the
       conflict set after completing the matching of WMEs added  to  the
       system in the ACT phase of the previous  cycle.   Note  that  the
       MATCH phase performs an  incremental  matching.   It  needs  only
       perform matching  for  newly  added  WMEs  since  the  result  of
       matching produces  instances  and  all  instances  produced  from
       previously added WMEs have already been calculated  and  retained
       in the conflict set.
            The cycle that  we  have  just  described  is  initiated  by
       adding WMEs to working memory, thus causing  matching  with  LHSs


                                     - 6 -






                                                      OPS5c User's Guide


       of the rules in the system.  The cycle will continue until  there
       are no more instances in the conflict set,  hence  no  rules  can
       fire,  or  a  rule  fires  which  contains   an   explicit   halt
       instruction in its RHS.  Hopefully in either case the system  has
       arrived at a solution to the problem at hand.
            It should  be  noted  that  in  our  brief  description  of
       CONFLICT  RESOLUTION, we indicated  that  the  system  selects  a
       specific instance to fire.  We speak of instances  firing  rather
       than rules for several reasons.  First, it is important  to  know
       exactly what WMEs match particular CEs.  This is  because  is  it
       common practice for an action in the RHS of a rule  to  reference
       values in the WMEs which match the LHS CEs.  Thus  we  must  know
       exactly which elements match which  CEs  in  order  to  know  the
       appropriate value to use in the actions.   Second,  we  associate
       an instance with a specific  rule,  so  specifying  the  instance
       specifies the rule implicitly.  As we shall  see  later  when  we
       describe how CONFLICT RESOLUTION is performed, the  set  of  WMEs
       that form a particular instance determines  its  "priority"  that
       is calculated by CONFLICT RESOLUTION.  All instances are  ordered
       by priority at the end of the MATCH phase and the  instance  with
       highest priority is selected to fire.
            Additionally,  we  should   address   the   OPS5c   matching
       algorithm at a slightly higher level of  detail.   These  details
       apply specifically  to  the  TREAT match algorithm used by OPS5c.
       The traditional match  algorithm  for  OPS5  is  the  RETE match.
       Refer  to  [Miranker87]  or   other   reference   materials   for
       additional details on the TREAT and RETE algorithms.   Associated
       with each CE is a data structure called  an  alpha memory (amem).
       Such a structure also exists in the RETE algorithm.   As  we  add
       new WMEs to working memory, we must first decide  which  CEs  the
       new WME might be associated  with  in  the  process  of  creating
       instances.  A WME can be associated with some CE for the  purpose
       of creating an instance only if it passes all the  constant tests
       as well as all  variable binding tests.  Constant tests are those
       whose values are not variables but  either  numeric  or  symbolic
       constants.  Variable tests make  comparisons  relative  to  other
       WMEs bound to CEs in the rule.  While the variable binding  tests
       depend on what WMEs are currently bound to the  other  CEs  in  a
       rule, the constant tests are independent of other WMEs.  Thus  it
       makes sense to perform these tests  only  once  for  each  CE/WME
       combination and if the WME passed the constant tests for the  CE,
       we store the WME in the alpha memory of the CE.  In that  fashion
       we some other WME is added to another CE  of  the  rule,  we  can
       scan  the  alpha  memory  structure  of  each  CE  to  look   for
       candidates for satisfying variable bindings  rather  than  having
       to scan all of working memory.  Usually  a  WME  will  match  the
       constant tests of many CEs and therefore will be stored  in  many
       alpha memories.   We  sometimes  refer  to  the  MATCH  phase  as
       containing  two  sub-phases,  SELECT  and  JOIN (these terms come
       from database terminology).  The SELECT sub-phase corresponds  to
       performing constant tests for a newly added  WME  so  it  can  be
       added to the appropriate  alpha  memories.   The  JOIN  sub-phase
       corresponds to the variable binding tests that are  performed  in
       order to try to create instances to  be  added  to  the  conflict


                                     - 7 -






       OPS5c User's Guide


       set.
            As a recap,  we  may  describe  the  incremental matching as
       such.  When a new WME is matched, we examine all CEs which  refer
       to the same class as the WME being added.  If all constant  tests
       of a particular CE are satisfied by the WME, we add  the  WME  to
       the  alpha  memory of the CE.  At this point we may stop and look
       for  correct  variable  bindings  in  the  rule   that   the   CE
       participates in.  We do this by scanning all the  alpha  memories
       of the other CEs to  find  consistent  variable  bindings.   Note
       that if we find consistent bindings for all CEs of the  rule,  we
       create  an  instance.  Also note that the instance  MUST  contain
       the new WME bound to the CE that we have just added the  WME  to.
       Actually we add to the alpha memory of a  CE,  not  the  CE,  but
       this is mearly terminology and  we  often  use  the  terms  alpha
       memory, amem, and CE to mean the same thing -  namely  a  storage
       structure for WMEs which satisfy the constant tests of the CE.








































                                     - 8 -






                                                      OPS5c User's Guide


       2.  Working Memory

       2.1  Class Declarations

            As mentioned earlier, classes  and  the  attributes they use
       are usually declared before being  used  in  any  rules.   It  is
       usually best to declare all classes and  specify  all  attributes
       to be used with each class although neither  of  these  practices
       are enforced by OPS5.  OPS5 will  allow  the  user  to  reference
       class names that have not  been  defined.   It  will  also  allow
       attributes which were defined in one class to  be  referenced  in
       another class.  This is due to the simplistic symbol  table  kept
       by OPS5 systems.  No record is kept of which classes  declared  a
       particular attribute name.  Unfortunately this "feature"  is  one
       that has been exploited by OPS5 programmers in the past and  thus
       is handled similarly by OPS5c to maintain compatibility.
            Classes  and  their  attributes  are  declared  using  the
       LITERALIZE  statement.   As  seen  in  an  earlier  example,  the
       keyword LITERALIZE is followed by  a  class  name  which  may  be
       followed by zero or more attribute names.   The  entire  declara-
       tion must be enclosed in parentheses.  It is  acceptable  to  use
       the same attribute name in different classes  but  a  class  name
       may appear in only one LITERALIZE statement.


       2.2  Working Memory Element Structure

            A  working  memory  element (WME) consists of a time tag and
       an  array  of  attributes.  The  time  tag  is  a  unique  number
       assigned to each WME at the  time  of  its  creation.   The  more
       recent the WME the larger its time tag will be.  The  time tag is
       used not only as  a  unique  identifier,  but  is  also  the  key
       feature in the algorithms used by CONFLICT RESOLUTION.   In  most
       OPS5 implementations there are 127 attribute "slots"  defined  in
       each WME.  Regardless of the number of attributes defined  for  a
       class, each WME contains room for  127  attribute  values.   When
       the declarations section of an OPS5 program has  been  parsed  by
       an OPS5 interpreter or compiler, it assigns  an  offset  in  this
       array to each of the attribute names  that  have  been  declared.
       The offset  assigned  to  a  particular  attribute  is  the  same
       regardless of the class  (or  classes)  the  attribute  has  been
       declared in.  The  algorithm  must  consider  which  classes  the
       attribute has been declared in so that it  can  assign  a  single
       offset to an attribute name while not assigning the  same  offset
       to attributes which appear in the same class.   Because  of  this
       it is not valid to assume that  the  order  of  attributes  in  a
       class declaration has anything to  do  with  the  assignment  of
       offsets to those attributes.  Assignments may be in  a  different
       order and may not be sequential. While  most  classes  will  have
       offsets not used by any attributes declared in  that  class,  the
       unused offsets may have assigned offsets that are  either  higher
       numbered or lower numbered.   If  a  programmer  chooses  to  use
       attribute names in classes for which they were not declared  when
       writing rules, there is the risk that the offset assigned to  two


                                     - 9 -






       OPS5c User's Guide


       or more attributes used in the  same  class  will  be  the  same.
       This will  usually  cause  over-writing  of  data  and  incorrect
       program behavior.  This is the main reason  that  declaration  of
       all attributes to be used in a class is a recommended practice.
            OPS5 also has a mechanism for  allowing  the  programmer  to
       control the offset assignments to certain  attributes.   This  is
       accomplished with  the  LITERAL statement.  This statement simply
       assigns  offsets  to  attributes  blindly.   An  example  LITERAL
       declaration follows.

            (literal name = 2 age = 4 address = 45)

       Attribute names appearing in a LITERAL statement do not  have  to
       appear in any LITERALIZE, though they may.  Since LITERAL  state-
       ments are processed before LITERALIZEs (although they may  appear
       intermixed in the source code),  the  system  may  find  that  it
       cannot  provide  assignments  for  LITERALIZEs  which  allow   no
       duplicate offsets in a class,  in  which  case  the  system  will
       abort with an error message.
            Attributes in a WME are similar  to  Lisp  atoms.  For those
       not familiar with Lisp, an atom  is  a  structure  with  a  field
       indicating the atom type (symbol, integer, float, etc.)  and  the
       data value.  Because the type is associated with the data  value,
       not with the attribute name or location, we may  assign  a  value
       with one data type (say  an  integer)  to  some  attribute,  then
       reassign  another  value  with  a  different  data  type  (say  a
       string).  Certain functions in the OPS5 language,  namely  calcu-
       lations and relational comparison  predicates, are the only parts
       of the language that operate on specific types.  Attribute  types
       will also be a concern to the programmer who wishes to  interface
       OPS5c programs to external C code.  It should be noted  that  for
       comparison  purposes  symbols (strings) must be identical and are
       case sensitive, i.e. 'dog' is not equal to 'DOG'.  Normally  OPS5
       will consider an integer and floating point value to be equal  if
       their difference, when the integer  is  converted  to  float,  is
       zero.  In OPS5c numeric attributes must be the same  type  to  be
       equal regardless of their values.  By defining  the  preprocessor
       symbol  COERCE  while  compiling  the  C  output  of  the   OPS5c
       compiler, the system will  perform  coercion of incompatible data
       types whenever possible.
            Whenever  a  WME  is  created  and  assigned   values,   the
       attribute positions which are not assigned values explicitly  are
       given  a  value  of  "nil" (a symbolic atom).  Rules may test for
       unassigned attribute values by comparing to  "nil"  in  a  CE  in
       their LHS.


       2.3  Vector Attributes

            Normally we associate a single value  with  each  attribute.
       There are cases where we wish to store a set of values  that  are
       associated with a single attribute name.  OPS5  provides  methods
       for finding the offset of an attribute and referencing  attribute
       slots a certain relative distance past the offset.  Thus  we  can


                                    - 10 -






                                                      OPS5c User's Guide


       say that the set of values associated with some attribute is  all
       values with an offset equal to or greater  than  the  attribute's
       offset.  In order to may sure  that  we  don't  over-write  other
       attribute  slots,  we  may  ensure  that  there  are   no   other
       attributes (at least in a specific  class)  that  has  a  greater
       offset.  This is done by declaring the  "multi-valued"  attribute
       in the class (or  classes)  it  will  be  used  and  additionally
       declaring it as a vector attribute.  One or more  attributes  may
       be declared as  vector  attributes  using  one  or  more  VECTOR-
       ATTRIBUTE statements.  An example would be:

            (vector-attribute classmates teachers)

       It should be noted that only one vector attribute is allowed  per
       class and any attributes declared to be  vector  attributes  will
       be treated as vector attributes in  all  classes  that  they  are
       declared in.
            The user should  be  aware  that  the  OPS5c  implementation
       normally will not treat  all  WMEs  as  being  of  equal  length.
       Instead it sizes each class according to the  maximum  offset  of
       the attributes declared in that class.  If the class  declaration
       contains an attribute that has  been  declared  to  be  a  vector
       attribute, then the class will be sized with the  maximum  number
       of  attributes  that   a   WME   can   contain   (128   in   this
       implementation).  There are ways, however, of  forcing  all  WMEs
       or WMEs of certain classes to be of specific  lengths.   See  the
       discussion of the '-w' compiler or run-time switch.  This  action
       might  be  desirable  (in  fact  necessary  for  correct  program
       execution) if the program being run references  attributes  in  a
       class for which the attribute was not declared.  This  is  a  bad
       programming practice but the above mentioned  override  mechanism
       can compensate.
























                                    - 11 -






       OPS5c User's Guide


       3.  Rules


       3.1  Rule Structure

            Below is a template for the syntactic structure of  an  OPS5
       rule:

            (p rule-name
                 (class-a ^attr-1 value-1 ^attr-2 value-2 ...)
                 (class-b ^attr-x value-x ^attr-y value-y ...)
                 ...
            -->
                 (action-a parameters-for-a)
                 (action-b parameters-for-b)
                 ...
            )

       The  indentation  is  optional  but  is  used  to  emphasize  the
       different parts of a rule.  A more  terse  template  for  a  rule
       might be:

            (p rule-name LHS-CEs --> RHS-actions)

       Rule names may be any string which does not contain any blanks.































                                    - 12 -






                                                      OPS5c User's Guide


       4.  The LHS


       4.1  Condition Elements

            As previously mentioned, the LHS of a rule  is  composed  of
       one  or  more  condition  elements (CEs).  A  CE  is  a  set  of
       attribute-value  pairs.   This  is  usually  an  attribute   name
       followed immediately by a value.  In OPS5 an attribute name in  a
       CE  is  distinguished  from  a  value  by  prefacing   a   string
       (representing a declared attribute  name)  with  a  caret  ('^').
       Spaces between the caret and the attribute name are allowed.   If
       a value is not immediately preceded by an  attribute  name,  then
       the value pertains to the attribute  slot  immediately  following
       the previously  referenced  attribute  slot.   If  there  are  no
       previously referenced attributes then the value pertains  to  the
       first WME attribute, which is always the class name of  the  WME.
       Another alternate method of specifying an attribute  position  is
       to follow the caret with a  numeric  value.   The  numeric  value
       indicates an attribute offset for the WME.


       4.2  Variables

            Instead of specifying an attribute value after an  attribute
       name,  an  attribute  variable may be  specified.   An  attribute
       value is indicated by enclosing  a  string  in  angled  brackets.
       The string  may  not  contain  any  blanks.   An  example  of  an
       attribute variable is <age>.  The first appearance of a  variable
       tells the system to create a variable binding  by  assigning  the
       attribute value of whatever WME is bound to that  CE  during  the
       matching  process  to   the   indicated   variable.    Subsequent
       occurrences of the variable  in  the  rule  will  substitute  the
       variable  value  literally  for  the  variable  occurrence.   The
       variable may appear in subsequent CEs or in actions in the  right
       hand side.


       4.3  Quoting

            Quoting symbols is a method of  using  characters  that  are
       not normally allowed in symbols or have  some  other  meaning  to
       the system.  For example, normally a  string  with  one  or  more
       imbedded spaces would be interpreted by the  system  as  multiple
       symbols rather than a single symbol.  Perhaps we wish to  include
       the  caret  character  as  the  first  character  of  a   symbol.
       Normally the system would interpret any symbol  starting  with  a
       caret to be an attribute name rather than a value.
            One method of quoting which is supported both in  rules  and
       in the entering of commands from the top level  (see  section  8)
       is the use of quote characters  to  surround  the  string  to  be
       treated  as  a  single  symbol.   The  three   quote   characters
       supported are  the  single  quote,  the  double  quote,  and  the
       vertical bar.  Another method of quoting which is only  supported


                                    - 13 -






       OPS5c User's Guide


       in CEs  is  by  using  the  OPS5  quote  operator  which  is  two
       consecutive slashes.  Using this method, a  space  must  separate
       the quote operator and the symbol to be  quoted.   Some  examples
       of quoted symbols are:
            "Hello world!"
            '"hi," she said'
            |That's correct|
            // ^dog


       4.4  Predicates

            Predicates are relational  tests  that  the  user  may  want
       performed between the attributes  of  WMEs  and  the  CE  pattern
       during  matching.   Predicates  are  specified  by  placing   the
       predicate preceding the  test  value  where  one  would  normally
       specify a value to match against.  For example,  if  we  want  to
       test for children under the  age  of  twelve,  we  might  specify
       '^age < 12'  as  our  attribute-value  pair.   We  may  also  use
       variables instead of constants to  test  the  attribute  against,
       thus we could have written '^age < <my-age>'.   Seven  predicates
       are defined, equal '=', not equal '<>', less  than  '<',  greater
       than '>', less than or equal '<=', greater than  or  equal  '>=',
       and same '<=>'.  The same predicate test to see if the  attribute
       and test value have the same type, i.e. if both  are  numeric  or
       both are symbolic.  If the variable has  been  previously  bound,
       i.e. it either appears in some earlier CE or appears  earlier  in
       the current CE, then in the absence of a  predicate,  equivalence
       testing is  performed  with  the  variable  binding  rather  than
       creating a new variable binding.


       4.5  Conjuctions

            We use braces ('{','}') when we wish to indicate that  there
       are several tests that we wish a single attribute value  to  hold
       true for.  For example if we are looking  for  an  age  group  we
       might specify '^age {> 20 < 25}'.  If we also wish  to  bind  the
       attribute value to an unbound variable, we  should  include  that
       variable without specifying a test predicate.   Additionally,  of
       course, the variable should not have appeared in  a  previous  CE
       of that rule (i.e. the variable is unbound).  For example:  '^age
       {<her-age> > 20 < 25}'.
            Another use for braces is as a place holder  in  a  pattern.
       The pattern (cat {} black) will match WMEs of class  'cat'  whose
       second attribute may be anything and  whose  third  attribute  is
       'black'.  Note that when we say second or third attribute we  are
       referring to the offset numbers  assigned  to  attributes.   This
       may  or  may  not  have  anything  to  do  with  the  order  that
       attributes appear in the literalize statements.






                                    - 14 -






                                                      OPS5c User's Guide


       4.6  Disjunctions

            Disjunctions allow the matching of one  of  a  selection  of
       choices.  Disjunctions  are  indicated  by  enclosing  a  set  of
       choices in double angled brackets ('<<','>>').  An example  would
       be the CE
            (cat << black tan yellow >>)
       which would match all WMEs of class 'cat' whose second  attribute
       is either 'black' or 'tan' or 'yellow'.  It should be noted  that
       there  is  an  implicit  quoting  mechanism   in   the   use   of
       disjunctions.  A CE such as
            (cat << black tan <x> >>)
       would specify the literal '<x>' as an  alternate  value  for  the
       second attribute rather than match the  current  binding  of  the
       variable x.  Hence, variables are not  allowed  to  be  bound  or
       tested in a disjunction.


       4.7  Negated Condition Elements

            Condition elements may be negated by placing  a  minus  sign
       before the rest of the CE.  This has the meaning  that  in  order
       for a rule to fire, we must be able to find a  WME  that  matches
       each of the positive CEs and there must not exist any  WMEs  that
       match the negated CEs.  As with positive  CEs,  negated  CEs  may
       contain tests against previously bound variables.  In  order  for
       an instance to be created,  there  must  exist  a  WME  for  each
       positive CE which satisfies all tests whether they are  constants
       tests or variable bindings that  test  values  between  different
       CEs.  When negated  CEs  are  present  in  a  rule  we  have  the
       additional restriction that  for  any  potential  instance  which
       might be created when we consider  only  positive  CEs,  we  must
       also not be able to find any WMEs matching the negated CEs.   Any
       WMEs which match a negated CE  (for  a  particular  instance)  is
       said to "block" the creation  of  that  instance  for  the  rule.
       Since negated CEs may contain variable bindings,  we  must  speak
       of WMEs that match negated CEs  with  respect  to  the  instance.
       The  instance  (considering  positive  CEs  only)   defines   the
       variable bindings which can decide which WMEs do or  don't  match
       negated CEs.  This also implies that variables  cannot  be  bound
       in negated CEs which might  be  intuitively  expected  since  the
       meaning of a  negated  CE  is  that  something  of  this  pattern
       couldn't be found.
            If all  WMEs  which  block  an  instance  are  removed  from
       working memory, and those WMEs which match the positive  elements
       remain, then one or more instances will be formed once  the  last
       blocking WME has been deleted.   (Remember  that  this  does  not
       mean that the instances from this rule will necessarily fire,  it
       just means that its instances are added to the conflict  set  and
       are allowed to compete in the selection of the next  instance  to
       fire.)  Similarly, if a WME is added to  working  memory  and  it
       matches a negated CE  for  some  instance  which  was  previously
       added to the conflict set but not yet fired, that  instance  will
       be removed from the conflict set.  Should the blocking WME  later


                                    - 15 -






       OPS5c User's Guide


       be removed and all the WMEs matching  positive  CEs  remain,  the
       instance will be recreated and added to the conflict  set.   This
       is the only set of circumstances which allows a  unique  instance
       to be created more than once (i.e. it  must  be  blocked  between
       creations).  This may also occur even if the  instance  had  been
       fired.   The  removal  of  the  blocking  WME  might  still  have
       resulted in a second (or subsequent) recreation of the  instance.
       This is usually not a concern but in some  cases  the  programmer
       should take into account that such a situation can occur.
            For convenience, we will use the abbreviations +CE  and  -CE
       to stand for positive condition element  and  negative  condition
       element, respectively.


       4.8  Element Variables

            Just as we might wish  to  bind  an  attribute  value  to  a
       variable for use in RHS actions, we  may  also  wish  to  specify
       that some action be taken with respect  to  the  WME  matching  a
       particular CE of the rule.  We may designate such a  WME  in  one
       of two ways.  The first is simply a reference number,  between  1
       and the maximum number  of  CEs  per  rule  (64  in  the  current
       implementation), which specifies the CEs appearence  position  in
       the LHS.  Another method is by associating a  name  with  certain
       CEs that we may wish to reference.  Such a  name  is  called  an
       element  variable.  This is the preferred method  of  referencing
       WMEs from the RHS since deletion and addition of new CEs  in  the
       rule can cause position shifts which would affect  the  numerical
       element designator, but not an element variable.  We  specify  an
       element variable by placing a variable name  (a  symbol  enclosed
       in angled brackets) either before the CE  or  after  the  CE  and
       enclosing  both  the  variable  and  CE  in  braces.   Below  are
       examples of element variables in the LHS.

            { <THE-CAR> (car ^manufacturer buick ^make <m-name>) }
            { (person ^hobby tennis) <THE-PLAYER> }

       We shall see how to use such references  when  we  discuss  those
       RHS actions that operate on WME references.

















                                    - 16 -






                                                      OPS5c User's Guide


       5.  The RHS


       5.1  Element Designators

            Some RHS actions require an  element designator to specify a
       particular WME of the instance being fired that the action is  to
       be  performed  on.   There  are   two   ways   of   making   this
       specification - an element variable, or a  numeric  offset.   The
       element variable specification is  simply  the  element  variable
       name  (with  enclosing  angled  brackets).   The  numeric  offset
       specification indicates the number of the WME  appearing  in  the
       instance.  Note that these numbers start at one and  -CEs are not
       counted.  Thus if a LHS has a +CE followed by a -CE  followed  by
       another +CE, the numeric  element  designator  for  the  last  CE
       would be two.


       5.2  RHS Patterns

            Patterns in the RHS are similar in form to those of the  LHS
       but have a somewhat different meaning.  RHS patterns  consist  of
       constants,  variables,  attribute  names,  the   quote   operator
       ('//'), and function  calls.   Unlike  LHS  patterns,  which  are
       evaluated at compile time, the evaluation of RHS patterns  occurs
       at run time.  The evaluation of RHS patterns has  the  effect  of
       altering a global buffer  area  called  the  result element.  The
       result  element  (RE) is simply an array of attributes.  One  can
       think of it as a  global  WME  which  is  not  actually  part  of
       working memory.  Associated with the RE is a pointer which  keeps
       track of the current position in the buffer.  Terms  in  the  RHS
       pattern  which  evaluate  to  attribute  references  (names   and
       attribute offsets) have the effect  of  moving  the  RE  pointer,
       while terms which evaluate to values are placed in the  locations
       indicated by the RE pointer.  When multiple values are placed  in
       the  RE  without  an  intervening  attribute   name   or   offset
       reference,  the  values  are  placed  in  consecutive   locations
       starting at the location indicated by the RE pointer.  Each  time
       a different pattern is evaluated, the result  element  is  filled
       with  the  atom  special  'nil' prior to evaluation.  As we shall
       see later, the RE is used not only for  pattern  evaluation,  but
       for argument passing and  value  reception  with  external  user-
       defined functions and actions.
            All RHS actions consist of an action keyword, followed by  a
       pattern.  The pattern is evaluated  and  the  resulting  list  of
       instantiated  values  is  used  as  arguments  for  the   action.
       Pattern instantiation is quite similar to that in  the  LHS  with
       the  effects  of  constants,  attribute  names,  and  the   quote
       operator being identical.  With the exception  of  the  BIND  and
       CBIND actions, variables in RHS patterns are not bound,  but  are
       mearly instantiated.  Functions do not  exist  in  LHS  patterns.
       In RHS patterns they are indicated by enclosing a list of one  or
       more terms  in  parentheses.   The  term  following  the  opening
       parenthesis must be a constant specifying the  function  name  to


                                    - 17 -






       OPS5c User's Guide


       be called.  The remainder of the list is evaluated and passed  to
       the function  as  arguments.   Function  arguments  may  only  be
       constants or variables, thus no nesting of function calls may  be
       used.  Refer to  section  5.3  for  a  discussion  of  predefined
       functions and to section 9.5 for  a  discussion  of  user-defined
       functions.
            Another difference between LHS patterns and RHS patterns  is
       the  use  of  variable  attribute  names.   The  term  '^<aname>'
       appearing in the RHS would be interpreted as the  attribute  name
       or offset number specified in the variable 'aname'.  This  syntax
       is not allowed in LHS patterns.


       5.3  Pre-defined Functions

            All RHS functions return one or more values  at  consecutive
       locations in the result element.  The values  returned  start  at
       the current position in the result element.

       5.3.1  genatom

            The genatom function is used to generate a  unique  symbolic
       value.  This value is placed  at  the  current  position  in  the
       result element.


       5.3.2  litval

            This function  takes  a  single  symbol  or  variable  which
       represents an attribute name.  It returns the offset assigned  to
       it in all WMEs.  If the  symbol  or  variable  value  is  not  an
       attribute name, then the function returns zero.


       5.3.3  substr

            This function extracts a sequence  of  one  or  more  values
       from a WME and places them in  sequential  locations  in  the  RE
       starting at the current position.   The  first  argument  to  the
       function is the element designator which  indicates  the  WME  to
       extract from.  The second and third arguments indicate  attribute
       offsets which specify the range of attribute values  to  copy  to
       the  RE.  Either of these two arguments may be  specified  as  an
       integer, an attribute name (which is converted  to  its  assigned
       offset), or a variable that is bound to an integer  or  attribute
       name.  The order of the range specification  arguments  does  not
       matter.


       5.3.4  compute

            This function  evaluates  arithmetic  expressions.   Expres-
       sions may contain the operators '+',  '-',  '*',  '//', and '\\'.
       The latter two are used for division and modulus.   Operands  may


                                    - 18 -






                                                      OPS5c User's Guide


       be numeric constants or variables bound to numeric values.   Note
       that  compute  has  no  operator  precedence  and  operators  are
       evaluated from right to left (not left  to  right  as  one  might
       expect).  This may be overriden by the use of parentheses.


       5.3.5  accept

            This function reads input from some input stream.  An  input
       stream is usually keyboard input typed by the user,  or  a  file.
       If called without arguments, accept reads input from the  current
       default  input  stream.   A  single  optional  argument  may   be
       supplied which indicates an alternate input stream to read  from.
       The optional argument must be  either  a  symbol  or  a  variable
       bound to a  symbolic  value.   This  string  indicates  the  file
       handle of the input stream (see section 5.4 for  descriptions  of
       accessing file streams using RHS actions or top level commands).
            If the input begins with an open parenthesis,  then  a  list
       of values will be read and placed at sequential locations in  the
       RE starting at the current  position.   Input  is  read  until  a
       closing parenthesis is found.  If  the  first  character  of  the
       input is not an open parenthesis, then a single  input  value  is
       read into the RE.
            If the input function tries to read past the end of a  file,
       then the atom 'end-of-file' is the value returned.


       5.3.6  acceptline

            This function also reads input from a  stream,  but  differs
       from the accept function in that it reads  exactly  one  line  of
       input, strips out all parentheses, and  then  places  the  values
       read into the RE.  Parameters are optional.   If  any  parameters
       are supplied, they are used to specify the  input  stream  and/or
       affect the behavior of the function when there are no  values  in
       the line input or an end of file condition exists.  If the  first
       parameter evaluates to a symbol associated with an input  stream,
       then that parameter acts as a specification of the  input  stream
       to read from.  If the first parameter is not associated  with  an
       input  stream,  then  it  is  treated  the  same  as   subsequent
       parameters.   The  remaining  parameters,  if  present,  will  be
       placed in the RE if an empty input line is read.


       5.4  RHS Actions

            The actions supported in  the  RHS  for  OPS5c  are  'make',
       'remove', 'modify', 'write',  'bind',  'cbind',  'call',  'halt',
       'openfile', 'closefile',  and  'default'.   These  are  the  same
       actions supported by  OPS5  except  that  OPS5  also  supports  a
       'build' command that may be used to dynamically add rules to  the
       system at run-time.  This is not supported in the OPS5c  compiled
       environment.



                                    - 19 -






       OPS5c User's Guide



       5.4.1  make

            The make command is used to create new WMEs to be  added  to
       WM during the  MATCH  phase  of  the  next  cycle.   The  pattern
       following the make keyword is  instantiated  and  a  new  WME  is
       created.  Minimally a class  name  must  be  given  and  optional
       attribute-value pairs or simply  values  may  be  supplied.   For
       example, the action:

            (make person ^name Cindy ^age 25)

       creates a new WME for the class person with the value 'Cindy'  in
       the attribute slot for 'name' and the value 25 in  the  attribute
       slot for age.   Similarly  to  patterns  appearing  in  the  LHS,
       attribute names  may  be  omitted  and  values  are  assigned  to
       sequential slot offsets after the last referenced offset.


       5.4.2  remove

            The remove action indicates one  or  more  WME  elements  to
       remove.   These  WMEs  are  indicates  by  a  list   of   element
       designators, which as previously mentioned can consist of  either
       a numeric CE offset (starting at 1) or an element  variable  name
       (including the angled brackets surrounding  the  variable  name).
       It is not an error to remove the  same  CE  twice,  but  removals
       after the first are ignored.


       5.4.3  modify

            The modify action can be thought of as a make followed by  a
       remove.  The first parameter to modify must be a  single  element
       designator.  This copies the WME specified to  a  temporary  work
       buffer where the remaining pattern elements  are  interpreted  as
       attribute-value pairs that alter the buffer  before  executing  a
       make command using the  buffer  values.   Once  a  WME  has  been
       modified, the old WME is removed.   Since  multiple  removes  are
       allowed without ill side effects, and removes  are  not  actually
       processed until  the  RHS  actions  have  been  executed,  it  is
       possible to have multiple modifications of a  single  WME  create
       several new WMEs.  For example, a rule such as:

            (p split-path
                 { <SEGMENT> (segment ^start <s> ^end <e>) }
                 (new-point ^value <p>)
            -->
                 (modify <SEGMENT> ^end <p>)
                 (modify <SEGMENT> ^start <p>)
            )

       could be used to make two line segments from one by adding a  new
       point in between the lines current start and end points.   Either


                                    - 20 -






                                                      OPS5c User's Guide


       modify command will operate using the original  contents  of  the
       WME bound to <SEGMENT> and the <SEGMENT> WME will be  removed  at
       the end of the ACT phase.


       5.4.4  write

            The write function  evaluates  a  pattern  and  writes  this
       output to an output stream.  If the first argument to write is  a
       symbol (or variable with a symbolic  value)  that  is  associated
       with an output file handle, then the first argument  acts  as  an
       output stream specifier, otherwise the first argument is  treated
       the same as the rest of the arguments.  Each  evaluated  argument
       is written  to  the  output  stream.   There  are  three  special
       "functions" which can modify the  action  of  write.   These  are
       'tabto',  'rjust',  and  'crlf'.  The  tabto  function  takes one
       argument  which  must  evaluate  to  a  numeric  quantity.   This
       quantity is the column number that the output cursor is  advanced
       to by printing space characters.  If the current output  line  is
       already  past  the  column  number  specified,  then  a   newline
       character is sent first.  The rjust function also takes a  single
       numeric parameter.  This indicates  a  field  width.   The  value
       following the rjust function will be  printed,  right  justified,
       in a field whose width is x characters, where x is the  value  of
       the numeric parameter.  The crlf  function  takes  no  arguments.
       It sends a newline character to the output stream.   These  three
       special functions are not really functions  at  all.   They  only
       have meaning with  the  write  action  and  are  referred  to  as
       functions because they follow function call syntax.  Example:

            (write (crlf) "The age of" <name> "is" <age> (crlf))

       It should be noted that printing of subsequent values always  has
       a space between the values.  Thus (write "hello" !) will  produce
       the output 'hello !', not 'hello!'.


       5.4.5  bind

            The bind action is used to bind a functions return value  to
       a variable.  Example:
            (bind <x> (compute <x> * 2))


       5.4.6  cbind

            The cbind action is used to bind an element variable to  the
       last element that was added to working memory.  The  addition  is
       usually due to a previous make or modify action, though WMEs  may
       be added by calling external functions.  The cbind  action  takes
       a single argument, the variable to be bound to.





                                    - 21 -






       OPS5c User's Guide


       5.4.7  call

            The call action is used to  invole  a  user-defined  action.
       The first parameter to call is the  name  of  the  user  routine.
       The  remaining  parameters  are  pattern   elements   which   are
       evaluated before being  passed  as  parameters  to  the  routine.
       Section 9.5 and the Appendicies describe interfacing  with  user-
       written C routines and library routines that may be  called  from
       these  routines.   Names  of  user-defined  routines  should   be
       declared  (with  class  declarations)  by  using   the   external
       declaration.  Example:
            /* In declaration section */
            (external DrawLine)
            ...
            /* Some rule RHS */
            (call DrawLine <x> <y>)


       5.4.8  halt

            The halt action terminates  program  execution  irregardless
       of the state of working memory or the conflict set.


       5.4.9  openfile

            The openfile action opens a file for reading or writing  and
       assigns a file handle to a symbol for future  reference  to  that
       file.  The first parameter supplied to openfile is  the  name  to
       be used as a file handle in subsequent  references.   The  second
       parameter is the file name,  usually  in  quotation  marks.   The
       third and final parameter is one of two keywords, either 'in'  or
       'out'.  These indicate if the file is being  opened  in  read  or
       write mode, respectively.


       5.4.10  closefile

            The closefile action  is  used  to  close  files  previously
       opened with the openfile action.  It takes the file's  handle  as
       a single argument.

       5.4.11  default

            The default action determines where various  output  streams
       created by OPS5c are directed or where the input stream  is  read
       from.  The three streams used by OPS5c are 'trace', 'write',  and
       'accept'.  The  trace stream is where any trace information, such
       as which rule fired on each cycle, is directed.   Various  levels
       of trace information, including  no  trace  information,  can  be
       provided as the system executes.  See the description of the  top
       level 'watch' command in  section  8  for  information  on  trace
       levels.   The  write stream is where output from the write action
       is  directed.   The   accept stream is the input stream where the


                                    - 22 -






                                                      OPS5c User's Guide


       accept and acceptline functions read  input  from.   One  of  the
       more common uses of default is to redirect trace  information  to
       a file.
            The default action takes two parameters, a file  handle  and
       a stream designator which must be one  of  'trace',  'write',  or
       'accept'.  Example:

            (openfile trace-output "foobar.trace" out)
            (default trace-output trace)
            /* run program */
            (closefile trace-output)













































                                    - 23 -






       OPS5c User's Guide


       6.  Conflict Resolution

            The  purpose  of   conflict  resolution  is  to  choose  one
       instantiation from the conflict set  which  is  to  fire  on  the
       current  cycle.   There  are  many  criterion  which  may   drive
       conflict resolution in a system like  OPS5,  but  the  two  major
       driving  forces  in  OPS5  conflict  resolution  strategies  are
       recency  and  specificity.  These are discussed  in  more  detail
       below.
            The conflict set  may  be  viewed  as  a  list  of  possible
       assertions that may be made on  a  particular  cycle.   A  single
       instance  can  be  thought  of  as  a  set  of  facts   and   the
       justification (rule) which allows new facts to be  asserted  (the
       RHS actions).  Once a  particular  instance has been selected for
       firing by conflict resolution, we must remove that instance  from
       the  conflict  set, otherwise it  may  fire  again  and  cause  a
       condition known as trivial cycling  where  the  same  rule  fires
       repeatedly.
            When a new assertion has been made, say adding a new WME  to
       the working memory, it is  frequently  the  case  that  this  new
       element will be the basis for further inferences.   Most  systems
       will have a large search  space  of  possible  solutions  to  the
       problem being solved and the most common system  behavior  is  to
       find one of many possible solutions rather  than  all  solutions.
       this implies that in scanning parts of  the  solution  space,  we
       wish to traverse the tree of selection possibilities in a  depth-
       first fashion as opposed to a  breadth-first  fashion.   This  is
       done by assuming that given two facts  to  reason  on,  the  most
       recent fact is probably the better one  to  base  assertions  on.
       This heuristic is known as recency and is a strong driving  force
       in the OPS5 conflict resolution strategies.  To support  recency,
       each WME in the system is assigned a time tag.  This is a  unique
       integer number given to the element at the time of its  creation.
       Part of the conflict resolution strategy is to look at  the  time
       tags of all the WMEs that make up each instance,  and  order  the
       instances  according  to  the  recency  of  the  WME   time  tags
       associated with it.
            Another heuristic used in conflict  resolution  is  that  of
       specificity.  Specificity assumes that  if  two  rules  are  very
       similar, but one either contains more condition elements  in  the
       LHS or more tests for the same number of  condition  elements  in
       the LHS, then the rule with more  CEs/tests  must  be  a  special
       case of the other, more general, rule.  Specificity demands  that
       we execute the rule with more CEs/tests first.
            There are two conflict resolution strategies  in  OPS5,  LEX
       and MEA.  They are fairly simple,  with  MEA being a modification
       of LEX.  We shall describe the  LEX strategy first.  The criteria
       for comparing two instances is used to order  the  conflict  set.
       First,  the  time  tags  of  the  positive  CEs  are  ordered  in
       descending  order.   The  first  time  tag  in  each  series   is
       compared.  The instance with the greater tag is the  more  recent
       and is thus preferred over the other one.  If the time  tags  are
       the same, then the second tags in each list are  compared.   This
       continues until a difference in  the  lists  is  noted.   If  the


                                    - 24 -






                                                      OPS5c User's Guide


       lists are of unequal length, then the longer list  is  preferred,
       provided the pair-wise comparisons  of  tags  do  not  favor  the
       shorter list before its elements are  exhausted.   This  provides
       for selection of the more specific rule (the one  with  more  CEs
       has the longer list).  If two lists are the same length and  have
       the same elements, then the number of tests (both constant  tests
       and variable binding tests) are compared and the rule  containing
       the most tests is selected.  This also favors the  more  specific
       rule.  If the  number  of  tests  are  equal  then  an  arbitrary
       selection if made.
            The  MEA strategy has the same rules  as  the  LEX  strategy
       with one change.  We first compare the time tags associated  with
       the first CE of each instance's  rule.   If  that  comparison  is
       equivalent, then  we  order  the  remaining time tags and perform
       the pair-wise comparisons.  This modification exists because  the
       first CE of a rule  is  often  a  context clause which can define
       when a rule is  eligible  to  fire.   More  will  be  said  about
       context clauses in section 7.






































                                    - 25 -






       OPS5c User's Guide


       7.  OPS5 Programming

            This section is not intended to teach you all the tricks  of
       programming in OPS5.  There are books devoted  to  this  subject.
       Instead, this section is intended to give you an overview of  the
       type of  structures  you  can  expect  to  see  in  typical  OPS5
       programs and some of the issues that should be  of  concern  when
       you begin writing your own OPS5 programs.  The novice  programmer
       will find this  section  important  to  understanding  rule-based
       programming in OPS5 while those who have some knowledge  of  OPS5
       will probably already know most of the points outlined here.
            By its  nature,  rule  based  programming  is  data  driven.
       Input data in the form of assertions active certain rules,  which
       may make new assertions activating different rules and so on.   A
       program execution is a constant  cycle  of  modifying  facts  and
       making and retracting assertions via rule firing.  This is  quite
       a bit different from the declarative programming  languages  that
       most  of  use  use  such  as  C,  Fortran,   Pascal,   etc.    In
       conventional languages we specify an algorithm or a  sequence  of
       steps to perform.  We know that A will be done before  B  because
       we have written the program such that the function that  performs
       A will be  called  before  the  function  that  performs  B.   In
       contrast, in a rule based system we  make  statements  that  when
       certain facts hold true, it is appropriate  to  assert  that  the
       addition or deletion of facts in  the  database  are  appropriate
       should a given rule be selected to fire.  Usually we  don't  know
       when a rule will fire, the number of times  it  should  fire,  or
       even if it will fire.  If our logic  manipulating  the  facts  is
       correct then we shouldn't care.
            While  this  seems  like  a  desirable  trait,   there   are
       pitfalls.  First, the methods that we use to solve a problem  can
       almost never be totally data driven.  Each method we use  can  be
       broken up into parts or sections  which  solve  subtasks  of  the
       larger problem.  Many times it is necessary to solve one  subtask
       before  considering  the  solutions  to  other  subtasks.  For an
       efficiency  standpoint  it  is  not  reasonable  to   incur   the
       execution overhead involved in maintaining a state  of  reasoning
       for some rule if we know  that  rule  does  not  pertain  to  the
       current subtask the system is trying to solve.  Not  only  is  it
       inefficient to perform such unnecessary calculation,  it  may  be
       incorrect to do so.  If we have no mechanism to disallow  a  rule
       from firing, it may  activate  and  fire  prematurely  making  an
       incorrect assertion based on incomplete data.   To  prevent  both
       undesirable actions, we  have  certain  implementation  dependent
       rule evaluation procedures and also allow the programmer  to  use
       such features to  control  the  flow  of  the  program  execution
       somewhat.
            We wish  the  system  to  do  the  minimum  amount  of  work
       necessary to correctly match rules that may fire with facts.   It
       should be obvious that if we do not have at  least  one  fact  in
       each alpha memory for the +CEs in a rule, then we  cannot  create
       an instantiation for that rule.  If the rule  does  not  have  at
       least one WME in each of its +CEs, then the  rule  is  considered
       inactive and the only computation  done  is  to  place  new  WMEs


                                    - 26 -






                                                      OPS5c User's Guide


       being added to working memory into the appropriate CEs  for  that
       rule.  We do not attempt to calculate variable  bindings  because
       we know that at least one CE cannot have anything  bound  to  it,
       thus  such  calculations   would   be   useless.    This   simple
       implementation rule allows a programmer to greatly increase  both
       program efficiency as well as control.  This is  accomplished  by
       the  programmer's  use  of  context clauses.  Normally, a context
       clause is a class declared by the programmer which describes  the
       current goal or focus of the program.  Normally such a  class  is
       given a name like 'goal' or 'context'.  Each rule in  the  system
       (or at least most of them) will contain  one  CE  specifying  the
       context in which that rule is eligible to fire.  If  the  context
       is  currently  set  to  something  else,  and  we  have   already
       specified that there is only one context element  in  the  system
       at a time, then the first CE of that rule will  have  nothing  in
       it and we will not attempt variable binding computations for  the
       rule when WMEs are added to the  other  CEs  of  the  rule.   The
       context specifies that the current  goal,  and  nothing  but  the
       current goal, will  be  worked  on  by  the  system.   Rules  not
       pertaining to solving  the  current  goal  are  given  a  minimal
       amount of attention by the system.  Note that when  we  recognize
       that it is appropriate to change the system goal, we must  modify
       the existing goal element.  Frequently, this will cause  a  large
       amount or work to be  done,  because  we  will  destroy  all  the
       instance that the old goal element participated in and there  are
       often many rules that the creation of a  new  goal  element  will
       activate and perform  variable  binding  calculations  for.   For
       this reason, we can see that it  would  be  very  inefficient  to
       code  a  rule  based  program  with  a  large  number  of   rules
       pertaining  to  a  few  goals  and  switch  between   the   goals
       frequently.  Each goal switch could force a large amount of  work
       to be done.
            One trick that is common in  OPS5  programming  pertains  to
       switching  contexts or goals.  Often we  may  desire  to  execute
       some task (a specific goal or context) until  no  more  rules  in
       that context can fire.  Then we wish to change the goal.   To  do
       this we rely on the OPS5 conflict resolution strategy.   Remember
       that in resolving which  instance  is  to  fire  on  the  current
       cycle, we use time ordered tag lists.  If  we  exhaust  one  list
       while doing the comparison between two  lists,  then  the  longer
       list wins.  This is  the  same  as  saying  that  when  comparing
       instances  between  two  rules,   given   identical   time   tags
       participating in both rules, the rule with the most CEs will  win
       the conflict resolution.  We can therefore write rules to  switch
       context by relying on the fact that such a rule will  never  fire
       as long as a more specific rule (one with more CEs) can fire.
            As an example, suppose that some part of our  algorithm  has
       produced a set of guesses, we select one  guess  to  take  action
       on, then we wish to  delete  the  non-selected  guesses,  perhaps
       with the intent of creating a new set later.  We might see  rules
       such as:





                                    - 27 -






       OPS5c User's Guide



            (p remove-guesses
                 (goal ^value delete-guesses)
                 { <THE-GUESS> (guess) }
            -->
                 (remove <THE-GUESS>)
            )

            (p process-guess-start
                 { <THE-GOAL> (goal ^value delete-guesses) }
            -->
                 (modify <THE-GOAL> ^value process-guess)
            )

       We know that although the second  rule  will  be  active  through
       this subtask, it cannot fire unless  the  is  no  possibility  of
       firing the first  rule.   Hence  we  will  achieve  our  goal  of
       deleting the old  guesses  before  moving  on  the  the  task  of
       processing the one selected.





































                                    - 28 -






                                                      OPS5c User's Guide


       8.  Top Level Commands

            Top  level commands are the interpreted  commands  that  the
       user types in.  The top level commands used  in  OPS5c  are  very
       similar to those used in the lisp-based OPS5.  Some commands  are
       unsupported while other commands are added to  OPS5c  to  enhance
       its usability.
            When a user executes  an  OPS5c  program,  a  few  lines  of
       system identification are printed followed  by  the  prompt  'Top
       Level> '.  At this point the user can type any  of  the  commands
       listed in this section.  Minimally, the user  must  do  something
       to initiate processing by the OPS5c system.  Initially  there  is
       no information in the  working  memory.   In  general  there  are
       three ways that a user can initiate program  execution  once  the
       initial top level prompt is given.  He  can  created  WMEs  using
       the  top  level  make command.  He may use the  make  command  to
       create a start symbol.  Or he may use the  include command to add
       many WMEs to working memory.
            The first two methods are the same techniques used in  OPS5.
       If the user knows that certain WMEs need to  be  created  at  the
       start of every run, he can create an  initialization  rule  whose
       RHS makes the  necessary  elements.   The  LHS  of  such  a  rule
       usually depends on the existance of  a  single  element  of  some
       class such as 'start'.   The  last  method  allows  the  user  to
       specify a path name to a file containing make  statements.   This
       file will be interpreted to create the WMEs  needed.   Note  that
       unlike OPS5, the act of making a WME mearly means  that  we  have
       created storage representing the WME  and  correctly  initialized
       the WME's  attribute  values.   The  WME  will  not  actually  be
       inserted into working memory until a cycle is run.  Thus  if  you
       type make commands from the top level prompt, do  not  expect  to
       see any instances  created  or  insertions  into  alpha  memories
       until you have issued  the  run command.  The same effect will be
       noticed  when  using  the  remove command.  Instances that may be
       created as a result of removing a WME will not be observed  until
       one or more cycles of  the  system  are  executed  following  the
       issuing of the remove command.
            Many RHS actions are also supported as  top  level  commands
       with nearly identical syntax.  The main  limitations  imposed  by
       using the top level command  is  that  you  cannot  use  variable
       references, the quote  operator  ('//'), and cannot use functions
       as arguments.  Commands with these characteristics include  make,
       remove,  openfile,  closefile, default, and call.  For the remove
       command, instead of supplying a list of  element  designators  to
       delete, the user supplies a list  of  time  tag  elements  to  be
       deleted.  If called with an asterisk as the  only  argument,  the
       command will delete all of working memory.   The  following  sub-
       sections  describe  the  remaining  top  level  commands.   Those
       specific to OPS5c are indicated as such.


       8.1  include (OPS5c only)

            This command is used to read a  text  file  containing  make


                                    - 29 -






       OPS5c User's Guide


       commands.  Appropriate WMEs are created  but  are  not  added  to
       working memory until at least one cycle has been  run  after  the
       include command.  The include command takes a file  name  as  the
       single parameter.  The file  name  may  be  quoted  using  double
       quotes, single quotes, or vertical bars. Example:
            (include "auto-diagnose.input")


       8.2  run

            This command starts executing the match/resolve/act  cycles.
       Optionally an integer parameter may be given to run  to  indicate
       the maximum number of cycles to run before returning to  the  top
       level.  This is particularly useful for debugging where  you  may
       want to examine the state of the system after  a  certain  number
       of cycles and before the program has completed executing.


       8.3  watch

            This command tells the system how much trace information  to
       print out as the system executes.  Watch takes a  single  numeric
       parameter which must be 0, 1, 2, or 3.  A  watch  level  of  zero
       indicates that no trace information is to be  output.   The  only
       output  from  the  program  will  be  that  generated  by   write
       statements in the RHS of  rules  that  fire  or  from  externally
       called procedures.  The default watch level of one will  print  a
       cycle number, rule number, rule name and time tag list  for  each
       instance that is fired.  A watch level  two  provides  the  watch
       level one information in  addition  to  indicating  when  working
       memory elements are made or removed.  The WME itself  is  printed
       preceded by '>>' if the element is being added to working  memory
       or '<<' if the element is being removed from working  memory.   A
       watch level of three will indicate watch  level  two  information
       in addition to showing instances being  added  and  removed  from
       the conflict set.


       8.4  ppwm

            The ppwm command is used to  print  WMEs.   The  command  is
       followed by a pattern which can only  consist  of  constants  and
       attribute names.  The system will scan all of working memory  for
       the specified pattern and will print out each WME (including  its
       assigned time tag) that matches the pattern.  When  no  arguments
       are given to ppwm, all of working memory is printed.


       8.5  wm

            The wm command is similar to the ppwm  command  except  that
       instead of specifying a pattern as the arguments of the  command,
       a  list  of  time tags is specified.  Similar to ppwm the command
       prints all of working memory if it is called with no arguments.


                                    - 30 -






                                                      OPS5c User's Guide



       8.6  cs

            This command prints out the contents  of  the  conflict set.
       The  dominant  instance (the instance to fire next) is  indicated
       as such.


       8.7  strategy

            This command selects the conflict resolution  strategy.   It
       takes either 'lex' or 'mea' as a single argument,  or  if  called
       with no arguments  it  prints  the  current  conflict  resolution
       strategy.


       8.8  pbreak

            This command can set break points on specific  rules.   When
       called with a rule name it will set a break point  on  that  rule
       if one is currently unset or remove a break point for  that  rule
       if one is  currently  set.   Having  a  break  point  set  for  a
       particular rule means that the system  will  return  to  the  top
       level  immediately  after  firing  an  instance  of  that   rule.
       Issuing the command with no arguments prints  the  names  of  all
       rules which currently have break points set.


       8.9  dump (OPS5c only)

            This command prints out the  contents  (WME  time  tags)  of
       each of the alpha memories.


       8.10  size (OPS5c only)

            This command prints out the number of WMEs  in  the  working
       memory.  The number of WMEs in each class is listed separately.


















                                    - 31 -






       OPS5c User's Guide


       9.  The OPS5c System


       9.1  Installing OPS5c

            Each  C  compiler  has  directories  that  it  searches  for
       standard include files  when  compiling  and  standard  libraries
       when linking.  By placing the appropriate OPS5c  files  in  these
       places, you may use the OPS5c compiler just as you would  your  C
       compiler.  The compiler itself is called 'ops5c'.  You may  place
       this somewhere in your  execution  path  if  you  desire  (C:  or
       elsewhere).  The header file needed to compile  the  output  from
       the  OPS5c  compiler  is  called  'o5c.h'.  Place this file  with
       other standard headers such as  'stdio.h'.   The  OPS5c  run-time
       library  is  called  'ops5c.lib'.  Place this with your  standard
       libraries such  as  'c.lib'.   The  commands  for  compiling  the
       sample program 'tourney.ops' using the Aztec C compiler is  given
       below:

            ops5c test_files/tourney.ops
            cc tourney1.c
            ln -o tourney tourney1.o -lops5c -lm -lc

       Note that to produce the very fastest executables  you  may  turn
       on optimization when compiling the C output file,  but  you  will
       probably find that this has little effect other than making  your
       compile take longer.  It is far more important  to  optimize  the
       library code.  The code provided in the distribution was  created
       using Aztec C 5.0 with complete optimization turned on (-so).


       9.2  Differences from OPS5


            OPS5c was designed to be  as  compatible  as  possible  with
       existing OPS5  programs.   Complete  compatibility  is  virtually
       unobtainable since  OPS5c  is  compiled  and  typically  OPS5  is
       interpreted.   Other  differences  may   be   observed   due   to
       implementation  details  of  underspecified   features   of   the
       language.  The following list is a summary of the most  important
       differences that you may encounter when running OPS5c.

            o  The pm, matches, excise, and back top level  commands  of
               OPS5 are not implemented in OPS5c.

            o  The top level command dump is used to examine  the  alpha
               memory contents.  It takes no arguments  and  prints  out
               the contents of all alpha memories.

            o  The top level command size is used to  count  the  number
               of elements in each class and add them to  determine  the
               entire size of working memory.

            o  The top level include  command  works  similarly  to  the


                                    - 32 -






                                                      OPS5c User's Guide


               load command found in some Lisp implementations of  OPS5.
               It accepts a file name as  a  parameter.   The  indicated
               file must contain only make  statements  which  will  add
               new elements to working memory.

            o  Several of the '$' functions used by  OPS5  do  not  make
               sense in a non-Lisp  environment.   Additions  have  also
               been  made  to  the  $functions  (see  Interfacing   With
               External Code).

            o  It may or may not be possible  to  provide  execution  of
               OPS5c which is identical to that  of  OPS5  for  programs
               that rely on  arbitrary  selection  of  instances.   This
               occurs  when  two  are  more  instances  are   considered
               equivalent by the  conflict  resolution  rules  and  they
               exist simultaneously in the conflict set.   See  Run-Time
               Switches for a possible fix to this problem.

            o  OPS5c does not normally perform coercion between  numeric
               data types.  You can make the system perform coercion  by
               defining the preprocessor symbol  COERCE  when  compiling
               the <program>1.c file.  This will substitute  a  function
               call to  perform  type  checking  and  coercion  for  the
               equals and not-equals tests rather than  use  the  macros
               that are normally used.

            o  OPS5 specifies that all  WMEs  should  contain  the  same
               number   of   attributes,    usually    128    in    most
               implementations.  In order to  conserve  space  on  small
               systems, OPS5c sizes  all  WMEs  of  a  particular  class
               according  to  the  maximum  offset  of  the   attributes
               declared in the class.  (Note that this is not  the  same
               as the number  of  attributes  in  the  class  since  one
               attribute may have a large offset assigned to it.)   This
               may be overriden with the -w switch  at  either  compile-
               time or run-time.

            o  OPS5c  supports  modular compilation.  A large system may
               be compiled into  multiple  C  source  code  files,  then
               linked together to form an executable.   This  is  useful
               for systems with small amounts of RAM or  compilers  that
               cannot handle large symbol tables.  It often  speeds  the
               compilation process as well.

            o  It should  be  noted  that  in  this  implementation  the
               maximum number of CEs per rule is  64.   It  is  STRONGLY
               recommended that you limit the number of  CEs  per  rule.
               (No  more  that  10  CEs  per  rule  is   suggested   for
               performance reasons.)  Large rules should  be  broken  up
               into smaller ones as necessary.






                                    - 33 -






       OPS5c User's Guide


       9.3  Compiler Switches

            There are five switches  accepted  by  the  OPS5c  compiler.
       These are -t, -s, -c, -o and -w.  The most commonly  used  switch
       is -s.  This switch controls the  ordering  method  used  by  the
       compiler.   A  separate  join code sequence is generated for each
       CE of each rule.  There are two methods  used  for  ordering  the
       scan order of  the  join.   Seed ordering uses the CE being added
       to as the first CE in the join ordering with  the  remaining  CEs
       being examined in lexical order.   Heuristic ordering is based on
       seed ordering but tries to examine CE dependencies to  produce  a
       more efficient join order of the non-seed  CEs  (those  remaining
       after  the  seed  CE  has  been  selected).   Normally  heuristic
       ordering is used since it normally produces results  as  good  or
       better than seed ordering.  The -s  switch  indicates  that  seed
       ordering should be  used.   One  item  of  concern  is  that  the
       heuristic ordering algorithm will perform  exhaustive  search  of
       all orderings in the worst case.  This  only  happens  for  rules
       with  highly  connected  CEs  (CEs  which  have  common  variable
       bindings).  If worst case behavior is  observed,  the  number  of
       orderings examined is proportional to the square  of  the  number
       of CEs in a rule, therefore the compilation time for  rules  with
       a large number of connected CEs may be very high.   The  compiler
       prints an asterisk to the screen upon  completion  of  each  rule
       compiled.  If compilation appears to be very slow then  the  user
       should consider aborting the compile and recompiling with the  -s
       switch.
            The  -c  and  -o  switches  are  used  in  conjunction  with
       creating  multiple  output  modules.  Multiple output modules may
       be necessary on some systems  to  overcome  certain  software  or
       hardware  limitations.   When  multiple  output  modules   become
       necessary,  the  compiler  produces  a  series  of  files   named
       '<file>#.c', where the # sign is a numeric sequence  number.   It
       also produces a script  file  called  'comp.sh' which can be used
       to compile and link the multiple modules.  Multiple  modules  may
       be advantageous for systems with limited memory which may not  be
       able to compile an entire large rule system.  They  may  also  be
       necessary for linkers which have hard set limits  on  the  number
       of symbols  a  single  object  module  may  have.   Normally  the
       compiler  counts  functions  produced  for  join  operations  and
       functions produced for executing right-hand-side actions.   These
       functions will constitute  symbols  present  in  object  modules.
       The compiler has  a  cut-off  setting   which  indicates  when  a
       module has too many symbols.  If compiling an addition rule  into
       the current module will  exceed  the  symbol  cut-off,  then  the
       current module is terminated and a new module  is  started.   The
       default symbol-cutoff value is 3000.  The user may specify a  new
       cut-off value by using the -c switch with  a  numeric  value  for
       the symbol cut-off immediately  following.   To  suppress  module
       creation and produce only one module, use the -o switch.
            The -t  switch  is  used  to  specify  tracefile  execution.
       Tracefile execution is used to  run  benchmarks  comparing  OPS5c
       with other systems.  A tracefile of some  expert  system  run  is
       produced with the other system using  a  watch  level  2  setting


                                    - 34 -






                                                      OPS5c User's Guide


       (with the watch command).  This tracefile can be  read  by  OPS5c
       to  determine  appropriate  RHS  actions  after   each   conflict
       resolution step.  In this way we  do  not  have  to  worry  about
       recoding external functions used in RHS actions in order  to  run
       OPS5c, the tracefile will determine RHS actions.  Note that  this
       method may give poor results since the cost of  interpreting  the
       tracefile may be considerably  more  or  considerably  less  than
       that observed had external function  calls  to  C  routines  been
       used.  To use tracefile execution, follow the -t switch with  the
       path name of the tracefile.
            The -w switch allows the user to specify  the  size  of  the
       WMEs created at run-time.  It applies to all WMEs rather than  to
       specific classes.   Its  use  is  primarily  for  programs  using
       undeclared classes or attribute specifications  in  classes  that
       the attributes were not declared in.  The switch is  followed  by
       an integer number from 1 to 128 which  indicates  the  number  of
       attribute slots the WMEs will contain.  This number  must  be  as
       large as the largest offset of any class or the program will  not
       execute correctly.  Programs  whose  class  declarations  contain
       all attributes used by references of that class do  not  have  to
       worry about setting the -w flag  as  the  system  will  correctly
       size each class.


       9.4  Run-Time Switches

            The executable produced by compiling and linking  the  OPS5c
       output files will accept three switches  at  run-time,  -r0,  -r1
       and -w.  The -r  switches  are  used  to  reverse  the  sense  of
       resolving arbitrary comparisons in the conflict resolution  step.
       When two equivalent instances are compared the system can  either
       retain its current best choice, or swap the best choice with  the
       newly encountered equivalent one.   Whether  or  not  the  system
       performs the swap when this equivalence arises is  determined  by
       these switches.  The -r0 switch controls intra-rule  comparisons,
       i.e. comparisons between instances produced  by  the  same  rule.
       The -r1 switch  controls  inter-rule  comparisons  -  comparisons
       between instances produced by different rules.
            The  -w  switch  works  identically  to   its   compile-time
       counterpart.  If used, it overrides variable  sizing  of  classes
       and will also override any setting  created  by  use  of  the  -w
       compile-time switch.


       9.5  Interfacing With External Code

            OPS5c has the  capability  of  interfacing  with  externally
       written C code.  Actually the type of code that is interfaced  to
       is irrelevant.  It may be FORTRAN or assembler  as  long  as  the
       translators output a  common  object  format  understood  by  the
       linker.  All external programs must use the interface defined  by
       OPS5c for passing  parameters  and  results  between  the  expert
       system and the external  routines.   Additionally,  the  external
       routines must have some  understanding  of  the  data  types  and


                                    - 35 -






       OPS5c User's Guide


       symbol tables used by the OPS5c  system  in  order  to  correctly
       interface with the expert system.

       9.5.1  Data Types

            The  OPS5c  system  has  the  attribute  as   its   simplest
       unstructured data type.   An  attribute  is  actually  synonymous
       with the term atom as used in the Lisp programming  language  and
       both terms will be used  interchangably.   An  atom  is  actually
       many different  data  types.   An  atom is a structure containing
       two parts, the storage location for  a  data  type,  and  a  flag
       indicating what type of data is actually being stored there.   An
       atom is similar to the concept of a union in the C language,  and
       in fact is implemented as such: (as defined in o5c.h)

            typedef union {
                 float fval;
                 int ival;
                 StrID string;
            } Data;

            typedef struct attribute {
                 unsigned char type;
                 Data data;
            } Attr;

       The types currently defined are:

            AT_FLOAT       :  a floating point value
            AT_INTEGER     :  an integer value
            AT_SYMBOL      :  an interned string (see interning below)

       If the user wished  to  create  an  attribute  to  represent  the
       constant integer 5, he might code it as:

            Attr five;

            five.type = AT_INTEGER;
            five.data.ival = 5;

       When coding external functions, the programmer must keep in  mind
       that attributes  may  be  of  any  type  and  change  their  type
       dynamically as new values are assigned.   No  assumptions  should
       be made about  attribute  types.   Library  functions  exist  for
       comparing  attribute  values.   If  these  are  not   used,   the
       programmer is responsible for type checking and  coercion.   Most
       functions that interface with  OPS5c  will  require  pointers  to
       attributes (typedef'd as  AttrID) as parameters.  It will usually
       be  necessary  for  external  routines  to  declare   attributes,
       initialize them correctly, and use the appropriate functions  for
       comparison, assignment, and retrieval of attribute values.





                                    - 36 -






                                                      OPS5c User's Guide


       9.5.2  The Result Element

            The   result  element  is  a  global  buffer  used  to  pass
       parameters between  OPS5c  and  external  routines.   The  result
       element  (RE) is an array of attributes whose size is that of the
       largest WME supported by  the  implementation  (128  attributes).
       Values of attributes may be copied to the RE or copied  from  the
       RE using a library of functions  known  as  the  dollar  library.
       This name arises from  the  fact  that  the  Lisp  implementation
       names functions which operate on the RE using  names  that  start
       with a dollar sign ($reset, $value, etc.).  Many of  these  names
       have been kept, where appropriate, but the  functions  are  named
       dollar_reset, dollar_value, etc. since C  function  names  cannot
       contain a dollar sign.  Appendix A  describes  the  functions  in
       the dollar library.


       9.5.3  Interning and String Spaces

            The  term  interning comes from the Lisp environment and  is
       the primary  difference  between  strings and symbols.  A string,
       as defined by the C programming language, is  simply  a  sequence
       of characters terminated by a null character.  We often refer  to
       a string or consider its value to be the  pointer  to  the  first
       character of the string.  Such  a  pointer  is  used  to  perform
       comparisons between two  strings  on  a  character  by  character
       basis to determine equality, inequality, or other  relationships.
       In OPS5c we are interested in the relationships of  equality  and
       inequality between attributes with non-numeric  data  types.   If
       we were to store non-numeric information as strings  and  perform
       character by character matching, the  testing  process  would  be
       very slow.  Instead, we form a data structure known as  a  symbol
       table.  Using such a structure we can  store  strings  (known  as
       symbols) and look  up  their  pointers  by  a  process  known  as
       interning.  To intern a string, we call the intern function  with
       the string as an argument.  The intern  function  will  scan  the
       symbol table looking for an identical string (i.e.  symbol).   If
       such a symbol  is  found  then  the  address  of  the  symbol  is
       returned as the value of the function.   If  no  such  symbol  is
       found, the string is copied into the symbol table, thus  creating
       a new symbol, and its address is returned as  the  value  of  the
       interning function.  This is done for all  non-numeric  attribute
       values in the system.  The main reason for this is  that  once  a
       string has been interned, i.e. entered into the symbol table,  we
       may compare two symbols by comparing their  addresses,  since  if
       the original strings were identical, then the  interning  process
       will  return  identical  addresses.   This  greatly   speeds   up
       comparison of non-numeric data and also results in  less  storage
       requirements since we store  the  address  as  the  value  of  an
       interned symbol.
            As a result, if an external  routine  wishes  to  manipulate
       symbolic data such that the  OPS5c  inference  engine  can  match
       properly, attribute values going into and coming out  of  the  RE
       must be represented as  interned  symbols.   The  dollar  library


                                    - 37 -






       OPS5c User's Guide


       contains a very useful function, dollar_intern, for converting  a
       string into an interned symbol.
            To fully interface with the system, the programmer  must  be
       aware of a more generic library known  as  the  strings  library.
       Functions in the  strings  library  aid  in  manipulating  values
       interned as symbols.  The  strings  library  operates  on  string
       spaces which are equivalent to symbol  tables.   The  distinction
       and hence reason for different names, is that  the  OPS5c  system
       keeps several different  string spaces (symbol tables).  The most
       often used string space is that  for  attribute  values.   It  is
       called  'attr_values' and  should  be  referenced  as  such  when
       calling functions in the string library.
            The functions in the string library are listed  in  Appendix
       B.   The  most  commonly  used  functions  are   AddString() and
       StringAvail().  The AddString() function performs interning in  a
       string space.  The StringAvail() function simply  tests  for  the
       existance of a symbol in a  string  space.   Unlike  AddString(),
       StringAvail() will not add a new symbol  if  it  is  not  already
       there.  Note that the string library  functions  return  pointers
       of type String Entry.  The String  Entry  data  type  is  defined
       below.

            typedef struct {
                 HT_Entry_Header link;
                 StrID str_id;
            } String_HT_Header;

            typedef String_HT_Header *StringEntry;

       Frequently the user will wish to dereference the  StringEntry  to
       obtain the StrID of the returned  value.   The  StrID  is  not  a
       string pointer and should be treated as a handle to  the  symbol.
       The  GetString()  macro  can  be  used  to  return   the   string
       associated with a StrID.
            Another  string  space  of  interest  is  'attr_names'.   It
       contains symbols for all the declared attribute  names  known  by
       the system.  The programmer should not  attempt  to  add  to  the
       attr_names string space, only to  read  from  it.   StringEntry's
       retrieved  from  this  name  space  should  be  cast  to  (struct
       attr_off *) where:

            struct attr_off {
                 String_HT_Header link;
                 int offset;
            };

       Such a pointer can be dereferenced  by  ptr->offset  to  retrieve
       the  offset  (slot  position  in  the  RE)  associated   with   a
       particular attribute name.  This is a common occurrance  when  we
       wish to access values by attribute name which is the most  common
       method.





                                    - 38 -






                                                      OPS5c User's Guide


       9.5.4  Functions Versus Actions

            There are two types of  external  code  that  the  user  can
       interface  to  an  OPS5c  program,  functions  and  actions.  The
       distinction between these two forms  of  interface  in  the  OPS5
       language is vague.  Functions must return a single value  in  the
       result element.  This is  accomplished  with  the  dollar_value()
       call.  One and only one call to dollar_value() must be made by  a
       function.  The  OPS5  language  does  not  specify  how  argument
       passing to functions are implemented.  For  predefined  functions
       in-line code or calls to routines in  the  run-time  library  are
       produced.  For user-defined functions, arguments are  passed  via
       a global array args[] which  is  an  array  of  attribute  values
       (atoms).  A global  counter,  fargc,  is  used  to  indicate  the
       number of valid arguments in args[].   This  is  similar  to  the
       argc and argv[] method of passing command  line  arguments  to  C
       programs.  Once parameters are loaded into the args[] array,  the
       external function is called.   A  C  function  integer  argument,
       which is the number  of  actual  parameters,  is  passed  to  the
       function.
            Unlike functions, actions  may  utilize  all  the  functions
       defined in the dollar library.  An  action  may  return  zero  or
       more values.  These values are usually  returned  in  the  result
       element using the dollar_value() function.   Actions  are  passed
       arguments through the result element.  Before calling the  action
       the result element is cleared (filled with nil  atoms)  and  then
       it is filled  with  the  evaluated  pattern  that  comprises  the
       parameters.  No modification of the result element  is  performed
       after the action has finished with it.
            Note that the OPS5  language  specifies  that  all  external
       functions  and  actions  must  be  declared  with  the   external
       statement.  In OPS5c this is not a requirement, however,  actions
       which are not declared using external cannot be called  from  the
       top-level environment.






















                                    - 39 -






       OPS5c User's Guide


       10. References

       Forgy81
            Forgy,  Charles  L.  ,  OPS5  User's  Manual, Department  of
            Computer Science, Carnegie-Mellon University. CMU-CS-81-135


       Miranker87
            Miranker,  D.P.,  TREAT: A Better  Match  Algorithm  for  AI
            Production  Systems:  Long  Version, Artificial Intelligence
            Laboratory, University of Texas at Austin, Technical  Report
            AI TR-87-58












































                                    - 40 -






                                                      OPS5c User's Guide


       Appendix A - Dollar Library Description



       /* Possible return value of dollar_litbind() */
       #define NOT_DEFINED      -1


       /************************************************************
       This routine creates a new wme from the result element.
        ************************************************************/
       void
       dollar_assert(class_index)
       int class_index;



       /************************************************************
       This function takes  an  atom  (attribute  id)  and  returns  its
       integer value.
        ************************************************************/
       int
       dollar_cvan(atom)
       AttrID atom;


       /************************************************************
       This function  takes  an  integer  and  returns  a  numeric  atom
       (interned).
        ************************************************************/
       Attr
       dollar_cvna(num)
       int num;


       /************************************************************
       This  function  is  used  to  test  the  equality  of  two  atoms
       (attributes).
        ************************************************************/
        BOOLEAN
       dollar_eql(atom1,atom2)
       AttrID atom1;
       AttrID atom2;


       /************************************************************
       This function places a float value in the  result  element.   The
       value of the float is returned.
        ************************************************************/
       float
       dollar_flt_val(value)
       float value;




                                    - 41 -






       OPS5c User's Guide


       /************************************************************
       This function determines if a file of  specified  name  has  been
       opened for input.
        ************************************************************/
       FILE *
       dollar_ifile(attr)
       AttrID attr;


       /************************************************************
       This function places an integer  value  in  the  result  element.
       The value of the integer is returned.
        ************************************************************/
       int
       dollar_int_val(value)
       int value;


       /************************************************************
       This function is used to intern a  string  into  the  attr_values
       string table.
        ************************************************************/
        StrID
       dollar_intern(str)
       char *str;


       /************************************************************
       This function determines if its string argument is  an  attribute
       name that has been assigned an offset at compile  time.   If  so,
       the offset is returned.  If not NOT_DEFINED is returned.
        ************************************************************/
       int
       dollar_litbind(str)
       char *str;


       /************************************************************
       This function returns an attibute  (Attr,  not  an  AttrID)  when
       given an index into the result element
        ************************************************************/
       Attr
       dollar_parameter(index)
       int index;


       /************************************************************
       This function returns a count of the number of  elements  in  the
       result element.
        ************************************************************/
       int
       dollar_parametercount()




                                    - 42 -






                                                      OPS5c User's Guide


       /************************************************************
       This routine clears the result element (fills it  with  nil)  and
       resets the result element index.
        ************************************************************/
       void dollar_reset()


       /************************************************************
       This function places a string value in  the  result  element.   A
       StrID must  be  passed.  (See  strings  module.)   The  StrID  is
       returned as the result.
        ************************************************************/
       StrID
       dollar_str_val(value)
       StrID value;


       /************************************************************
       This predicate determines if an atom (attribute) is symbolic.
        ************************************************************/
       BOOLEAN
       dollar_symbol(x)
       Attr x;


       /************************************************************
       This routine sets the index of the result element.  Indicies  are
       numbered starting at 1.  The argument passed must be integer.
        ************************************************************/
       dollar_tab1(num)
       int num;


       /************************************************************
       Similar to dollar_tab1() above except that  the  argument  passed
       is an AttrID.  The attribute may be numeric  (integer  or  float)
       or a numeric string.
        ************************************************************/
       void
       dollar_tab2(attr_id)
       AttrID attr_id;


       /************************************************************
       This routine takes an attribute structure  (not  an  AttrID)  and
       places it in the result element at  the  current  position.   The
       pointer is then incremented to the next position.
        ************************************************************/
       dollar_value(attr)
       Attr attr;






                                    - 43 -






       OPS5c User's Guide


       Appendix B - String Library Description


       /************************************************************
        * This function "interns" a string and returns its ID code.  In
        * this implementation version, the ID is a memory address.
        ************************************************************/
       StringEntry
       AddString(str,string_table,struct_size)
       char *str;
       HashTable string_table;
       int struct_size;


       /************************************************************
        * This function checks to see if the indicated string already
        * exists in the specified string table.  If so, the StringEntry
        * of the string is returned, else NULL is returned.
        ************************************************************/
       StringEntry
       StringAvail(str,string_table)
       char *str;
       HashTable string_table;


       /************************************************************
        * This is a macro which can be used with a StrID to return the
        * pointer to the C string representation of the interned
        * string.
        ************************************************************/
       char *
       GetString(str_id)
       StrID str_id;























                                    - 44 -






                                                      OPS5c User's Guide


                                     Index

       //  14, 17-18, 29
       accept stream  22
       ACT  2-3, 5-13, 16-24, 26-30, 34-37, 39
       actions  2-3, 5-7, 12-13, 16-17, 19-20, 24, 26, 29, 34-35, 39
       AddString()  38
       alpha memory  7-8, 26, 32
       amem  7-8
       atom  2, 10, 17-19, 36, 39, 41, 43
       Attr  2, 5, 9-18, 20, 29-30, 33, 35-39, 41-43
       attribute  2, 5, 9-11, 13-18, 20, 29-30, 33, 35-39, 41-43
       attribute variable  13
       attribute-value pair  13-14, 20
       AttrID  36, 41-43
       attr_names  38
       attr_values  38, 42
       call  2, 4-7, 16-19, 21-22, 26, 29-39
       case  5-7, 10, 16, 24, 34
       CE  2-43
       class  2, 4-5, 8-15, 20, 22, 27, 29, 31-33, 35, 41
       closefile  2, 19, 22-23, 29
       coercion  10, 33, 36
       comp.sh  34
       condition element  2, 5, 13, 15-16, 24
       conflict resolution  2, 6-7, 9, 24, 27, 31, 33, 35
       conflict set  6-7, 15-16, 22, 24, 30-31, 33
       conjuctions  2, 14
       constant tests  7-8, 25
       context clause  25, 27
       contexts  27
       crlf  21
       default  2, 19, 22-23, 29-30, 34
       disjunctions  2, 15
       dominant instance  31
       element designator  2, 16-18, 20, 29
       element variable  2, 16-17, 20-21
       functions  2-4, 10, 17-18, 21, 23, 29, 33-39
       heuristic ordering  34
       incremental matching  6, 8
       instance  5-8, 15-17, 24-25, 27, 29-31, 33, 35
       interning  3, 36-38
       JOIN  7, 34
       join code  34
       LEX  24-25, 31, 34
       LHS  2, 5-7, 10, 12-13, 16-18, 20, 24, 29
       literal  5, 9-10, 13-15
       literalize  5, 9-10, 14
       make  2, 5, 7, 16, 19-21, 24, 26, 29, 33
       MATCH  4, 6-8, 13-16, 20, 26, 30, 32, 37, 40
       MEA  4, 6, 8, 13, 15, 17, 21, 24-25, 29, 31
       modular compilation  33
       modules  34
       nil  10, 17, 39, 43


                                    - 45 -






       OPS5c User's Guide


       o5c.h  32, 36
       offsets  9-10, 17-18, 20
       openfile  2, 19, 22-23, 29
       ops5c.lib  32
       predicates  2, 10, 14, 43
       quoting  2, 13, 15
       RE  2-44
       recency  24
       remove  2, 6, 15-16, 19-21, 24, 28-31
       result element  3, 17-18, 37, 39, 41-43
       RETE  4-5, 7, 9, 13, 18, 20, 29, 32
       RHS  2, 5-7, 12, 16-20, 22, 24, 29-30, 35
       rjust  21
       rule  2, 4-10, 12-16, 19-20, 22, 24-31, 33-35
       seed ordering  34
       SELECT  5-7, 15, 24-28, 31, 33-34
       specificity  24
       StrID  36, 38, 42-44
       string space  3, 37-38
       StringAvail()  38
       StringEntry  38, 44
       strings  10, 37-38, 43
       subtasks  26
       symbol table  9, 33, 36-38
       symbols  10, 13-14, 34, 37-38
       tabto  21
       time tags  9, 24-25, 27, 29-31
       top level  2, 13, 19, 22, 29-32
       trace stream  22
       TREAT  4-5, 7, 11, 13, 19, 21, 38, 40
       variable binding tests  7, 25
       vector attributes  2, 10-11
       WM  2, 5-11, 13-18, 20-21, 24, 26-27, 29-31, 33, 35, 37, 41
       WME  6-11, 13-18, 20-21, 24, 26-27, 29-31, 33, 35, 37, 41
       Working memory  2, 5-7, 9, 15, 17, 21-22, 24, 27, 29-33
       working memory element  2, 6, 9, 30
       write stream  22
       \\  18


















                                    - 46 -