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