Skip to content

WIP: Implement the “Constraint based arrow notation” proposal (and rewrite the arrow notation desugarer)

Alexis King requested to merge lexi.lambda/ghc:constraint-based-arrow-notation into master

This MR implements the “Constraint based arrow notation” GHC proposal, which currently has not actually been accepted. However, I’m confident enough that it eventually will be accepted (albeit possibly with revisions) that I’ve decided to go ahead and make the changes so that they can be presented alongside the proposal.

The implementation is divided into three parts:

  1. The new module GHC.Builtin.Types.Arrows implements the two wired-in type families from the proposal, ArrowStackTup and ArrowEnvTup.

  2. GHC.Tc.Gen.Arrow has been updated to use the wired-in type families and to thread the stack around as a type-level list.

  3. Most significantly, this MR includes a complete rewrite of the arrow notation desugarer.

    The desugaring strategy itself is mostly the same, so this is an internal refactor, not a user-facing change. The major simplification is the introduction of a very simple intermediate AST between HsExpr and CoreExpr called DsArrExpr. Unusually, the desugarer for DsArrExpr includes its own tiny “optimizer,” which allows the rest of the desugaring code to be simplified significantly; see Note [Tidying arrow expressions] in GHC.HsToCore.Arrows.Expr.

Also included is an Ott file with a complete specification of the updated command typing rules. It does not currently contain the desugaring rules, as I found them awkward to express in Ott, but I may have another go at them in the future.

The following things still need to be finished before this MR can be merged:

  • Most obviously, the GHC proposal needs to be accepted.
  • Various bits of the implementation still need some cleaning-up, and there are some more Notes I would like to write.
  • I intend to add custom type error messages upon failure to solve the magical arrow type families.
  • The User’s Guide needs to be updated, and I’d like to significantly expand portions of the arrow notation docs.
  • The Ott model should at the very least be expanded with explanatory prose, and possibly with the addition of the desugaring rules as well.

In the meantime, what’s here is complete enough to be reviewed, should anyone be interested in doing so (though do keep in mind that I know some things need some cleaning up!). The implementation is fully-functional in the sense that it passes the entire arrows test suite, but I have not yet tried it on my real-world codebase, so there may be lingering bugs.

Merge request reports