I've come around to Vector being the best name for this type, as opposed to something like RigidArray or FixedCountArray, specifically because it's stored inline. At first, I overlooked this property as an implementation detail, but under further consideration, it really is crucial to the design of Vector. Because it's stored inline, APIs that append to or concatenate Vectors would have unexpected complexities that a 'true' fixed-count array shouldn't have (and thus they shouldn't exist).
A fixed-count version of Array (supporting functionality like appending and concatenation) would be nice, but Vector isn't that.
It seems to me the main feature of this new type is that its elements are stored inline. To me, being fixed size or suitable as a mathematical vector (at least when the vector size is small) are properties that are derived from its elements being stored inline, not the other way around.
I think InlineArray would be a better name than FixedSizeArray or Vector. We don't need to say the size is fixed when the type is spelled in a way that includes the size InlineArray<3, Int>. And the type name making people realize the storage is inline also seems important.
As for Vector, I'm inclined to leave the name available for math and other domain-specific libraries. They are all going to want to have a vector type but then will probably disagree on the meaning and in particular what operators/methods they have and how they works. If we use Vector as the name, then we're encouraging everyone to repurpose this type for domain specific ends without creating domain-specific wrappers structs, adding all their operators and methods to it, and I'm not sure how wise it is because it can easily create clashes.
For the past couple of days I've been trying to distill the underlying requirements for fixed-size arrays, because it really comes down to efficiency of memory handling and compile-time optimisations, and I think you've expressed the gist of it perfectly. (And the name is good too.)
I think that all standard base types should reflect their fundamental nature, not their application purpose, because decades of computing has shown that attempts to make libraries of high-level types and functions have always led to either failure of adoption or (for worse) such widespread adoption that they strangle future developments. I bet more time and money was spent sorting out CGFloat than Euclid spent sorting out half of geometry.
Depends what you mean by "size". Inline storage causes the type to have a fixed capacity, but it does not necessarily force it to have a fixed count.
Vector isn't just about storage - it means "N values of type T" rather than just "inline storage for up to N values of type T".
If I consider a type which contains a vector:
struct Foo {
var someProperty: Int
var elements: Vector<4, String>
}
When I read those stored properties, in my mind I can translate Vector<4, T> to something approximately like:
struct Vector4<T> {
var `0`: T
var `1`: T
var `2`: T
var `3`: T
}
I could imagine a name which reflects this "N values of type T" more directly - something along the lines of Repeat<4, T> or Many<4, T> or Elements<4, T>. Those specific names are all a little awkward, but I wonder if there's something in that general direction.
I agree that it would be unfortunate to take the name Vector away from expert geometry libraries. I'm not a fan of that name.
I think the name Vector is great. To someone who understands the basics of memory, it's a very small leap to assume that Vector<8, Double> is stored inline (the count is a compile-time constant).
This type will be great for replacing patterns like:
... with the benefits of being able to have methods, computed properties, and conform to protocols.
3 Likes
lorentey
(Karoy "Vector is not an Array type" Lorentey)
169
Taking the name InlineArray for vectors would not be a good idea. We are also hoping to implement actual arrays (deques, hash tables, etc) with inline storage, and the Inline prefix would best be reserved for that.
InlineArray would be a statically sized fixed-capacity array type offering range-replacement operations; InlineDeque is a fixed-capacity ring buffer.
The Inline* family of types will be of particular interest to the lowest-level use cases of Swift. In some of these cases, memory allocations are either extraordinarily expensive or not available at all, and that renders most existing Swift data structure implementations unusable. But containers with inline storage can still work.
Vector has inline storage, but it isn't this InlineArray type.
Having a count and a mutable subscript does not an array make.
To reiterate once more: Vector is not an array type in the taxonomy that Swift has clearly established. We really, really should not name it as if it was. Vector's preexisting sister types are homogeneous tuples, Unsafe*BufferPointer, the SIMD* family of types and the new Span. We call none of these constructs arrays; we must not call Vector an array, either.
Do polar coordinates give you any pause regarding the name Vector? To me this is the perfect example of why I remain uneasy about the name even after reading all of your explanations of why you support it. It feels like deciding that from now on apples will be named simply “fruit”.
For anyone who is unaware of polar coordinates, the main point here is that it is common and useful to represent 2D vectors as the combination of an angle and a radius, which one would very likely want to represent using distinct types, and this would be unsupported by Vector since all of the values must be of the same type.
which one would very likely want to represent using distinct types
I actually don't remember seeing people define separate types for angles. Matrices — yes, quaternions — yes, but not scalar angles. Polar coordinates are usually fine being a simple Vector<2, Double>.
Polar coordinates do not act like a vector space under componentwise addition and scalar product (the vector space scalar multiplication has to act only on the magnitude component, and the addition rule is more complicated). It would be very strange to store that coordinate representation in a thing called “Vector” (it’s perfectly normal to represent a vector that way, but I wouldn’t call the (magnitude, angle) pair itself a “Vector”.)
Why is it normal to call the (x, y) representation a "Vector" but it is not normal to call the (r, ø) representation a "Vector"?
Is it related to these complexities of polar coordinates that you mentioned (which I'm not familiar with as they relate to the formal rules about "behaving like a vector space")?
I do wonder if we can elaborate as to why adding the proposed functionality to tuples would be a no-go? Is it simply because we don't want to be expressing more "magic" in the compiler? Is there a preference to define all new standard library types completely in Swift? There seem to be several benefits to doing so, namely tuples would be itterable and or extensible in extensions, C-imports don't need special import rules, and new syntax sugar could cover defining (UInt8, ..., UInt8) 64 times.
At least for myself, my initial excitement here was for an actual InlineArray type that can grow up to a capacity, and not necessarily one that has fixed capacity from the get go.
I mentioned this upthread, but a bunch of smart people spent a bunch of time trying to do exactly that in the last few years, and it turns out to be a lot more trouble than it sounds like at first. Maybe if tuples had been designed for that purpose back in the early days of the language it would be more straightforward, but in the language we have, having a dedicated type works out a lot nicer.
That’s one reason, yes. Today a tuple is represented in a way where operations on it are inherently O(n) in the length of the tuple — for example, various code generation paths will explode a tuple into its constituent parts, or iterate over all fields at compile time, etc.
To subsume fixed size arrays into tuples we would need to change the representation of a tuple type inside the compiler so that it’s essentially this:
enum TupleType {
case heterogeneous(elements: [Type])
case homogeneous(element: Type, count: IntegerParameterType)
}
At this point you have to handle both cases everywhere and there’s no benefit to using this common representation anymore.
(And you’d still need integer generic parameters so that you can abstract over the length of an array. Remember the interesting case is not Vector<3, Int> but Vector<N, Int>).
It's normal to call the thing being represented a "vector" no matter what its representation is. But the normal expectation for a vector in coordinate form is that you add them using (x₁, y₁) + (x₂, y₂) = (x₁ + x₂, y₁ + y₂), which you do not do with polar coordinates. Instead you have something like (x₁, y₁) + (x₂, y₂) = (sqrt(x₁² + x₂² + 2x₁x₂cos(y₂-y₁)), y₁ + atan(x₂sin(y₂-y₁)/(x₁ + x₂cos(y₂-y₁)))--typing that out from memory, so probably don't blindly implement it in a geometry library without some tests.
This is a little bit weird of an objection mathematically, because vectors are vectors no matter how you represent them--the coordinates aren't what make a vector space, it's the operations that matter. But there are also some pragmatic considerations in the semantic expectations on a thing called "vector" in a programming context.
As far as I've read in this thread we're not planning on implementing any operators for Vector, which would seem to me to diminish the argument that practical concerns about (Cartesian-centric) assumptions about vector addition should justify the name Vector.
Sadly it does feel to me as if Tuple really is the perfect name. It has the name-as-opposed-to-dictionary-definition quality that @lorentey has been advocating for, and yet it still leverages english precedents to convey the repetition of a single type.
Then again, this is assuming that we agree that the proposed type is deserving of a less dry name than HomogenousTuple, but actually the basis on which @lorentey was arguing this point sounded like it was somewhat contradicted by @John_McCall when he said this:
This seems to stand in contrast to this statement:
So maybe it would be best to settle this question first.
There's really no conflict between these; some folks on the thread are expecting Vector to replace normal usage of Array, which is almost certainly a mistake, for the reasons that Karoy and others have laid out in the proposal and thread. But there is an enormous gulf between "not replacing Array as the fundamental collection type" and "not being frequently used as a building block for other types, and therefore not meriting a good name". Vector sits somewhere in that gulf (where exactly depends largely on how far up/down the software stack one sits).