[Haskell-cafe] Difficulties with tagless - create "primitives" or compose them

[Bruno Oliveira]

Hi Gunther,

The "finally tagless" approach can be viewed as one instance of the  
typecase pattern,
which myself and others have investigated the past:

http://ropas.snu.ac.kr/~bruno/papers/Typecase.pdf

Your problem is related to a problem that is found when designing  
generic programming
libraries. Namely the existence of what we call "ad-hoc" cases. These  
are cases that
most of the times have a default, but sometimes we would like to  
override that default.
This is essentially the source of your confusion. What is the best  
thing todo: shall I provide
a default by using composition by creating a definition for "mul"  
outside the class; or
shall I create a primitive. There is a trade-off between the two.  
Fortunatelly it is possible
to avoid such trade-off. This is one of the things that is described  
in the EMGM paper,
which uses the same variation of the typecase pattern that is used in  
the "finally tagless"
approach:

http://ropas.snu.ac.kr/~bruno/papers/ExtensibleGM.pdf

Now, for your particular example, this amounts to the following:

type Arr exp a b = exp a -> exp b

class EDSL exp where
     lam :: (exp a -> exp b) -> exp (Arr exp a b)
     app :: exp (Arr exp a b) -> exp a -> exp b

     int :: Int -> exp Int		-- Integer literal
     add :: exp Int -> exp Int -> exp Int
     sub :: exp Int -> exp Int -> exp Int

class EDSL exp => EDSLMul exp where
     mul :: exp Int -> exp Int -> exp Int
     mul e1 e2 = -- a default definition in terms of the primitives in  
EDSL

By creating a subclass and defining "mul" as a default method you get  
the advantages
of the primitive approach ( you can define your own interpretations)  
with the advantages
of the compositional approach (you can modularly add as many as you  
want without having
to touch EDSL).

There is a little extra work that you need to do though, because now  
you'll need to say:

instance EDSLMul MyInterpretation

to get an instance for mul at a particular interpretation. You can  
actually avoid this, if you
use overlapping instances:

instance EDSLMul a

then, only when you you really want to override an interpretation, you  
will need an instance.

More generally this approach tells you how you can modularize your  
EDSLs. Or, put another
way, if offers a solution for the expression problem:

http://www.daimi.au.dk/~madst/tool/papers/expression.txt

Hope this helps!

Cheers,

Bruno Oliveira

On Jun 13, 2010, at 10:58 AM, Günther Schmidt wrote:

> Hi list,
>
> there is one thing about the "Finally tagless" EDSL approach that  
> really confuses me: (Well more than one actually but this one more so)
>
> When to decide to introduce a term as a primitive in the syntax  
> class and when to define it from primitives already defined.
>
> For example this one here:
>
> type Arr exp a b = exp a -> exp b
>
> class EDSL exp where
>     lam :: (exp a -> exp b) -> exp (Arr exp a b)
>     app :: exp (Arr exp a b) -> exp a -> exp b
>
>     int :: Int -> exp Int		-- Integer literal
>     add :: exp Int -> exp Int -> exp Int
>     sub :: exp Int -> exp Int -> exp Int
>     mul :: exp Int -> exp Int -> exp Int
>
> Let's take "mul" here, defined as a "primitive", in other words  
> defined in the EDSL class.
>
> Technically, with lam, app and add already defined, I could have  
> defined "mul" outside the EDSL class, just built from the 3  
> primitive operators.
>
> Of course doing so then does not give me the possibility to choose  
> alternative evaluation strategies for "mul" itself, only for lam,  
> app and add.
>
> So what is a good measure for deciding when to define a term  
> primitive or not?
>
> Günther
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe