Expressions and substitution

Starting with a representation of Boolean formulas, we'll gradually work up to representing more general expressions, then statements, then programs.

  1. Define an algebraic data type Exp to represent expressions including these features:

  2. Write a substitution function

     subst :: Exp -> Name -> Exp -> Exp

    where subst e' x e is pronounced e' is substituted for x in e.

  3. Write a function eval that evaluates an expression and produces a value. The type of eval should be discussed in class.

  4. Write a simplifier

     simplify :: Exp -> Maybe Exp

    which, if it can, returns a simpler version of its argument, and if it cannot, returns Nothing.

    Hint: find a way to reuse eval and other functions you may have already written.

Back to list of assignments