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

[wren ng thornton]

Brad Larsen wrote:
> On Thu, Sep 24, 2009 at 8:36 PM, wren ng thornton <wren at freegeek.org> wrote:
>> The reason this is unsatisfying is [...] 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/(>>=)/(>>).

As you say :)


> 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.
> [...]
> One can alleviate the ambiguity of Bar by splitting it into two
> classes, similarly to splitting up Monad:
> [...]
> It's not clear to me that such a decomposition is always possible.
> I'll keep experimenting with modular, tagless EDSLs...


I don't know that it will always work (though Oleg could say for sure). 
For simple classes like Monad and similar algebraic concepts, it works 
quite well; but then the maths are sort of designed that way. The more 
you move to large families of complexly interconnected methods, the more 
it seems likely it'll break down or require fundeps/typefamilies to 
resolve ambiguity cleanly.

Depending on exactly what your goal is re multiple interpretation, Ralf 
Hinze has some nice work on the "lifting lemma" for re-interpreting 
lambda-calculus syntax under different idioms:

     http://www.comlab.ox.ac.uk/ralf.hinze/WG2.8//26/slides/ralf.pdf

-- 
Live well,
~wren