[Haskell-cafe] Using type families to define runtime representation and evaluation strategy?

[Corey O'Connor]

On Wed, Jun 3, 2009 at 1:09 PM, Don Stewart <dons at galois.com> wrote:
> coreyoconnor:
>> I'm interested in the feasibility of extending the compiler using a
>> construct similar to type synonym families to determine runtime
>> representation and evaluation strategy for types. Can anybody point me
>> to existing work in this area?
>
> There's a lot of work on controlling data representations with
> associated types -- indeed, that was their original use case!

What I'm imagining as a use case would be taking the canonical example
from the adaptive-containers:
l :: [(Int, Int)]
l = [ (x,y) | x <- [1..3], y <- [x..3] ]

A module that uses "l" that requires the same data representation as
the List(Pair Int Int) type when using adaptive containers would then
include an equation somewhat like the following:

type instance DataRep [(Int, Int)] = List(Pair Int Int)

However all list code would then need to be augmented to take into
consideration the DataRep associated type. Correct?

Seems like this augmentation could be done implicitly by the compiler.
Potentially going off the deep end: Data representation is how a block
of memory represents a type such that the representation supports the
required evaluation semantic. The data representation for a data
constructor where the definition equation is evaluated lazily is
different than the data representation for the same constructor where
the definition is evaluated strictly. One requires representing the
state of the thunk in memory while the other does not. Assuming that
is accurate then equations could be represented implicitly
parametrized over the data representation equations for each type.
Kinda akin to how equations using type class equations are implicitly
parametrized by the dictionary representing the witness of that type
class for a given type. Except I'm imagining something at the type
level instead of value level.

Regardless. I need to read up on associated types and try some
experiments before I can make claims on what they can and what they
cannot do. :-)

> Also related might be the new paper "Types are calling conventions"

>From the abstract it does sound related. Thanks! I'll add it to my reading pile.

Cheers,
Corey O'Connor