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

[Brad Larsen]

Wren,

On Thu, Sep 24, 2009 at 8:36 PM, wren ng thornton <wren at freegeek.org> wrote:
> Brad Larsen wrote:
>>
>> The modularity problem I speak of is that to add a new interpretation of
>> the
>> DSL, I will likely have to modify the EDSL definition to add additional
>> constraints.  Ideally, I would like to be able to define the EDSL once, in
>> a
>> module, and be able to write arbitrary interpretations of it in other
>> modules, without having to go back and change the EDSL definition.
>
> The canonical, if theoretically unsatisfying, way to do this is to lift all
> type variables into the class specification. Thus, instead of
>
>    class Foo f where
>        foo :: forall a. a -> f a
>
> we would instead have
>
>    class Foo f a where
>        foo :: a -> f a
>
> According to the intention of the design, variables thus lifted should
> remain polymorphic in instances however they can have contexts applied to
> them:
>
>    instance (Num a) => Foo F a where
>        foo = ...
>
> The reason this is unsatisfying is that there's no way to enforce that
> instances don't ground these variables, which can interfere with the
> validity of applying certain laws/transformations. Also, if you need to lift
> more than one variable in the same class then it can be tricky to do the
> encoding right. For instance, when converting Monad into this form (e.g. so
> we can define an instance for Set) it is prudent to separate it into one
> class for return and another for join/(>>=)/(>>). But it does solve the
> problem at hand.
>
> --
> Live well,
> ~wren
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

I have experimented some in the past day with this canonical technique
of lifting type variables into the class specification.  This is
somewhat successful; however, one problem is that when multiple
variables are lifted into the specification, ambiguity creeps in (and
over-generality?), in the absence of superclass constraints or
functional dependencies.

So, for example, Foo seems to work well, but Bar does not:

    class Foo a where
        ...

    class Bar a b where
        ...

One can alleviate the ambiguity of Bar by splitting it into two
classes, similarly to splitting up Monad:

    class PreBar a where
        ...

    class (PreBar a) => Bar a b where
        ...

It's not clear to me that such a decomposition is always possible.
I'll keep experimenting with modular, tagless EDSLs...

Sincerely,
Brad