prop-src/T9.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>
   6 #include <AD/gc/gcobject.h>
   7
   8 //////////////////////////////////////////////////////////////////////////////
   9 //  Datatype EXP denotes an expression.
  10 //////////////////////////////////////////////////////////////////////////////
  11 datatype EXP :: collectable =
  12    num (int)       => _
  13 |  fib (EXP)       => "fib " _
  14 |  add (EXP, EXP)  => "(" _ "+" _ ")"
  15 ;
  16
  17 //////////////////////////////////////////////////////////////////////////////
  18 //  Defines the interface to a rewrite class.
  19 //  A private counter ``rewrite_count'' is encapsulated by the class
  20 //  mechanism.
  21 //////////////////////////////////////////////////////////////////////////////
  22 rewrite class Fib (EXP) {
  23    int rewrites;  // number of replacements performed during rewriting
  24 public:
  25    Fib() : rewrites(0) {}
  26   ~Fib() {}
  27
  28    inline int number_of_rewrites() const { return rewrites; }
  29 };
  30
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  Specifies the rewrite rules.  We'll use rewriting to compute
  34 //  addition also.  The algorithm is exponential in time and generates
  35 //  a lot of garbage in the process.
  36 //
  37 //  Notice that all private data within the rewrite class is visible within
  38 //  the rewrite rules.
  39 //////////////////////////////////////////////////////////////////////////////
  40 rewrite Fib {
  41   fib (x as num 0):   x
  42 | fib (x as num 1):   x
  43 | fib (num n):        add(fib(num(n-1)),fib(num(n-2)))
  44 | add (num x, num y): 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    GC::get_default_gc().set_initial_heap_size(2*1024*1024);
  66
  67    int n;
  68    cout << "This simple benchmark tests the efficiency of rewriting\n"
  69            "by computing the Fibonacci numbers with a naive, exponential\n"
  70            "algorithm.  The goal is to stress the pattern matching and\n"
  71            "term replacement facilities.\n"
  72            "Please input a small non-negative number(0-25): " << flush;
  73    cin >> n;
  74    Fib F;
  75    EXP x = fib(num(n));
  76    F(x);
  77    cout << "fib(" << n << ") = " << x << '\n';
  78    cout << "Number of replacements = " << F.number_of_rewrites() << '\n';
  79    return 0;
  80 }