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@foo.net ---------------------------------------------------------------------------
On 16-Dec-2003, John Meacham <john@repetae.net> wrote:
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
[...] 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?
I think views <http://www.haskell.org/development/views.html> would solve this problem, wouldn't they? You could define a view of `E Id' with constructors that skip over the conversions to/from Id view EId of E Id = App (E Id) (E Id) | Lam Int (E Id) | LetRec [(Int,E Id)] (E Id) | Var Int where eid (EAp (Id x) (Id y)) = Ap x y eid (ELam x (Id y)) = Lam x y eid (ELetRec (B bindings) (Id e)) = LetRec bindings' e where bindings' = map (\(v,(Id x))->(v,x)) bindings eid (EVar v) = Var v Then you can traverse expressions without needing to write any explicit conversions to/from Id, e.g. -- "occurs v e" returns True iff v occurs somewhere in e occurs :: Int -> (E Id) -> Bool occurs v (Lam v1 e) = v == v1 || occurs v e occurs v (Ap x y) = occurs v x || occurs v y occurs v (LetRec bindings e) = any (\(vi,ei)->v==vi || occurs v ei) bindings || occurs v e occurs v (Var v1) = v == v1 -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
G'day all. Quoting John Meacham <john@repetae.net>:
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.
http://haskell.org/hawiki/DecoratingStructures http://haskell.org/hawiki/IndirectComposite Cheers, Andrew Bromage
On 16-Dec-2003, ajb@spamcop.net <ajb@spamcop.net> wrote:
G'day all.
Quoting John Meacham <john@repetae.net>:
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.
http://haskell.org/hawiki/DecoratingStructures http://haskell.org/hawiki/IndirectComposite
Unless I missed something, none of those solve all the problems that Meacham is trying to solve (numbers 1 and 2 in his original mail). -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
G'day all. Quoting Fergus Henderson <fjh@cs.mu.oz.au>:
Unless I missed something, none of those solve all the problems that Meacham is trying to solve (numbers 1 and 2 in his original mail).
Many of them solve problem number 1, in that an unannotated structure is computationally identical to the original data structure. They don't solve problem number 2, that's true, but problem number 2 is largely a matter of taste. Having said that, have you considered Template Haskell? I'm not very familiar with it, but should, in theory, be possible not only to generate multiple type declarations from the one specification (e.g. one undecorated type, one decorated with unboxed decorations and another with boxed decorations), but also generate code which traverses each version uniformly, ignoring decorations if they're not needed. However, you may find this even more annoying than casting and uncasting the newtype. Cheers, Andrew Bromage
participants (4)
-
ajb＠spamcop.net -
Fergus Henderson -
Fergus Henderson
-
John Meacham