Algebraic Expression Languages   [2]

Abstracting out operator representations

We can increase the modularity of our expression type by abstracting out a separate type of symbols (here the enumerated type AOp) for the operators used in the expressions. Note the use of a generalized ternary Bop constructor (for "binary operator") which now must be applied to an operator symbol before it is applied to the representations of its left and right sub-expressions.

This generalization is the first step of several which will result in a more flexible and reusable type.

data Expr = Lit Int | Add Expr Expr | Mul Expr Expr



eval (Lit k) = k
eval (Add s t) = eval s + eval t
eval (Mul s t) = eval s * eval t

t = Add (Lit 2) (Mul (Lit 3) (Lit 5))

data Expr = Lit Int | Bop AOp Expr Expr

data AOp = Add | Mul

eval (Lit k) = k
eval (Bop Add s t) = eval s + eval t
eval (Bop Mul s t) = eval s * eval t

t  = Bop Add (Lit 2) (Bop Mul (Lit 3) (Lit 5))

t' = Lit 2 + (Lit 3 * Lit 5)  where (+) = Bop Add
                                    (*) = Bop Mul

Notes

• note that the patterns on the left-hand side of the evaluation function must be modified in a minimal way, to include the extra Bop constructor (the sample tree must also be extended)
• we can ameliorate the excessive syntax required to write out terms by making suitable abbreviations; these can be especially readable if we use an infix syntax
• on the other hand, using this sort of syntax tends to blur the distinction between values in the meta-language and terms in the object language: tread with care!