tests/rewriting5.pcc

   1 //////////////////////////////////////////////////////////////////////////////
   2 //  This program tests rewriting and garbage collection by using
   3 //  the rewriting mechanism to compute the Fibonacci number the hard way.
   4 //////////////////////////////////////////////////////////////////////////////
   5 #include <iostream.h>
   6 #include <AD/gc/gcobject.h>
   7 #include <AD/gc/markswp.h>
   8
   9 //////////////////////////////////////////////////////////////////////////////
  10 //  Datatype EXP denotes an expression.
  11 //////////////////////////////////////////////////////////////////////////////
  12 datatype EXP :: collectable =
  13    num (int)       => _
  14 |  fib (EXP)       => "fib " _
  15 |  add (EXP, EXP)  => "(" _ "+" _ ")"
  16 ;
  17
  18 //////////////////////////////////////////////////////////////////////////////
  19 //  Defines the interface to a rewrite class.
  20 //  A private counter ``rewrite_count'' is encapsulated by the class
  21 //  mechanism.
  22 //////////////////////////////////////////////////////////////////////////////
  23 rewrite class Fib (EXP) {
  24    int rewrites;  // number of replacements performed during rewriting
  25 public:
  26    Fib() : rewrites(0) {}
  27   ~Fib() {}
  28
  29    inline int number_of_rewrites() const { return rewrites; }
  30 };
  31
  32
  33 //////////////////////////////////////////////////////////////////////////////
  34 //  Specifies the rewrite rules.  We'll use rewriting to compute
  35 //  addition also.  The algorithm is exponential in time and generates
  36 //  a lot of garbage in the process.
  37 //
  38 //  Notice that all private data within the rewrite class is visible within
  39 //  the rewrite rules.
  40 //////////////////////////////////////////////////////////////////////////////
  41 rewrite Fib {
  42   fib (x as num n):        { rewrites++;
  43      if (n <= 1) rewrite(x); else; rewrite(add(fib(num(n-1)),fib(num(n-2))));}
  44 | add (num x, num y): { rewrites++; rewrite(num(x+y)); }
  45 };
  46
  47 //////////////////////////////////////////////////////////////////////////////
  48 //  Instantiate the datatype
  49 //////////////////////////////////////////////////////////////////////////////
  50 instantiate datatype EXP;
  51
  52 //////////////////////////////////////////////////////////////////////////////
  53 //  Input a number and test the rewrite rules.
  54 //////////////////////////////////////////////////////////////////////////////
  55 int main()
  56 {
  57    ///////////////////////////////////////////////////////////////////////////
  58    //  Give ourselves some more memory (2Meg) to work with.
  59    //  The default heap size is only 128K.   Using a larger heap
  60    //  can drastically cut down the overhead of GC since almost all
  61    //  intermediate terms generated can be reclaimed.  With the copying
  62    //  garbage collecting scheme that we are using, the overhead of GC
  63    //  is proportional to the amount of live data, not the total heap size.
  64    ///////////////////////////////////////////////////////////////////////////
  65    MarkSweepGC ms;
  66    GC::set_default_gc(ms);
  67    GC::get_default_gc().set_initial_heap_size(2*1024*1024);
  68
  69    int n;
  70    cout << "This simple benchmark tests the efficiency of rewriting\n"
  71            "by computing the Fibonacci numbers with a naive, exponential\n"
  72            "algorithm.  The goal is to stress the pattern matching and\n"
  73            "term replacement facilities.\n"
  74            "Please input a small non-negative number(0-25): " << flush;
  75    cin >> n;
  76    Fib F;
  77    EXP x = fib(num(n));
  78    F(x);
  79    cout << "fib(" << n << ") = " << x << '\n';
  80    cout << "Number of replacements = " << F.number_of_rewrites() << '\n';
  81    return 0;
  82 }