Version 7 (modified by chak, 8 years ago) (diff) |
---|

DataParallel/ClosureConversion Up?

## Closure conversion without a conversion class

The following scheme - if Roman doesn't find any problems with it (he is notorious for that) - should be simpler than what we had in mind so far for mixing converted and unconverted code.

### Type declarations

If a type declaration for constructor `T` occurs in a converted module, we
(1) generate a converted type declaration `T_CC` together two conversion functions `fr_T` and `to_T`, and
(2) store these three names in the representation of `T`.
Concerning Point (2), more precisely the alternatives of `TyCon.TyCon` get a new field `tyConCC :: Maybe (TyCon, Id, Id)`. This field is `Nothing` for data constructors for which we have no conversion and `Just (T_CC, fr_T, to_T)` if we have a conversion.

Incidentally, if during conversion we come across a type declaration that we don't know how to convert (as it uses fancy extensions), we just don't generate a conversion.

Note that basic types, such as `Int` and friends, would have `tyConCC` set to `Nothing`, which is exactly what we want.

### Class declarations

If we come across a class declaration for a class `C` during conversion, we convert it generating `C_CC`. Like with type constructors, `Class.Class` gets a `classCC :: Maybe Class` field that is `Just C_CC` for classes that have a conversion. We also ensure that the `classTyCon` of `C`, let's call it `T_C`, refers to `T_C_CC` and `fr_T_C` and `to_T_C` in its `tyConCC` field, and that the `classTyCon` of `C_CC` is `T_C_CC`.

### Instance declarations

If we encounter an instance declaration for `C tau` during conversion, there are two alternatives: we have a conversion for `C` or not:

- if we do not have a conversion, we generate an instance (and hence dfun) for
`C tau^`, where`tau^`is the closure converted`tau`; - if we have a conversion, we generate an instance for
`C_CC tau^`.

In any case, we add a field `is_CC :: Just Instance` to `InstEnv.Instance` that contains the additionally generated instance. And in both cases, we should be able to derive the required code for the dfun from the definition of `C tau`. We also make sure that the `dfun`'s `idCC` field (see below) is set to that of the converted dfun.

### Type terms

We determine the converted type `t^` of `t` as follows:

T^ = T_CC , if available T , otherwise a^ = a (t1 t2)^ = t1^ t2^ (t1 -> t2)^ = Clo t1 t2 (forall a.t)^ = forall a.t^ (C t1 => t2)^ = C_CC t1^ => t2^ , if available C t1^ => t2^ , otherwise

### Value bindings

When converting a toplevel binding for `f :: t`, we generate `f_CC :: t^`. The alternatives `GlobalId` and `LocalId` of `Var.Var` get a new field `idCC :: Maybe Id` and the `Id` for `f` contains `Just f_CC` in that field.

### Core terms

Apart from the standard rules, we need to handle the following special cases:

- We come across a value variable
`v`where`idCC v == Nothing`whose type is`t`: we generate`convert t v`(see below). - We come across a case expression where the scrutinised type
`T`has`tyConCC T == Nothing`: we leave the case expression as is (i.e., unconverted), but make sure that the`idCC`field of all variables bound by patterns in the alternatives have their`idCC`field as`Nothing`. (This implies that the previous case will kick in and convert the (unconverted) values obtained after decomposition.) - Whenever we have an FC
`cast`from or to a newtype`T`, where`tyConCC T == Nothing`, we need to add a`convert tau`or`trevnoc tau`, respectively. We can spot these casts by inspecting the kind of every coercion used in a cast. One side of the equality will have the newtype constructor. - We come across a dfun: If its
`idCC`field is`Nothing`, we keep the selection as is, but apply`convert t e`from it it, where`t`is the type of the selected method and`e`the selection expression. If`idCC`is`Just d_CC`, and the dfun's class is converted,`d_CC`is fully converted. If it's class is not converted, we also keep the selection unconverted, but have a bit less to do in`convert t e`.**TODO**This needs to be fully worked out.

### Generating conversions

Whenever we had `convert t e` above, where `t` is an unconverted type and `e` a converted expression, we need to generate some conversion code. This works roughly as follows in a type directed manner:

convert T = id , if tyConCC T == Nothing = to_T , otherwise convert a = id convert (t1 t2) = convert t1 (convert t2) convert (t1 -> t2) = createClosure using (trevnoc t1) and (convert t2) on argument and result resp.

where `trevnoc` is the same as `convert`, but using `from_T` instead of `to_T`.

The idea is that conversions for parametrised types are parametrised over conversions of their parameter types. Wherever we call a function using parametrised types, we will know these type parameters (and hence can use `convert`) to compute their conversions. This fits well, because it is at occurences of `Id`s that have `idCC == Nothing` where we have to perform conversion.

The only remaining problem is that a type parameter to a function may itself be a type parameter got from a calling function; so similar to classes, we need to pass conversion functions with every type parameter. So, maybe we want to stick `fr` and `to` into a class after all and requires that all functions used in converted contexts have the appropriate contexts in their signatures.

### Issues, aka rl's complaints

#### Non-converted versus unchanged type declarations

Many type declarations will not be changed by conversion, as they do not contain any arrows. Hence, it is more economic to avoid generating a `_CC` version of these declarations. I initially thought that we can ignore this for a moment, because it is only an optimisation. However, consider

data T = MkT Int data S = MkS (Int -> Int)

As we don't convert `Int`, we cannot convert `T` and `S`, which is a shame as their conversion is simple and (in the vectorisation case may affect performance dramatically). As a matter of fact, if we identify declarations that need not be converted, then we would mark `Int` and `T` as such and can convert `S` easily.

#### FC Coercions

Closure conversion happens on Core, which means that constructors, such as `MkT` of

-- unconverted newtype T a = MkT (a -> a)

in a definition

-- converted foo :: (a -> a) -> T a foo f = MkT f

have vanished, leaving only a coercion. As `T` is not converted, we need to notice that we need to generate `MkT (fr f)`. So, we need to spot the conversion representing `MkT`.

Generally, we need a story about treating coercions during conversion.

#### Function type constructor

It is clear how to treat types involving subtypes of the form `a -> b`. It is less clear how to deal with partial applications of `(->)`. Consider

-- unconverted data T f = T (Int -> Int) (f Int Int)

used as `T (->)` in converted code. What is `convert (T (->))`?

#### Classes

It might be sufficient to never convert class declarations as a whole, but only their representation types.