[swift-evolution] [Pitch] New Version of Array Proposal

[Taylor Swift]

On Sun, Jul 23, 2017 at 3:08 AM, Daryle Walker <darylew at mac.com> wrote:

>
> 9. I don’t see the value in having both nested FSAs and multi-dimensional
> FSAs. Aren’t they the same thing? For example, in the code snippet
>
>
> Why does any language with multi-dimensional arrays (like Fortran or Ada)
> have them? By this standard, no language should have multi-dimensional
> arrays. They exist because of data modeling. Co-equal coordinates in the
> model should be co-equal in their representation in the program. Yes, they
> are implemented the same way underneath. We don’t copy C everywhere, so why
> not take this opportunity to do better. Also, just using nesting could
> imply that the intermediate array types have a meaning, but they might not
> if they’re just implementation quirks and not part of the abstract model.
>
> Nested arrays are not my solution for multi-coordinate indexing; use
> multi-dimensional arrays for that. I mention nested arrays because:
>
>
>    - Nested arrays fundamentally cannot be banned. (What if an element
>    type is hidden behind a type-alias and is conditionally an array type?)
>
> Doesn’t Swift have to resolve the types at some point anyway? If it’s
impossible to ban, we can allow it, but still make it unidiomatic. Nested
arrays are much messier to write than multidimensional arrays.

>
>    - I need the definition to explain the “inner non-array type”
>       - I need the inner non-array type to explain which pairings of FSAs
>       for reshaping are legal. (And a similar reason for tuple conversion.) Note
>       the two types can have different nesting levels.
>    - I need to explain that empty arrays cannot be an array element type.
>    (Should this be changed? What happens with tuples or structures containing
>    empty tuples/structures as members? What about empty tuples/sturctures in
>    “Array”? Banning empty arrays means we don’t have to worry about every
>    array element being at the same address. The other way to solve this is to
>    make them one byte (or word) long.)
>
>
> ```
> let a = [;1, 2, 3, 4]
> assert(a[0] == 1)
> assert(a[1] == 2)
> assert(a[2] == 3)
> assert(a[3] == 4)
> let b = a as [2, 2; Int]
> assert(b[0, 0] == 1)
> assert(b[0, 1] == 2)
> assert(b[1, 0] == 3)
> assert(b[1, 1] == 4)
> let c = a as [2; [2; Int]]
> assert(c[0][0] == 1)
> assert(c[0][1] == 2)
> assert(c[1][0] == 3)
> assert(c[1][1] == 4)
> ```
>
> There’s three syntaxes which accomplish two unique things. I lean towards
> disallowing FSA nesting and instead allowing *incomplete* index lists to
> partially unnest multidimensional FSAs. Let’s reserve “[][][]...” for
> flexible array chained dereferencing.
>
>
> I don’t understand what your incomplete index list idea is. And as I said,
> the chaining technique is less I desire it and more I can’t ban it and keep
> Swift features orthogonal.
>

Incomplete indexing means

let fsa:[5, 2; Int] = [5, 2; 2, 4, 3, 5, 4, 6, 5, 7, 6, 8]
fsa[3] // [2; 5, 7]

this would be the same as writing

let fsa:[5; [2; Int]] = [5; [2; 2, 4], [2; 3, 5], [2; 4, 6], [2; 5, 7], [2; 6,
8]]
fsa[3] // [2; 5, 7]

in your current system. This would obviate the need to nest FSAs for the
purpose of extracting entire rows of data.


> 10. I don’t see much value in runtime DI. It seems to add a lot of
> complexity to the compiler with little benefit.
>
>
> In other languages, people initialize their arrays in loops with run-time
> indexes. This frustrates compile-time DI. C doesn’t have this problem
> because it doesn’t have DI and is willing to risk undefined behavior during
> uninitialized reads. So it’s either work in the confines of static DI,
> allow dynamic DI (hopefully under as limited circumstances as possible), or
> give up on checking for FSAs and allow undefined behavior (which would blow
> a big hole in static DI). Maybe this can be pushed to version 2.
>
> 11. This should have defined behavior:
>
> let data = [2, 2; 1, 2, 4, 8]
> for (i, x) in data.enumerated()
> {
>     total += x
> }
>
>
> FSAs are compound types, not named types, so there are no methods. (Just
> like tuples, FSAs don’t follow any protocols.) But since they’re a
> built-in, I can customize the “for-in” loop to cover all the elements in an
> implementation-optimized order. (The implementation has the option of
> multi-threading if it can see there’s no cross-iteration contamination.)
> Since you can’t control the order without manual looping, the “#indexOf”
> expression exists to let you know where you are during an iteration loop.
>
> I first used the iteration variable as the operand to “#indexOf” to
> determine which array instance to track. Then I saw that the for-loop
> implements its iteration variable as a pattern in the grammar instead of
> something simpler. And what happens if a wildcard is used as the iteration
> variable? And would people question why when the pattern has multiple
> iteration variables, all are equally valid for “#indexOf”? I moved the
> operand to be the label because we usually don’t have multiple labels on
> statements (Is that even legal in Swift?) and can optimize which loops need
> to be indexable.
>

I really dislike the addition of magical builtin variables. Iterating
through a FSA should just take the FSA down one dimension level, so

let data = [2, 3; 1, 2, 3, 4, 8, 12]
for x:[3;] in data
{
    total += x[0] + x[1] + x[2]
}

would be the pattern.


>
> “with” methods should be used sparingly and not be part of common idioms
> like iterating through an array as a buffer.
>
>
> I need some library function to convert a FSA into a Collection, and to
> represent the “T[]” function parameter type concept from C, which
> represents any array size (instead of being locked for one length, or since
> we have multi-dimensional arrays, one shape). For safety, the callback
> function uses the buffer version so you have a pointer and size. You
> generally should be using the for-loop, though.
>
> Using an unsafe buffer pointer forces the data into addressable memory,
> which isn’t necessarily the case of an instance’s location by default. (C
> optimizes the other way. Objects are addressable by default, and that is
> disabled, and any optimizations by being un-aliased activated, by the
> “restrict” qualifier.)
>
> We should have some way to cull specific indexes in loops. (Like “lock
> index 2 to column 5 but iterate over all the qualifying subset of
> elements.”) I don’t know if this has to be a new base operation on a loop,
> or if it can be done through a library function, or if it can be done
> through a library function after we complete generics. But I think it can
> wait until version 2.
>
> 12. Can we rename the `cardinality` type property to `nestingCount` or
> `nestingLevels` something similar? That seems a lot clearer and more
> descriptive of that the property actually represents. I’d also bet that
> close to no one knows what cardinality is.
>
>
> The nesting-level is “layers.” “Cardinality” is the number of co-equal
> coordinates. But that second name probably needs some work, although it can
> be synthesized from the length of “dimensions.” The “cardinality” and
> “elementCount” properties work around us not having (integer) compile-time
> constants yet; otherwise we can derive them from compile-time expressions
> on “dimensions."
>

I understand there is currently a distinction due to FSA nesting, however I
don’t see why FSA nesting has to be a first-class citizen in this model.
Multidimensionality should be the idiomatic way to add nesting to an FSA.


>
> —
> Daryle Walker
> Mac, Internet, and Video Game Junkie
> darylew AT mac DOT com
>
> On Sat, Jul 22, 2017 at 3:41 PM, Daryle Walker via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> It’s at <https://gist.github.com/CTMacUser/cfffa526b971d0e1f3a079f53
>> c6819bb>.
>>
>> * Try to clarify that fixed-size arrays are a new kind of compound type,
>> *not* a (ridiculously magical) library generic type.
>> * Change the separator between the bounds and element type from a colon
>> to a semicolon.
>> * Specify that violating the bounds of an array during indexing is a
>> run-time error.
>> * Reword how the mapping of static-indexing elements for
>> multi-dimensional arrays works.
>> * Completely redo array values/literals. A literal for a fixed-size array
>> always includes a semicolon, which separates the bounds from the values.
>> (The separator in FSA types was changed to a semicolon to match.) A value
>> can be a plain expression or a dictionary expression where the right side
>> of the colon is the value and the left side is the index of the target
>> element or “default” for all un-targeted elements. The left side can also
>> be “func”, with the right side being an initialization closure.
>> * Move the “Reshaping Arrays” section and add an example.
>> * Right now, deterministic initialization is unchanged, so an
>> initializing loop has to be changed to initializing the array with a
>> function term, moving the loop to the closure.
>> * Remove the “parallel” declaration attribute. Add a future note about it
>> and the “fragmentary” attribute.
>> * Change the for-loop example to conform to deterministic initialization.
>> Reword how the flattening buffer functions work.
>> * Add examples to element-wise casting.
>> * Reword tuple conversion section, and add an example.
>> * Reword various vector-mode attribute sections. Note that there need to
>> be two ABI additions for FSA, one for non-vectorized FSAs and one for
>> vectorized FSAs. These two kinds of arrays need conversion functions at our
>> (i.e. the ABI) level, but are transparent for the user.
>>
>>     let v1: @vector [3; Int] = [; 1, 3, 5]
>>     let v2: [3; Int] = v1  // Not a type-mismatch error
>>
>> * Due to FSA’s literals including the bounds, or using automatic bounds
>> mode, array-placeholder syntax is not longer needed for type annotations
>> and has been removed.
>> * Renamed “nestings” to “layers”.
>>
>> —
>> Daryle Walker
>> Mac, Internet, and Video Game Junkie
>> darylew AT mac DOT com
>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170723/0e594397/attachment.html>