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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
