lib-src/rete/rete.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <iostream>
  26 #include <AD/rete/rete.h>         // RETE inference engine
  27 #include <AD/hash/lhash.h>        // coalesced chaining hash table
  28 #include <AD/contain/varqueue.h>  // generic queue
  29 #include <AD/memory/arena.h>      // arenas
  30
  31 /////////////////////////////////////////////////////////////////////////
  32 // Make hidden types visible
  33 /////////////////////////////////////////////////////////////////////////
  34 typedef Rete::Priority Priority;  // priority of rule
  35 typedef Rete::RuleId   RuleId;    // rule number
  36 typedef Rete::Node     Node;      // a node in the RETE network
  37 typedef Rete::Age      Age;       // age of fact
  38
  39 /////////////////////////////////////////////////////////////////////////
  40 // Equality and hashing for facts.
  41 /////////////////////////////////////////////////////////////////////////
  42 Bool equal(Fact * a, Fact * b) { return a == b; }
  43 unsigned int hash(Fact * f)    { return (unsigned int)f; }
  44
  45 /////////////////////////////////////////////////////////////////////////
  46 // A token
  47 /////////////////////////////////////////////////////////////////////////
  48 class ReteToken {
  49
  50    RuleId rule_id;   // rule id
  51    int    arity;     // length of the token
  52    Age    _age;      // age
  53    Fact * token[1];  // the token
  54
  55 public:
  56
  57    //////////////////////////////////////////////////////////////////////
  58    //  Method to allocate a new token
  59    //////////////////////////////////////////////////////////////////////
  60    inline void * operator new
  61       (size_t, Arena& arena, int n, RuleId id, Fact * f[], Age a)
  62       {  ReteToken * t = (ReteToken*) arena();
  63          t->arity = n; t->rule_id = id; t->_age = a;
  64          for (int i = n - 1; i >= 0; i--) t->token[i] = f[i];
  65          return t;
  66       }
  67
  68    //////////////////////////////////////////////////////////////////////
  69    //  Selectors
  70    //////////////////////////////////////////////////////////////////////
  71    // inline         operator Fact ** ()     { return token; }
  72    inline Fact ** get_token()               { return token; }
  73    inline int     size()              const { return arity; }
  74    inline Fact *  operator [] (int i) const { return token[i]; }
  75    inline RuleId  rule()              const { return rule_id; }
  76    inline Age     age()               const { return _age; }
  77
  78    //////////////////////////////////////////////////////////////////////
  79    //  Equality and hashing
  80    //////////////////////////////////////////////////////////////////////
  81    inline friend Bool equal(ReteToken * a, ReteToken * b)
  82       { if (a->rule_id != b->rule_id || a->arity != b->arity) return false;
  83         for (int i = a->arity - 1; i >= 0; i--)
  84            if (a->token[i] != b->token[i]) return false;
  85         return true;
  86       }
  87
  88    inline friend unsigned hash(ReteToken * a)
  89       { unsigned int h = a->rule_id + a->arity;
  90         for (int i = a->arity - 1; i >= 0; i--) h += (unsigned int)a->token[i];
  91         return h;
  92       }
  93 };
  94
  95 /////////////////////////////////////////////////////////////////////////
  96 //  Definition of the conflict set
  97 /////////////////////////////////////////////////////////////////////////
  98 class ReteConflictSet {
  99
 100    ReteConflictSet(const ReteConflictSet&);  // no copy constructor
 101    void operator = (const ReteConflictSet&); // no assignment
 102
 103 protected:
 104    friend class Rete;
 105
 106    //////////////////////////////////////////////////////////////////////
 107    // Internal members
 108    //////////////////////////////////////////////////////////////////////
 109    Age                         timestamp; // current time
 110    VarQueue   <ReteToken *>    tokens;    // queue of tokens
 111    LHashTable <Fact *, Fact *> facts;     // database of facts
 112    Arena                       arena;     // arena (for tokens only)
 113
 114 public:
 115
 116    //////////////////////////////////////////////////////////////////////
 117    // Constructor and destructor
 118    //////////////////////////////////////////////////////////////////////
 119    ReteConflictSet(int max_token_arity, int n = 64, int m = 1025);
 120   ~ReteConflictSet() {}
 121
 122    //////////////////////////////////////////////////////////////////////
 123    // Timestamp and priority management.
 124    //////////////////////////////////////////////////////////////////////
 125    inline void reset_time() { timestamp = 0; }
 126    inline Age  now () const { return timestamp; }
 127    inline Age  new_time()   { return timestamp++; }
 128 };
 129
 130 /////////////////////////////////////////////////////////////////////////
 131 //  Constructor for the conflict set.
 132 /////////////////////////////////////////////////////////////////////////
 133 ReteConflictSet::ReteConflictSet(int max_token_arity, int n, int m)
 134    : timestamp(0),
 135      tokens(n),
 136      facts(m),
 137      arena(sizeof(ReteToken) + (max_token_arity - 1) * sizeof(Fact *))
 138    {}
 139
 140 /////////////////////////////////////////////////////////////////////////
 141 //  An auxiliary function calculate the maximum arity of all tokens.
 142 /////////////////////////////////////////////////////////////////////////
 143 static int max_arity_of(int N, const ReteNet::Node network[])
 144 {  int max_arity = 0;
 145    for (int i = N - 1; i >= 0; i--)
 146       if (network[i].arity > max_arity) max_arity = network[i].arity;
 147    return max_arity;
 148 }
 149
 150 /////////////////////////////////////////////////////////////////////////
 151 // Constructor
 152 /////////////////////////////////////////////////////////////////////////
 153 Rete::Rete(int N, const Node my_network[], int M, const RelationTable T[])
 154    : Super        (N,my_network),
 155      conflict_set (*new ReteConflictSet(max_arity_of(N,my_network)))
 156    {  int max_tag = 0;
 157       for (int i = 0; i < M; i++) {
 158          if (*T[i].relation_tag > max_tag) max_tag = *T[i].relation_tag;
 159          if (*T[i].relation_tag <= 0)
 160             std::cerr << "Bug: relation " << T[i].relation_name
 161                  << " has not been properly initialised in inference class "
 162                  << name_of() << '\n';
 163       }
 164       inject_table_size = max_tag + 1;
 165       inject_table = (int*)mem.c_alloc(sizeof(int) * inject_table_size );
 166       for (int j = 0; j < M; j++)
 167          inject_table[ *T[j].relation_tag ] = T[j].inject;
 168    }
 169
 170 /////////////////////////////////////////////////////////////////////////
 171 // Destructor
 172 /////////////////////////////////////////////////////////////////////////
 173 Rete::~Rete() { delete (&conflict_set); }
 174
 175 /////////////////////////////////////////////////////////////////////////
 176 // Return the name of the inference class
 177 /////////////////////////////////////////////////////////////////////////
 178 const char * Rete::name_of() const { return "Rete"; }
 179
 180 ////////////////////////////////////////////////////////////////////////
 181 // Conflict resolution methods
 182 ////////////////////////////////////////////////////////////////////////
 183
 184 ////////////////////////////////////////////////////////////////////////
 185 // Method to add a new token into the conflict set
 186 ////////////////////////////////////////////////////////////////////////
 187 void Rete::activate(RuleId rule, int arity, Fact * token[])
 188 {  ReteToken * T = new(conflict_set.arena, arity, rule, token,
 189                        conflict_set.new_time()) ReteToken;
 190    conflict_set.tokens.insert_tail(T);
 191 }
 192
 193 ////////////////////////////////////////////////////////////////////////
 194 // Method to remove a token from the conflict set
 195 ////////////////////////////////////////////////////////////////////////
 196 void Rete::deactivate(RuleId /*rule*/, int /*arity*/, Fact * /*token*/[])
 197 {
 198 }
 199
 200 ////////////////////////////////////////////////////////////////////////
 201 //  Method: fire()
 202 //    Select the highest priority rule to execute( which may as a result
 203 //  alter the discriminant network.)
 204 ////////////////////////////////////////////////////////////////////////
 205 void Rete::fire()
 206 {  if (! conflict_set.tokens.is_empty()) {
 207       ReteToken * T =
 208          conflict_set.tokens.remove_head(); // look for any token
 209       // action(T->rule(), *T);               // execute the action
 210       action(T->rule(), T->get_token());    // execute the action
 211       conflict_set.arena.free(T);           // frees the token.
 212    }
 213 }
 214
 215 ////////////////////////////////////////////////////////////////////////
 216 //  Method to perform infernence until stabilised.
 217 ////////////////////////////////////////////////////////////////////////
 218 void Rete::infer()
 219 {  while (! is_stable()) fire(); }
 220
 221 ////////////////////////////////////////////////////////////////////////
 222 //  Method to check whether the conflict set is empty.
 223 ////////////////////////////////////////////////////////////////////////
 224 Bool Rete::is_stable() const
 225 {  return conflict_set.tokens.is_empty(); }
 226
 227 ////////////////////////////////////////////////////////////////////////
 228 //  Auxiliary methods to assert and retract facts from the conflict set
 229 ////////////////////////////////////////////////////////////////////////
 230 void Rete::clear()
 231    { conflict_set.tokens.clear(); conflict_set.reset_time(); }
 232
 233 ////////////////////////////////////////////////////////////////////////
 234 //  Method to assert a fact.
 235 //  Steps:
 236 //    (1) Lookup the unique relation tag of the fact.
 237 //        Each relation type is given an unique tag by the runtime
 238 //        system.
 239 //    (2) Lookup the entry number using the dispatch table.
 240 //    (3) Then run the alpha test.
 241 ////////////////////////////////////////////////////////////////////////
 242 ReteNet& Rete::assert_fact(Fact * fact)
 243 {  conflict_set.facts.insert(fact,fact);
 244    RelTag tag = fact->get_tag();
 245    if (tag < inject_table_size) {
 246       int inj = inject_table[tag];
 247       if (inj > 0) alpha_test(inj, 1, fact);
 248    }
 249    return *this;
 250 }
 251
 252 ////////////////////////////////////////////////////////////////////////
 253 //  Method to retract a fact.
 254 ////////////////////////////////////////////////////////////////////////
 255 ReteNet& Rete::retract_fact (Fact * fact)
 256 {  if (conflict_set.facts.remove(fact)) {
 257       RelTag tag = fact->get_tag();
 258       if (tag < inject_table_size) {
 259          int inj = inject_table[tag];
 260          if (inj > 0) alpha_test(inj, 0, fact);
 261       }
 262    }
 263    return *this;
 264 }
 265
 266 ////////////////////////////////////////////////////////////////////////
 267 //  Selectors
 268 ////////////////////////////////////////////////////////////////////////
 269 int Rete::size() const { return conflict_set.facts.size(); }
 270
 271 ////////////////////////////////////////////////////////////////////////
 272 //  Iterator methods
 273 ////////////////////////////////////////////////////////////////////////
 274 Ix Rete::first()     const { return conflict_set.facts.first(); }
 275 Ix Rete::next (Ix i) const { return conflict_set.facts.next(i); }
 276 Fact * Rete::operator () (Ix i) const { return conflict_set.facts.value(i); }
 277
 278 ////////////////////////////////////////////////////////////////////////
 279 //  Add all the facts of a database into another
 280 ////////////////////////////////////////////////////////////////////////
 281 void Rete::add(const Rete& rete)
 282 {
 283    for (Ix i = rete.first(); i; i = rete.next(i))
 284       assert_fact(rete(i));
 285 }