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

Peter Gammie peteg42 at gmail.com
Thu Sep 24 00:22:49 EDT 2009


On 24/09/2009, at 11:59 AM, excerpts of what Brad Larsen wrote:

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

A better fix is to shift the type constraint to the class head, e.g.:

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


instance PolyArithExprFixed E Integer where

or if you want to be more general:

instance Num n => PolyArithExprFixed E n where

but note that this instance precludes any other ones for  
PolyArithExprFixed without allowing overlapping instances and hence  
some Olegs / Olegging.

See, e.g.:


(the slides link)

Ambiguity is IMHO best handled with a judicious application of type  
(or data) families, but you can get surprisingly far by simply  
requiring that every class member mention all type variables in the  
class head. YMMV of course.


More information about the Haskell-Cafe mailing list