Making generated code independent of Futhark's semantics for empty arrays

[athas]

@melsman and I have been talking about handling APL's peculiar shape algebra in a way that is independent of Futhark's semantics for array sizes. This is currently handled by tail2futhark in a fairly hacky way (inserting reshapes), and is probably broken in various edge cases. I have come up with two schemes of doing it. Both should be simplified to the same code by the Futhark optimiser, so it's mostly a question of what we want tail2futhark and its output to look like.

The First Scheme

We define a Futhark type for representing APL values, consisting of a value array and a shape array:

type A 't = { value: t, shape: []i32 }

We will now represent e.g. a two-dimensional APL array of integers as the Futhark type A ([][]i32). Pretty much every TAIL operation is then handled by writing a corresponding Futhark functions that accepts and produces one or more A values. For consistency, we would also use A for representing scalars.

Currently, tail2futhark generates a lot of inline code, e.g. the TAIL expression iotaV(8) becomes (map (\ (x: i32): i32 -> (x + 1)) (iota (8))). Under this scheme, we would instead define a function

let iotaV (n: A i32): A ([]i32) =
  {value= map (\ (x: i32): i32 -> (x + 1)) (iota (#value a)),
   shape= [#value a]}

which would be used whenever iotaV TAIL operator are invoked. The basic idea is to translate every TAIL operator to a corresponding Futhark function (except for a few exotic ones, like power). The resulting code would look very little like sane Futhark, with lots of packing and unpacking into the A record, but the optimiser easily gets rid of all that, I think. It will look a lot like the original TAIL program, however.

The Second Scheme

The idea here is to embed the A type directly in tail2futhark. We will modify the function

compileExp :: T.Exp -> CompilerM F.Exp

to instead read

compileExp :: T.Exp -> CompilerM (F.Exp,F.Exp)

returning a value expression and a shape expression. When compiling many operator, the shape expression is unimportant, and will thus never never be inserted into the generated program.

What do you think, @melsman ?

[melsman]

I would definitely prefer the first scheme, which would allow us to understand the operations and their fusion properties in isolation... It would also simplify tail2futhark, I think...

lør. 30. sep. 2017 kl. 10.10 skrev Troels Henriksen < notifications@github.com>:

@melsman https://github.com/melsman and I have been talking about handling APL's peculiar shape algebra in a way that is independent of Futhark's semantics for array sizes. This is currently handled by tail2futhark in a fairly hacky way (inserting reshapes), and is probably broken in various edge cases. I have come up with two schemes of doing it. Both should be simplified to the same code by the Futhark optimiser, so it's mostly a question of what we want tail2futhark and its output to look like. The First Scheme

We define a Futhark type for representing APL values, consisting of a value array and a shape array:

type A 't = { value: t, shape: []i32 }

We will now represent e.g. a two-dimensional APL array of integers as the Futhark type A ([][]i32). Pretty much every TAIL operation is then handled by writing a corresponding Futhark functions that accepts and produces one or more A values. For consistency, we would also use A for representing scalars.

Currently, tail2futhark generates a lot of inline code, e.g. the TAIL expression iotaV(8) becomes (map (\ (x: i32): i32 -> (x + 1)) (iota (8))). Under this scheme, we would instead define a function

let iotaV (n: A i32): A ([]i32) = {value= map (\ (x: i32): i32 -> (x + 1)) (iota (#value a)), shape= [#value a]}

which would be used whenever iotaV TAIL operator are invoked. The basic idea is to translate every TAIL operator to a corresponding Futhark function (except for a few exotic ones, like power). The resulting code would look very little like sane Futhark, with lots of packing and unpacking into the A record, but the optimiser easily gets rid of all that, I think. It will look a lot like the original TAIL program, however. The Second Scheme

The idea here is to embed the A type directly in tail2futhark. We will modify the function

compileExp :: T.Exp -> CompilerM F.Exp

to instead read

compileExp :: T.Exp -> CompilerM (F.Exp,F.Exp)

returning a value expression and a shape expression. When compiling many operator, the shape expression is unimportant, and will thus never never be inserted into the generated program.

What do you think, @melsman https://github.com/melsman ?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/henrikurms/tail2futhark/issues/11, or mute the thread https://github.com/notifications/unsubscribe-auth/ABHRu3Ck2wFeTDsPfVr7AbU0dff9cA5gks5snfeOgaJpZM4PpfBI .

[athas]

Alright, I'll do it that way.