[Haskell-cafe] Bug in SYB, SYB-documentation or GHC-API (or I messed up somewhere)

"Philip K. F. Hölzenspies" pkfh at st-andrews.ac.uk
Fri May 11 18:12:14 CEST 2012

Dear Haskelers,

Since I don't quite know whether this is a SYB-thing or a GHC-specific thing, I figured this report should go here. If not, kindly redirect.

I am trying to write a program, using the GHC-API to refactor some parts of the GHC-code (initially, I want to add a type variable to the types in the AST to express the representation of types, as noted to be a Good Thing at [1]). To do this, I first search for all definitions of and references to type constructors. I do this using SYB.

Consider these functions:

type OccurrenceTable = [(RdrName, (SrcSpan,Bool))]

locTyNames :: SrcSpan -> Bool -> HsType RdrName -> OccurrenceTable
locTyNames l p (HsTyVar n ) = [(n, (l, p))]
<… HSType-specific traversal cases omitted for brevity …>

extTyNamesDef :: Data a => SrcSpan -> a -> OccurranceTable
extTyNamesDef l x = gmapQl (++) [] (extTyNames l) x

extTyNamesTy :: SrcSpan -> HsType RdrName -> OccurranceTable
extTyNamesTy l x  = locTyNames l True x

extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l) x

The OccurrenceTable type collects for every type constructor (RdrName) the location of its occurrence (either definition or reference, SrcSpan) and whether adding a type variable (formal or actual) requires parenthesis (Bool).

This works fine, although now, we always find the same SrcSpan for everything. When traversing an AST, whenever we find anything that's Located, we want to continue the traversal with this new location information. To this end, we define:

extTyNamesLoc :: Data a => Located a -> OccurrenceTable
extTyNamesLoc (L l x) = extTyNames l x

and modify the universal entry point to:

extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l `ext1Q` extTyNamesLoc) x

However, it turns out that this never leads to an evaluation of extTyNamesLoc. I've come as far as to see that, since "Located a" is a synonym for "GenLocated SrcSpan a", the type we're looking for really has a binary constructor, thus we should use ext2Q.

This made things work: We first modify the function we apply to Located things:

extTyNamesLoc :: (Data loc, Data a) => SrcSpan -> GenLocated loc a -> OccurrenceTable
extTyNamesLoc l (L l' x) = case cast l' of
	Just l'' -> extTyNames l'' x
	Nothing -> extTyNames l x

and define the universal entry point to be:

extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l `ext2Q` extTyNamesLoc l) x

Even though I see why this works, I'm not completely sure why the former version does not. Is there no currying with type constructors (for SYB)? The cast I perform always succeeds, because all types that occur in the traversal are "Located x" and never "GenLocated NonSrcSpanType x".

The extensions to extX functions (i.e. ext1Q, ext2Q, ext1T, etc.) are not very extensively documented. Their discussion in the ICFP04 paper only discusses their relation to TypeableX classes, but not to the partiality of type constructor application and/or synonyms. (As a side-note on that discussion in ICFP04, the remark that we're generally interested in type constructors with arguments of kind * sounded fine, until I started to try and parameterise the AST in the location-annotation-type as well; it made my brain hurt.)

Apologies for the waffling, but comments would be greatly appreciated.


[1] http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/HsSynType
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120511/2d511857/attachment.htm>

More information about the Haskell-Cafe mailing list