Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,251
    • Issues 4,251
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 394
    • Merge Requests 394
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #13358

Closed
Open
Opened Mar 01, 2017 by Edward Z. Yang@ezyangDeveloper

Role ranges (allow decomposition on newtypes)

Extracted from #13140 (closed).

Today, there is a strange asymmetry between data types, for which the decomposition rule holds (if T A ~R T B then A ~ρ B, where ρ is the role of the type), and newtypes, for which the decomposition rule is unsound.

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.

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 data T a = MkT a, a is used exactly at representational role, but we could also say that a *might* be used nominally, giving the role range nominal-representational.

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 a ~N b evidence to show that T a ~R T b. 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 T A ~R T B, I learn A ~R B. Clearly, the role range nominal-phantom permits the most implementations, but gives the client the least information about equalities.

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 N <= R <= P. To compute the upper bound, we do exactly the same rules, but with the opposite subroling relation: P <= R <= N.

Some examples:

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

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 #13140 (closed)##13358

Edited Mar 10, 2019 by Edward Z. Yang
Assignee
Assign to
None
Milestone
None
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#13358