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