tools/misc/tri.pcc

   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 relation Number = num   (int)
  15                 | limit (int);
  16 instantiate relation Number;
  17
  18 //
  19 // The following inference construct defines an inference class
  20 // with two rules and one axiom.
  21 //
  22 inference class Triangle {};
  23
  24 inference Triangle {
  25
  26   //
  27   //  Start from 1
  28   //
  29   ->  num   (1);
  30
  31   //
  32   //  Assert all numbers from 1 to n
  33   //
  34       num   (m)
  35   and limit (n) where (m < n)
  36   ->  num   (m + 1);
  37
  38   //
  39   //  Now try all combination of x, y, and z's and look for witnesses
  40   //  of the Pythagorean Theorem.
  41   //
  42   //  Notice that we are in effect performing a three way
  43   //  cartesian product.  Since Prop doesn't yet have indexing,
  44   //  all permutations have to be enumerated.  So this is in effect
  45   //  a good benchmark for the basic (naive) inference speed of Prop.
  46   //  This is NOT a recommended use of inference, of course.
  47   //
  48   //  Notice that the inferencing will go progressively slower as
  49   //  more and more facts are entered into the database.  The time
  50   //  complexity is O(n^3), where n is the limit.  Space complexity
  51   //  is O(n^2), since the RETE algorithm caches intermediate results
  52   //  from the first join in its beta memory.
  53   //
  54       num (x)
  55   and num (y) where (x < y)
  56   and num (z) where (y < z && x * x + y * y == z * z)
  57   ->  { cout << x << " * " << x << " + "
  58              << y << " * " << y << " = "
  59              << z << " * " << z << '\n';
  60       };
  61 };
  62
  63 int main()
  64 {
  65    Triangle triangle;   // instantiate an inference module
  66    int top;
  67
  68    //
  69    // Get the limit
  70    //
  71    cout << "Please input a limit (say, between 10 - 100): " << flush;
  72    cin >> top;
  73    cout << "Trying all numbers from 1 to " << top << '\n';
  74
  75    //
  76    // Insert the initial parameter into the database.
  77    //
  78    triangle << limit (top);
  79
  80    //
  81    // Run the inference engine until it is stable.
  82    // The inference rules defined above will be fired and triangular
  83    // identities will be printed.
  84    //
  85    triangle.infer();
  86
  87    return 0;
  88 }