... | @@ -5,7 +5,7 @@ |
... | @@ -5,7 +5,7 @@ |
|
## Context and Scope
|
|
## Context and Scope
|
|
|
|
|
|
|
|
|
|
The new [HsSyn](implementing-trees-that-grow/hs-syn) AST supporting the TTG idiom (from now on referred to as TTG [HsSyn](implementing-trees-that-grow/hs-syn)) is engineered to subsume five different representations of Haskell syntax:
|
|
The new [HsSyn](implementing-trees-that-grow/hs-syn) AST supporting the TTG idiom (from now on referred to as TTG [HsSyn](implementing-trees-that-grow/hs-syn)) is designed to subsume five different representations of Haskell syntax:
|
|
|
|
|
|
- AST GhcPs: the AST used in GHC's parsing phase
|
|
- AST GhcPs: the AST used in GHC's parsing phase
|
|
- AST GhcRn: the AST used in GHC's renaming phase
|
|
- AST GhcRn: the AST used in GHC's renaming phase
|
... | @@ -14,40 +14,75 @@ The new [HsSyn](implementing-trees-that-grow/hs-syn) AST supporting the TTG idio |
... | @@ -14,40 +14,75 @@ The new [HsSyn](implementing-trees-that-grow/hs-syn) AST supporting the TTG idio |
|
- AST HSE: the AST used in an external tool such as Haskell-Src-Exts
|
|
- AST HSE: the AST used in an external tool such as Haskell-Src-Exts
|
|
|
|
|
|
|
|
|
|
|
|
By "subsume" we mean that it should be possible to instantiate TTG [HsSyn](implementing-trees-that-grow/hs-syn) to serve all five use-cases.
|
|
|
|
|
|
|
|
|
|
The subsumption of above five ASTs is done by providing instances for the extension type families.
|
|
The subsumption of above five ASTs is done by providing instances for the extension type families.
|
|
For instance, the AST for GHC's parsing, renaming, and typechecking are defined by providing instances of the extension type families using accordingly the indices `GhcPs`, `GhcRn`, and `GhcTc`.
|
|
For instance, the AST for GHC's parsing, renaming, and typechecking are defined by providing instances of the extension type families using accordingly the indices `GhcPs`, `GhcRn`, and `GhcTc`.
|
|
[ Here](https://github.com/ghc/ghc/blob/master/compiler/hsSyn/HsExpr.hs#L737-L835) is the actual code providing such instances for the `HsExpr` datatype of expressions in the TTG [HsSyn](implementing-trees-that-grow/hs-syn).
|
|
[ Here](https://github.com/ghc/ghc/blob/master/compiler/hsSyn/HsExpr.hs#L737-L835) is the actual code providing such instances for the `HsExpr` datatype of expressions in the TTG [HsSyn](implementing-trees-that-grow/hs-syn).
|
|
|
|
|
|
|
|
|
|
|
|
## General pattern for TTG
|
|
|
|
|
|
|
|
|
|
|
|
In general a TTG-idiom data type has
|
|
|
|
|
|
|
|
- A type parameter, called the *phase descriptor*, that indexes which particular instantiation is required
|
|
|
|
- One *extension field* in each data constructor, whose type is given by a type family. By giving phase-specific instances to this type family, we can add phase-specific information to the constructor.
|
|
|
|
- One unary *extension constructor* for each data type, whose argument type is given by a type family. By giving phase-specific instances to this type family, we can add extra phase-specific constructors to the type.
|
|
|
|
|
|
|
|
|
|
|
|
For example:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
data Exp x
|
|
|
|
= Var (XVar x) (IdP x)
|
|
|
|
| Lam (XLam x) (IdP x) (Exp x)
|
|
|
|
| App (XApp x) (Exp x) (Exp x)
|
|
|
|
| New (XNew x)
|
|
|
|
|
|
|
|
type family XVar x
|
|
|
|
type family XLam x
|
|
|
|
type family XApp x
|
|
|
|
type family XNew x
|
|
|
|
|
|
|
|
```
|
|
|
|
|
|
Subsuming above five trees fixes the scope of the design space. For example, TTG [HsSyn](implementing-trees-that-grow/hs-syn) is not intended to subsume the AST in the GHC's backend (i.e., GHC Core), but it can indeed be used for other purposes like prettyprinting and IDEs.
|
|
|
|
|
|
Here the phase descriptor is `x`. The first field of each constructor (of type `XVar x` etc) are the extension fields. The data construcotr `XNew` is the extension constructor.
|
|
|
|
|
|
|
|
|
|
|
|
All fields of the data constructors except the first (extension) field are called *payload fields*. They are present in every instantiation of the data type.
|
|
|
|
|
|
## Guiding Principles
|
|
## Guiding Principles
|
|
|
|
|
|
1. The instantiation of TTG [HsSyn](implementing-trees-that-grow/hs-syn) should result in a tree that does not have extra fields and constructors.
|
|
|
|
|
|
|
|
>
|
|
The design of TTG [HsSyn](implementing-trees-that-grow/hs-syn) follows these principles:
|
|
> For example, the `HsExpr GhsPs` expressions of AST GhcPs should not have the constructor `HsUnboundVar` of the post-renaming phases, or its `HsMultiIf` constructor should also not have an unused field (of the type `Type`) to store the related type produced in the typechecking phase.
|
|
|
|
|
|
|
|
>
|
|
1. The base TTG [HsSyn](implementing-trees-that-grow/hs-syn) should have all the constructors common across all five ASTs (the *common data constructors*). These constructors should have, as payload fields, all the fields common across all five ASTs.
|
|
> As a result, the instantiated TTG [HsSyn](implementing-trees-that-grow/hs-syn) should not depend on the code from the other phases. Hence, the base (uninstantiated) TTG [HsSyn](implementing-trees-that-grow/hs-syn) should not depend on any GHC/TH/HSE-specific code.
|
|
|
|
|
|
|
|
>
|
|
1. Note, however, that the type of a payload field of a constructor may vary with phase. For example, in `Lam` above, the first payload field has type `Id x`, and that may vary with phase:
|
|
> For example, if `HsExpr GhsPs` expressions of AST GhcPs had the constructor `HsUnboundVar` then it had to depend on the code defining `UnboundVar` (a field of `HsUnboundVar`) in the renaming phase, or if its constructor `MultiIf` had a field of type `Type` then it had to depend on the code defining `Type` in the typechecking phase.
|
|
|
|
|
|
|
|
1. The base TTG [HsSyn](implementing-trees-that-grow/hs-syn) should have all the constructors common across all five ASTs, and these constructors should have all the fields common across all five ASTs (even if the type of some fields vary from an AST to another).
|
|
```wiki
|
|
|
|
type family IdP x
|
|
|
|
type instance IdP GhcPs = RdrName
|
|
|
|
type instance IdP GhcRn = Name
|
|
|
|
type instance IdP GhcTc = Id
|
|
|
|
```
|
|
|
|
|
|
>
|
|
But it is still a payload field, because every instantiation of `Exp` has a lambda with a binder; albeit the type of that binder field varies. This happens in [HsSyn](implementing-trees-that-grow/hs-syn): for example, the type of the common (payload) field of the common constructor `HsVar`of `HsExpr x` is `IdP x` where `IdP` is a type family and `x` the phase descriptor.
|
|
> SPJ refers to these common fields as "payload fields" (as opposed to extension fields).
|
|
|
|
|
|
|
|
1. The constructors that are not common are introduced using TTG's new constructor extensions.
|
|
1. The non-payload (i.e. phase-specific) fields of a data constructor are grouped together and introduced via the extension field. Similarly the phase-specific data constructors are introduced using the extension constructor.
|
|
|
|
|
|
1. For common constructors, their fields that are not common are grouped together and introduced using TTG's new field extensions.
|
|
1. The instantiation of TTG [HsSyn](implementing-trees-that-grow/hs-syn), for a particular phase, should result in a tree that has no redundant fields and constructors.
|
|
|
|
|
|
|
|
>
|
|
|
|
> For example, the `HsExpr GhsPs` expressions of AST GhcPs should not have the constructor `HsUnboundVar` of the post-renaming phases, or its `HsMultiIf` constructor should also not have an unused field (of the type `Type`) to store the related type produced in the typechecking phase.
|
|
|
|
|
|
1. For common constructors, their common fields with a varying type, are given a type using a new type family that extracts from the phase descriptor the type specific to each AST.
|
|
>
|
|
|
|
> As a result, the instantiated TTG [HsSyn](implementing-trees-that-grow/hs-syn) should not depend on the code from the other phases. Hence, the base (uninstantiated) TTG [HsSyn](implementing-trees-that-grow/hs-syn) should not depend on any GHC/TH/HSE-specific code.
|
|
|
|
|
|
>
|
|
>
|
|
> For example, the type of the common (payload) field of the common constructor `HsVar`of `HsExpr x` is `IdP x` where `IdP` is a type family and `x` the phase descriptor.
|
|
> For example, if `HsExpr GhsPs` expressions of AST GhcPs had the constructor `HsUnboundVar` then it had to depend on the code defining `UnboundVar` (a field of `HsUnboundVar`) in the renaming phase, or if its constructor `MultiIf` had a field of type `Type` then it had to depend on the code defining `Type` in the typechecking phase.
|
|
|
|
|
|
## Example
|
|
## Example
|
|
|
|
|
... | @@ -60,9 +95,9 @@ module Parsing where |
... | @@ -60,9 +95,9 @@ module Parsing where |
|
-- the definition of RdrName
|
|
-- the definition of RdrName
|
|
-- ...
|
|
-- ...
|
|
|
|
|
|
data ExpPs
|
|
data ExpPs
|
|
= Var RdrName
|
|
= Var RdrName
|
|
| Abs RdrName ExpPs
|
|
| Lam RdrName ExpPs
|
|
| App ExpPs ExpPs
|
|
| App ExpPs ExpPs
|
|
```
|
|
```
|
|
|
|
|
... | @@ -74,7 +109,7 @@ module Renaming where |
... | @@ -74,7 +109,7 @@ module Renaming where |
|
|
|
|
|
data ExpRn
|
|
data ExpRn
|
|
= Var Name
|
|
= Var Name
|
|
| Abs Name ExpRn
|
|
| Lam Name ExpRn
|
|
| App ExpRn ExpRn
|
|
| App ExpRn ExpRn
|
|
| UVar UnboundVar
|
|
| UVar UnboundVar
|
|
```
|
|
```
|
... | @@ -87,7 +122,7 @@ module Typechecking where |
... | @@ -87,7 +122,7 @@ module Typechecking where |
|
|
|
|
|
data ExpTc
|
|
data ExpTc
|
|
= Var Id
|
|
= Var Id
|
|
| Abs Id ExpTc
|
|
| Lam Id ExpTc
|
|
| App Type ExpTc ExpTc
|
|
| App Type ExpTc ExpTc
|
|
| UVar UnboundVar
|
|
| UVar UnboundVar
|
|
```
|
|
```
|
... | @@ -98,18 +133,18 @@ Based on the TTG idiom, we will have a base declaration such as the following. |
... | @@ -98,18 +133,18 @@ Based on the TTG idiom, we will have a base declaration such as the following. |
|
```wiki
|
|
```wiki
|
|
module AST where
|
|
module AST where
|
|
|
|
|
|
data Exp x
|
|
data Exp x
|
|
= Var (XVar x) (XId x)
|
|
= Var (XVar x) (IdP x)
|
|
| Abs (XAbs x) (XId x) (Exp x)
|
|
| Lam (XLam x) (IdP x) (Exp x)
|
|
| App (XApp x) (Exp x) (Exp x)
|
|
| App (XApp x) (Exp x) (Exp x)
|
|
| New (XNew x)
|
|
| New (XNew x)
|
|
|
|
|
|
type family XVar x
|
|
type family XVar x
|
|
type family XAbs x
|
|
type family XLam x
|
|
type family XApp x
|
|
type family XApp x
|
|
type family XNew x
|
|
type family XNew x
|
|
|
|
|
|
type family XId x
|
|
type family IdP x
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
... | @@ -127,11 +162,11 @@ data Ps |
... | @@ -127,11 +162,11 @@ data Ps |
|
type ExpPs = Exp Ps
|
|
type ExpPs = Exp Ps
|
|
|
|
|
|
type instance XVar Ps = ()
|
|
type instance XVar Ps = ()
|
|
type instance XAbs Ps = ()
|
|
type instance XLam Ps = ()
|
|
type instance XApp Ps = ()
|
|
type instance XApp Ps = ()
|
|
type instance XNew Ps = Void
|
|
type instance XNew Ps = Void
|
|
|
|
|
|
type instance XId Ps = RdrName
|
|
type instance IdP Ps = RdrName
|
|
```
|
|
```
|
|
|
|
|
|
```wiki
|
|
```wiki
|
... | @@ -145,11 +180,11 @@ data Rn |
... | @@ -145,11 +180,11 @@ data Rn |
|
type ExpRn = Exp Rn
|
|
type ExpRn = Exp Rn
|
|
|
|
|
|
type instance XVar Rn = ()
|
|
type instance XVar Rn = ()
|
|
type instance XAbs Rn = ()
|
|
type instance XLam Rn = ()
|
|
type instance XApp Rn = ()
|
|
type instance XApp Rn = ()
|
|
type instance XNew Rn = UnboundVar
|
|
type instance XNew Rn = UnboundVar
|
|
|
|
|
|
type instance XId Rn = Name
|
|
type instance IdP Rn = Name
|
|
```
|
|
```
|
|
|
|
|
|
```wiki
|
|
```wiki
|
... | @@ -163,9 +198,9 @@ data Tc |
... | @@ -163,9 +198,9 @@ data Tc |
|
type ExpTc = Exp Tc
|
|
type ExpTc = Exp Tc
|
|
|
|
|
|
type instance XVar Tc = ()
|
|
type instance XVar Tc = ()
|
|
type instance XAbs Tc = ()
|
|
type instance XLam Tc = ()
|
|
type instance XApp Tc = Type
|
|
type instance XApp Tc = Type
|
|
type instance XNew Tc = UnboundVar
|
|
type instance XNew Tc = UnboundVar
|
|
|
|
|
|
type instance XId Tc = Id
|
|
type instance IdP Tc = Id
|
|
``` |
|
``` |
|
|
|
\ No newline at end of file |