Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#12409 closed bug (duplicate)

Unboxed tuples have no type representations

Reported by: bgamari Owned by:
Priority: normal Milestone: 8.2.1
Component: Compiler Version: 8.0.1
Keywords: typeable Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #11722 Differential Rev(s):
Wiki Page:

Description (last modified by bgamari)

This ticket continues with the long tradition of types missing type representations (see #12082, #12132, #11120). This time the culprit is unboxed tuples,

$ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/ben/.ghci
λ> import Data.Typeable
λ> :set -XUnboxedTuples 
λ> typeRep (Proxy :: Proxy (#Int, Int#)) 
ghc: panic! (the 'impossible' happened)
  (GHC version 8.0.1 for x86_64-unknown-linux):
	tyConRep (#,#)

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

The problem, as usual, is that the tycons are missing from primTyCons.

Change History (10)

comment:1 Changed 3 years ago by simonpj

Why does it matter that they are not in knownKeyNames?

comment:2 Changed 3 years ago by bgamari

Description: modified (diff)

Why does it matter that they are not in knownKeyNames?

Sorry, I had meant primTyCons above. The reason is that TcTypeable uses primTyCons as the list of TyCons which are defined in GHC.Prim. When compiling GHC.Types TcTypeable generate Typeable representations for the types in primTyCons. If a primitive TyCon is missing from the list then that type's Typeable representation will also be missing (which I believe is what happened in this bug).

Ultimately we don't want to add unboxed tuples to primTyCons since we don't want to add them to the original name cache (as discussed in #12357). I have a proposed solution on the way.

comment:3 Changed 3 years ago by bgamari

On further investigation it looks like my previous hypothesis is completely wrong. The problem is that TyCon.tyConRepName_maybe does not handle the case of AlgTyCon { algTcParent = UnboxedAlgTyCon }.

Last edited 3 years ago by bgamari (previous) (diff)

comment:4 Changed 3 years ago by bgamari

I guess the question here is do we want unboxed tuples to be representable? It looks like it would be easy to make them representable: just add a field carrying the representation name to UnboxedAlgTyCon just as we do with AlgTyCon.

If we'd prefer to keep them unrepresentable then I suppose we should make the solver throw a more polite error message.

comment:5 Changed 3 years ago by bgamari

Blocked By: 11736 added

However, I should note that making unboxed tuples representable will involve resolving #11736. I think this may be something I try to fix in the course of the TTypeable work.

comment:6 Changed 3 years ago by simonpj

Yes -- for now, a more polite error would suffice I think.

Anyway, it's unrelated to the other stuff about knownTyCons etc.

comment:7 Changed 3 years ago by bgamari

Milestone: 8.0.28.2.1

Sadly this won't make it for 8.0.2.

comment:8 Changed 3 years ago by simonpj

Blocked By: 11736 removed

comment:9 Changed 3 years ago by bgamari

Resolution: duplicate
Status: newclosed

This is a duplicate of #11722.

comment:10 Changed 3 years ago by Ben Gamari <ben@…>

In 8fa4bf9a/ghc:

Type-indexed Typeable

This at long last realizes the ideas for type-indexed Typeable discussed in A
Reflection on Types (#11011). The general sketch of the project is described on
the Wiki (Typeable/BenGamari). The general idea is that we are adding a type
index to `TypeRep`,

    data TypeRep (a :: k)

This index allows the typechecker to reason about the type represented by the `TypeRep`.
This index representation mechanism is exposed as `Type.Reflection`, which also provides
a number of patterns for inspecting `TypeRep`s,

```lang=haskell
pattern TRFun :: forall k (fun :: k). ()
              => forall (r1 :: RuntimeRep) (r2 :: RuntimeRep)
                        (arg :: TYPE r1) (res :: TYPE r2).
                 (k ~ Type, fun ~~ (arg -> res))
              => TypeRep arg
              -> TypeRep res
              -> TypeRep fun

pattern TRApp :: forall k2 (t :: k2). ()
              => forall k1 (a :: k1 -> k2) (b :: k1). (t ~ a b)
              => TypeRep a -> TypeRep b -> TypeRep t

-- | Pattern match on a type constructor.
pattern TRCon :: forall k (a :: k). TyCon -> TypeRep a

-- | Pattern match on a type constructor including its instantiated kind
-- variables.
pattern TRCon' :: forall k (a :: k). TyCon -> [SomeTypeRep] -> TypeRep a
```

In addition, we give the user access to the kind of a `TypeRep` (#10343),

    typeRepKind :: TypeRep (a :: k) -> TypeRep k

Moreover, all of this plays nicely with 8.2's levity polymorphism, including the
newly levity polymorphic (->) type constructor.

Library changes
---------------

The primary change here is the introduction of a Type.Reflection module to base.
This module provides access to the new type-indexed TypeRep introduced in this
patch. We also continue to provide the unindexed Data.Typeable interface, which
is simply a type synonym for the existentially quantified SomeTypeRep,

    data SomeTypeRep where SomeTypeRep :: TypeRep a -> SomeTypeRep

Naturally, this change also touched Data.Dynamic, which can now export the
Dynamic data constructor. Moreover, I removed a blanket reexport of
Data.Typeable from Data.Dynamic (which itself doesn't even import Data.Typeable
now).

We also add a kind heterogeneous type equality type, (:~~:), to
Data.Type.Equality.

Implementation
--------------

The implementation strategy is described in Note [Grand plan for Typeable] in
TcTypeable. None of it was difficult, but it did exercise a number of parts of
the new levity polymorphism story which had not yet been exercised, which took
some sorting out.

The rough idea is that we augment the TyCon produced for each type constructor
with information about the constructor's kind (which we call a KindRep). This
allows us to reconstruct the monomorphic result kind of an particular
instantiation of a type constructor given its kind arguments.

Unfortunately all of this takes a fair amount of work to generate and send
through the compilation pipeline. In particular, the KindReps can unfortunately
get quite large. Moreover, the simplifier will float out various pieces of them,
resulting in numerous top-level bindings. Consequently we mark the KindRep
bindings as noinline, ensuring that the float-outs don't make it into the
interface file. This is important since there is generally little benefit to
inlining KindReps and they would otherwise strongly affect compiler performance.

Performance
-----------

Initially I was hoping to also clear up the remaining holes in Typeable's
coverage by adding support for both unboxed tuples (#12409) and unboxed sums
(#13276). While the former was fairly straightforward, the latter ended up being
quite difficult: while the implementation can support them easily, enabling this
support causes thousands of Typeable bindings to be emitted to the GHC.Types as
each arity-N sum tycon brings with it N promoted datacons, each of which has a
KindRep whose size which itself scales with N. Doing this was simply too
expensive to be practical; consequently I've disabled support for the time
being.

Even after disabling sums this change regresses compiler performance far more
than I would like. In particular there are several testcases in the testsuite
which consist mostly of types which regress by over 30% in compiler allocations.
These include (considering the "bytes allocated" metric),

 * T1969:  +10%
 * T10858: +23%
 * T3294:  +19%
 * T5631:  +41%
 * T6048:  +23%
 * T9675:  +20%
 * T9872a: +5.2%
 * T9872d: +12%
 * T9233:  +10%
 * T10370: +34%
 * T12425: +30%
 * T12234: +16%
 * 13035:  +17%
 * T4029:  +6.1%

I've spent quite some time chasing down the source of this regression and while
I was able to make som improvements, I think this approach of generating
Typeable bindings at time of type definition is doomed to give us unnecessarily
large compile-time overhead.

In the future I think we should consider moving some of all of the Typeable
binding generation logic back to the solver (where it was prior to
91c6b1f54aea658b0056caec45655475897f1972). I've opened #13261 documenting this
proposal.
Note: See TracTickets for help on using tickets.