tools/pretty/t.tex

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