On Wed, Jun 3, 2009 at 1:09 PM, Don Stewart
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