Re: [Haskell-cafe] An issue with EDSLs in the ``finally tagless'' tradition

24 Sep 2009

      Luke,

On Wed, Sep 23, 2009 at 11:12 PM, Luke Palmer  wrote:
...
On Wed, Sep 23, 2009 at 7:59 PM, Brad Larsen  wrote:
...
The trouble comes in when defining a more general arithmetic
expression type class.  Suppose we want polymorphic arithmetic
expressions:
...
class PolyArithExpr exp where
  constant :: a     -> exp a
  addP     :: exp a -> exp a -> exp a
We then try to define an evaluator:
...
-- instance PolyArithExpr E where
--   constant   = E
--   addP e1 e2 = E (eval e1 + eval e2)  -- bzzt!
The instance definition for `addP' is not type correct:
   Could not deduce (Num a) from the context ()
     arising from a use of `+' at /home/blarsen/mail.lhs:42:20-36
One way to remedy this is to change the class definition of
PolyArithExpr so that `addP' has a Num constraint on `a':
...
class PolyArithExprFixed exp where
  pae_constant :: a -> exp a
  pae_add      :: Num a => exp a -> exp a -> exp a
which allows us to define an evaluator:
...
instance PolyArithExprFixed E where
  pae_constant = E
  pae_add e1 e2 = E (eval e1 + eval e2)
I find this ``fix'' lacking, however: to define a new interpretation
of the EDSL, we may be forced to change the DSL definition.  This is
non-modular, and seems like an instance of the expression
problem. (There may be a multiparameter type class solution for this.)
I don't know what you expect from pae_add, such that it could "add" a
couple of a's without knowing anything about them.  Don't think of Num
as a implementation detail, think of it as information about that a.
An implementation which adds another typeclass constraint is requiring
too much information, and either the implementation is undefinable
(that happens, but it's always for a good reason), or the interface is
weaker than you wrote.
I don't know what kind of implementation would add another constraint
on a.  Are you referring maybe to a specialized interpreter for
Integer math?  Well, if this is truly a polymorphic type that needs a
constructor class, there could be some non-Integer math in the middle
somewhere, and your interpreter would be incorrect.
I would like to see an example of this unmodularity, making use of the
polymorphism, so I can understand what you're asking better.
Luke
To elaborate a point I mentioned in my original email, and discussed
in ``Unembedding Domain-Specific Languages'' by Atkey, Lindley, and
Yallop: EDSLs defined using type classes in this way can be freely
combined, and so you can cobble together an EDSL from several smaller EDSLs.

For example, we can define an EDSL for boolean expressions:

    class BooleanExpr exp where
      true  :: exp Bool
      false :: exp Bool
      cond  :: exp Bool -> exp a -> exp a -> exp a
      (&&*) :: exp Bool -> exp Bool -> exp Bool
      (||*) :: exp Bool -> exp Bool -> exp Bool

      infixr 3 (&&*)
      infixr 2 (||*)

Then, combined with PolyArithExprFixed, we can define an EDSL
supporting polymorphic arithmetic and boolean expressions, as well as
an evaluator for this language.  (I've repeated the PolyArithExprFixed
and previous evaluator stuff for reference.)

    class PolyArithExprFixed exp where
      pae_constant :: a -> exp a
      pae_add      :: Num a => exp a -> exp a -> exp a

    class (BooleanExpr exp, PolyArithExprFixed exp) => BoolArithExpr exp

    -- a well-typed evaluator
    newtype E a = E { unE :: a }

    instance BooleanExpr E where
      true       = E True
      false      = E False
      cond p t f = if unE p then t else f
      e1 &&* e2  = E (unE e1 && unE e2)
      e1 ||* e2  = E (unE e1 || unE e2)

    instance PolyArithExprFixed E where
      pae_constant  = E
      pae_add e1 e2 = E (unE e1 + unE e2)

A simple test case, combining boolean expressions and arithmetic expressions:

    test1 = cond (true &&* false)
                 (pae_constant 0)
                 (pae_add (pae_constant 22) (pae_constant 20))
    -- unE test1 <===> 42

Sincerely,
Brad Larsen