Update levity polymorphism (WIP)
Needs RevisionPublic

Authored by goldfire on Dec 13 2016, 8:20 PM.

Details

Summary

This commit implements the proposal in
https://github.com/ghc-proposals/ghc-proposals/pull/29.

Here are some of the pieces of that proposal:

  • Some of RuntimeRep's constructors have been shortened.
  • TupleRep and SumRep are now parameterized over a list of RuntimeReps. This means that two types with the same kind surely have the same representation. Previously, all unboxed tuples had the same kind, and thus the fact above was false.
  • RepType.typePrimRep and friends now return a *list* of PrimReps. These functions can now work successfully on unboxed tuples. This change is necessary because we allow abstraction over unboxed tuple types and so cannot always handle unboxed tuples specially as we did before.
  • The RepType.RepType type was removed, as it didn't seem to help with much.
  • The RepType.repType function is also removed, in favor of typePrimRep.
  • I have waffled a good deal on whether or not to keep VoidRep in TyCon.PrimRep. In the end, I decided to keep it there. PrimRep is *not* represented in RuntimeRep, and typePrimRep will never return a list including VoidRep. But it's handy to have in, e.g., ByteCodeGen and friends. I can imagine another design choice where we have a PrimRepV type that is PrimRep with an extra constructor. That seemed to be a heavier design, though, and I'm not sure what the benefit would be.
  • The last, unused vestiges of # (unliftedTypeKind) have been removed.

This code is also available on the wip/rae branch of the main GHC repo. Beware of upstream rebases here, though.

Test Plan

A few test cases that I haven't added yet.

goldfire retitled this revision from to Update levity polymorphism THIS IS A WORK IN PROGRESS..Dec 13 2016, 8:20 PM
goldfire updated this object.
goldfire edited the test plan for this revision. (Show Details)
goldfire added reviewers: simonpj, bgamari, austin.
goldfire updated the Trac tickets for this revision.
goldfire updated this object.Dec 13 2016, 8:26 PM

I'm stuck on a few points here.

  • There are a few places where we look at tycons to decide something about code generation. For example, we might look to see if we have an id whose type is headed by an unlifted tycon to decide that the id should be treated strictly. Previously, this was OK because we never abstracted over unlifted types. Not so anymore! I've updated cases where I could, but there are a few that are beyond my area of expertise:
    • CoreToStg.mkStgAltType
    • ByteCodeGen.generateCCall (this does some truly scary stuff, differentiating between normal arrays and small arrays and making me worried if we need finer-grained kinds in RuntimeRep)
  • The new RepType.unwrapType function is highly suspicious. It is an outgrowth of the old RepType.repType function. In the unary-type case, repType would "unwrap" a type, dropping foralls and newtypes, exposing the underlying type. What made this suspicious (and what makes unwrapType still suspicious) is that these types do not unwrap type families, with no type family env to hand. So I suspect that any use of unwrapType will be wrong in the presence of type families. Perhaps similarly, now that we are relaxing restrictions around where unboxed types can occur, we might find type variables cropping up in new places, and unwrapType will run into trouble. So I'd dearly like another pair of eyes to look over all usages of this function:
    • StgCmmClosure.might_be_a_function (this one seems OK)
    • StgCmmForeign.add_shim
    • DsForeign.typeTyCon (used in mkFExportCBits's ffi_cResType function and in showFFIType
    • DsForeign.getPrimTyOf (used in fun_type_arg_stdcall_info and mkFExportCBits's arg_info
    • ByteCodeGen.schemeE (third-to-last case)
    • ByteCodeGen.maybe_is_tagToEnum_call (this one seems OK because tagToEnum# doesn't work with type families anyway)
    • RtClosureInspect.getDataConArgTys (I'm always utterly stymied by this module)
    • RtClosureInspect.congruenceNewtypes
    • RtClosureInspect.isMonomorphicOnNonPhantomArgs
    • RepType.countFunRepArgs (used in RepType.idFunRepArity, used in StgCmmClosure.mkLFImported)
    • RepType.countConRepArgs (used in StgCmmCon.cgTopRhsCon [in an assertion], StgCmmExpr.cgConApp [also an assertion])
    • StgLint.lintStgExpr (last case, for StgCase)
  • StgLint.stgEqType seems ill-specified, and I didn't know how to update it. It almost looks like I should just be comparing the typePrimRep of the two types, but I wanted more expert eyes on this.

Until these points can be clarified, I'll be unable to make progress. Thanks!

goldfire retitled this revision from Update levity polymorphism THIS IS A WORK IN PROGRESS. to Update levity polymorphism (WIP).Dec 13 2016, 8:52 PM
goldfire updated this object.
goldfire updated this revision to Diff 9970.Dec 13 2016, 9:08 PM
  • Fix isUnboxed{Sum,Tuple}Type
goldfire updated this revision to Diff 10125.Dec 19 2016, 6:05 PM

This resolves the challenges above as well as I could.

It compiles. And it doesn't immediately fall over.

But it falls over when it starts dealing with unboxed tuples.
I think the problem arises when it has to deal with
(# State# RealWorld, MutableByteArray# RealWorld #).
The representation of this type is, rightly, [UnliftedRep].
But then the code generator treats it as a unary type, not
as an unboxed tuple. (I had been assuming that an unboxed tuple
with one non-void component was treated identically to a unary
type.) Then, the ASSERT in StgCmmCon.bindConArgs fails, because
an unboxed tuple constructor shows up where it shouldn't.

Previous to my patch, an unboxed tuple was considered a MultiRep
(one of the constructors of the now-abandoned RepType type),
even if it had only one non-zero-width field. But now,
we consider the representations of the unboxed tuple above
to be identical to the representation for, say, Array# Bool.
This causes trouble.

I'm not sure how to proceed, not being familiar with the code
generator. Do we bring back RepType, basically in order to
distinguish between an unboxed tuple with one non-zero-width
field and an ordinary type? Or make the code generator deal with
this case?

goldfire updated this revision to Diff 10150.Dec 21 2016, 2:31 PM
  • More bugfixing. Much of base compiles.

Simon helped me out about the problem above. Now I'm stuck at another
obstacle: the ASSERT on line 813 of CoreToStg is triggering because
an unboxed tuple constructor is there, during compilation of
GHC.Event.Poll. But I've no clue what's going
on around here. I may be able to dig up the answer myself, but an
Expert would surely be helpful.

. Now I'm stuck at another
obstacle: the ASSERT on line 813 of CoreToStg is triggering because
an unboxed tuple constructor is there, during compilation of
GHC.Event.Poll.

That suggests you have

let  x = (# p, q #) in ...

Do you? Do -ddump-prep to see it just before CoreToStg

goldfire updated this revision to Diff 10306.Jan 6 2017, 11:56 AM

This patch now contains the work originally in D2852. They are
merged because that patch is easier in the context of this one,
and they're so related anyway.

This version works, but there's an unfortunate issue with an
error message I don't know how to resolve. The problem is in
the output to typecheck/should_fail/T6078, where checkStrictBinds
(now in the desugarer) reports (correctly) an error. The problem
is that the in-scope Ptr is rendered as GHC.Ptr.Ptr. I believe
that this unnecessary qualified is because the type-checked
Ptr constructor is really a datacon wrapper, which is
not in the GlobalRdrEnv.

I don't know how best to proceed. I see two options:

  1. Somehow avoid qualifying datacon wrappers by cleverly looking up their OccNames in the GlobalRdrEnv during printing. This logic would seem to need to be written in the Outputable instance for Var, which is regrettable. Maybe it could be done in HsExpr.ppr_expr, but I'm worried that the logic won't catch all cases.
  2. Add the wrappers to the GlobalRdrEnv. The problem then is that they may appear to be ambiguous.

Happily, this patch seems mighty close to completion!

goldfire updated this revision to Diff 10308.Jan 6 2017, 12:04 PM

This patch now contains the work originally in D2852. They are
merged because that patch is easier in the context of this one,
and they're so related anyway.

This version works, but there's an unfortunate issue with an
error message I don't know how to resolve. The problem is in
the output to typecheck/should_fail/T6078, where checkStrictBinds
(now in the desugarer) reports (correctly) an error. The problem
is that the in-scope Ptr is rendered as GHC.Ptr.Ptr. I believe
that this unnecessary qualified is because the type-checked
Ptr constructor is really a datacon wrapper, which is
not in the GlobalRdrEnv.

I don't know how best to proceed. I see two options:

  1. Somehow avoid qualifying datacon wrappers by cleverly looking up their OccNames in the GlobalRdrEnv during printing. This logic would seem to need to be written in the Outputable instance for Var, which is regrettable. Maybe it could be done in HsExpr.ppr_expr, but I'm worried that the logic won't catch all cases.
  2. Add the wrappers to the GlobalRdrEnv. The problem then is that they may appear to be ambiguous.

Happily, this patch seems mighty close to completion!

goldfire updated this revision to Diff 10309.Jan 6 2017, 12:08 PM

This patch now contains the work originally in D2852. They are
merged because that patch is easier in the context of this one,
and they're so related anyway.

This version works, but there's an unfortunate issue with an
error message I don't know how to resolve. The problem is in
the output to typecheck/should_fail/T6078, where checkStrictBinds
(now in the desugarer) reports (correctly) an error. The problem
is that the in-scope Ptr is rendered as GHC.Ptr.Ptr. I believe
that this unnecessary qualified is because the type-checked
Ptr constructor is really a datacon wrapper, which is
not in the GlobalRdrEnv.

I don't know how best to proceed. I see two options:

  1. Somehow avoid qualifying datacon wrappers by cleverly looking up their OccNames in the GlobalRdrEnv during printing. This logic would seem to need to be written in the Outputable instance for Var, which is regrettable. Maybe it could be done in HsExpr.ppr_expr, but I'm worried that the logic won't catch all cases.
  2. Add the wrappers to the GlobalRdrEnv. The problem then is that they may appear to be ambiguous.

Happily, this patch seems mighty close to completion!

goldfire updated this revision to Diff 10310.Jan 6 2017, 12:13 PM

As you can see above, I ran into some technical trouble. This
is a test.

I don't know how best to proceed. I see two options:

Here's a third. Add HsDataCon to HsExpr with a ConLike as payload. When the typechecker looks up a HsVar and find that it is AConLike it reutrns the con-like thing in HsDataCon. The desugarer does the wrapper extraction.

Now you can pretty-print the typechecked code more nicely.

Rather like ConPatOut in HsPat

goldfire updated this revision to Diff 10366.Jan 9 2017, 10:20 PM

More bugfixing and straightening out of checkStrictBinds,
which was rather broken before.

Also included in this version is a change to make an unexpectedly-strict
pattern into a warning, instead of an error. We've waffled on this
in the past (see Trac #2806) but I think a warning is best. Looking forward
to feedback on this point. The change was motivated by the fact that
we really shouldn't treat unboxed tuples any differently from, say,
I#. So, if we remove the distinction between unboxed tuples
and I#, then we would need a lot more bangs to get code to compile.

This won't validate because we need -Wno-unbanged-strict-patterns
for libraries.

goldfire updated this revision to Diff 10411.Jan 10 2017, 10:14 PM

Some cleaning up. Some testsuite. There are still
some failing tests, including a nasty one about
printing type-checked unlifted pattern synonyms occurrences
without the void# argument. Any ideas of how to do this
would be greatly appreciated!

The problem is that the type-checker inserts the void# argument
to unlifted pattern synonym builder occurrences. But I don't know
how to skip printing it. Previously, we rarely printed type-checked
source, so this bug has lurked.

Some cleaning up. Some testsuite. There are still
some failing tests, including a nasty one about
printing type-checked unlifted pattern synonyms occurrences
without the void# argument. Any ideas of how to do this
would be greatly appreciated!

If I understand correctly, this would be solved by my suggestion above

Here's a third. Add HsDataCon to HsExpr with a ConLike as payload. When the typechecker looks up a HsVar and find that it is AConLike it reutrns the con-like thing in HsDataCon. The desugarer does the wrapper extraction.

Somehow I'm not getting emails from this diff. Perhaps this will help.

dfeuer requested changes to this revision.Jan 13 2017, 9:10 PM
dfeuer added a reviewer: dfeuer.
dfeuer added a subscriber: dfeuer.

Requesting changes to bump out of the review queue as WIP, but I have a few minor comments as well.

compiler/basicTypes/IdInfo.hs
185–192

The pattern checker should recognize this case as unreachable.

290–291

As long as you're updating this line, you might as well align the column with the rest.

compiler/codeGen/StgCmmExpr.hs
414–422

Why not

reps_compatible = ((==) `on` (primRepSlot . idPrimRep)) v bndr
compiler/coreSyn/CoreLint.hs
1409–1415

Where's this equality come from?

compiler/coreSyn/CoreUtils.hs
151

Above you say "checking type is fast". These comments seem contradictory.

compiler/coreSyn/PprCore.hs
330

Why not

Just name <- (dataConName <$>  isDataConId_maybe var) <|>
                       (patSynName <$> isPatSynBuilderId_maybe var)
compiler/stgSyn/StgSyn.hs
130

How onerous would it be to add the rest of the constructors explicitly, to make life less horrible if someone adds another address rep later?

compiler/typecheck/TcBinds.hs
552

Why not

mono_id <$ tcSpecPrags mono_id (lookupPragEnv prag_fn name)
compiler/typecheck/TcEnv.hs
415

This should surely be

isTypeClosedLetBndr = noFreeVarsOfType . idType
compiler/typecheck/TcEvidence.hs
193

Because of SDoc? How does that get in the way? (I'm not saying it doesn't, but the comment could be more descriptive, and a hand-written Data instance is clearly not the most fun). Would it be possible to define the Data instance by converting the HsWrapper to a type for which Data *can* be derived, and wrapping the methods appropriately (aside from dataTypeOf)? There aren't any associated types to get in the way.

compiler/typecheck/TcHsSyn.hs
937

And why should it indeed always be lifted?

This revision now requires changes to proceed.Jan 13 2017, 9:10 PM
goldfire updated this revision to Diff 10541.Jan 18 2017, 11:47 PM

Add HsConLikeOut to get cleaner pretty-printing of typechecked
ConLikes. More tests and such. Still need to update manual.

Otherwise, good to go?

dfeuer requested changes to this revision.Jan 25 2017, 1:13 PM

I left a few minor comments earlier, which have not been addressed.

This revision now requires changes to proceed.Jan 25 2017, 1:13 PM
austin resigned from this revision.Nov 9 2017, 9:44 AM