Annotating Expressions

John Meacham john at repetae.net
Tue Dec 16 14:56:31 EST 2003


Imagine I have a data structure like so:

data E = EAp E E | ELam Int E | ELetRec [(Int,E)] E | EVar Int

now, I want to annotate every occurence of E with some pass specific
information, such as free variables or levels for lambda lifting.

in [PEY91] this technique was used:

data EAn a = EaAp (a,EAn a) (a,EAn a) | EaLam Int (a,EAn a) | 
        EaLetRec [(Int,(a,EAn a))] (a,EAn a) | EaVar Int

however this suffered from two problems, 
1. EAn () is not computationally identical to E, since it has an extra indirection
2. it is anoying to work with EAn () when we don't want to use the extra info,
meaning we keep both E and EAn around, despite them being very similar

using an idea inspired by [SHEARD01] I came up with the following

newtype Id a = Id a

type Er f = f (E f)  -- E used recursivly
data E f = EAp (Er f) (Er f) | ELam Int (Er f) | 
        ELetRec [(Int,Er f)] (Er f) | EVar Int


now, this solves problem 1. (E Id) is computationally identical to the
original E, however problem 2 persists. If I don't want to be constantly
casting to and from Id, I have to use both the seperate annotated and
unannotated versions.

is this actually the case? is there a better solution I don't see? perhaps
something using crazy GHC extensions? if not, are there any proposed
extensions which would solve this promlem?

if there were some limited way to partially apply a type declaration that
would solve the problem, but raise others.

perhaps a 'nullary' type constructor, as in
type Id = 
or just type Id
so Id is of kind (* -> *) and expands to nothing.
then in (E Id) it is fully applied...  

any other ideas? perhaps some that work :)
        John

[PEY91] http://research.microsoft.com/~simonpj/papers/fully-lazy-lambda-lifter.ps.gz
[SHEARD01]  http://www.cse.ogi.edu/~sheard/papers/generic.ps
          


-- 
---------------------------------------------------------------------------
John Meacham - California Institute of Technology, Alum. - john at foo.net
---------------------------------------------------------------------------


More information about the Haskell mailing list