Support mechanism to rewrite AST during compilation

[brandonchinn178]

Broken out from #362:

I would be willing to add MicroHs support for skeletest but it hooks in to autodiscover tests, rewrite certain expressions, etc.

[augustss]

There are several places where a plugin could be inserted:

• After parsing
• After type checking and name resolution
• After desugaring (only lambda calculus + constants left)
• After bracket abstraction (no more lambdas)

Should the plugins have IO type, or just pure?

[brandonchinn178]

For skeletest's purposes, I only need pure functions.

Skeletest needs the following functionality from a plugin:

• Generate a main function (currently added after the parsing phase in GHC)
• Rewrite expressions (currently added after the rename phase in GHC)
  e.g.

  -- original
  (encode . decode) P.=== id
  
  -- transformed
  IsoChecker (Fun "encode . decode" (encode . decode)) (Fun "id" id)

So I think the answer is "after parsing" and "after name resolution"

[augustss]

Name resolution and type checking happen at the same time. Transforming after type checking is trickier since you need to produce type correct code with overloading resolved.

Doing name resolution before type checking, like GHC, is a mistake, IMO.

[brandonchinn178]

I see. I'm curious why you see doing name resolution before typechecking is a mistake. Is it for performance?

I could do the expression rewriting after parsing, but it's better to do after name resolution so that I only rewrite uses of === from my library, and not a user's === function. I guess I could parse the import statements, find what Skeletest.Predicate is imported as, and only match <import qualified name>.===, but that feels brittle.

Maybe we can start with a plugin after parsing phase and see if that's sufficient?

[augustss]

If you resolve names while type checking you can use type directed name resolution. E.g., having the same name for two constructors in two different types would be OK, if you always know the type whenever you use them.
Another example is the required type arguments. With required type arguments you cannot syntactically tell if an expression is a type or a value. So you don't know if names should be resolved in the type or value name space. GHC has a hack so you have to say type to disambiguate.
Example:

foo :: forall a -> a -> Int
data T = A | Bool
foo x y = ...
bar = foo Bool True

Is Bool the type or the constructor? GHC can't tell. So you have to write foo (type Bool) True. MicroHs can tell, because it knows type type of foo when resolving the names.

[augustss]

And yes, it's also more efficient.