wiki:TypeFunctionsStatus

Version 172 (modified by chak, 7 years ago) (diff)

--

TypeFunctions/Status

Type Functions: Implementation Status

Debugging of type family patch:

  1. boxySplitTyConApp and friends must be able to deal with orig_tys that have outermost type family applications; i.e., they need to try to normalise and possibly have to defer. They also need to defer on skolems. Consequently, they also need to return a coercion. This , in particular, affects the treatment of literal lists, parallel arrays, and tuples inTcExpr.tcExpr is fishy.
  2. The tests tcfail068 and rw used to raise more type errors right away. Now, we see less recovery.
  3. To fix Roman's GADT1 test, proceed as follows (as suggested by SPJ):
    • TcGadt.uUnrefined: the occurs check needs to be more subtle. If the variable occurs, but does so under a type family application, do not fail, but just defer.
    • This requires a function Types.tyVarsOfTypeDefinite that returns only those variables not occurring under type family applications.
    • Moreover, the unification monad UM must be extended to be able to collect EqInst for later insertion into the LIE.
    • We may have to do the same for other occurs checks.
    • And we definitely need the whole deferral machinery for the GADT unification in TcGadt.

Current:

  • Merge and debug type family patch.
  • Add some wiki documentation of how inference with type families works.

Parsing and Renaming

Todo (low-level): None.

Todo (high-level):

  1. Defaults for associated type synonyms. (Having both a kind signature and vanilla synonym is problematic as in RnNames.getLocalDeclBinders its hard to see that not both of them are defining declarations, which leads to a multiple declarations error. Defaults are quite different from vanilla synonyms anyway, as they usually have tyvars on their rhs that do not occur on the lhs.)

Done:

  • Parsing and renaming of kind signatures (toplevel and in classes).
  • Parsing and renaming of indexed type declarations (toplevel and in classes).
  • Using new syntax with family and instance on top level.
  • Added -findexed-types switch.
  • Allowing type tag in export lists to list associated types in the sub-binder list of an import/export item for a class.
  • Import/export lists: ATs can be listed as subnames of classes and the data constructors of instances of a data family are subnames of that family.
  • Parsing and renaming of equational constraints in contexts.

Type Checking

Todo (low-level):

  • Enforce syntactic constraints on type instances needed to ensure the termination of constraint entailment checking.
  • If an associated synonym has a default definition, use that in the instances. In contrast to methods, this cannot be overridden by a specialised definition. (Confluence requires that any specialised version is extensionally the same as the default.)

Todo (high-level): [Tom has done much of this.]

  1. Type checking of type functions (and hence, associated type synonyms); routines in TcUnify that need to be extended:
    • boxySplitTyConApp: The second argument (BoxyRhoType) can be a synonym family application. Then, we must produce a wanted coercion and return a HsWrapper value that applies that coercion.
    • boxySplitAppTy: Basically, the same deal as the previous.
    • boxySubMatchType: Not sure yet. Do we need to handle the case where in go one type is FunTy and the other a synonym family application? But the function doesn't handle the case where a FunTy meets a tyvar either, so its probably ok to ignore.
    • boxy_match: Not sure yet. Do we have to handle the case where t_ty is a synonym family application? On the other hand, this prematching seems to be an approximation. How much does it hurt if we just ignore this?
    • boxy_lub: Unclear. Also seems to approximate.
    • tcSubExp: Defer to boxy matching if we have a synonym family application.
    • uTysOuter, u_tys, uPred, uVar, and their intefaces boxyUnify, boxyUnifyList, unifyType, unifyPred, unifyTheta, and unifyTypeList: Generate wanted equalities and produce coercion(s). !!!Still need to check usage patterns!!!
    To make things easy, we might want to always return a HsWrapper value (unless the unification fails), which is WpHole whenever the coercion is empty. The disadvantage is that this blows the tree between type checking and desugaring up. An alternative is to return the coercion only when needed, but write some auxilliary functions that take the result of boxySplitTyConApp and friends and turn the optional coercion result in an always present (real Haskell) function that we always apply to the type-checked pattern (in TcPat) or expression. It is simply id when we don't need a coercion.

Invariants:

  • Arguments and results of synonym families are always tau types. Then, boxy subsumption becomes easy to handle. When we have a synonym family application, we defer to boxy matching (i.e., unification) and if that comes up with a coercion, we return it as the subsumption coercion.
  1. Type checking in the presence of associated synonym defaults. (Default AT synonyms are only allowed for ATs defined in the same class.)
  2. Type check functional dependencies as type functions.

Done:

  • Kind and type checking of kind signatures.
  • Kind and type checking of instance declarations of indexed types, including the generation of representation tycons.
  • Wrapper generation and type checking of pattern matching for indexed data and newtypes.
  • Consistency checking for family instances.

Desugaring

Todo (low-level): None.

Todo (high-level): None.

Done:

  • Representation of family kind signatures as TyCon.TyCons.
  • Extension of Class.Class by associated TyCons.
  • Extension of TyCon.TyCon with a reference to the parent TyCon for data instances.
  • Extension of DataCon.DataCon with instance types for constructors belonging to data instances.
  • Extension of TyCon.TyCon such that the parent of a data instance is paired with a coercion identifying family instance and representation type.
  • For indexed data types, the datacon wrapper uses data instance coercion and pattern matching casts the scrutinee via an ExprCoFn in a CoPat.
  • Import and exporting.
  • Generation and plumbing through of rough matches.
  • Equational constraints in contexts.

Regression tests of type family patches

Current validate result:

Unexpected passes:
   Class1(normal)
   GADT2(normal)

Unexpected failures:
   Refl2(normal)
   Simple5a(normal)
   rw(normal)
   tcfail065(normal)
   tcfail068(normal)
   tcfail071(normal)
   tcfail076(normal)
   tcfail102(normal)
   tcfail103(normal)
   tcfail153(normal)
   tcfail179(normal)
  • Class1: VALID. (Only marked to fail in head to keep validate happy.)
  • GADT2: VALID. (Only marked to fail in head to keep validate happy.)
  • Relf2: VALID. Type family BUG.
  • Simple5a: VALID. Error message changed.
  • break001: INVALID. GHC panic instead of printing error message about ambiguous variable.
  • break006: INVALID. Seems to be the same problem as break001.
  • print019: INVALID. Seems to be the same problem as break001.
  • rw: VALID. Changed error message. Reports one error less. Other one is pruned, but still raised if the first one is removed.
  • tc210: INVALID (matching forall a.a -> Int against `Int -> Int fails).
  • tc211: INVALID (tests impredicative types).
  • tcfail046: VALID. Changed error message, BUT the new error message has one more type synonym unfolding, which should be avoided.
  • tcfail065: VALID. Cosmetic difference, as tidy names are assigned in different order.
  • tcfail068: VALID. Reports two errors less (probably due to different recovery points). Yes, I checked that its not that it admits incorrect programs, but just due to different order of checking/pruning of errors.
  • tcfail071: VALID. Now reports one instead of two errors as deferred unification is checked only after the contexts of mutually recursive groups have been unified. (The latter is what this test case is really about, and it still works fine for that.)
  • tcfail076: VALID. Same as tcfail065.
  • tcfail102: VALID.
  • tcfail103: VALID. Error message is actually better!
  • tcfail128: VALID. Same as tcfail046.
  • tcfail145: VALID. Error message got worse.
  • tcfail153: VALID. Error message is different, but equally correct and accurate. The type mismatch manifests itself at two different subexpressions. Due to a different traversal order, we now report the error at the other subexpression.
  • tcfail179: VALID. If anything, the error message improved.
  • while: VALID. Works if definition of succeed gets a type signature Monad m => a -> m a. The error seems to be due to the new GADT rules about annotations, but the error message is a bit strange; ie, need to be improved.

Regression tests that are not part of the fast run:

  • cholewo-eval: core-lint breackage