[Pitch] Array full proposal


(Daryle Walker) #1

Spent the past week coming up with a full proposal for fixed-size arrays. I wrote it mainly from the bottom upwards. There may be some inconsistencies. And I'm not entirely sure what "structural sub-typing" means, or if it's appropriate for arrays.

<https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53c6819bb>

···

Sent from my iPad


(Beta) #2

I think this proposal is trying to do too much at once. Correct me if I’m wrong, but you’re proposing

1) New sugar for fixed-length arrays without a corresponding stdlib declaration
2) Arity and type inference for literals
3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized
4) 2 new attribute declarations for unspecified concurrency semantics
5) A magical compiler intrinsic that declares loop counters
6) Static collection subtyping constraints referencing convertibility constraints we don’t currently have
7) Tuple conversions

I believe your aims are noble, and this is certainly a tremendously important problem we need to solve, but I think there needs to be a measured response to the current state of things.

~Robert Widmann

···

On Jul 10, 2017, at 9:54 PM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

Spent the past week coming up with a full proposal for fixed-size arrays. I wrote it mainly from the bottom upwards. There may be some inconsistencies. And I'm not entirely sure what "structural sub-typing" means, or if it's appropriate for arrays.

<https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53c6819bb <https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53c6819bb#file-nnnn-fixed-size-arrays-md>>

Sent from my iPad
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Gor Gyolchanyan) #3

I agree, given the current state of Swift, fixed-sized arrays are way too magical.
I’d suggest postponing the idea of fixed-sized arrays (even though I myself have ached for them for a long time now) until its prerequisites are met.

There are three language features that have been discusses before that are required for this:
Variadic generic parameters.
Tuples as nominal types with a variadic generic parameter and a tuple concatenation ability.
Non-type generic parameters (probably, only compile-time value types).

In these terms, a fixed-sized array would be a type that takes an Int as a generic parameter and uses a variadic tuple for its storage. If C++ templates has taught us anything is that metaprogramming can be used for achieving fantastic compile-time wizardry, like converting a single integer generic parameter and a single generic type parameter to a generic homogeneous variadic type parameter (by using a recursively defined variadic parameter dummy type).

···

On Jul 12, 2017, at 11:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

I think this proposal is trying to do too much at once. Correct me if I’m wrong, but you’re proposing

1) New sugar for fixed-length arrays without a corresponding stdlib declaration
2) Arity and type inference for literals
3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized
4) 2 new attribute declarations for unspecified concurrency semantics
5) A magical compiler intrinsic that declares loop counters
6) Static collection subtyping constraints referencing convertibility constraints we don’t currently have
7) Tuple conversions

I believe your aims are noble, and this is certainly a tremendously important problem we need to solve, but I think there needs to be a measured response to the current state of things.

~Robert Widmann

On Jul 10, 2017, at 9:54 PM, Daryle Walker via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Spent the past week coming up with a full proposal for fixed-size arrays. I wrote it mainly from the bottom upwards. There may be some inconsistencies. And I'm not entirely sure what "structural sub-typing" means, or if it's appropriate for arrays.

<https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53c6819bb <https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53c6819bb#file-nnnn-fixed-size-arrays-md>>

Sent from my iPad
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Daryle Walker) #4

I think this proposal is trying to do too much at once. Correct me if I’m wrong, but you’re proposing

1) New sugar for fixed-length arrays without a corresponding stdlib declaration

IIUC, “sugar” means an easier way to use existing functionality, right? In this proposal, there is neither sugar nor a standard library declaration for the same reason: these arrays are a new primitive at the user and ABI levels, not a library type. What is the (existing since you mentioned sugar) primitive you’re expecting a library fixed-size array to be based on?

Obviously, this means arrays can’t be implemented until at least Swift 5.

2) Arity and type inference for literals

I don’t know what you mean by these.

3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized

My first thought was full initialization, like other objects, but someone on the list really wanted a way to not have full initialization. I could see his point; filling in a bunch of zeros for a large array for math purposes could get expensive, especially if the values are immediately ran over. Even if we make closure-initialization return non-optionals, we still have to worry when an array is filled by a loop that gets exited early.

4) 2 new attribute declarations for unspecified concurrency semantics

Why not add some modern features relative to classic C? Or is it possible for these to be automatically determined (and carried out) by the compiler? I don’t think the vector-unit one can.

5) A magical compiler intrinsic that declares loop counters

Having the compiler figure out the best way to iterate an array seems a lot better than manually doing a bunch of loop and range calls, especially for multi-dimensional arrays. (I want one loop statement, no matter the number of dimensions.) But without those manual calls, you need some other way to determine your position in the loop.

6) Static collection subtyping constraints referencing convertibility constraints we don’t currently have

I copied that from the section of the ABI document about tuples. We could drop it.

7) Tuple conversions

Since these arrays will replace manually homogenous tuples as the conversion for C arrays, we need a way to handle older code. I probably wouldn’t have bothered except for backwards compatibility.

Are manually homogenous tuples, with the multiplicity of the element type is specified with lexical repetition instead of a number, the sugar from point 1? If so, that use would be depreciated, not continued.

···

On Jul 12, 2017, at 4:05 PM, Robert Widmann <rwidmann@apple.com> wrote:

I believe your aims are noble, and this is certainly a tremendously important problem we need to solve, but I think there needs to be a measured response to the current state of things.


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


(Daryle Walker) #5
···

Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jul 12, 2017, at 4:30 PM, Gor Gyolchanyan gor@gyolchanyan.com wrote:

I agree, given the current state of Swift, fixed-sized arrays are way too magical.

Any more “magical” than the existing primitive types?

I’d suggest postponing the idea of fixed-sized arrays (even though I myself have ached for them for a long time now) until its prerequisites are met.

There are three language features that have been discusses before that are required for this:

  • Variadic generic parameters.
  • Tuples as nominal types with a variadic generic parameter and a tuple concatenation ability.
  • Non-type generic parameters (probably, only compile-time value types).

Improved generics would synergize with fixed-size arrays, but are not a prerequisite.

Wouldn’t nominal tuples be structures? Not that it matters here since FSAs aren’t quirky tuples. (I mentioned in the proposal that no language that I know of does this; homogenous and heterogenous product types are always distinct kinds of types.)

In these terms, a fixed-sized array would be a type that takes an Int as a generic parameter and uses a variadic tuple for its storage. If C++ templates has taught us anything is that metaprogramming can be used for achieving fantastic compile-time wizardry, like converting a single integer generic parameter and a single generic type parameter to a generic homogeneous variadic type parameter (by using a recursively defined variadic parameter dummy type).

I thought Swift was to avoid that kind of wizardry. And unless you don’t want any of the optimizations array operations get, then the compiler has to analyze tuple types to trigger “array mode."


(Beta) #6

I think this proposal is trying to do too much at once. Correct me if I’m wrong, but you’re proposing

1) New sugar for fixed-length arrays without a corresponding stdlib declaration

IIUC, “sugar” means an easier way to use existing functionality, right? In this proposal, there is neither sugar nor a standard library declaration for the same reason: these arrays are a new primitive at the user and ABI levels, not a library type. What is the (existing since you mentioned sugar) primitive you’re expecting a library fixed-size array to be based on?

“Sugar” means an equivalent way to spell something concrete, but here there is nothing concrete. We’d be hard-coding a magical library type into the compiler which is something that, up to now, we have refrained from doing because it massively complicates type checking and forces us to compromise to work around “just this one corner case”. Our notion of a “primitive” is not the same as C and C++; Int, Float, String, these are all Standard Library types - that happen to be backed by compiler intrinsics in some cases.

Obviously, this means arrays can’t be implemented until at least Swift 5.

2) Arity and type inference for literals

I don’t know what you mean by these.

var b: [_, _] = [3.14159, 2.71828]

On the syntactic side: underbar has a very specific meaning in this language, and “infer this type/arity” isn’t one of them.

3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized

My first thought was full initialization, like other objects, but someone on the list really wanted a way to not have full initialization. I could see his point; filling in a bunch of zeros for a large array for math purposes could get expensive, especially if the values are immediately ran over. Even if we make closure-initialization return non-optionals, we still have to worry when an array is filled by a loop that gets exited early.

As long as you have this magical type, you should probably give it some magical methods. A “backfill” initializer, perhaps. We cannot break DI just because it’s syntactically inconvenient.

You’ve also stumbled onto the notion of a “reasonable default”, which for a language with a rich type system is a farce. We can’t assume every type has some reasonable default that we can fill in automatically because many types don’t (for an extreme example, see Never).

4) 2 new attribute declarations for unspecified concurrency semantics

Why not add some modern features relative to classic C? Or is it possible for these to be automatically determined (and carried out) by the compiler? I don’t think the vector-unit one can.

You must define these semantics. We cannot hand-wave about something so massively complicated. For one, I don’t know what “automatically determined” in regards to a non-referentially-transparent language means.

5) A magical compiler intrinsic that declares loop counters

Having the compiler figure out the best way to iterate an array seems a lot better than manually doing a bunch of loop and range calls, especially for multi-dimensional arrays. (I want one loop statement, no matter the number of dimensions.) But without those manual calls, you need some other way to determine your position in the loop.

See above. Auto-vectorization semantics are great, but we have to have them defined first.

6) Static collection subtyping constraints referencing convertibility constraints we don’t currently have

I copied that from the section of the ABI document about tuples. We could drop it.

7) Tuple conversions

Since these arrays will replace manually homogenous tuples as the conversion for C arrays, we need a way to handle older code. I probably wouldn’t have bothered except for backwards compatibility.

We control the import of those “tuples", so we could switch them to be imported as your new type. If you can make your proposal function in a backwards-compatible manner we wouldn’t need this.

···

On Jul 12, 2017, at 9:09 PM, Daryle Walker <darylew@mac.com> wrote:

On Jul 12, 2017, at 4:05 PM, Robert Widmann <rwidmann@apple.com> wrote:

Are manually homogenous tuples, with the multiplicity of the element type is specified with lexical repetition instead of a number, the sugar from point 1? If so, that use would be depreciated, not continued.

I believe your aims are noble, and this is certainly a tremendously important problem we need to solve, but I think there needs to be a measured response to the current state of things.


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


(Gor Gyolchanyan) #7

Yes, by nominal tuples I did mean a struct definition somewhere in swift’s standard library.

Seems like there are some quirks to tuples in Swift that I’m not aware of. I always assumed that they are packed ordinary structures. Since structure member offset is a compile-time constant, using tuples for arrays would not really be bad for performance, unless I’m missing something.

The C++ style compile-time wizardry is a subpar solution because it’s a hacky workaround due to lack of proper compile-time tools. If Swift would some day gain ability to execute imperative metaprogramming code that would manipulate the types at compile-time, all problems of this sort would be solved forever. But depending on how Swift compiler is implemented that may or may not be a monumental endeavor.

···

On Jul 13, 2017, at 7:27 AM, Daryle Walker <darylew@mac.com> wrote:


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jul 12, 2017, at 4:30 PM, Gor Gyolchanyan <gor@gyolchanyan.com <mailto:gor@gyolchanyan.com>> wrote:

I agree, given the current state of Swift, fixed-sized arrays are way too magical.

Any more “magical” than the existing primitive types?

I’d suggest postponing the idea of fixed-sized arrays (even though I myself have ached for them for a long time now) until its prerequisites are met.

There are three language features that have been discusses before that are required for this:
Variadic generic parameters.
Tuples as nominal types with a variadic generic parameter and a tuple concatenation ability.
Non-type generic parameters (probably, only compile-time value types).

Improved generics would synergize with fixed-size arrays, but are not a prerequisite.

Wouldn’t nominal tuples be structures? Not that it matters here since FSAs aren’t quirky tuples. (I mentioned in the proposal that no language that I know of does this; homogenous and heterogenous product types are always distinct kinds of types.)

In these terms, a fixed-sized array would be a type that takes an Int as a generic parameter and uses a variadic tuple for its storage. If C++ templates has taught us anything is that metaprogramming can be used for achieving fantastic compile-time wizardry, like converting a single integer generic parameter and a single generic type parameter to a generic homogeneous variadic type parameter (by using a recursively defined variadic parameter dummy type).

I thought Swift was to avoid that kind of wizardry. And unless you don’t want any of the optimizations array operations get, then the compiler has to analyze tuple types to trigger “array mode."


(Daryle Walker) #8

I think this proposal is trying to do too much at once. Correct me if I’m wrong, but you’re proposing

1) New sugar for fixed-length arrays without a corresponding stdlib declaration

IIUC, “sugar” means an easier way to use existing functionality, right? In this proposal, there is neither sugar nor a standard library declaration for the same reason: these arrays are a new primitive at the user and ABI levels, not a library type. What is the (existing since you mentioned sugar) primitive you’re expecting a library fixed-size array to be based on?

“Sugar” means an equivalent way to spell something concrete, but here there is nothing concrete. We’d be hard-coding a magical library type into the compiler which is something that, up to now, we have refrained from doing because it massively complicates type checking and forces us to compromise to work around “just this one corner case”. Our notion of a “primitive” is not the same as C and C++; Int, Float, String, these are all Standard Library types - that happen to be backed by compiler intrinsics in some cases.

I don’t mean fixed-size arrays are a type vs. Int / Float / String (i.e. primitive types), but a kind of type vs. class / struct / enum / tuple (i.e. type primitives). It’s a primitive because it cannot be implemented by existing features. It's why the proposal mentions bit-code representations and ABI changes instead of library ones (besides support).

Obviously, this means arrays can’t be implemented until at least Swift 5.

2) Arity and type inference for literals

I don’t know what you mean by these.

var b: [_, _] = [3.14159, 2.71828]

On the syntactic side: underbar has a very specific meaning in this language, and “infer this type/arity” isn’t one of them.

I guessed this after I woke up this morning. A way around this would be a new (but similar) kind of literal. But we’ve already used up all the ASCII bracketing character pairs. And you see there’s problems reusing the square brackets that array- and dictionary-literals use. Maybe we can chord the square brackets with something else:

#[1, 2, 3, 4]# // [4: Int]
#[6; 1, 2, 3, 4]# // [6: Int], last two elements to be initialized later
#[6; “a", “b", “c", “d", default: “k"]# // [6: String], all elements initialized, need semicolon since the comma and colon are already used
#[6; 0: “a", 2: “c", 1: “b", 3: “d", default: “k"]# // [6: String], with specific indexes assigned per element initializer
#[2, 2; #[0, 0]#: 1, #[0, 1]#: 2, #[1, 0#]: 3, #[1, 1]#: 4]# // [2, 2: Int], this form gets long really fast, maybe use the closure version
#[1, 2, 3, 4]# as [2, 2: Int] // Reshaping uses less text
#[0;]# // Empty array
#[]# // Also empty array, can be used a shortcut initializer for any FSA to indicate no elements initially initialized

3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized

My first thought was full initialization, like other objects, but someone on the list really wanted a way to not have full initialization. I could see his point; filling in a bunch of zeros for a large array for math purposes could get expensive, especially if the values are immediately ran over. Even if we make closure-initialization return non-optionals, we still have to worry when an array is filled by a loop that gets exited early.

As long as you have this magical type, you should probably give it some magical methods. A “backfill” initializer, perhaps. We cannot break DI just because it’s syntactically inconvenient.

There’s already the “default” term in extended array literals. And the “func” term allows the elements to be determined via closure.

For DI, it’s worse than you think, which is why I put out a separate post on this issue. DI assumes one sub-declaration per sub-object; the raison de-tere for arrays is to defeat this assumption. DI and FSAs are fundamentally incompatible; something has to break (forced initialization on declaration, static array indexing, run-time DI, or undefined behavior on possible uninitialized reads).

You’ve also stumbled onto the notion of a “reasonable default”, which for a language with a rich type system is a farce. We can’t assume every type has some reasonable default that we can fill in automatically because many types don’t (for an extreme example, see Never).

4) 2 new attribute declarations for unspecified concurrency semantics

Why not add some modern features relative to classic C? Or is it possible for these to be automatically determined (and carried out) by the compiler? I don’t think the vector-unit one can.

You must define these semantics. We cannot hand-wave about something so massively complicated. For one, I don’t know what “automatically determined” in regards to a non-referentially-transparent language means.

I meant could the compiler see the code in the loop, determine there’s no cross-iteration dependencies (or other disqualifiers) and apply the effects of the “parallel” attribute automatically.

I’m not a professional compiler writer, so I don’t know how much I have to specify and how much I can punt to the Swift developers to figure it out. If I have to do more on my side, I would appreciate help from actual compiler writers on what to put down.

5) A magical compiler intrinsic that declares loop counters

Having the compiler figure out the best way to iterate an array seems a lot better than manually doing a bunch of loop and range calls, especially for multi-dimensional arrays. (I want one loop statement, no matter the number of dimensions.) But without those manual calls, you need some other way to determine your position in the loop.

See above. Auto-vectorization semantics are great, but we have to have them defined first.

6) Static collection subtyping constraints referencing convertibility constraints we don’t currently have

I copied that from the section of the ABI document about tuples. We could drop it.

7) Tuple conversions

Since these arrays will replace manually homogenous tuples as the conversion for C arrays, we need a way to handle older code. I probably wouldn’t have bothered except for backwards compatibility.

We control the import of those “tuples", so we could switch them to be imported as your new type. If you can make your proposal function in a backwards-compatible manner we wouldn’t need this.

New imports would use FSAs, but it wouldn’t be retroactive, so there needs to be a conversion between old C-array adaptations and the new ones. Unless you mean for translated C code to interact with newer Swift code, the C code would have to be re-adapted (which would swap out manually homogenous tuples for FSAs in the new source files)?

···

On Jul 13, 2017, at 1:28 PM, Robert Widmann <rwidmann@apple.com> wrote:

On Jul 12, 2017, at 9:09 PM, Daryle Walker <darylew@mac.com <mailto:darylew@mac.com>> wrote:

On Jul 12, 2017, at 4:05 PM, Robert Widmann <rwidmann@apple.com <mailto:rwidmann@apple.com>> wrote:

Are manually homogenous tuples, with the multiplicity of the element type is specified with lexical repetition instead of a number, the sugar from point 1? If so, that use would be depreciated, not continued.

I believe your aims are noble, and this is certainly a tremendously important problem we need to solve, but I think there needs to be a measured response to the current state of things.


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


(Daryle Walker) #9

Yes, by nominal tuples I did mean a struct definition somewhere in swift’s standard library.

Seems like there are some quirks to tuples in Swift that I’m not aware of. I always assumed that they are packed ordinary structures. Since structure member offset is a compile-time constant, using tuples for arrays would not really be bad for performance, unless I’m missing something.

I’ve been looking at the ABI documents. Structures and tuples can be packed ordinary product types, like in C. But the Swift people want to reserve the right to do extreme rearrangements, like packing bitwise-smaller members between the spacing of the larger ones. (This would mean later-declared sub-objects won’t necessarily have their addresses in increasing order.) Tragically, the current need for tuples to have an “array mode” would block this optimization. Having fixed-size arrays as a separate primitive would allow tuples to have tuple-specific optimizations and arrays to have array-specific optimizations without relying on implementation conventions.

The C++ style compile-time wizardry is a subpar solution because it’s a hacky workaround due to lack of proper compile-time tools. If Swift would some day gain ability to execute imperative metaprogramming code that would manipulate the types at compile-time, all problems of this sort would be solved forever. But depending on how Swift compiler is implemented that may or may not be a monumental endeavor.

Since arrays (I think) pre-date functional programming, generics, meta-programming, and other “modern” language features, requiring those features as prerequisites for arrays seems weird.

···

On Jul 13, 2017, at 7:09 AM, Gor Gyolchanyan <gor@gyolchanyan.com> wrote:


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


(Daryle Walker) #10

In a response to that separate post, I chose run-time DI for local objects and stored instance properties (the checks happen within each designated initializer), and one-shot initialization otherwise.

···

On Jul 13, 2017, at 7:32 PM, Daryle Walker <darylew@mac.com> wrote:

3) Default initialization semantics for arrays including a DI exception for fixed-length arrays that aren’t fully initialized

My first thought was full initialization, like other objects, but someone on the list really wanted a way to not have full initialization. I could see his point; filling in a bunch of zeros for a large array for math purposes could get expensive, especially if the values are immediately ran over. Even if we make closure-initialization return non-optionals, we still have to worry when an array is filled by a loop that gets exited early.

As long as you have this magical type, you should probably give it some magical methods. A “backfill” initializer, perhaps. We cannot break DI just because it’s syntactically inconvenient.

There’s already the “default” term in extended array literals. And the “func” term allows the elements to be determined via closure.

For DI, it’s worse than you think, which is why I put out a separate post on this issue. DI assumes one sub-declaration per sub-object; the raison de-tere for arrays is to defeat this assumption. DI and FSAs are fundamentally incompatible; something has to break (forced initialization on declaration, static array indexing, run-time DI, or undefined behavior on possible uninitialized reads).


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com