wiki:DataParallel/ClosureConversion

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

--

DataParallel Up?

Closure conversion as part of vectorisation

TODO Describe the treatment of higher-order functions and closure conversion here. The relevant paper is http://www.cse.unsw.edu.au/~chak/papers/LCK06.html. The approach is described in more detail in http://opus.kobv.de/tuberlin/volltexte/2006/1286/.

Closure-converted types as indexed-types

One option for implementing closure-conversion is to represent closure-converted types as an indexed type whose type index is the original type and to combine that indexed type in a type class with methods for converting between closure-converted and vanilla terms. The details are under indexed closure conversion. There are two potential benefits for this approach: (1) we will probably have to do something similar for vectorisation anyway - see the requirements of vectorisation? - and (2) it seems that we need less bookkeeping (e.g., the name of a closure converted data type is just the indexed type with the original data type as its index). However, there are problems, too; in particular, as we currently don't have class contexts and polytypes as type indexes.

Closure conversion without classes

Here is an alternative scheme that does no rely on conversion classes.

Requirements of closure conversion

The straight forward part

The actual closure-conversion transformation on lambda terms, which we intend to perform on Core.

Type declarations, classes, and instances

Type declarations. If the program contains a type declaration including an arrow type, we need a closure-converted version of that declaration (for use in the closure converted code); e.g., for

data T = MkT (Int -> Int)

we need

data T_CC = MkT_CC (Clo Int Int)

Note how this also introduces new constructor names.

Classes. Moreover, if the closure-converted code uses a type class, we need a closure-converted type class. It might appear that this is a non-issue on Core as classes have already been desugared to plain System F. The trouble is that GHC does not use plain System F. It extends it by a whole array of extra type features. In particular, classes induce datatype declarations., and yhey almost always contain arrow types. Hence, as we just discussed, they need to be transformed. Matters are complicated by GHC not actually generating standalone datatypes declarations that are emitted into interface files, a class declaration siliently implies a data declaration - GHC calls this an iface declaration sub-binder. So, it appears best to create for every class a closure-converted class that - as all other class declarations - implies the closure-converted class representation datatype.

Instances. When we call overloaded closure-converted functions, we need to supply closure-converted dictionaries; i.e., closure-converted dfuns.

Interface files

How much information do we want to put into interface files? For example, for type declarations, we can add the closure-converted declaration to the interface file or we can only add the vanilla one and have the importing modules derive the converted form on the fly during iface type checking - similar to how iface declaration sub-binders are generated on the fly, instead of being put into the interface files.

Mixing converted and vanilla code

Mixing converted and vanilla code for closure-conversion is simple as long as we only have lambda terms (we just generate and apply closure as appropriate at places where we move from one representation to another). However, data types make this more involved again. Imagine the following scenario:

-- converted code
data T = MkT (Int -> Int)

-- unconverted code
foo = MkT ((+) (1::Int))

-- converted code
appT :: T -> Int -> Int
appT (MkT f) x = f x

bar = appT foo

Here the result of foo needs to be converted before we can call appT in bar. In other words, we need conversion functions between converted and unconverted versions of data types.

A problem becomes apparent when we change the example slightly:

-- unconverted code
data T = MkT (Int -> Int)
foo = MkT ((+) (1::Int))

-- converted code
appT :: T -> Int -> Int
appT (MkT f) x = f x

bar = appT foo

Now, we don't have a converted version of T available. Converting it on the fly might be problematic. If appT and bar reside in different modules, we convert T twice and need to make sure the two versions are compatible. Even worse, the module holding bar may only import T abstractly and hence can neither derive the converted version of T nor can it infer suitable conversion functions. In this case, we have to give up on converting appT foo (and maybe all of bar).

Alternatively, we might decide that we do not convert the case expression in appT's Core code that scrutinises its first argument. Then, the type of the converted function would be

appT_CC :: Clo T (Clo Int Int)

i.e., it still uses T, not T_CC. As callers of appT_CC also will not have a converted version of T available, everything still fits together nicely. This appears to be a simpler scheme than on-the-fly type conversions.

The same should work for classes and their dictionaries. If we can use unconverted functions in converted code, we can also select from unconverted dictionaries and use the unconverted methods.


OLD STUFF

From the Skype discussion, 16 Mar 07

For each function f::ty, create a closure-converted function fc::ty', where ty' is the closure-converted verion of ty. Optimisation: make fc=f, if the code for fc will be identical to that of f.

For each data type T, create a closure-converted data type Tc, whose constructors use Clo instead of ->. Optimisation: if Tc is identical to T, don't create a new data type.

Attachments (1)

Download all attachments as: .zip