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

[Peter Gammie]

Brad:

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

then:

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

http://www.soi.city.ac.uk/~ross/papers/fop.html

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

cheers
peter