wiki:DataParallel/ClosureConversion/ClassLess

Version 15 (modified by chak, 7 years ago) (diff)

--

DataParallel/ClosureConversion Up?

Closure conversion without indexed types

The following scheme - if Roman doesn't find any problems with it (he is notorious for that) - should be simpler (as in relying on fewer other mechanisms) than what we had in mind so far for mixing converted and unconverted code. In particular, the scheme gracefully handles any declarations that themselves cannot be converted, but occur in a converted module.

Conversion status

We add to all declaration that are affected by closure conversion a value of type

data StatusCC a 
  = NoCC      -- Declaration has not been converted
  | AsIsCC    -- Conversion not necessary, use original
  | ConvCC a  -- Here is the converted version

For example, Id gets a field of type StatusCC Id. Declarations can be in one of three categories:

  • NoCC: We did not convert that declaration, either because it was declared in an unconverted module or because it uses some feature that prevents conversion.
  • AsIsCC: The original declaration can be directly used in converted code. It's converted form is identical to the original (e.g., type declarations not involving arrows directly or indirectly).
  • ConvCC decl: The variant decl is the closure converted form of the original declaration.

Converting type declarations

Preliminaries

The alternatives of TyCon.TyCon get a new field tyConCC :: StatusCC (TyCon, Id, Id). This field is NoCC for data constructors for which we have no conversion, AsIsCC if the original and the converted form coincide, and ConvCC (T_CC, fr_T, to_T) if we have a converted form.

Moreover, we have a type constructor (-->) that represents closures and we assume that the field tyConCC of (->) has the value ConvCC ((-->), fr_fun, to_fun), where fr_fun and to_fun are appropriate conversion functions.

Conversion rules

If a type declaration for constructor T occurs in a converted module, we need to decide whether to convert the declaration of T. We decide this as follows:

  • If the declaration of T mentions another type constructor S and we have tyConCC S == NoCC, we do not convert T and set its tyConCC field to NoCC as well.
  • If the declaration of T uses any features that we cannot (or for the moment, don't want to) convert, we do not convert T and set its tyConCC field to NoCC.
  • If all type constructors S mentioned in T's definiton have tyConCC S == AsIsCC, we do not convert T and set its tyConCC field to AsIsCC as well. (NB: This implies that T does not mention any function arrows.)
  • Otherwise, generate a converted type declaration T_CC together two conversion functions fr_T and to_T, and set

tyConCC to ConvCC (T_CC, fr_T, to_T). Note that basic types, such as Int and friends, should have tyConCC set to AsIsCC.

Converting 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 :: StatusCC Class field that is ConvCC 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.

Converting 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 :: StatusCC 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.

Converting 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

Converting 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 :: StatusCC Id whose values, for a declaration f, we determine as follows:

  • If Id's declaration uses any features that we cannot (or currently, don't want to) convert, set idCC to NoCC.
  • If all type constructors involved in f's type are marked NoCC or AsIsCC, we set f's idCC field to AsIsCC.
  • Otherwise, convert f and set its ifCC field to ConvCC f_CC.

Converting 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 == NoCC 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 == NoCC: 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 NoCC. (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 == NoCC, 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 NoCC, we keep the selection as is, but apply convert t e from it, where t is the type of the selected method and e the selection expression. If idCC is ConvCC 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 == NoCC or AsIsCC
                   = 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 Ids that have idCC == NoCC 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

This issue has now been addressed.

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

This issue has now been addressed.

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.