tests/rewriting6.pcc

   1 /////////////////////////////////////////////////////////////////////////////
   2 //  This test implements a rewrite based simplifier for the abstract
   3 //  syntax of a toy imperative language.
   4 //  This test is the same as rewriting3 except that we are using
   5 //  topdown rules.
   6 //
   7 //  The test is quite elobarate and requires polymorphic datatypes to work
   8 //  correctly with garbage collection, pretty printing and rewriting.
   9 /////////////////////////////////////////////////////////////////////////////
  10 #include <iostream.h>
  11
  12 /////////////////////////////////////////////////////////////////////////////
  13 //  The following recursive type equations define the abstract syntax
  14 //  of our small language.
  15 //  ( Note: we define our own boolean type because not all C++ compilers
  16 //    have bool built-in yet. )
  17 /////////////////////////////////////////////////////////////////////////////
  18 datatype List<T> = #[]                             // a polymorphic list
  19                  | #[ T ... List<T> ]
  20
  21 and      BOOL    = False | True                    // a boolean type
  22
  23 and      Exp     = integer ( int )                 // integers
  24                  | real    ( double )              // real numbers
  25                  | string  ( char * )              // strings
  26                  | boolean ( BOOL )                // booleans
  27                  | binop   ( BinOp, Exp, Exp )     // binary op expression
  28                  | unaryop ( UnaryOp, Exp )        // unary op expression
  29                  | var     ( Id )                  // variables
  30                  | no_exp
  31                  | om_exp
  32
  33 and      BinOp   = add | sub | mul | divide | mod  // binary operators
  34                  | logical_and | logical_or
  35                  | eq  | ge | le | lt | gt | ne
  36
  37 and      UnaryOp = uminus | logical_not            // unary operators
  38
  39 and      Stmt    = assign_stmt ( Id, Exp )                // assignments
  40                  | while_stmt  ( Exp, Stmt )              // while statements
  41                  | if_stmt     ( Exp, Stmt, Stmt )        // if statements
  42                  | print_stmt  ( Exp )                    // print statements
  43                  | block_stmt  ( List<Decl>, List<Stmt> ) // blocks
  44                  | skip_stmt
  45
  46 and      Type    = primitive_type ( Id )                  // type expressions
  47                  | pointer_type   ( Type )
  48                  | array_type     { element : Type, bound : Exp }
  49                  | function_type  { args : Type, range : Type }
  50                  | tuple_type     ( List<Type> )
  51                  | record_type    ( List<LabeledType> )
  52
  53 and      Decl    = decl { name : Id, typ : Type }        // declarations
  54
  55 and  LabeledType = labeled_type (Id, Type)               // labeled types
  56
  57 where type Id    = const char *
  58 ;
  59
  60 /////////////////////////////////////////////////////////////////////////////
  61 //  Refine the implementation of the datatypes.
  62 //  The qualifiers may be also declared in the datatype definition.
  63 //  We qualify the datatypes here so that they won't clutter up
  64 //  the equations above.
  65 //
  66 //  All types are declared to be garbage collectable, printable by
  67 //  the printer method and rewritable.
  68 /////////////////////////////////////////////////////////////////////////////
  69 refine List<T>     :: collectable printable rewrite
  70 and    BOOL        :: collectable printable rewrite
  71 and    Exp         :: collectable printable rewrite
  72 and    BinOp       :: collectable printable rewrite
  73 and    UnaryOp     :: collectable printable rewrite
  74 and    Stmt        :: collectable printable rewrite
  75 and    Type        :: collectable printable rewrite
  76 and    Decl        :: collectable printable rewrite
  77 and    LabeledType :: collectable printable rewrite
  78
  79 /////////////////////////////////////////////////////////////////////////////
  80 //  Specify the pretty printing formats.
  81 /////////////////////////////////////////////////////////////////////////////
  82 and printable
  83     False          => "false"
  84   | True           => "true"
  85   | integer        => _
  86   | real           => _
  87   | string         => "\"" _ "\""
  88   | var            => _
  89   | boolean        => _
  90   | binop          => "(" 2 1 3 ")"  // reorder the arguments
  91   | unaryop        => "(" _ _")"
  92   | add            => "+"
  93   | sub            => "-"
  94   | mul            => "*"
  95   | divide         => "/"
  96   | mod            => "mod"
  97   | logical_and    => "and"
  98   | logical_or     => "or"
  99   | eq             => "="
 100   | ne             => "<>"
 101   | gt             => ">"
 102   | lt             => "<"
 103   | ge             => ">="
 104   | le             => "<="
 105   | uminus         => "-"
 106   | logical_not    => "not"
 107   | assign_stmt    => _ ":=" _ ";"
 108   | while_stmt     => "while" _ "do" { _ } "end while;"
 109   | if_stmt        => "if" _ " then" { _ } "else" { _ } "endif;"
 110   | print_stmt     => "print" _ ";"
 111   | block_stmt     => "begin" { _ / _ } "end"
 112   | primitive_type => _
 113   | pointer_type   => _ "^"
 114   | array_type     => "array" bound "of" element
 115   | function_type  => args "->" range
 116   | decl           => "var" name ":" typ ";"
 117   | labeled_type   => _ ":" _
 118   | #[]            => ""
 119   | #[...]         => _ / _
 120   ;
 121
 122 /////////////////////////////////////////////////////////////////////////////
 123 //  Generate the interfaces to instantiated polymorphic datatypes.
 124 //  These are not strictly necessary since the instantiation is in the
 125 //  same file below.  However, in general the 'instantiate extern' declaration
 126 //  must be placed in the .h files for each instance of a polymorphic
 127 //  datatype.
 128 /////////////////////////////////////////////////////////////////////////////
 129 instantiate extern datatype
 130    List<Type>, List<Stmt>, List<LabeledType>, List<Decl>;
 131
 132 /////////////////////////////////////////////////////////////////////////////
 133 //  Now instantiate all the datatypes.
 134 //  As specified in the definition, garbage collector type info and
 135 //  pretty printers will be generated automatically.
 136 /////////////////////////////////////////////////////////////////////////////
 137 instantiate datatype Exp, BOOL, BinOp, UnaryOp, Stmt, Type, Decl, LabeledType,
 138                      List<Type>, List<Stmt>, List<LabeledType>, List<Decl>;
 139
 140 /////////////////////////////////////////////////////////////////////////////
 141 //  Defines the interface of a rewrite class Simplify.
 142 //  All types that are referenced (directly or indirectly) should be
 143 //  declared in the interface.
 144 /////////////////////////////////////////////////////////////////////////////
 145 rewrite class Simplify
 146    ( Exp, BOOL, BinOp, UnaryOp, Stmt, Type, Decl, LabeledType,
 147      List<Decl>, List<Stmt>, List<Type>, List<LabeledType>
 148    )
 149 {
 150    // Method to print an error message
 151    void error(const char message[]) { cerr << message << '\n'; }
 152 public:
 153    Simplify() {}
 154 };
 155
 156 /////////////////////////////////////////////////////////////////////////////
 157 //  Now defines the rewrite rules.  These rules will be compiled into
 158 //  efficient pattern matching code by the translator.  A real life
 159 //  system will probably have many more rules than presented here.
 160 //  (A machine code generator usually needs a few hundred rules)
 161 //  Currently there are about 60 rules in this class.
 162 /////////////////////////////////////////////////////////////////////////////
 163 rewrite Simplify
 164 {
 165 topdown:
 166    // Type coercion rules from integer -> real
 167    binop(some_op, integer x, real y): rewrite(binop(some_op,real(x),real(y)));
 168 |  binop(some_op, real x, integer y): rewrite(binop(some_op,real(x),real(y)));
 169
 170    // Constant folding rules for integers and reals.
 171 |  binop(add,    integer x, integer y): rewrite(integer(x + y));
 172 |  binop(sub,    integer x, integer y): rewrite(integer(x - y));
 173 |  binop(mul,    integer x, integer y): rewrite(integer(x * y));
 174 |  binop(divide, integer x, integer 0): { error("division by zero"); }
 175 |  binop(divide, integer x, integer y): rewrite(integer(x / y));
 176 |  binop(mod,    integer x, integer 0): { error("modulo by zero"); }
 177 |  binop(mod,    integer x, integer y): rewrite(integer(x % y));
 178 |  binop(add,    real x,    real y):    rewrite(real(x + y));
 179 |  binop(sub,    real x,    real y):    rewrite(real(x - y));
 180 |  binop(mul,    real x,    real y):    rewrite(real(x * y));
 181 |  binop(divide, real x,    real 0.0):  { error("division by zero"); }
 182 |  binop(divide, real x,    real y):    rewrite(real(x / y));
 183 |  unaryop(uminus, integer x):          rewrite(integer(-x));
 184 |  unaryop(uminus, real    x):          rewrite(real(-x));
 185
 186 // Constant folding rules for relational operators
 187 |  binop(eq,  integer x, integer y):    rewrite(boolean((BOOL)(x == y)));
 188 |  binop(ne,  integer x, integer y):    rewrite(boolean((BOOL)(x != y)));
 189 |  binop(gt,  integer x, integer y):    rewrite(boolean((BOOL)(x > y)));
 190 |  binop(lt,  integer x, integer y):    rewrite(boolean((BOOL)(x < y)));
 191 |  binop(ge,  integer x, integer y):    rewrite(boolean((BOOL)(x >= y)));
 192 |  binop(le,  integer x, integer y):    rewrite(boolean((BOOL)(x <= y)));
 193 |  binop(eq,  real x,    real y):       rewrite(boolean((BOOL)(x == y)));
 194 |  binop(ne,  real x,    real y):       rewrite(boolean((BOOL)(x != y)));
 195 |  binop(gt,  real x,    real y):       rewrite(boolean((BOOL)(x > y)));
 196 |  binop(lt,  real x,    real y):       rewrite(boolean((BOOL)(x < y)));
 197 |  binop(ge,  real x,    real y):       rewrite(boolean((BOOL)(x >= y)));
 198 |  binop(le,  real x,    real y):       rewrite(boolean((BOOL)(x <= y)));
 199
 200 // Constant folding rules for boolean operators
 201 |  binop(logical_and, boolean x, boolean y):  rewrite(boolean((BOOL)(x && y)));
 202 |  binop(logical_or,  boolean x, boolean y):  rewrite(boolean((BOOL)(x || y)));
 203 |  unaryop(logical_not, boolean x):           rewrite(boolean((BOOL)(! x)));
 204
 205 // Simple algebraic laws for integers
 206 |  binop(add, integer 0, x        ):  rewrite(x);
 207 |  binop(add, x,         integer 0):  rewrite(x);
 208 |  binop(sub, x,         integer 0):  rewrite(x);
 209 |  binop(mul, integer 0, x        ):  rewrite(integer(0));
 210 |  binop(mul, x,         integer 0):  rewrite(integer(0));
 211 |  binop(mul, integer 1, x        ):  rewrite(x);
 212 |  binop(mul, x,         integer 1):  rewrite(x);
 213 |  binop(divide, x,      integer 1):  rewrite(x);
 214
 215 // Simple algebraic laws for reals
 216 |  binop(add, real 0.0, x        ):  rewrite(x);
 217 |  binop(add, x,         real 0.0):  rewrite(x);
 218 |  binop(sub, x,         real 0.0):  rewrite(x);
 219 |  binop(mul, real 0.0, x        ):  rewrite(real(0.0));
 220 |  binop(mul, x,         real 0.0):  rewrite(real(0.0));
 221 |  binop(mul, real 1.0, x        ):  rewrite(x);
 222 |  binop(mul, x,         real 1.0):  rewrite(x);
 223 |  binop(divide, x,      real 1.0):  rewrite(x);
 224 // more ...
 225
 226 // Simple strength reduction (assume CSE will be applied)
 227 |  binop(mul, integer 2, x        ):  rewrite(binop(add,x,x));
 228 |  binop(mul, x, integer 2        ):  rewrite(binop(add,x,x));
 229 // more ...
 230
 231 // Simple boolean identities
 232 |  binop(logical_and, boolean False, _): rewrite(boolean(False));
 233 |  binop(logical_and, boolean True, b):  rewrite(b);
 234 |  binop(logical_and, _, boolean False): rewrite(boolean(False));
 235 |  binop(logical_and, b, boolean True):  rewrite(b);
 236 |  binop(logical_or,  boolean True, _):  rewrite(boolean(True));
 237 |  binop(logical_or,  boolean False, b): rewrite(b);
 238 |  binop(logical_or,  _, boolean True):  rewrite(boolean(True));
 239 |  binop(logical_or,  b, boolean False): rewrite(b);
 240 // more ...
 241
 242 // The following rules eliminate unreachable statements.
 243 |  if_stmt(boolean True, a, _):          rewrite(a);
 244 |  if_stmt(boolean False, _, b):         rewrite(b);
 245 |  #[while_stmt(boolean False, _) ... continuation]:
 246                                          rewrite(continuation);
 247 // more ...
 248 };
 249
 250 /////////////////////////////////////////////////////////////////////////////
 251 //  The main program.
 252 //  We'll test it with a simple program.
 253 /////////////////////////////////////////////////////////////////////////////
 254 int main()
 255 {
 256    // Instantiate a rewriting object.
 257    Simplify simplify;
 258
 259    // The input is the following block:
 260    //
 261    //  var x : int;
 262    //  var y : int;
 263    //  var z : array [10 * 30] of int;
 264    //  begin
 265    //     x = 0 + y * 1;
 266    //     while (1 <> 1) y := y + 1;
 267    //     print (not false);
 268    //  end
 269    //
 270    Stmt prog =
 271       block_stmt( #[ decl("x", primitive_type("integer")),
 272                      decl("y", primitive_type("integer")),
 273                      decl("z", array_type(primitive_type("integer"),
 274                                   binop(mul,integer(10), integer(30))
 275                                          )
 276                          )
 277                   ],
 278                   #[
 279                    assign_stmt("x",
 280                       binop(add,integer(0),
 281                          binop(mul,var("y"),integer(1)))),
 282                    while_stmt(binop(ne, integer(1), integer(1)),
 283                               assign_stmt("y",
 284                                  binop(add,var("y"),integer(1)))),
 285                    print_stmt(unaryop(logical_not,boolean(False)))
 286                   ]
 287                 );
 288    cout << "Before:\n" << prog << "\n\n";
 289    simplify(prog);
 290    cout << "After:\n"  << prog << "\n";
 291    return 0;
 292 }