Simplifying Expressions

Pt04
----+++ Expression Language

1) Develop a syntax definition Exp.sdf for a language of arithmetic and boolean expressions using
at least the following operators: 
<verbatim>
  + - * / ** % 
  > < <= >= != == 
  ! & |
</verbatim>
Use the standard rules for priority and associativity. Furthermore, the language should have
identifiers (variables), integer constants, and boolean constants.

2) Write a number of files with example expressions.

3) Derive a signature for the abstract syntax of the language from the syntax definition. (The makefile in the skeleton package should already take care of this.

4) Derive a default pretty-printer from the syntax definition and annotate it with box expressions to produce pretty output.

-----+++ Simplification of Expressions

5) Write a simplifier for expressions using rewrite rules and innermost rewriting in module =simplify=.

6) Write tests for simplification and evaluate the results using the 'make check' target.

-----+++ Concrete Syntax

7) Write another version of the simplifier implemented using concrete syntax instead of abstract syntax.

-----+++ Assesment

The assignment will be judged by feeding the simplifier a couple of complex expressions according
to the following criteria:

   * the expression should be parsed correctly 
   * its should be transformed to an expression that has the same meaning, i.e., for any assignment of values to variables the original and the result should retain the same value
   * the result should be pretty-printed correctly
   * it should be as simple as possible, i.e., any computations that can be done, have been done, and expensive operations have been replaced with less expensive operations, e.g., multiplication by addition; this is a flexible criterion