lib-src/rete/gen_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 welcomed 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(read crave for)
  19 // any suggestions and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <iostream>
  26 #include <AD/rete/gen_rete.h>    // generalised Rete network
  27 #include <AD/rete/alphamem.h>    // alpha memory
  28 #include <AD/rete/betamem.h>     // beta memory
  29 #include <AD/memory/boundtag.h>  // generic memory manager
  30 #include <AD/memory/arena.h>     // free list memory manager
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  Class Constructor
  34 //////////////////////////////////////////////////////////////////////////////
  35 ReteInterp:: ReteInterp(int N, const Node net[], const NodeId chain[])
  36       : mem             (* new BoundaryTag(4096)),
  37         alpha_mem       (new AlphaMem [ N ]),
  38         beta_mem        (new BetaMem  [ N ]),
  39         network         (net),
  40         chain_table     (chain),
  41         number_of_nodes (N),
  42         number_of_facts (0),
  43         max_token_arity (0)
  44    {}
  45
  46 //////////////////////////////////////////////////////////////////////////////
  47 //  Class Destructor
  48 //////////////////////////////////////////////////////////////////////////////
  49 ReteInterp::~ReteInterp()
  50 {  delete (&mem);
  51    delete [] alpha_mem;
  52    delete [] beta_mem;
  53 }
  54
  55 //////////////////////////////////////////////////////////////////////////////
  56 //  Method to return the name of the rete network.
  57 //////////////////////////////////////////////////////////////////////////////
  58 const char * ReteInterp::name_of() const { return "ReteInterp"; }
  59
  60 //////////////////////////////////////////////////////////////////////////////
  61 //  Method to clear all the database, alpha and beta memory
  62 //////////////////////////////////////////////////////////////////////////////
  63 void ReteInterp::clear()
  64 {  //
  65    // Since all the memory is allocated from the our memory manager,
  66    // we'll simply reset of the manager and reallocate all the alpha
  67    // and beta memory.
  68    //
  69    mem.clear();
  70    delete [] alpha_mem;
  71    delete [] beta_mem;
  72    alpha_mem = new AlphaMem [ number_of_nodes ];
  73    beta_mem  = new BetaMem  [ number_of_nodes ];
  74    number_of_facts = 0;
  75 }
  76
  77 //////////////////////////////////////////////////////////////////////////////
  78 //  Method to run the inference engine until equilibrium.
  79 //////////////////////////////////////////////////////////////////////////////
  80 void ReteInterp::infer() { while (! is_stable()) fire(); }
  81
  82 //////////////////////////////////////////////////////////////////////////////
  83 //  Method to insert a fact into the right side of a node
  84 //////////////////////////////////////////////////////////////////////////////
  85 void ReteInterp::insert_right (NodeId n, Fact * fact)
  86 {  const Node& node = network[n];
  87    switch (node.kind) {
  88       ////////////////////////////////////////////////////////////////////////
  89       // Memorize fact in alpha memory and distribute the fact to the
  90       // sub-network.
  91       ////////////////////////////////////////////////////////////////////////
  92       case Node::ENTRY:
  93          alpha_mem[n].add_fact(mem, fact);
  94
  95       ////////////////////////////////////////////////////////////////////////
  96       // Propagate fact into the sub-network
  97       ////////////////////////////////////////////////////////////////////////
  98       case Node::FORK:
  99       {  for (int i = node.child; chain_table[i] >= 0; i++)
 100             insert_right(chain_table[i], fact);
 101       }  break;
 102
 103       ////////////////////////////////////////////////////////////////////////
 104       // Compute join using linear search
 105       ////////////////////////////////////////////////////////////////////////
 106       case Node::JOIN:
 107       {  BetaMem& b = beta_mem [node.left_input];
 108          for (int i = b.size() - 1; i >= 0; i--) {
 109             Fact ** token = b[i];
 110             token [ node.left_arity ] = fact;
 111             if (node.join == 0 || beta_test(node.join, token))
 112                insert_left (node.child, token);
 113          }
 114       } break;
 115
 116       ////////////////////////////////////////////////////////////////////////
 117       // Compute negation using linear search
 118       ////////////////////////////////////////////////////////////////////////
 119       case Node::NOT:
 120       {  BetaMem& b = beta_mem [node.left_input];
 121          for (int i = b.size() - 1; i >= 0; i--) {
 122             Fact ** token = b[i];
 123             token [ node.left_arity ] = fact;
 124             if (node.join == 0 || beta_test(node.join, token))
 125                if (b.inc_neg(i)) remove_left(node.child, token);
 126          }
 127       }  break;
 128
 129       ////////////////////////////////////////////////////////////////////////
 130       // Insert token into the conflict set
 131       ////////////////////////////////////////////////////////////////////////
 132       case Node::BOT:
 133          activate(node.child, 1, &fact); break;
 134       default: break;
 135    }
 136 }
 137
 138 //////////////////////////////////////////////////////////////////////////////
 139 //  Method to insert a fact into the left side of a node
 140 //////////////////////////////////////////////////////////////////////////////
 141 void ReteInterp::insert_left (NodeId n, Fact * token[])
 142 {  const Node& node = network[n];
 143    switch (node.kind) {
 144       case Node::ENTRY:
 145       {
 146       } break;
 147
 148       ////////////////////////////////////////////////////////////////////////
 149       // Propagate fact into the sub-network
 150       ////////////////////////////////////////////////////////////////////////
 151       case Node::FORK:
 152       {  for (int i = node.child; chain_table[i] >= 0; i++)
 153             insert_left(chain_table[i], token);
 154       }  break;
 155
 156       ////////////////////////////////////////////////////////////////////////
 157       // Compute join using linear search
 158       ////////////////////////////////////////////////////////////////////////
 159       case Node::JOIN:
 160       {  AlphaMem& a = alpha_mem[ node.right_input ];
 161          for (int i = a.size() - 1; i >= 0; i--) {
 162             token[ node.left_arity ] = a[i];
 163             if (node.join == 0 || beta_test(node.join, token))
 164                insert_left (node.child, token);
 165          }
 166       }  break;
 167
 168       ////////////////////////////////////////////////////////////////////////
 169       // Compute negation using linear search
 170       ////////////////////////////////////////////////////////////////////////
 171       case Node::NOT:
 172       {  AlphaMem& a = alpha_mem[ node.right_input ];
 173       }  break;
 174
 175       case Node::BOT:
 176          activate(node.child, node.arity, token); break;
 177       default: break;
 178    }
 179 }
 180
 181 //////////////////////////////////////////////////////////////////////////////
 182 //  Method to removes a fact
 183 //////////////////////////////////////////////////////////////////////////////
 184 void ReteInterp::remove_right (NodeId n, Fact * fact)
 185 {  const Node& node = network[n];
 186    switch (node.kind) {
 187       case Node::ENTRY:
 188       case Node::FORK:
 189       case Node::JOIN:
 190       case Node::BOT:
 191       case Node::NOT:
 192          deactivate(node.child, 1, &fact); break;
 193       default: break;
 194    }
 195 }
 196
 197 //////////////////////////////////////////////////////////////////////////////
 198 //  Method to removes a fact from the left
 199 //////////////////////////////////////////////////////////////////////////////
 200 void ReteInterp::remove_left (NodeId n, Fact * token[])
 201 {  const Node& node = network[n];
 202    switch (node.kind) {
 203       case Node::ENTRY:
 204       case Node::FORK:
 205       case Node::JOIN:
 206       case Node::BOT:
 207       case Node::NOT:
 208          deactivate(node.child, node.arity, token); break;
 209       default: break;
 210    }
 211 }