CODEWITHSUNDEEP
haskelllambda-calculushaskell-src-exts
xcvii
xcvii

Reputation: 470

Alpha conversion on a Haskell expression

Given a Haskell expression, I'd like to perform alpha conversion, ie. rename some of the non free variables.

I've started implementing my own function for this, which works on a haskell-src-exts Exp tree, however it turns out to be surprisingly nontrivial, so I can't help wondering - is there an established easy-to-use library solution for this kind of source conversion? Ideally, it should integrate with haskell-src-exts.

Upvotes: 4

Views: 1379

Answers (1)

C. A. McCann
C. A. McCann

Reputation: 77384

This is one of the problems where the "Scrap Your Boilerplate" style generic libraries shine!

The one I'm most familiar with is the uniplate package, but I don't actually have it installed at the moment, so I'll use the (very similar) functionality found in the lens package. The idea here is that it uses Data.Data.Data (which is the best qualified name ever) and related classes to perform generic operations in a polymorphic way.

Here's the simplest possible example:

alphaConvert :: Module -> Module
alphaConvert = template %~ changeName

changeName :: Name -> Name
changeName (Ident n) = Ident $ n ++ "_conv"
changeName n = n

The (%~) operator is from lens and just means to to apply the function changeName to everything selected by the generic traversal template. So what this does is find every alphanumeric identifier and append _conv to it. Running this program on its own source produces this:

module AlphaConv where
import Language.Haskell.Exts
import Control.Lens
import Control.Lens.Plated
import Data.Data.Lens

instance Plated_conv Module_conv
main_conv
  = do ParseOk_conv md_conv <- parseFile_conv "AlphaConv.hs"
       putStrLn_conv $ prettyPrint_conv md_conv
       let md'_conv = alphaConvert_conv md_conv
       putStrLn_conv $ prettyPrint_conv md'_conv

alphaConvert_conv :: Module_conv -> Module_conv
alphaConvert_conv = template_conv %~ changeName_conv

changeName_conv :: Name_conv -> Name_conv
changeName_conv (Ident_conv n_conv)
  = Ident_conv $ n_conv ++ "_conv"
changeName_conv n_conv = n_conv

Not terribly useful since it doesn't distinguish between identifiers bound locally and those defined in an outside scope (such as being imported), but it demonstrates the basic idea.

lens may seem a bit intimidating (it has a lot more functionality than just this); you may find uniplate or another library more approachable.

The way you'd approach your actual problem would be a multi-part transformation that first selects the subexpressions you want to alpha-convert inside of, then uses a transformation on those to modify the names you want changed.

Upvotes: 5

Related Questions