Algebraic Expression Languages [3]

Parameterizing the type definition

As a next step toward making the expression type more general and reusable, we can abstract out some more of the structure into parameters of the type definition. The new declaration of Expr on the right takes two type parameters, a and b, and defines the new type in terms of these. In some sense, then, Expr becomes a function from types to types, taking two type arguments and returning a "fully instantiated" type result.

What does this buy us? Now we can use different instantiations of Expr to capture expression types with different base-case literals and with different sets of operator symbols. For example, we might want to use Strings to represent literal numerals, or even the Peano-style natural numbers from the previous lecture. (In some sense, it is more precise to use a type which doesn't allow much slop, and more honest to use one which is not so gifted with functionality by the meta-language that it becomes too transparent.) We might also represent operators by Strings or Chars, but for similar reasons we choose to use an enumerated type for these.

Once we have made this generalization, we can more esily switch between various "carrier" types for the literal or operator symbols. We can also reuse the expression type for Boolean expressions or for any expression language with binary operators and literals representing some other semantic domain.

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))

data Expr a b = Lit a | Bop b (Expr a b) (Expr a b)

data AOp = Add | Mul
data BOp = And | Or | Xor | Nand | Nor

type AExp = Expr Int  AOp
type BExp = Expr Bool BOp

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))

Notes

note that when we "upgrade" the expression type to include parameters, we must also include the parameters in the recursive uses of the type on the right-hand side of the declaration
interestingly, the definition of the eval function and the sample tree don't change: the inferred types are different, but the code remains the same: this shows that the change is giving us more flexibility at compile time, but that we needn't pay any real price for it at run-time
the type definitions introduced by the type keyword are in some sense just abbreviations: they don't introduce any new constructors, and in fact they are resolved during type-checking
furthermore, these type abbreviations aren't at all necessary: everything would work out the same without them, they just provide a kind of documentation of intent and short-hand for when we need to write types out explicitly