tools/pretty/test.tex

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