... | @@ -7,11 +7,23 @@ This page is part of [ImplementingTreesThatGrow](implementing-trees-that-grow). |
... | @@ -7,11 +7,23 @@ This page is part of [ImplementingTreesThatGrow](implementing-trees-that-grow). |
|
## Example
|
|
## Example
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Here's our example:
|
|
Here's our example:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
type family XOverLit p
|
|
type family XOverLit p
|
|
dataHsOverLit p =OverLit(XOverLit p)(HsExpr p)dataGhcPass(c ::Pass)derivinginstanceTypeable c =>Data(GhcPass c)dataPass=Parsed|Renamed|TypecheckedtypeinstanceXOverLit(GhcPass'Parsed)=PlaceHoldertypeinstanceXOverLit(GhcPass'Renamed)=NametypeinstanceXOverLit(GhcPass'Typechecked)=Type
|
|
data HsOverLit p = OverLit (XOverLit p) (HsExpr p)
|
|
|
|
|
|
|
|
data GhcPass (c :: Pass)
|
|
|
|
deriving instance Typeable c => Data (GhcPass c)
|
|
|
|
|
|
|
|
data Pass = Parsed | Renamed | Typechecked
|
|
|
|
|
|
|
|
type instance XOverLit (GhcPass 'Parsed ) = PlaceHolder
|
|
|
|
type instance XOverLit (GhcPass 'Renamed ) = Name
|
|
|
|
type instance XOverLit (GhcPass 'Typechecked) = Type
|
|
|
|
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
... | @@ -20,10 +32,14 @@ We want a `Data` instance for this type. |
... | @@ -20,10 +32,14 @@ We want a `Data` instance for this type. |
|
### PLAN A
|
|
### PLAN A
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I propose
|
|
I propose
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
derivinginstance(Typeable p,Data(XOverLit(GhcPass p)))=>Data(HsOverLit(GhcPass p))
|
|
deriving instance (Typeable p, Data (XOverLit (GhcPass p))) =>
|
|
|
|
Data (HsOverLit (GhcPass p))
|
|
|
|
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
... | @@ -36,8 +52,10 @@ This is what is currently implemented in GHC master. It works, but every time th |
... | @@ -36,8 +52,10 @@ This is what is currently implemented in GHC master. It works, but every time th |
|
### PLAN B
|
|
### PLAN B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alan would like to see
|
|
Alan would like to see
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
deriving instance Data (HsOverLit (GhcPass p))
|
|
deriving instance Data (HsOverLit (GhcPass p))
|
|
```
|
|
```
|
... | @@ -49,12 +67,17 @@ which should have all the information available to the derivation process, since |
... | @@ -49,12 +67,17 @@ which should have all the information available to the derivation process, since |
|
This "does not compile".
|
|
This "does not compile".
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alan has discovered that the three instances:
|
|
Alan has discovered that the three instances:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
derivinginstanceData(HsOverLit(GhcPass'Parsed))derivinginstanceData(HsOverLit(GhcPass'Renamed))derivinginstanceData(HsOverLit(GhcPass'Typechecked))
|
|
deriving instance Data (HsOverLit (GhcPass 'Parsed ))
|
|
|
|
deriving instance Data (HsOverLit (GhcPass 'Renamed))
|
|
|
|
deriving instance Data (HsOverLit (GhcPass 'Typechecked))
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
**will** compile, but only with GHC 8.2.1, not with 8.0.2, due to a flaw in the standalone deriving process.
|
|
**will** compile, but only with GHC 8.2.1, not with 8.0.2, due to a flaw in the standalone deriving process.
|
|
|
|
|
|
|
|
|
... | @@ -184,18 +207,36 @@ I have no idea how this would affect `Data`. |
... | @@ -184,18 +207,36 @@ I have no idea how this would affect `Data`. |
|
### Plan H
|
|
### Plan H
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The performance issue of Plan A presumably comes from the fact that we have instance search running every time we are typechecking an instance with a large constraint set. That is:
|
|
The performance issue of Plan A presumably comes from the fact that we have instance search running every time we are typechecking an instance with a large constraint set. That is:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
typeLargeConstraintSet p =(Outputable(XIPBinds p),Outputable(XViaStrategy p),...,...,...,...-- and so on, for each extension field)instanceLargeConstraintSet p =>Outputable(HsExpr p)instanceLargeConstraintSet p =>Outputable(HsPat p)instanceLargeConstraintSet p =>Outputable(HsType p)instanceLargeConstraintSet p =>Outputable(HsBinds p)instance(LargeConstraintSet idL,LargeConstraintSet idR,Outputable body)=>Outputable(StmtLR idL idR body)...
|
|
type LargeConstraintSet p =
|
|
|
|
( Outputable (XIPBinds p)
|
|
|
|
, Outputable (XViaStrategy p)
|
|
|
|
, ...
|
|
|
|
, ...
|
|
|
|
, ...
|
|
|
|
, ... -- and so on, for each extension field
|
|
|
|
)
|
|
|
|
|
|
|
|
instance LargeConstraintSet p => Outputable (HsExpr p)
|
|
|
|
instance LargeConstraintSet p => Outputable (HsPat p)
|
|
|
|
instance LargeConstraintSet p => Outputable (HsType p)
|
|
|
|
instance LargeConstraintSet p => Outputable (HsBinds p)
|
|
|
|
instance (LargeConstraintSet idL, LargeConstraintSet idR, Outputable body) => Outputable (StmtLR idL idR body)
|
|
|
|
...
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
Every time we add something to the `LargeConstraintSet`, typechecking each of these instances slows down.
|
|
Every time we add something to the `LargeConstraintSet`, typechecking each of these instances slows down.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Instead, we could create a single constraint, `OutputableX`, and hide the large constraint set inside it:
|
|
Instead, we could create a single constraint, `OutputableX`, and hide the large constraint set inside it:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
class OutputableX p where
|
|
class OutputableX p where
|
|
withOutputableX :: (LargeConstraintSet p => r) -> r
|
|
withOutputableX :: (LargeConstraintSet p => r) -> r
|
... | @@ -204,16 +245,23 @@ classOutputableX p where |
... | @@ -204,16 +245,23 @@ classOutputableX p where |
|
|
|
|
|
and then
|
|
and then
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
instanceOutputableX p =>Outputable(HsExpr p)instanceOutputableX p =>Outputable(HsPat p)instanceOutputableX p =>Outputable(HsType p)instanceOutputableX p =>Outputable(HsBinds p)instance(OutputableX idL,OutputableX idR,Outputable body)=>Outputable(StmtLR idL idR body)
|
|
instance OutputableX p => Outputable (HsExpr p)
|
|
|
|
instance OutputableX p => Outputable (HsPat p)
|
|
|
|
instance OutputableX p => Outputable (HsType p)
|
|
|
|
instance OutputableX p => Outputable (HsBinds p)
|
|
|
|
instance (OutputableX idL, OutputableX idR, Outputable body) => Outputable (StmtLR idL idR body)
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
becomes fast, as it only has one constraint: `OutputableX`. Operationally, we have `LargeConstraintSet p` stored inside `OutputableX`, but for the typechecker, this is hidden information.
|
|
becomes fast, as it only has one constraint: `OutputableX`. Operationally, we have `LargeConstraintSet p` stored inside `OutputableX`, but for the typechecker, this is hidden information.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We will have only three instances of `OutputableX`, defined as follows:
|
|
We will have only three instances of `OutputableX`, defined as follows:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
instance OutputableX (GhcPass 'Parsed) where
|
|
instance OutputableX (GhcPass 'Parsed) where
|
|
withOutputableX r = r
|
|
withOutputableX r = r
|
... | @@ -243,13 +291,17 @@ Inside `withOutputableX @p`, we have `LargeConstraintSet p` in context. |
... | @@ -243,13 +291,17 @@ Inside `withOutputableX @p`, we have `LargeConstraintSet p` in context. |
|
### Plan H\*
|
|
### Plan H\*
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Plan H relies on the assumption that calls to `withOutputableX` will not lead to the same kind of performance degradation. This is an untested, but hopefully true assumption. In case it proves to be wrong, we can augment this plan by having separate methods for each constraint:
|
|
Plan H relies on the assumption that calls to `withOutputableX` will not lead to the same kind of performance degradation. This is an untested, but hopefully true assumption. In case it proves to be wrong, we can augment this plan by having separate methods for each constraint:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
class OutputableX p where
|
|
class OutputableX p where
|
|
withOutputableXIPBinds :: (Outputable (XIPBinds p) => r) -> r
|
|
withOutputableXIPBinds :: (Outputable (XIPBinds p) => r) -> r
|
|
withOutputableXViaStrategy :: (Outputable (XViaStrategy p) => r) -> r
|
|
withOutputableXViaStrategy :: (Outputable (XViaStrategy p) => r) -> r
|
|
.........-- and so on, for each extension field
|
|
...
|
|
|
|
...
|
|
|
|
... -- and so on, for each extension field
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
... | @@ -272,14 +324,17 @@ This means that we're not dealing with `LargeConstraintSet` at all, we're workin |
... | @@ -272,14 +324,17 @@ This means that we're not dealing with `LargeConstraintSet` at all, we're workin |
|
It is still painful generating three virtually identical chunks of traversal code.
|
|
It is still painful generating three virtually identical chunks of traversal code.
|
|
So suppose we went back to
|
|
So suppose we went back to
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
derivinginstance(...)=>Data(OverLit(GhcPass p))where…
|
|
deriving instance (...)
|
|
|
|
=> Data (OverLit (GhcPass p)) where…
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
We'd get unresolved constraints like `Data (XOverLit (GhcPass p))`. Perhaps we
|
|
We'd get unresolved constraints like `Data (XOverLit (GhcPass p))`. Perhaps we
|
|
could resolve them like this
|
|
could resolve them like this
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
instance Data (XOverLIt (GhcPass p)) where
|
|
instance Data (XOverLIt (GhcPass p)) where
|
|
gmapM f x = x
|
|
gmapM f x = x
|
... | @@ -296,9 +351,11 @@ That might not be so bad, for now! |
... | @@ -296,9 +351,11 @@ That might not be so bad, for now! |
|
If there were cases when we really did want to look at those extension fields,
|
|
If there were cases when we really did want to look at those extension fields,
|
|
we still could, by doing a runtime test, like this:
|
|
we still could, by doing a runtime test, like this:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
instance IsGhcPass p => Data (XOverLIt (GhcPass p)) where
|
|
instance IsGhcPass p => Data (XOverLIt (GhcPass p)) where
|
|
gmapM =case ghcPass @p ofIsParsed-> gmapM
|
|
gmapM = case ghcPass @p of
|
|
|
|
IsParsed -> gmapM
|
|
IsRenamed -> gmapM
|
|
IsRenamed -> gmapM
|
|
IsTypechecked -> gmapM
|
|
IsTypechecked -> gmapM
|
|
...etc...
|
|
...etc...
|
... | @@ -307,12 +364,19 @@ instanceIsGhcPass p =>Data(XOverLIt(GhcPass p))where |
... | @@ -307,12 +364,19 @@ instanceIsGhcPass p =>Data(XOverLIt(GhcPass p))where |
|
|
|
|
|
Here I'm positing a new class and GADT:
|
|
Here I'm positing a new class and GADT:
|
|
|
|
|
|
|
|
|
|
```
|
|
```
|
|
class IsGhcPass p where
|
|
class IsGhcPass p where
|
|
ghcPass :: IsGhcPassT p
|
|
ghcPass :: IsGhcPassT p
|
|
|
|
|
|
dataIsGhcPassT p whereIsParsed::IsGhcPassParsedIsRenamed::IsGhcPassRenamedIsTypechecked::IsGhcPassTypecheckedinstanceIsGhcPassParsedwhere
|
|
data IsGhcPassT p where
|
|
ghcPass =IsParsed...etc...
|
|
IsParsed :: IsGhcPass Parsed
|
|
|
|
IsRenamed :: IsGhcPass Renamed
|
|
|
|
IsTypechecked :: IsGhcPass Typechecked
|
|
|
|
|
|
|
|
instance IsGhcPass Parsed where
|
|
|
|
ghcPass = IsParsed
|
|
|
|
...etc...
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
... | | ... | |