initial
[prop.git] / tests / test_gc10.pcc
blobe22ab8071869a1e8f8e8a39bf3959c2a99d8959e
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>
8 MarkSweepGC marksweep_gc;
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.
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                                     ;
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.
31 instantiate datatype EXP;
34 //  Define a method that prints an expression.  This is a simple
35 //  inductive definition
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    }
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.   
59 //  In this example it involves only the datatype EXP.
61 rewrite class Simplify (EXP)
62 {  // nothing here for now.
63 public:
64    Simplify() {}
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).
71 //  In this brief sample class we have some rules that perform 
72 //  simple constant folding and strength reduction.
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.
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); 
98 //  Now defines the function that uses all this stuff.
100 void do_my_stuff()
102    //
103    // Instantiate a rewriting class 
104    //
105    Simplify sim;
106    EXP t1, term, term2;
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);
117       //
118       //  Rewrite the big term above.
119       // 
120       // cout << "Before: " << term << '\n';
121       sim(term);
122       // cout << "After: " << term << '\n';
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';
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    }
141 int main()
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;