representation getting verbose...

Paul Hudak
Fri, 18 Oct 2002 12:09:59 -0400

> In Paul Hudak's SOE, I find a definition of expression:
> data Expr = C Float | V String | Expr :+ Expr | Expr :- Expr
>             | Expr :* Expr | Expr :/ Expr
> Now this is compelling, but sometimes, I might want to have a function
> that takes a variable only, not just any kind of expression.  I could
> write something like:
> typeOfVariable :: Expression -> Type
> typeOfVariable (V s) = ...
> _                    = error...
> But thats not very satisfying from a type-checking perspective.  So it
> makes sense to create a constructor:
> data Variable = VVariable String
> data Expr = C Float | V Variable | Expr :+ Expr
>              | Expr :- Expr  | Expr :* Expr | Expr :/ Expr
> and make typeOfVariable :: Variable -> Type.  But then when I want to
> match or create a variable expression, things are starting to get
> verbose:
> case expr of
>   C f -> ...
>   V (Variable (VVariable s)) -> ...
>   ...

I think you mean:

  case expr of
    C f -> ...
    V (VVariable s) -> ...

which is not quite as verbose.

> And if I want a still more accurate hierarchy, the construction and
> destruction of Variables can really become cumbersome.  For an
> interpreter I'm writing, I found myself writing a function
> "constructVarExpr :: String -> Expr" just to make it easier.  This all
> seems very inelegant, and I get the feeling that there's a better way
> to do this.
> Any suggestions on how I could better represent Expressions or
> Variables to keep the type-checking but decrease the verbosity?

I don't think that the problem is as bad as you make it out to be.  If
you adopt my use of short constructor names, then something like:

  data Var = Var String
  data Expr = C Float | V Var | Expr :+ Expr
               | Expr :- Expr  | Expr :* Expr | Expr :/ Expr

is quite concise, as is:

  case expr of
    C f       -> ...
    V (Var s) -> ...

Also I don't see the point of defining constructVarExpr since 
"constructVarExpr s" is not much clearer or shorter than "V (Var s)".

On the other hand, there are much deeper issues at play here regarding
the representation of a language with variables as a data type.  What I
did in my book was very simple, and the use of variables was only given
as an exercise (by the way, you left out the "Let" constructor, which
presuambly has the form "Let String Expr").  Ideally you will also want
to express polymorphism and properly-typed higher-order functions, which
gets into the use of "phantom types".  A more recent idea is to use
"higher-order abstract syntax", in which variables and functions of the
language being implemented (often called the "object language") are
modelled as variables and functions in the implementation language
(often called the "meta language"), i.e. Haskell.  For a good
explanation of this, see Morton Rhiger's paper "A simple take on typed
abstract syntax in Haskell-like languages" at:

Hope this helps,