initial
[prop.git] / prop-src / T9.pcc
blob6da75344b35e5b89532fd20c1360191e5bcc27ba
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>
8 //////////////////////////////////////////////////////////////////////////////
9 //  Datatype EXP denotes an expression. 
10 //////////////////////////////////////////////////////////////////////////////
11 datatype EXP :: collectable =
12    num (int)       => _
13 |  fib (EXP)       => "fib " _
14 |  add (EXP, EXP)  => "(" _ "+" _ ")"
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() {}
28    inline int number_of_rewrites() const { return rewrites; }
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. 
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)
47 //////////////////////////////////////////////////////////////////////////////
48 //  Instantiate the datatype
49 //////////////////////////////////////////////////////////////////////////////
50 instantiate datatype EXP;
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);
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;