Should backends deal with one-argification?

[dcrc2]

Compiling prelude.ks with ksc currently produces output such as this:

(edef [add (Tuple Float Float)] Float ((Tuple Float Float)))
(def
 [fwd [add (Tuple Float Float)]] Float
 ((xt : (Tuple Float Float)) (dxt : (Tuple Float Float)))
 (let (((dx1 dx2) dxt)) ([add (Tuple Float Float)] dx1 dx2)))

Note that the arguments to the edef are given in one-argified form, but the arguments to the def of [fwd add] are not. Also, the call to the edef-ed function uses multiple arguments. This currently causes type-checking failures in ksc-mlir. How should we be dealing with this?

(Note: the fact that structured names are always one-argified isn't a problem: as far as the backend is concerned, the structured name is just a name - we don't care what relationship it has to the actual arguments.)

Do backends need to understand one-argification, so that they recognize that (edef f Float ((Tuple Float Float))) is equivalent to (edef f Float (Float Float))?

Or should ksc's output be changed so that it consistently uses one form or the other (ie. decide whether we want the .kso to use one-arg or multi-arg form?)

[toelli-msft]

Would it help if we removed syntax of the form (edef f Float (Float Float))? I would much rather see (edef f Float (Tuple Float Float)). We only needed the former before we moved to one-arg. We don't need it anymore. I think it's just confusing.

[dcrc2]

Yes, I agree it's confusing, and removing the multi-argument form for edefs would simplify the parsers.

That would leave similar issues with defs and calls, though, which may be more difficult to resolve. For example, the def of [fwd add] above is written with multiple arguments, but later in the same .kso we have a function written in one-arg form:

(def
 [rev [sub (Tuple (Vec Float) (Vec Float))]] (Tuple (Vec Float)
                                                    (Vec Float))
 (_t1 : (Tuple (Tuple (Vec Float) (Vec Float)) (Vec Float)))
 (let
  ((_t (get$1$2 _t1))
   (a (get$1$2 _t))
   (b (get$2$2 _t))
   (ksc$argVar (get$2$2 _t1))
   ...

But again, calls to this function are generally output in the multi-argument style, so the backend needs to know that the two forms are interchangeable.

Similarly, although calls are usually written using multiple arguments, it's still possible to have a call which passes a tuple in single-argument form, as long as it's not an explicitly-constructed tuple, e.g.

(edef f (Tuple Float Float) (Integer))
(edef g Integer ((Tuple Float Float)))

(def main Integer ()
    (g (f 0)))

(this is output unchanged by ksc, except for turning the function names into structured names).

So again the question is whether the backend should be able to deal with both forms, or whether ksc should pick one to output.

[toelli-msft]

it's still possible to have a call which passes a tuple in single-argument form, as long as it's not an explicitly-constructed tuple

By way of clarification, it is also possible for a call to pass a literal ("explicitly-constructed") tuple, e.g.

(edef g Integer ((Tuple Float Float)))

(def main Integer ()
    (g (Tuple 0.0 0.0)))

[toelli-msft]

That would leave similar issues with defs and calls, though, which may be more difficult to resolve.

Hmm, then I'm not sure I fully understand the problem. The recommended strategy is as follows:

• When you see

  (def f T ((x1 : S1) ... (xn : Sn)) ...)

  proceed as if you'd seen

  (def f T (x : (Tuple S1 ... Sn))
      (let ((x1 ... xn) x) ...))

• When you see

  (f e1 ... en)

  proceed as if you'd seen

  (f (tuple e1 ... en))

(See https://github.com/microsoft/knossos-ksc/blob/485ba76331e0cc4dfb1c5e7689d0a6d8b445b1a4/src/ksc/Lang.hs#L133-L162)

Can you elaborate on what difficulties this causes?

(Whether the backend chooses to unpack tuple arguments is an orthogonal issue.)

[dcrc2]

There's nothing here that's especially difficult to implement. But since it's work that will have to be done multiple times (in each backend, or anything else that processes the output of ksc), I was wondering whether it might be better to handle this in a single place on the ksc side, by picking one of the two possible representations, and only using that form in the output.

[toelli-msft]

Would it help if we removed syntax of the form (edef f Float (Float Float))? I would much rather see (edef f Float (Tuple Float Float)).

I have implemented this suggestion at https://github.com/microsoft/knossos-ksc/pull/685. I suggest we go ahead with it because having a list of types there is misleading.

[toelli-msft]

Or should ksc's output be changed so that it consistently uses one form or the other (ie. decide whether we want the .kso to use one-arg or multi-arg form?)

When you say ".kso to use one-arg form" I think you are talking specifically about the concrete syntax and you mean

• The args of every def should (in the concrete syntax) be of the form (x : T) i.e. a single argument.

  If you want T to be a tuple type, and in the body you want variables that reference the components of x then unpack those components in the body.

• Every call should (in the concrete syntax) have exactly a single argument (f x)

  x being of the form (tuple ...) if necessary.

But I don't understand what ".kso to use multi-arg form" could mean. Could you elaborate?

[toelli-msft]

[Sorry, hit the wrong button and closed accidentally]

[dcrc2]

But I don't understand what ".kso to use multi-arg form" could mean. Could you elaborate?

Roughly, a subset of KSIR which "looks like" it uses multiple arguments for function calls. I think this would mean, whenever a function argument is an n-tuple (with n not equal to 1):

• The def is written with n named arguments.
• Any call to the function is written as having n arguments. If the original argument (in one-arg form) is a non-literal tuple, then this would have to be transformed to introduce a temporary variable for the tuple, and pass a sequence of gets to the function.

Both of these things are currently done by Cgen, and will need to be done by ksc-mlir as well (unless we decide that it's better to do this in ksc).

[simonpj]

Any call to the function is written as having n arguments. If the original argument (in one-arg form) is a non-literal tuple, then this would have to be transformed to introduce a temporary variable for the tuple, and pass a sequence of gets to the function.

Simpler than that. Instead of f( e ) we'd want let (a,b,c) = e in f(a,b,c). Unless e is a Tuple. Easy really!

[dcrc2]

A good reason for doing this in ksc is, after converting a one-arg def to a multi-arg def, it would be good to be able to run optLets to remove redundant variables. I think this is the same transformation as we previously discussed on #538.

[dcrc2]

Any call to the function is written as having n arguments. If the original argument (in one-arg form) is a non-literal tuple, then this would have to be transformed to introduce a temporary variable for the tuple, and pass a sequence of gets to the function.

Simpler than that. Instead of f( e ) we'd want let (a,b,c) = e in f(a,b,c). Unless e is a Tuple. Easy really!

Oh, good point, yes!

[awf]

I'm beginning to think we should say "KS is 1-arg".
That is different from other IRs (MLIR, LLVM, ONNX are all multi-in, multi-out), but we have a good reason for it, which is our AD is much cleaner with one arg

f : S -> T
f' : (S, dS) -> dT
f` : (S, dT) -> dS
Df : S -> LM dS dT

We don't want our IR to have too much sugar, but we also don't want it to be unreadable, but now we have tuple-unpacking let, it's much more readable. Hence moving from

(def f Float ((a : (Vec Float)) (b : String))
       (foo a b))

to

(def f Float (arg : Tuple (Vec Float) String)
    (let ((a b) arg)
       (foo a b)))

One possible tweak. As there's only ever one arg, maybe we should just call it arg?

(def f Float (Tuple (Vec Float) String)
    (let ((a b) arg)
       (foo a b)))

This makes def and edef more similar, and removes syntax for arg : Type

[simonpj]

A good reason for doing this in ksc is, after converting a one-arg def to a multi-arg def, it would be good to be able to run optLets to remove redundant variables

To be concrete, I think you are saying this.

• For calls the transformation is

  f(e)   ==>   let (a,b,c) = e in f(a,b,c)
        when e is not a literal tuple

• For definitions the transformation is

  (def f res_ty ( x : Tuple t1 t2 t3 ) rhs)
  ===>
  (def f res_ty( a : t1, b : t2, c : t3 ) (let x = (a,b,c) in rhs))

  Following (1) we get no follow-on transformation. But following (2) we might well get some optimisations; e.g. buried inside rhs we might have a subexpression let (p,q,r) = x in blah, and this would optimise to blah[a/p, b/q, c/r].

Good point.

This many-arg-ification is a pretty simple ks->ks transformation. Let's make sure that the above rationale and examples appear in a Note that describes it.

[toelli-msft]

Any call to the function is written as having n arguments. If the original argument (in one-arg form) is a non-literal tuple, then this would have to be transformed to introduce a temporary variable for the tuple

@simonpj Any thoughts on how this would interact with your polymorphism proposal? At parse time we would have no idea if an argument will be used at tuple type or not.

[awf]

This also reduces (or perhaps crystallizes) confusion about whether "(Tuple (Tuple Int))" is different from "Int".

It also has the property that backends can and should choose what argument-passing convention they wish. For example, imagine an architecture with 3 registers for argument passing, with all other args living on the stack, then I might pass the tuple

(tuple 1.0 (tuple (rand 7) 2.0) (rand 8))

as if it had been

(1.0, 2.0, (tuple (rand 7) (rand 8))

i.e. I pack all scalars into the registers, regardless of how deep in the tuple they were. This is essentially calling convention, and as long as I'm consistent, it's entirely a backend decision.

[simonpj]

I'm beginning to think we should say "KS is 1-arg".

I agree -- but I also agree with David that doing many-argification immediately prior to the back end may do work once that would otherwise need to be done many times.

So I think think we can have one-arg almost always, with many-arg as a transition into codegen.

[toelli-msft]

To be concrete, I think you are saying this.

I'm not sure what these transformations are. They're not transformations on the IR because in the IR calls and defs have exactly one argument. Are they transformations from IM to pretty-printed code?

[simonpj]

@simonpj Any thoughts on how this would interact with your polymorphism proposal? At parse time we would have no idea if an argument will be used at tuple type or not.

We just would not many-argify polymorphic functions. I don't this this would be hard.

[awf]

To be concrete, I think you are saying this.

I'm not sure what these transformations are. They're not transformations on the IR because in the IR calls and defs have exactly one argument. Are they transformations from IM to pretty-printed code?

Well, we might also ask the parser not to accept many-arg code.

[toelli-msft]

We just would not many-argify polymorphic functions. I don't this this would be hard.

But unless I'm misunderstanding what David wants, that defeats the point of his suggestion. As I understand it he wants to know that if he sees (f a) then a is not of tuple type (I think).

[toelli-msft]

Well, we might also ask the parser not to accept many-arg code.

Yes, going one-arg in the concrete syntax is a coherent thing to do. I'm skeptical that going many-arg in the concrete syntax is a coherent thing to do.

[toelli-msft]

I'm skeptical that going many-arg in the concrete syntax is a coherent thing to do.

(unless we also go many-arg in the IR, but then one-arg in the concrete syntax will no longer be a coherent thing to do.)

[awf]

Yes, going one-arg in the concrete syntax is a coherent thing to do.

Agreed. And I think @dcrc2 will too :)

[dcrc2]

We just would not many-argify polymorphic functions. I don't this this would be hard.

But unless I'm misunderstanding what David wants, that defeats the point of his suggestion. As I understand it he wants to know that if he sees (f a) then a is not of tuple type (I think).

I hadn't really thought about this, but I think you're right: there's little point in getting ksc to convert to a multi-arg representation unless it's done fully. (Otherwise the backend will still need to have code for dealing with the one-arg case.)

(Aside: are there going to be polymorphic functions in the output .kso? I'd been assuming that they'd be like gdefs: they'd be present in the input .ks, but ksc would then generate monomorphic implementations for any argument types that are actually used.)

I'm not sure what these transformations are. They're not transformations on the IR because in the IR calls and defs have exactly one argument. Are they transformations from IM to pretty-printed code?

I think it is an IR transformation: the transformation is to the subset defined by two constraints:

• In any function call where the argument is a tuple, that argument must be a literal tuple;
• In any function definition where the argument is a tuple, the body of the function must begin with a let which unpacks the argument, and the argument must not be used anywhere else in the body.

Having done this transformation, the pretty-printer is then able to emit code which looks like it's multi-arg.

But I'm happy to use the one-arg representation if we're confident that that's the right thing to do. I've already started on the ksc-mlir implementation for this; I just didn't want to finish it off and then later decide that most of the work belonged in ksc instead.

Also as @awf says above, even if the target language is multi-arg, that doesn't necessarily mean that the right calling convention is to flatten exactly one level of tuples. (This is what Cgen and ksc-mlir do at the moment, but we might want to change that.) That seems like a very good reason to stick with one-arg.

[toelli-msft]

are there going to be polymorphic functions in the output .kso?

I think this is yet to be decided

[awf]

Notes:

• Should have a helper mode where C++ edef templates are emitted

[toelli-msft]

Aha, subsequent to today's KSC meeting I do understand what Simon meant.

f(e)   ==>   let (a,b,c) = e in f(a,b,c)
        when e is not a literal tuple

The call f(a,b,c) is a call to f with a literal tuple argument. Perhaps it would be clearer to write it as

f(e)   ==>   let (a,b,c) = e in f( (a,b,c) )
        when e is not a literal tuple

to distinguish it from a call to f with multiple arguments (which can't exist in KSC's IR).