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

[Brad Larsen]

Edward,

On Sat, Sep 26, 2009 at 11:41 AM, Edward Kmett <ekmett at gmail.com> wrote:
> I would just like to add that Oleg and Chung-chieh made sure in their
> finally tagless paper to use monomorphic lifting of literals explicitly to
> avoid this sort of ambiguity. Using Num or another typeclass is fine as long
> as all you want to do is evaluate your EDSL. But what about partial
> evaluation? CPS transformation? Compilation? You might be able to muddle
> through the first two, but compilation will derail your solution. Ultimately
> you will not be able to work over arbitrary Num instances if you want to do
> more than interpret. That was the main point of the monomorphic int :: Int
> -> r Int, char :: Char -> r Char methods they were using. If all I know
> about something is that there is a valid Num instance for it I have no way
> to emit machine code for it.
> -Edward
[...]

If thye type parameter is present in the class head, you can put
constraints on it in your instances.  E.g.,

class ENum repr a where
  constant :: a -> repr a
  add :: repr a -> repr a -> repr a

newtype E a = E { unE :: a }

instance (Num a) => ENum E a where
  constant = E

Similarly to the ENum instance for an evaluator, E, you could define a
type class for code gen:

data UntypedIntermediate = ConstInt Int | ConstFloat Float | Add
Intermediate Intermediate

class Emittable a where
  emit :: a -> UntypedIntermediate

instance Emittable Int where
  emit i = ConstInt i

instance Emittable Float where
  emit f = ConstFloat f

Then, you could do compilation, given an Emittable constraint:

newtype C a = C { unC :: UntypedIntermediate }

instance (Emittable a) => ENum C a where
  constant e = C $ emit $ unC e
  add e1 e2 = C $ Add (emit $ unC e1) (emit $ unC e2)


I think that by using the strategy of lifting type parameters into
class head, and by defining the type classes & instances you need for
a certain interpretation, you can modularly define tagless EDSLs, i.e.
define the language once, as a collection of typeclasses, and then be
able to define arbitrary interpretations of that EDSL, in separate
modules, without having to modify the EDSL type classes.

(Note:  I haven't tried running the above code.)

Sincerely,
Brad