tests/test_gc3.pcc

   1 //
   2 //  Testing garbage collection with the rewriting features.
   3 //  This test is created by modifying rewriting.pcc in this directory
   4 //
   5 #include <iostream.h>
   6
   7 //
   8 //  Define an algebraic datatype.  Currently, rewriting can only be
   9 //  performed on datatypes(and not views) in Prop.
  10 //  If replacement is to be performed on a datatype, then it should
  11 //  be declared using the ``rewrite'' qualifier.
  12 //  In this example, we'll use garbage collection with rewriting.
  13 //
  14 datatype EXP :: collectable rewrite = om
  15                                     | num (int)
  16                                     | var (char)
  17                                     | add (EXP, EXP)
  18                                     | sub (EXP, EXP)
  19                                     | mul (EXP, EXP)
  20                                     | div (EXP, EXP)
  21                                     ;
  22
  23 //
  24 //  Datatype instantiation generates any additional methods and definitions.
  25 //  In this case garbage collection tracing methods are generated.
  26 //  As always, this should be placed in an implementation file.
  27 //
  28 instantiate datatype EXP;
  29
  30 //
  31 //  Define a method that prints an expression.  This is a simple
  32 //  inductive definition
  33 //
  34 ostream& operator << (ostream& f, EXP e)
  35 {  match (e) {
  36       om:       { return f << "om"; }
  37    |  num i:    { return f << i; }
  38    |  var v:    { return f << v; }
  39    |  add(a,b): { return f << '(' << a << " + " << b << ')'; }
  40    |  sub(a,b): { return f << '(' << a << " - " << b << ')'; }
  41    |  mul(a,b): { return f << '(' << a << " * " << b << ')'; }
  42    |  div(a,b): { return f << '(' << a << " / " << b << ')'; }
  43    }
  44 }
  45
  46 //
  47 //  Define the interface to a ``rewriting class.''  A rewriting class
  48 //  is simply a C++ class with rewriting rules attached.  In real programs
  49 //  this definition should be placed in some definition (i.e. .ph) files.
  50 //
  51 //  In parenthesis, we must list all datatypes involved.   Unlike
  52 //  simple pattern matching, rewriting can involve a set of mutually
  53 //  recursive (or mutually exclusive, if desired) datatype definitions.
  54 //  So in general this is a comma delimited list.
  55 //
  56 //  In this example it involves only the datatype EXP.
  57 //
  58 rewrite class Simplify (EXP)
  59 {  // nothing here for now.
  60 public:
  61    Simplify() {}
  62 };
  63
  64 //
  65 //  Now we define the rewriting rules in the rewriting class Simplify.  These
  66 //  rules should be placed in an implementation file (.pcc, .pC, .pc++ etc).
  67 //
  68 //  In this brief sample class we have some rules that perform
  69 //  simple constant folding and strength reduction.
  70 //
  71 //  Currently, all the rules for a rewrite class must be placed in
  72 //  the same rewrite construct.  This will probably change in the future
  73 //  once I work out the details on incremental tree automata compilation.
  74 //
  75 rewrite Simplify {
  76    add (num 0, x):                    rewrite(x);
  77 |  add (x, num 0):                    rewrite(x);
  78 |  sub (x, num 0):                    rewrite(x);
  79 |  mul (x, num 0):                    rewrite(num(0));
  80 |  mul (num 0, x):                    rewrite(num(0));
  81 |  mul (x, num 1):                    rewrite(x);
  82 |  mul (num 1, x):                    rewrite(x);
  83 |  mul (x, num 2):                    rewrite(add(x,x));
  84 |  mul (num 2, x):                    rewrite(add(x,x));
  85 |  div (x, num 1):                    rewrite(x);
  86 |  add (num x, num y):                rewrite(num(x + y));
  87 |  sub (num x, num y):                rewrite(num(x - y));
  88 |  mul (num x, num y):                rewrite(num(x * y));
  89 |  div (num x, num y) where (y != 0): rewrite(num(x / y));
  90 |  div (_, num 0):                    { /* cout << "Division by zero!\n"; */ }
  91 |  div (zero as num 0, x):            rewrite(zero);
  92 };
  93
  94 //
  95 //  Now defines the function that uses all this stuff.
  96 //
  97 void do_my_stuff()
  98 {
  99    //
 100    // Instantiate a rewriting class
 101    //
 102    Simplify sim;
 103    EXP t1, term, term2;
 104
 105    for (int trials = 1; trials < 10000; trials++) {
 106       //
 107       // (0 + x * 2) / (1 * 5 + 1 * 3) / (0 / y);
 108       //
 109       t1 = div(div(add(num(0), mul(var('x'),num(2))),
 110                    add(mul(num(1), num(5)),mul(num(1),num(3)))),
 111                div(num(0),var('y')));
 112       term = mul(t1,t1);
 113
 114       //
 115       //  Rewrite the big term above.
 116       //
 117       // cout << "Before: " << term << '\n';
 118       sim(term);
 119       // cout << "After: " << term << '\n';
 120
 121       //
 122       //  Rewrite it again.  It should have no effect since the term
 123       //  is already in normal form.
 124       //
 125       sim(term);
 126       // cout << "Again (should have no effect): " << term << '\n';
 127
 128       //
 129       //  Rewrite some other term.
 130       //
 131       term2 = add(sub(num(3),num(3)), var('z'));
 132       // cout << "Before: " << term2 << '\n';
 133       sim(term2);
 134       // cout << "After: " << term2 << '\n';
 135    }
 136 }
 137
 138 int main()
 139 {
 140    cout << "Now performing some rewrites and generating some garbage.\n"
 141            "(See also the test 'test_rc1')\n" << flush;
 142    // GC::get_default_gc().set_verbosity(0);
 143    do_my_stuff();
 144    cout << "Finished.  Now I'll force one more GC to clean up.\n"
 145            "There should be at most a few kilobytes of retention at the end.\n"
 146            "The GC should be able to recognized a large part of the heap as\n"
 147            "garbage.  See below:\n";
 148    // GC::get_default_gc().set_verbosity(1);
 149    GC::garbage_collect();
 150    if (GC::get_default_gc().statistics().bytes_used <= 1024)
 151       cout << "Seems like it's working well for your platform.   Lucky dog!\n";
 152    return 0;
 153 }