GHC: Ticket #13358: Role ranges (allow decomposition on newtypes)
http://trac.haskell.org/trac/ghc/ticket/13358
<p>
Extracted from <a class="closed ticket" href="http://trac.haskell.org/trac/ghc/ticket/13140" title="#13140: feature request: Handle subtyping relation for roles in Backpack (closed: fixed)">#13140</a>.
</p>
<p>
Today, there is a strange asymmetry between data types, for which the decomposition rule holds (if <code>T A ~R T B</code> then <code>A ~ρ B</code>, where ρ is the role of the type), and newtypes, for which the decomposition rule is unsound.
</p>
<p>
I believe the root cause of this problem is the fact that we only maintain a single role per type parameter, while in fact what we need is a role *range* (i.e., and lower and upper role bound) to specify what inferences can be made about a type. Here's how it works.
</p>
<p>
Every type parameter is ascribed a role range, specifying the possible roles by which the type parameter might possibly be used. For example, if I write <code>data T a = MkT a</code>, <code>a</code> is used exactly at representational role, but we could also say that a *might* be used nominally, giving the role range nominal-representational.
</p>
<p>
The lower bound (nominal is lowest in subroling) specifies at what role the application rule is valid: if I say that the role is at least nominal, then I must provide <code>a ~N b</code> evidence to show that <code>T a ~R T b</code>. The upper bound (phantom is highest) specifies at what role the decomposition rule is valid. If I say that the role is at most phantom, I learn nothing from decomposition; but if I say the role is at most representational, when <code>T A ~R T B</code>, I learn <code>A ~R B</code>. Clearly, the role range nominal-phantom permits the most implementations, but gives the client the least information about equalities.
</p>
<p>
How do we tell if a role range is compatible with a type? The lower bound (what we call a role today) is computed by propagating roles through, but allowing substitution of roles as per the subroling relationship <code>N <= R <= P</code>. To compute the upper bound, we do exactly the same rules, but with the opposite subroling relation: <code>P <= R <= N</code>.
</p>
<p>
Some examples:
</p>
<pre class="wiki">type role T representational..representational
newtype T a = MkT a
-- T a ~R T b implies a ~R b
type role T nominal..representational -- NB: nominal..nominal illegal!
newtype T a = MkT a
-- T a ~R T b implies a ~R b, BUT
-- a ~R b is insufficient to prove T a ~R T b (you need a ~N b)
type role T nominal..phantom -- NB: nominal..representational illegal!
newtype T a = MkT Int
-- T a ~R T b implies a ~P b (i.e. we don't learn anything)
-- a ~N b implies T a ~R T b
</pre><p>
Richard wonders if we could use this to solve the "recursive newtype unwrapping" problem. Unfortunately, because our solver is guess-free, we must also maintain the most precise role for every type constructor. See <a class="ext-link" href="https://ghc.haskell.org/trac/ghc/ticket/13140#comment:12"><span class="icon"></span>https://ghc.haskell.org/trac/ghc/ticket/13140#comment:12</a>
</p>
en-usGHChttp://trac.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://trac.haskell.org/trac/ghc/ticket/13358
Trac 1.2.2ezyangWed, 01 Mar 2017 08:33:39 GMTdescription changed
http://trac.haskell.org/trac/ghc/ticket/13358#comment:1
http://trac.haskell.org/trac/ghc/ticket/13358#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/13358?action=diff&version=1">diff</a>)
</li>
</ul>
TicketsimonpjWed, 01 Mar 2017 08:43:51 GMTkeywords changed
http://trac.haskell.org/trac/ghc/ticket/13358#comment:2
http://trac.haskell.org/trac/ghc/ticket/13358#comment:2
<ul>
<li><strong>keywords</strong>
<em>Roles</em> added
</li>
</ul>
TicketRyanGlScottWed, 01 Mar 2017 10:27:21 GMTcc changed
http://trac.haskell.org/trac/ghc/ticket/13358#comment:3
http://trac.haskell.org/trac/ghc/ticket/13358#comment:3
<ul>
<li><strong>cc</strong>
<em>RyanGlScott</em> added
</li>
</ul>
TicketezyangWed, 01 Mar 2017 19:27:30 GMTpriority changed
http://trac.haskell.org/trac/ghc/ticket/13358#comment:4
http://trac.haskell.org/trac/ghc/ticket/13358#comment:4
<ul>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>low</em>
</li>
</ul>
Ticket