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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe