demos/inference.pC

   1 //////////////////////////////////////////////////////////////////////////////
   2 //  This is a simple self-contained test to benchmark the speed of
   3 //  naive inferencing in Prop.
   4 //
   5 //  To compile on Unix:
   6 //
   7 //     prop triangle.pcc
   8 //     gcc -I<prop-include-dir> triangle.cc -o triangle -L<ADLib-library-dir>
   9 //         -lad -liostream -lg++
  10 //////////////////////////////////////////////////////////////////////////////
  11
  12 #include <iostream.h>
  13
  14 //////////////////////////////////////////////////////////////////////////////
  15 //
  16 //  Defines two relations to be used during inference
  17 //
  18 //////////////////////////////////////////////////////////////////////////////
  19 datatype Number :: relation = num   (int);
  20 datatype Limit  :: relation = limit (int);
  21 instantiate datatype Number, Limit;
  22
  23 //////////////////////////////////////////////////////////////////////////////
  24 //
  25 // The following inference construct defines an inference class
  26 // with two rules and one axiom.
  27 //
  28 //////////////////////////////////////////////////////////////////////////////
  29 inference class Triangle {};
  30
  31 inference Triangle {
  32
  33   //
  34   //  Start from 1
  35   //
  36   --------------------
  37       num   (1);
  38
  39   //
  40   //  Assert all numbers from 1 to n
  41   //
  42       num   (m)
  43   and limit (n) where m < n
  44   ---------------------------
  45       num   (m + 1);
  46
  47   ///////////////////////////////////////////////////////////////////////////
  48   //
  49   //  Now try all combination of x, y, and z's and look for witnesses
  50   //  of the Pythagorean Theorem.
  51   //
  52   //  Notice that we are in effect performing a three way
  53   //  cartesian product.  Since Prop doesn't yet have indexing,
  54   //  all permutations have to be enumerated.  So this is in effect
  55   //  a good benchmark for the basic (naive) inference speed of Prop.
  56   //  This is NOT a recommended use of inference, of course.
  57   //
  58   //  Notice that the inferencing will go progressively slower as
  59   //  more and more facts are entered into the database.  The time
  60   //  complexity is O(n^3), where n is the limit.  Space complexity
  61   //  is O(n^2), since the RETE algorithm caches intermediate results
  62   //  from the first join in its beta memory.
  63   //
  64       num (x)
  65   and num (y) where x < y
  66   and num (z) where y < z && x * x + y * y == z * z
  67   -----------------------------------------------------
  68       { cout << x << " * " << x << " + "
  69              << y << " * " << y << " = "
  70              << z << " * " << z << '\n';
  71       };
  72 };
  73
  74 int main()
  75 {
  76    Triangle triangle;   // instantiate an inference module
  77    int top;
  78
  79    ///////////////////////////////////////////////////////////////////////////
  80    //
  81    // Get the limit
  82    //
  83    ///////////////////////////////////////////////////////////////////////////
  84    cout << "Please input a limit (say, between 10 - 100): " << flush;
  85    cin >> top;
  86    cout << "Trying all numbers from 1 to " << top << '\n';
  87
  88    ///////////////////////////////////////////////////////////////////////////
  89    //
  90    // Insert the initial parameter into the database.
  91    //
  92    ///////////////////////////////////////////////////////////////////////////
  93    triangle << limit (top);
  94
  95    ///////////////////////////////////////////////////////////////////////////
  96    //
  97    // Run the inference engine until it is stable.
  98    // The inference rules defined above will be fired and triangular
  99    // identities will be printed.
 100    //
 101    ///////////////////////////////////////////////////////////////////////////
 102    triangle.infer();
 103
 104    return 0;
 105 }