prop-src/T9.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.4),
   3 //  last updated on Mar 31, 1997.
   4 //  The original source file is "T9.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_REWRITING_USED
   8 #define PROP_GARBAGE_COLLECTION_USED
   9 #define PROP_PRINTER_USED
  10 #define PROP_QUARK_USED
  11 #include <propdefs.h>
  12 #line 1 "T9.pcc"
  13 //////////////////////////////////////////////////////////////////////////////
  14 //  This program tests rewriting and garbage collection by using
  15 //  the rewriting mechanism to compute the Fibonacci number the hard way.
  16 //////////////////////////////////////////////////////////////////////////////
  17 #include <iostream>
  18 #include <AD/gc/gcobject.h>
  19
  20 //////////////////////////////////////////////////////////////////////////////
  21 //  Datatype EXP denotes an expression.
  22 //////////////////////////////////////////////////////////////////////////////
  23 #line 11 "T9.pcc"
  24 #line 15 "T9.pcc"
  25 ///////////////////////////////////////////////////////////////////////////////
  26 //
  27 // Forward class definition for EXP
  28 //
  29 ///////////////////////////////////////////////////////////////////////////////
  30 #ifndef datatype_EXP_defined
  31 #define datatype_EXP_defined
  32    class a_EXP;
  33    typedef a_EXP * EXP;
  34 #endif
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37 //
  38 // Base class for datatype EXP
  39 //
  40 ///////////////////////////////////////////////////////////////////////////////
  41 class a_EXP : public GCObject {
  42 public:
  43    enum Tag_EXP {
  44       tag_num = 0, tag_fib = 1, tag_add = 2
  45    };
  46
  47 public:
  48    const Tag_EXP tag__; // variant tag
  49 protected:
  50    inline a_EXP(Tag_EXP t__) : tag__(t__) {}
  51 public:
  52    inline virtual ~a_EXP()
  53    {
  54    }
  55    ////////////////////////////////////////////////////////////////////////////
  56    //
  57    // Method for garbage collection tracing
  58    //
  59    ////////////////////////////////////////////////////////////////////////////
  60 protected:
  61    virtual void trace(GC *);
  62 public:
  63 };
  64 inline int boxed(const a_EXP *) { return 1; }
  65 inline int untag(const a_EXP * x) { return x->tag__; }
  66 ///////////////////////////////////////////////////////////////////////////////
  67 //
  68 //  Pretty printing methods for EXP
  69 //
  70 ///////////////////////////////////////////////////////////////////////////////
  71 class PrettyOStream;
  72 extern std::ostream& operator<<(std::ostream&, EXP);
  73 extern PrettyOStream& operator<<(PrettyOStream&, EXP);
  74 ///////////////////////////////////////////////////////////////////////////////
  75 //
  76 // Class for datatype constructor EXP::num
  77 //
  78 ///////////////////////////////////////////////////////////////////////////////
  79 class EXP_num : public a_EXP {
  80 public:
  81 #line 11 "T9.pcc"
  82    int num;
  83    inline EXP_num (int x_num)
  84     : a_EXP(tag_num), num(x_num)
  85    {
  86    }
  87    inline ~EXP_num()
  88    {
  89    }
  90    ////////////////////////////////////////////////////////////////////////////
  91    //
  92    // Method for garbage collection tracing
  93    //
  94    ////////////////////////////////////////////////////////////////////////////
  95 protected:
  96    virtual void trace(GC *);
  97 public:
  98 };
  99
 100 ///////////////////////////////////////////////////////////////////////////////
 101 //
 102 // Class for datatype constructor EXP::fib
 103 //
 104 ///////////////////////////////////////////////////////////////////////////////
 105 class EXP_fib : public a_EXP {
 106 public:
 107 #line 12 "T9.pcc"
 108    EXP fib;
 109    inline EXP_fib (EXP x_fib)
 110     : a_EXP(tag_fib), fib(x_fib)
 111    {
 112    }
 113    inline ~EXP_fib()
 114    {
 115    }
 116    ////////////////////////////////////////////////////////////////////////////
 117    //
 118    // Method for garbage collection tracing
 119    //
 120    ////////////////////////////////////////////////////////////////////////////
 121 protected:
 122    virtual void trace(GC *);
 123 public:
 124 };
 125
 126 ///////////////////////////////////////////////////////////////////////////////
 127 //
 128 // Class for datatype constructor EXP::add
 129 //
 130 ///////////////////////////////////////////////////////////////////////////////
 131 class EXP_add : public a_EXP {
 132 public:
 133 #line 13 "T9.pcc"
 134    EXP _1; EXP _2;
 135    inline EXP_add (EXP x_1, EXP x_2)
 136     : a_EXP(tag_add), _1(x_1), _2(x_2)
 137    {
 138    }
 139    inline ~EXP_add()
 140    {
 141    }
 142    ////////////////////////////////////////////////////////////////////////////
 143    //
 144    // Method for garbage collection tracing
 145    //
 146    ////////////////////////////////////////////////////////////////////////////
 147 protected:
 148    virtual void trace(GC *);
 149 public:
 150 };
 151
 152 ///////////////////////////////////////////////////////////////////////////////
 153 //
 154 // Datatype constructor functions for EXP
 155 //
 156 ///////////////////////////////////////////////////////////////////////////////
 157 inline a_EXP * num (int x_num)
 158 {
 159    return new EXP_num (x_num);
 160 }
 161 inline a_EXP * fib (EXP x_fib)
 162 {
 163    return new EXP_fib (x_fib);
 164 }
 165 inline a_EXP * add (EXP x_1, EXP x_2)
 166 {
 167    return new EXP_add (x_1, x_2);
 168 }
 169 ///////////////////////////////////////////////////////////////////////////////
 170 //
 171 // Downcasting functions for EXP
 172 //
 173 ///////////////////////////////////////////////////////////////////////////////
 174 inline EXP_num * _num(const a_EXP * _x_) { return (EXP_num *)_x_; }
 175 inline EXP_fib * _fib(const a_EXP * _x_) { return (EXP_fib *)_x_; }
 176 inline EXP_add * _add(const a_EXP * _x_) { return (EXP_add *)_x_; }
 177
 178 #line 15 "T9.pcc"
 179 #line 15 "T9.pcc"
 180
 181
 182 //////////////////////////////////////////////////////////////////////////////
 183 //  Defines the interface to a rewrite class.
 184 //  A private counter ``rewrite_count'' is encapsulated by the class
 185 //  mechanism.
 186 //////////////////////////////////////////////////////////////////////////////
 187 #line 22 "T9.pcc"
 188 #line 29 "T9.pcc"
 189 class Fib : public BURS {
 190 private:
 191    Fib(const Fib&);               // no copy constructor
 192    void operator = (const Fib&); // no assignment
 193 public:
 194    struct Fib_StateRec * stack__, * stack_top__;
 195 public:
 196    void labeler(const char *, int&, int);
 197    void labeler(Quark, int&, int);
 198           void  labeler(EXP & redex, int&, int);
 199    inline virtual void  operator () (EXP & redex) { int s; labeler(redex,s,0); }
 200 private:
 201 #line 22 "T9.pcc"
 202
 203    int rewrites;  // number of replacements performed during rewriting
 204    public:
 205    Fib() : rewrites(0) {}
 206    ~Fib() {}
 207
 208    inline int number_of_rewrites() const { return rewrites; }
 209 #line 29 "T9.pcc"
 210 };
 211 #line 29 "T9.pcc"
 212 #line 29 "T9.pcc"
 213
 214
 215
 216 //////////////////////////////////////////////////////////////////////////////
 217 //  Specifies the rewrite rules.  We'll use rewriting to compute
 218 //  addition also.  The algorithm is exponential in time and generates
 219 //  a lot of garbage in the process.
 220 //
 221 //  Notice that all private data within the rewrite class is visible within
 222 //  the rewrite rules.
 223 //////////////////////////////////////////////////////////////////////////////
 224 #line 40 "T9.pcc"
 225 #line 45 "T9.pcc"
 226 ///////////////////////////////////////////////////////////////////////////////
 227 //
 228 // This macro can be redefined by the user for debugging
 229 //
 230 ///////////////////////////////////////////////////////////////////////////////
 231 #ifndef DEBUG_Fib
 232 #define DEBUG_Fib(repl,redex,file,line,rule) repl
 233 #else
 234 static const char * Fib_file_name = "T9.pcc";
 235 #endif
 236
 237 static const TreeTables::Offset Fib_accept_base [ 4 ] = {
 238    0, 0, 1, 5
 239 };
 240 static const TreeTables::ShortRule Fib_accept_vector [ 7 ] = {
 241    -1, 0, 1, 2, -1, 3, -1
 242 };
 243 static const TreeTables::ShortState Fib_theta_1[2] = {
 244    0, 2
 245 };
 246
 247
 248 static const TreeTables::ShortState Fib_theta_2[2][2] = {
 249    { 0, 0 },
 250    { 0, 3 }
 251 };
 252
 253
 254 static const TreeTables::ShortState Fib_mu_1_0[4] = {
 255    0, 1, 0, 0
 256 };
 257
 258
 259 static const TreeTables::ShortState Fib_mu_2_0[4] = {
 260    0, 1, 0, 0
 261 };
 262
 263
 264 static const TreeTables::ShortState Fib_mu_2_1[4] = {
 265    0, 1, 0, 0
 266 };
 267
 268
 269 inline void  Fib::labeler(char const * redex,int& s__,int)
 270 {
 271    {
 272 s__ = 0;
 273    }
 274 }
 275
 276 inline void  Fib::labeler(Quark redex,int& s__,int)
 277 {
 278    {
 279 s__ = 0;
 280    }
 281 }
 282
 283 void  Fib::labeler (EXP & redex, int& s__, int r__)
 284 {
 285 replacement__:
 286    switch(redex->tag__) {
 287       case a_EXP::tag_num: {
 288          int s0__;
 289          s0__ = 0; // int
 290          s__ = 1;} break;
 291       case a_EXP::tag_fib: {
 292          int s0__;
 293          labeler(_fib(redex)->fib, s0__, r__);
 294          s__ = Fib_theta_1[Fib_mu_1_0[s0__]]; } break;
 295       default: {
 296          int s0__;
 297          int s1__;
 298          labeler(_add(redex)->_1, s0__, r__);
 299          labeler(_add(redex)->_2, s1__, r__);
 300          s__ = Fib_theta_2[Fib_mu_2_0[s0__]][Fib_mu_2_1[s1__]]; } break;
 301    }
 302    const TreeTables::ShortRule * o__ = Fib_accept_vector + Fib_accept_base[s__];
 303 accept__:
 304    switch (*o__) {
 305       case 3: {
 306 #line 44 "T9.pcc"
 307          { redex = DEBUG_Fib(num((_num(_add(redex)->_1)->num + _num(_add(redex)->_2)->num)),redex,Fib_file_name,44,"add (num x, num y): ...");
 308            r__ = 1; goto replacement__; }
 309 #line 45 "T9.pcc"
 310 } break;
 311       case 2: {
 312 #line 43 "T9.pcc"
 313          { redex = DEBUG_Fib(add(fib(num((_num(_fib(redex)->fib)->num - 1))),fib(num((_num(_fib(redex)->fib)->num - 2)))),redex,Fib_file_name,43,"fib num n: ...");
 314            r__ = 1; goto replacement__; }
 315 #line 44 "T9.pcc"
 316 } break;
 317       case 1: if ((_num(_fib(redex)->fib)->num == 1))
 318       {
 319 #line 42 "T9.pcc"
 320          { redex = DEBUG_Fib(_fib(redex)->fib,redex,Fib_file_name,42,"fib x as num _ | (_num(_fib(redex)->fib)->num == 1): ...");
 321            r__ = 1; goto replacement__; }
 322 #line 43 "T9.pcc"
 323 }
 324       else { ++o__; goto accept__; } break;
 325       case 0: if ((_num(_fib(redex)->fib)->num == 0))
 326       {
 327 #line 41 "T9.pcc"
 328          { redex = DEBUG_Fib(_fib(redex)->fib,redex,Fib_file_name,41,"fib x as num _ | (_num(_fib(redex)->fib)->num == 0): ...");
 329            r__ = 1; goto replacement__; }
 330 #line 42 "T9.pcc"
 331 }
 332       else { ++o__; goto accept__; } break;
 333    }
 334
 335 }
 336
 337 #line 45 "T9.pcc"
 338 #line 45 "T9.pcc"
 339
 340
 341 //////////////////////////////////////////////////////////////////////////////
 342 //  Instantiate the datatype
 343 //////////////////////////////////////////////////////////////////////////////
 344 #line 50 "T9.pcc"
 345 #line 50 "T9.pcc"
 346 ///////////////////////////////////////////////////////////////////////////////
 347 //
 348 // Interface specification of datatype EXP
 349 //
 350 ///////////////////////////////////////////////////////////////////////////////
 351 #line 50 "T9.pcc"
 352 ///////////////////////////////////////////////////////////////////////////////
 353 //
 354 // Pretty printing methods for EXP
 355 //
 356 ///////////////////////////////////////////////////////////////////////////////
 357 std::ostream& operator << (std::ostream& strm__, EXP  obj__);
 358 PrettyOStream& operator << (PrettyOStream& strm__, EXP  obj__);
 359
 360 ///////////////////////////////////////////////////////////////////////////////
 361 //
 362 // Instantiation of datatype EXP
 363 //
 364 ///////////////////////////////////////////////////////////////////////////////
 365 #line 50 "T9.pcc"
 366 void a_EXP::trace(GC * gc__)
 367 {
 368 }
 369
 370 ///////////////////////////////////////////////////////////////////////////////
 371 //
 372 // Pretty printing methods for EXP
 373 //
 374 ///////////////////////////////////////////////////////////////////////////////
 375 std::ostream& operator << (std::ostream& strm__, EXP  obj__)
 376 {  PrettyOStream S(strm__); S << obj__; return strm__; }
 377
 378 PrettyOStream& operator << (PrettyOStream& strm__, EXP  obj__)
 379 {
 380    switch (untag(obj__))
 381    {
 382       case 0:
 383          strm__ << _num(obj__)->num; // int
 384          break;
 385       case 1:
 386          strm__ << "fib ";
 387          strm__ << _fib(obj__)->fib; // EXP
 388          break;
 389       case 2:
 390          strm__ << '(';
 391          strm__ << _add(obj__)->_1; // EXP
 392          strm__ << '+';
 393          strm__ << _add(obj__)->_2; // EXP
 394          strm__ << ')';
 395          break;
 396    }
 397    return strm__;
 398 }
 399
 400 void EXP_num::trace(GC * gc__)
 401 {
 402    // call to method a_EXP::trace() has been optimized out
 403    // omitted int
 404 }
 405
 406 void EXP_fib::trace(GC * gc__)
 407 {
 408    // call to method a_EXP::trace() has been optimized out
 409    this->fib = (EXP )gc__->trace(this->fib); // EXP
 410 }
 411
 412 void EXP_add::trace(GC * gc__)
 413 {
 414    // call to method a_EXP::trace() has been optimized out
 415    this->_1 = (EXP )gc__->trace(this->_1); // EXP
 416    this->_2 = (EXP )gc__->trace(this->_2); // EXP
 417 }
 418
 419
 420
 421 #line 50 "T9.pcc"
 422 #line 50 "T9.pcc"
 423
 424
 425 //////////////////////////////////////////////////////////////////////////////
 426 //  Input a number and test the rewrite rules.
 427 //////////////////////////////////////////////////////////////////////////////
 428 int main()
 429 {
 430    ///////////////////////////////////////////////////////////////////////////
 431    //  Give ourselves some more memory (2Meg) to work with.
 432    //  The default heap size is only 128K.   Using a larger heap
 433    //  can drastically cut down the overhead of GC since almost all
 434    //  intermediate terms generated can be reclaimed.  With the copying
 435    //  garbage collecting scheme that we are using, the overhead of GC
 436    //  is proportional to the amount of live data, not the total heap size.
 437    ///////////////////////////////////////////////////////////////////////////
 438    GC::get_default_gc().set_initial_heap_size(2*1024*1024);
 439
 440    int n;
 441    cout << "This simple benchmark tests the efficiency of rewriting\n"
 442            "by computing the Fibonacci numbers with a naive, exponential\n"
 443            "algorithm.  The goal is to stress the pattern matching and\n"
 444            "term replacement facilities.\n"
 445            "Please input a small non-negative number(0-25): " << flush;
 446    cin >> n;
 447    Fib F;
 448    EXP x = fib(num(n));
 449    F(x);
 450    cout << "fib(" << n << ") = " << x << '\n';
 451    cout << "Number of replacements = " << F.number_of_rewrites() << '\n';
 452    return 0;
 453 }
 454 #line 81 "T9.pcc"
 455 /*
 456 ------------------------------- Statistics -------------------------------
 457 Merge matching rules         = yes
 458 Number of DFA nodes merged   = 0
 459 Number of ifs generated      = 0
 460 Number of switches generated = 0
 461 Number of labels             = 0
 462 Number of gotos              = 0
 463 Adaptive matching            = disabled
 464 Fast string matching         = disabled
 465 Inline downcasts             = disabled
 466 --------------------------------------------------------------------------
 467 */