The Wonders of generic applicative traversal routines
Before http://repetae.net/drop/TypeSyns_old.hs and after http://repetae.net/drop/TypeSyns_new.hs that's right, the work of a 550 line complicated file done in a few lines. The magic is in FrontEnd.Syn.Traverse where I have a class that recurses over arbitrary source syntax and takes a data HsOps m = HsOps { opHsDecl :: HsDecl -> m HsDecl, opHsExp :: HsExp -> m HsExp, opHsPat :: HsPat -> m HsPat, opHsType :: HsType -> m HsType, opHsStmt :: HsStmt -> m HsStmt } as an argument, by recursively defining your ops by 'tying the knot' each of the routines will recurse down the others. quite handy. Now I have about 2500 lines of code to excise from FrontEnd/. Many improvements to the front end have been put off due to the sheer amount of traversal code that has to modified for every new syntax construct. good times. John -- John Meacham - http://notanumber.net/
Nice!
See also
http://ro-che.info/articles/2013-03-11-generalizing-gfoldl.html
http://ro-che.info/articles/2013-03-29-gtraverse-vs-gfoldl.html
http://hackage.haskell.org/package/traverse-with-class
* John Meacham
Before
http://repetae.net/drop/TypeSyns_old.hs
and after
http://repetae.net/drop/TypeSyns_new.hs
that's right, the work of a 550 line complicated file done in a few lines.
The magic is in FrontEnd.Syn.Traverse where I have a class that recurses over arbitrary source syntax and takes a
data HsOps m = HsOps { opHsDecl :: HsDecl -> m HsDecl, opHsExp :: HsExp -> m HsExp, opHsPat :: HsPat -> m HsPat, opHsType :: HsType -> m HsType, opHsStmt :: HsStmt -> m HsStmt }
as an argument, by recursively defining your ops by 'tying the knot' each of the routines will recurse down the others. quite handy. Now I have about 2500 lines of code to excise from FrontEnd/.
Many improvements to the front end have been put off due to the sheer amount of traversal code that has to modified for every new syntax construct. good times.
John
-- John Meacham - http://notanumber.net/ _______________________________________________ jhc mailing list jhc@haskell.org http://www.haskell.org/mailman/listinfo/jhc
Yeah, I have used those before, and still use Data.Data generics in jhc in some places but always found them unwieldy. As you note in your page, .exact structural children and logical children of a type may be different and I found them brittle when I modified a type, I ended up not being able to use standard types like [] and Maybe as much because I occasionally wanted to do more interesting things with traversal. This hybrid explicit dictionary approach that applies the traversal to components in parallel seems to be a sweet spot. I attempted something like it before using typeclasses, but it didn't work because I needed to modify the traversal functions en route sometimes based on dynamic info so anything hardcoded at the type level, even with clever newtype deriving, I found lacking. John -- John Meacham - http://notanumber.net/
* John Meacham
Yeah, I have used those before, and still use Data.Data generics in jhc in some places but always found them unwieldy. As you note in your page, .exact structural children and logical children of a type may be different and I found them brittle when I modified a type, I ended up not being able to use standard types like [] and Maybe as much because I occasionally wanted to do more interesting things with traversal.
To be 100% clear, the approach proposed on that page doesn't have this limitation and doesn't conflate structural and logical children. (Sorry if I'm stating the obvious; I am not sure what you're referring to by "those".)
This hybrid explicit dictionary approach that applies the traversal to components in parallel seems to be a sweet spot. I attempted something like it before using typeclasses, but it didn't work because I needed to modify the traversal functions en route sometimes based on dynamic info so anything hardcoded at the type level, even with clever newtype deriving, I found lacking.
It's great that it works for you! I guess you're dealing with an intermediate representation of Haskell code. My motivation behind traverse-with-class is dealing with full Haskell AST as defined in haskell-src-exts. An traversal dictionary for that would be enormous, and most of the components would be the same in any particular traversal (but you don't know in advance which ones, of course). So traverse-with-class helped me to manage that complexity. I also had to deal with modifying the traversal; e.g. here's how I propagate scope information in haskell-names: https://github.com/haskell-suite/haskell-names/blob/master/src/Language/Hask... https://github.com/haskell-suite/haskell-names/blob/master/src/Language/Hask... It's a small edsl, so it may look weird at first, but it actually worked out pretty nicely. Roman
On Tue, May 13, 2014 at 4:28 AM, Roman Cheplyaka
To be 100% clear, the approach proposed on that page doesn't have this limitation and doesn't conflate structural and logical children. (Sorry if I'm stating the obvious; I am not sure what you're referring to by "those".)
Ah, sorry. I was refering to the 'syb' ones. looks like gtraverse is a better primitive.
I guess you're dealing with an intermediate representation of Haskell code. My motivation behind traverse-with-class is dealing with full Haskell AST as defined in haskell-src-exts. An traversal dictionary for that would be enormous, and most of the components would be the same in any particular traversal (but you don't know in advance which ones, of course).
Actually, the data structure I am traversing and haskell-src are quite related and have a common ancestor. They both branched from the same project a long while ago though, Every now and again I consider merging in the changes, maybe after I get done rewriting the existing code with traversals I will look into it again. It would mean there is a lot less code I'd have to modify if I can just swap out traversal routines.
So traverse-with-class helped me to manage that complexity.
I also had to deal with modifying the traversal; e.g. here's how I propagate scope information in haskell-names:
https://github.com/haskell-suite/haskell-names/blob/master/src/Language/Hask... https://github.com/haskell-suite/haskell-names/blob/master/src/Language/Hask...
Interesting. On the subject of module and haskell name resolution, A major issue for jhc is how haddock just refuses to deal with code it can't handle and barfs, especially on my module/name resolution which allows fully recursive imports without restriction (based on the formal definition given in http://ogi.altocumulus.org/~hallgren/hsmod/Description.pdf ) With the --annotate-src option, jhc can spit out annotated source specifying exactly where each name maps, still trying to figure out how to get that into haddock though but seeing as how bugs with attached fixes get closed like this (http://trac.haskell.org/haddock/ticket/257) I'm not sure how well that will go. Last time I tried to submit a patch that let haddock skip over extensions it didn't recognize it wasn't put in.
It's a small edsl, so it may look weird at first, but it actually worked out pretty nicely.
I do have aversions to implicit parameters in general, I think this is the first time I've seen them in the wild actually. will have to look at what you are doing with them. John -- John Meacham - http://notanumber.net/
* John Meacham
It's a small edsl, so it may look weird at first, but it actually worked out pretty nicely.
I do have aversions to implicit parameters in general, I think this is the first time I've seen them in the wild actually. will have to look at what you are doing with them.
Yeah, I know there's a stigma against them; yet I rather like them. Roman
Sjoerd Visscher says:
«You might want to point him to multiplate too, that's an exact match with what
he's doing. (I'm not on the jhc mailing list)»
(https://twitter.com/sjoerd_visscher/status/466247707699736576)
* John Meacham
Before
http://repetae.net/drop/TypeSyns_old.hs
and after
http://repetae.net/drop/TypeSyns_new.hs
that's right, the work of a 550 line complicated file done in a few lines.
The magic is in FrontEnd.Syn.Traverse where I have a class that recurses over arbitrary source syntax and takes a
data HsOps m = HsOps { opHsDecl :: HsDecl -> m HsDecl, opHsExp :: HsExp -> m HsExp, opHsPat :: HsPat -> m HsPat, opHsType :: HsType -> m HsType, opHsStmt :: HsStmt -> m HsStmt }
as an argument, by recursively defining your ops by 'tying the knot' each of the routines will recurse down the others. quite handy. Now I have about 2500 lines of code to excise from FrontEnd/.
Many improvements to the front end have been put off due to the sheer amount of traversal code that has to modified for every new syntax construct. good times.
John
-- John Meacham - http://notanumber.net/ _______________________________________________ jhc mailing list jhc@haskell.org http://www.haskell.org/mailman/listinfo/jhc
Ah, interesting. that looks very very similar. even ends up using the
same data type as mine. convergent evolution? I guess the main
differences are that a plate is used for all traversal, wereas with my
traversal routine a typeclass is used for traversal that decides
whether to use the plate on a case by case basis. Which isn't that big
of a difference really, both can work like the other just fine.
Although mine was originally written with monads in mind, I have
dropped that just just applicative functors so they are even
converging there.
The other difference seems to be that multiplates use a typeclass to
'tie' up the traversal routines to reference each other and I use
direct cyclic assignment. as in, instead of declaring ops a plate I do
ops = (defaultOps ops) { opHsDecl = \d -> processDecl d }
So, we have the same logic, and data structures, we just decided to
insert the typeclass at different spots into the framework. :)
Incidentally, my next version of E core will be written with generic
traversal specifically in mind. I'll run it by the list before I
devote to much into it. still working on consistency proofs of the new
type system. Integrating the coercions from GHCs system Fc into a
stratified pure type system.
John
On Tue, May 13, 2014 at 9:12 AM, Roman Cheplyaka
Sjoerd Visscher says:
«You might want to point him to multiplate too, that's an exact match with what he's doing. (I'm not on the jhc mailing list)» (https://twitter.com/sjoerd_visscher/status/466247707699736576)
* John Meacham
[2014-05-12 17:36:43-0700] Before
http://repetae.net/drop/TypeSyns_old.hs
and after
http://repetae.net/drop/TypeSyns_new.hs
that's right, the work of a 550 line complicated file done in a few lines.
The magic is in FrontEnd.Syn.Traverse where I have a class that recurses over arbitrary source syntax and takes a
data HsOps m = HsOps { opHsDecl :: HsDecl -> m HsDecl, opHsExp :: HsExp -> m HsExp, opHsPat :: HsPat -> m HsPat, opHsType :: HsType -> m HsType, opHsStmt :: HsStmt -> m HsStmt }
as an argument, by recursively defining your ops by 'tying the knot' each of the routines will recurse down the others. quite handy. Now I have about 2500 lines of code to excise from FrontEnd/.
Many improvements to the front end have been put off due to the sheer amount of traversal code that has to modified for every new syntax construct. good times.
John
-- John Meacham - http://notanumber.net/ _______________________________________________ jhc mailing list jhc@haskell.org http://www.haskell.org/mailman/listinfo/jhc
-- John Meacham - http://notanumber.net/
to +sjoerd visscher
Maybe you can help with something I am trying to do, I'd like to
parameterize on a traversable over the input as well as the output so,
something like
where Traversable t and Applicative f
current plate definition
data Ops f = Ops { Â
opDecl :: Decl -> f Decl, Â Â
opExp  :: Exp -> f Exp
}
data OpsT t f = Ops {
opDeclT :: t Decl -> f (t Decl)
opExpT :: t Exp -> f (t Exp)
}
where I can specify specify T versions, for instance, override [Decl] -> f
[Decl] but otherwise they will automatically default to
opDeclT = T.traverse opDecl
now, the above is easy to write, tieing it all up recursively and allowing
the automatic choosing of the right 'traversable' instance seems hard
without ruining encapsulation.
See http://repetae.net/repos/jhc/src/FrontEnd/Syn/Traverse.hs for a basic
attempt, everything ending with ' is an attempt at the two level idea here.
John
On Tue, May 13, 2014 at 3:30 PM, John Meacham
Ah, interesting. that looks very very similar. even ends up using the same data type as mine. convergent evolution? I guess the main differences are that a plate is used for all traversal, wereas with my traversal routine a typeclass is used for traversal that decides whether to use the plate on a case by case basis. Which isn't that big of a difference really, both can work like the other just fine. Although mine was originally written with monads in mind, I have dropped that just just applicative functors so they are even converging there.
The other difference seems to be that multiplates use a typeclass to 'tie' up the traversal routines to reference each other and I use direct cyclic assignment. as in, instead of declaring ops a plate I do
ops = (defaultOps ops) { opHsDecl = \d -> processDecl d }
So, we have the same logic, and data structures, we just decided to insert the typeclass at different spots into the framework. :)
Incidentally, my next version of E core will be written with generic traversal specifically in mind. I'll run it by the list before I devote to much into it. still working on consistency proofs of the new type system. Integrating the coercions from GHCs system Fc into a stratified pure type system.
John
On Tue, May 13, 2014 at 9:12 AM, Roman Cheplyaka
wrote: Sjoerd Visscher says:
«You might want to point him to multiplate too, that's an exact match with what he's doing. (I'm not on the jhc mailing list)» (https://twitter.com/sjoerd_visscher/status/466247707699736576)
* John Meacham
[2014-05-12 17:36:43-0700] Before
http://repetae.net/drop/TypeSyns_old.hs
and after
http://repetae.net/drop/TypeSyns_new.hs
that's right, the work of a 550 line complicated file done in a few lines.
The magic is in FrontEnd.Syn.Traverse where I have a class that recurses over arbitrary source syntax and takes a
data HsOps m = HsOps { opHsDecl :: HsDecl -> m HsDecl, opHsExp :: HsExp -> m HsExp, opHsPat :: HsPat -> m HsPat, opHsType :: HsType -> m HsType, opHsStmt :: HsStmt -> m HsStmt }
as an argument, by recursively defining your ops by 'tying the knot' each of the routines will recurse down the others. quite handy. Now I have about 2500 lines of code to excise from FrontEnd/.
Many improvements to the front end have been put off due to the sheer amount of traversal code that has to modified for every new syntax construct. good times.
John
-- John Meacham - http://notanumber.net/ _______________________________________________ jhc mailing list jhc@haskell.org http://www.haskell.org/mailman/listinfo/jhc
-- John Meacham - http://notanumber.net/
-- John Meacham - http://notanumber.net/
participants (2)
-
John Meacham -
Roman Cheplyaka