Location of "indirect" declaration modifier


(Marc Knaup) #1

Hey guys,

I'm working on a proposal and the question arose why the declaration
modifier indirect can only be specified for the whole enum case and the
whole enum but not for the actual parameter which is indirect.

I.e. is there any technical reason which would prevent something like the
following?

   1. enum ArithmeticExpression {
   2. case Number(Int)
   3. case Addition(indirect ArithmeticExpression, indirect
   ArithmeticExpression)
   4. case Multiplication(indirect ArithmeticExpression, indirect
   ArithmeticExpression)
   5. }

Also is there any technical reason which would prevent indirect from being
used for structs?

Thanks,
  Marc


(Slava Pestov) #2

Hi Marc,

Hey guys,

I'm working on a proposal and the question arose why the declaration modifier indirect can only be specified for the whole enum case and the whole enum but not for the actual parameter which is indirect.

I.e. is there any technical reason which would prevent something like the following?

enum ArithmeticExpression {
    case Number(Int)
    case Addition(indirect ArithmeticExpression, indirect ArithmeticExpression)
    case Multiplication(indirect ArithmeticExpression, indirect ArithmeticExpression)
}

Right now, notice that direct and indirect cases look the same from the perspective of the type system.

With your proposal, the fact that the entire tuple payload can be matched by a pattern implies that ‘indirect’ has to become a formal type in the language, since you will now be able to write down a value of type '(indirect ArithmeticExpression, Int)’, for example. It also raises the issue of how these indirect values are wrapped and unwrapped, since now the ‘indirect ArithmeticExpression’ is itself a value.

An alternative is to make ‘indirect’ a non-materializable type, like ‘inout’. ‘inout’ can appear inside tuple types, but is not a first class value. This creates lots of special cases for ‘inout’ and you can imagine it will be equally difficult for ‘indirect’.

If you want an ‘indirect’ that can be nested inside a tuple type, you could just define ‘class Box<T> { let payload: T }’ and tolerate a bit of verbosity when wrapping and unwrapping values. As long as the payload is immutable, you will still have value semantics using this trick.

Also is there any technical reason which would prevent indirect from being used for structs?

Like an ‘indirect’ modifier for stored properties on structs? Yes, this should be possible, however note that right now enum payloads are not themselves lvalues, which means that assignment of indirect enum cases only has to update the reference count of the box to maintain value semantics, since the contents of the box will never change. Presumably for structs you would need to be able to define an ‘indirect var’ with a mutable payload — immutable-only indirect stored properties don’t seem very useful.

Making the indirect payload mutable will require either copying the box upon assignment, or alternatively, a copy-on-write scheme could be used. The SIL @box type that implements indirect cases isn’t set up to support either of those right now. Also, unlike enums, indirect fields of structs won’t give you any new generality that was not possible before — its just a performance change. A value type that contains a cycle through an ‘indirect’ struct field is still invalid, for example, because the resulting type is still infinite.

Slava

···

On Dec 11, 2015, at 3:06 AM, Marc Knaup via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Thanks,
  Marc
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev


(Marc Knaup) #3

Thank you for your thorough answer.

So when direct and indirect cases already look the same for the type system
then why is there the indirect modifier in the first place?
Couldn't the compiler just automatically box variables which would cause a
recursion? For structs, enums and probably tuples.

From what I understand in indirected enum cases the compiler will basically

just box either

   - the case value as a whole or
   - just the associative values which cause the recursion.

What is boxed?

I do not intend to propose to make indirect part of the type itself. I'm
checking whether the modifier can be moved closer to the declaration of the
variables which cause the indirections.
What I need for my proposal is indeed indirection on structs and for that
I'd like to understand how indirections work under the hood and what their
limitations are.
Your answer already gives a lot of insight there.

Actually I once needed to design a recursive struct
<https://gist.github.com/fluidsonic/6a8f1c1def2a92416519> and did so by
just wrapping the recursive variable in an indirect enum case. Works fine
in Swift 2.1
I could have done it differently - e.g. by storing an array of parents
instead of using recursion - but the approach worked.

How can a recursive struct using indirection be an infinite type? Since the
indirect variables are just boxes which have a fixed size (just a pointer?)
independent of the struct's size the type is no longer infinite.

Thanks,
  Marc

···

On Fri, Dec 11, 2015 at 4:03 PM, Slava Pestov <spestov@apple.com> wrote:

Hi Marc,

On Dec 11, 2015, at 3:06 AM, Marc Knaup via swift-dev <swift-dev@swift.org> > wrote:

Hey guys,

I'm working on a proposal and the question arose why the declaration
modifier indirect can only be specified for the whole enum case and the
whole enum but not for the actual parameter which is indirect.

I.e. is there any technical reason which would prevent something like the
following?

   1. enum ArithmeticExpression {
   2. case Number(Int)
   3. case Addition(indirect ArithmeticExpression, indirect
   ArithmeticExpression)
   4. case Multiplication(indirect ArithmeticExpression, indirect
   ArithmeticExpression)
   5. }

Right now, notice that direct and indirect cases look the same from the
perspective of the type system.

With your proposal, the fact that the entire tuple payload can be matched
by a pattern implies that ‘indirect’ has to become a formal type in the
language, since you will now be able to write down a value of type
'(indirect ArithmeticExpression, Int)’, for example. It also raises the
issue of how these indirect values are wrapped and unwrapped, since now the
‘indirect ArithmeticExpression’ is itself a value.

An alternative is to make ‘indirect’ a non-materializable type, like
‘inout’. ‘inout’ can appear inside tuple types, but is not a first class
value. This creates lots of special cases for ‘inout’ and you can imagine
it will be equally difficult for ‘indirect’.

If you want an ‘indirect’ that can be nested inside a tuple type, you
could just define ‘class Box<T> { let payload: T }’ and tolerate a bit of
verbosity when wrapping and unwrapping values. As long as the payload is
immutable, you will still have value semantics using this trick.

Also is there any technical reason which would prevent indirect from
being used for structs?

Like an ‘indirect’ modifier for stored properties on structs? Yes, this
should be possible, however note that right now enum payloads are not
themselves lvalues, which means that assignment of indirect enum cases only
has to update the reference count of the box to maintain value semantics,
since the contents of the box will never change. Presumably for structs you
would need to be able to define an ‘indirect var’ with a mutable payload —
immutable-only indirect stored properties don’t seem very useful.

Making the indirect payload mutable will require either copying the box
upon assignment, or alternatively, a copy-on-write scheme could be used.
The SIL @box type that implements indirect cases isn’t set up to support
either of those right now. Also, unlike enums, indirect fields of structs
won’t give you any new generality that was not possible before — its just a
performance change. A value type that contains a cycle through an
‘indirect’ struct field is still invalid, for example, because the
resulting type is still infinite.

Slava

Thanks,
  Marc
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev


(Chris Lattner) #4

With your proposal, the fact that the entire tuple payload can be matched by a pattern implies that ‘indirect’ has to become a formal type in the language, since you will now be able to write down a value of type '(indirect ArithmeticExpression, Int)’, for example. It also raises the issue of how these indirect values are wrapped and unwrapped, since now the ‘indirect ArithmeticExpression’ is itself a value.

Yes.

An alternative is to make ‘indirect’ a non-materializable type, like ‘inout’. ‘inout’ can appear inside tuple types, but is not a first class value. This creates lots of special cases for ‘inout’ and you can imagine it will be equally difficult for ‘indirect’.

Incidentally, I’m of the opinion that we’re modeling this wrong, on both the call and the declaration side.

Decl side: because we historically allowed arbitrary irrefutable patterns in argument lists, the argument list of a AbstractFunctionDecl is represented as a Pattern. This doesn’t make sense because we’ve since realized that that was a bad idea, and now argument lists have their own parsing logic and can only support specific trivial kinds of patterns. It is also annoying because general patterns cannot use “inout” or internal vs external parameter names, so argument lists are making real patterns more complicated. I plan to fix this by splitting AbstractFunctionDecl onto a custom data structure, allowing this to be simplified.

On the call side, we have analogous representation damage, where ApplyExpr takes a function and an argument, and the argument is usually a tuple, sometimes a parenexpr, or sometimes neither! This makes a lot of stuff more complicated, and forces “&” in argument lists to be represented as InOutExpr, and that Expr needs a type (InOutType). If we changed ApplyExpr to take a structured argument list, we could dispel this complexity (eliminating InOutType and InOutExpr completely, along with a ton of corner case bugs). This would lead to a lot simpler code throughout the compiler as well.

Fixing these are on my todo list somewhere :-) and I’ve heard that ChrisW is also interested in this area.

-Chris

···

On Dec 11, 2015, at 7:03 AM, Slava Pestov via swift-dev <swift-dev@swift.org> wrote:


(Slava Pestov) #5

Thank you for your thorough answer.

So when direct and indirect cases already look the same for the type system then why is there the indirect modifier in the first place?
Couldn't the compiler just automatically box variables which would cause a recursion? For structs, enums and probably tuples.

The compiler could certainly infer ‘indirect’ if there is a cycle of unsubstituted types, eg,

enum A {
  case X
  case Y(S) // could infer indirect here
}

struct S {
  let a: A
}

However, the circularity might be introduced by a generic type substitution:

enum A<T, U> {
  case X
  case Y(T)
  case Z(U)
}

struct R {}

struct S {
  let a: A<S, R>
}

Here, A<S, R> needs Y to be indirect, but A<R, S> needs Z to be indirect. This would put the indirectness on different cases for different substitutions of the same generic type, which would complicate code generation for functions which manipulate A<T, U> generically.

Also even if ‘indirect’ could always be inferred, it seems like a good idea to give the user control over where the indirection occurs — this can have an effect on the size of the enum value for instance.

From what I understand in indirected enum cases the compiler will basically just box either
the case value as a whole or
just the associative values which cause the recursion.
What is boxed?

Applying the ‘indirect’ keyword to the enum has the same effect as applying it to all payload cases. In both instances, the enum case discriminator is stored as part of the value, and not inside the box.

I do not intend to propose to make indirect part of the type itself. I'm checking whether the modifier can be moved closer to the declaration of the variables which cause the indirections.

Basically, the problem is the type of an enum payload is a single value, which may be a tuple. So if indirect can appear inside this tuple, it’s part of the type, because it becomes possible to get a value whose type is the type of the payload, with the indirect and all.

What I need for my proposal is indeed indirection on structs and for that I'd like to understand how indirections work under the hood and what their limitations are.
Your answer already gives a lot of insight there.

Actually I once needed to design a recursive struct <https://gist.github.com/fluidsonic/6a8f1c1def2a92416519> and did so by just wrapping the recursive variable in an indirect enum case. Works fine in Swift 2.1
I could have done it differently - e.g. by storing an array of parents instead of using recursion - but the approach worked.

How can a recursive struct using indirection be an infinite type? Since the indirect variables are just boxes which have a fixed size (just a pointer?) independent of the struct's size the type is no longer infinite.

Yes, but each indirect box has to have a value. So for example, this is invalid, whether or not the property is ‘indirect’ — DI would require S.s be initialized to a value of type S in the constructor, which in turn has to be initialized, leading to an infinite chain S.s.s.s.s… of values.

struct S {
  let s: S
}

···

On Dec 11, 2015, at 8:01 AM, Marc Knaup <marc@knaup.koeln> wrote:

Thanks,
  Marc

On Fri, Dec 11, 2015 at 4:03 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:
Hi Marc,

On Dec 11, 2015, at 3:06 AM, Marc Knaup via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Hey guys,

I'm working on a proposal and the question arose why the declaration modifier indirect can only be specified for the whole enum case and the whole enum but not for the actual parameter which is indirect.

I.e. is there any technical reason which would prevent something like the following?

enum ArithmeticExpression {
    case Number(Int)
    case Addition(indirect ArithmeticExpression, indirect ArithmeticExpression)
    case Multiplication(indirect ArithmeticExpression, indirect ArithmeticExpression)
}

Right now, notice that direct and indirect cases look the same from the perspective of the type system.

With your proposal, the fact that the entire tuple payload can be matched by a pattern implies that ‘indirect’ has to become a formal type in the language, since you will now be able to write down a value of type '(indirect ArithmeticExpression, Int)’, for example. It also raises the issue of how these indirect values are wrapped and unwrapped, since now the ‘indirect ArithmeticExpression’ is itself a value.

An alternative is to make ‘indirect’ a non-materializable type, like ‘inout’. ‘inout’ can appear inside tuple types, but is not a first class value. This creates lots of special cases for ‘inout’ and you can imagine it will be equally difficult for ‘indirect’.

If you want an ‘indirect’ that can be nested inside a tuple type, you could just define ‘class Box<T> { let payload: T }’ and tolerate a bit of verbosity when wrapping and unwrapping values. As long as the payload is immutable, you will still have value semantics using this trick.

Also is there any technical reason which would prevent indirect from being used for structs?

Like an ‘indirect’ modifier for stored properties on structs? Yes, this should be possible, however note that right now enum payloads are not themselves lvalues, which means that assignment of indirect enum cases only has to update the reference count of the box to maintain value semantics, since the contents of the box will never change. Presumably for structs you would need to be able to define an ‘indirect var’ with a mutable payload — immutable-only indirect stored properties don’t seem very useful.

Making the indirect payload mutable will require either copying the box upon assignment, or alternatively, a copy-on-write scheme could be used. The SIL @box type that implements indirect cases isn’t set up to support either of those right now. Also, unlike enums, indirect fields of structs won’t give you any new generality that was not possible before — its just a performance change. A value type that contains a cycle through an ‘indirect’ struct field is still invalid, for example, because the resulting type is still infinite.

Slava

Thanks,
  Marc
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev


(Matthew Johnson) #6

Also even if ‘indirect’ could always be inferred, it seems like a good idea to give the user control over where the indirection occurs — this can have an effect on the size of the enum value for instance.

+1. Requiring it to be specified also prevents unintentional indirection.


(Marc Knaup) #7

I also agree that requiring the developer to specify the modifier does make
sense esp. with the performance downsides and the generic issue described
by Slava.

The example with the recursive struct makes sense! I forgot that in my
cases either an enum, an Optional (so an enum) or a protocol were breaking
that init cycle for recursive variables.
lazy private(set) var will probably also work although it's use is likely
limited.

Now I do have a good sense what is possible and how.
Thank you very much, Slava!

···

On Fri, Dec 11, 2015 at 5:32 PM, Matthew Johnson <matthew@anandabits.com> wrote:

> Also even if ‘indirect’ could always be inferred, it seems like a good
idea to give the user control over where the indirection occurs — this can
have an effect on the size of the enum value for instance.

+1. Requiring it to be specified also prevents unintentional indirection.