Vectors, understood as 2, 3, or 4-component numerical aggregates, are a fundamental currency type across many domains of programming. This document seeks to lay out a cohesive vision for adding standard vector support to the Swift language, with consideration for relevant long-term goals for the language type system.
Past discussions: 1 2, 3, 4, 5
Past pitches: 1
Vectors are closely related to fixed-size arrays, and can be considered a special case where the array count is 2, 3, or 4. However, there are important differences between the usage and implementation of the two concepts that make it a bad idea to unify them under a single language feature.
-
Vectors should use SIMD backing storage and SIMD operations. SIMD, however, cannot be generalized to an arbitrary element count — as of Swift 5, only
SIMD2<T>,SIMD3<T>,SIMD4<T>,SIMD8<T>,SIMD16<T>,SIMD32<T>, andSIMD64<T>are supported. -
Vectors make heavy use of element-wise operations. Fixed-size arrays generally don’t.
-
Vectors only make sense when their element type is numeric. Fixed-size arrays should support any element type, including vector types. For example, matrices are essentially fixed-size arrays of column vectors.
However, the two concepts also share many similarities, and both depend more or less on a related set of language features.
To avoid confusion with Swift’s dynamic Arrays, we will use the term Vector{N}<Scalar> for geometric vectors, and Vector<N:Int, T> for fixed-size arrays. These names can be bikeshedded as needed.
struct Vector2<Scalar> where Scalar:SIMDScalar
{
...
}
struct Vector3<Scalar> where Scalar:SIMDScalar
{
...
}
struct Vector4<Scalar> where Scalar:SIMDScalar
{
...
}struct Vector<N:Int, T>
{
...
}Despite some apparent overlap, the two groups of Vector types are orthogonal. For example, we can model a 4x4 matrix as Vector<4, Vector4<Float>>. The fixed-size array Vector<3, Float> is superficially similar to Vector3<Float>, and would likely have the same in-memory representation, but the latter would take advantage of SIMD operations, and support elementwise arithmetic operations and geometric operations like dot and cross product.
Fixed-size arrays require a language feature we will call generic multiplicity parameters. These are the integer constants like 32 in the generic parameter brackets of types like Vector<32, T>.
Multiplicity parameters are passed in the angle brackets just as type parameters are currently, and can be used in tuple declarations, where they would signify repeated component types.
struct Foo<N:Int>
{
let storage:(Int * N, Bool * N, UInt8 * 2)
}The syntax (Int * 2, Float * 4) is sugar for (Int, Int, Float, Float, Float, Float). (This would also fulfill a feature request for a shorthand to write long homogenous tuples.) However, generic multiplicity parameters are not a sugaring feature; they would be part of the type system, and the compiler would have to be able to inference them.
Internally, the Swift compiler would model tuples as maximal sequences of (type, count) pairs, where no two adjacent runs is of the same type. This means that (Float, Float, Float, Bool, Bool, Float) would actually be sugar for (Float * 3, Bool * 2, Float * 1) instead of the other way around. Type inference would then involve pattern-matching this normalized form against (Float * N, Bool * M, Float * 1) to get the solution N = 3, M = 2.
Note: The compiler would parse
(Int * 1)asInt, as it does now, but the inferencer would not viewIntas a tuple, and a generic specialization that would turn a parameterized tuple member into a 1-tuple would be a compiler error.
The compiler would require a more sophisticated unification algorithm to make this work, but the problem can be made more tractable by enforcing strict restrictions on allowed generic tuple expressions.
-
Expressions have to be in “normalized” form, that is, no two adjacent runs can have the same base type. This means
(Int * N, Int * N)is not allowed. -
The multiplicity parameter has to be used by itself; arithmetic expressions are not allowed. This means
(Int * (N + 1))is not allowed. (Making arithmetic expressions work would also depend on compile-time constants in Swift.)
These restrictions would save the type checker/inferencer from having to solve equations for now, but could always be loosened in the future.
Note that the first restriction only applies to generic expressions; (Int * 2, Int * 2) would be perfectly legal, and be equivalent to (Int, Int, Int, Int) and (Int * 4).
Heterogenous tuples such as (Int * 2, Bool * 1, UInt * 2) will have the same alignment and padding guarantees as (Int, Int, Bool, UInt, UInt) have today. (That is to say, not many.) Homogenous tuples will have additional guarantees as described in the memory layout guarantees section.
Link: Generics manifesto
When discussing vectors and fixed-size arrays (and tuple-related features in general), people often tag variadic generics as relevant to the implementation. In reality though, fixed-size arrays are independent of variadic generics, which are only relevant for heterogenous type aggregates. Vectors and fixed-size arrays are inherently homogenously typed, and so only ever need a constant number of type parameters (one). Variadic generics do come into play, however, when talking about literal syntax for fixed-size arrays.
Link: Compile-time parameters
Generic multiplicity parameters resemble generic value parameters where the value is of type Int.
For those unfamiliar with the concept, generic value parameters are Ints, Bools, Strings, etc that are passed to a type as generic parameters, with the constraint that the value must be known at compile time. Generic types access the value parameters essentially like static type properties. This feature is analogous to template parameters in C++.
We can think of generic multiplicity parameters as special cases of generic value parameters, but it’s probably better to separate the concepts when talking about changes to the type system. The compiler can infer multiplicity parameters from the structure of member tuple types, while it’s unclear how the compiler could infer an arbitrary value parameter like a String. An ordinary Int value parameter would also appear to a generic type like a gyb-ed static var, and would not allow you to declare a “variadic” (but not variadic generic) tuple member containing that number of elements.
To users, the two features could probably be presented as a unified concept, and would not need additional syntax to differentiate, as the compiler could just treat Int as a special case of value parameter that you can use as a multiplicity parameter. As compile-time constants become better-supported in Swift, the two features could eventually converge.
Implementation-wise, generic value parameters and generic multiplicity parameters are independent. We could support multiplicity parameters first, only allowing Ints inside the angle brackets, and then open them up to arbitrary types, or, we could support value parameters first, and then give Int special “multiplicity powers”.
We want to have a literal syntax for for vectors and fixed-size arrays, as packing and unpacking them is a pretty common thing to do, and the VectorN(...) or .init(...) constructors tend to add a lot of code noise without aiding code clarity. Tuple syntax seems like a natural fit, especially since fixed-size arrays are stack-allocated, and everything currently written with square brackets (Array<T>, Set<T>, Dictionary<K, V>, etc) is heap-allocated. Tuple syntax is also precedented in languages such as Python, where (x, y, z) is an immutable, fixed-size array, while [x, y, z] is a dynamic array.
let vector:Vector4<Float> = (0.0, 0.5, 1.0, 1.5)
let digits:Vector<10, Character> = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")Link: Swift evolution thread
ExpressibleByTupleLiteral is the natural extension of the ExpressibleBy family of literal protocols to tuple expressions. There are two main pathways through which this protocol could be implemented, both of which fit into larger features in the language.
Compound type constraints would allow users to constrain type parameters to be certain kinds of compound type, such as Tuple or Function, filling an existing hole in the language.
protocol ExpressibleByTupleLiteral
{
associatedtype TupleType:Tuple
init(tupleLiteral:TupleType)
}Variadic generics would allow us to parameterize by the types of the fields in the tuple, instead of the tuple as a whole.
protocol ExpressibleByTupleLiteral
{
associatedtype ...Members
init(tupleLiteral:(Members...))
}Regardless of how the protocol is spelled, conformances to it would look like this:
extension Vector:ExpressibleByTupleLiteral
{
init(tupleLiteral:(T * N))
{
self.storage = tupleLiteral
}
}While both approaches look similar, compound type constraints are probably far easier to implement in the compiler than variadic generics. In addition, approach 1 has an important advantage: it preserves the tuple argument labels.
Variadic generics, by only parameterizing the types of the tuple fields, can carry no tuple label information. This means all conformances to ExpressibleByTupleLiteral would have to accept unlabeled tuples, weakening type safety.
extension RGBA:ExpressibleByTupleLiteral
{
init(tupleLiteral:(Float * 4))
{
...
}
}
let c1:RGBA = (0, 0.25, 0.5, 0.75) // always okay
let c2:RGBA = (r: 0, g: 0.25, b: 0.5, a: 0.75) // works
let c3:RGBA = (x: 0, y: 0.25, z: 0.5, w: 0.75) // also worksApproach 2 allows conformances to specify tuple labels, limiting the kinds of tuples that the initializer accepts.
extension RGBA:ExpressibleByTupleLiteral
{
init(tupleLiteral:(r:Float, g:Float, b:Float, a:Float))
{
...
}
}
let c1:RGBA = (0, 0.25, 0.5, 0.75) // always okay
let c2:RGBA = (r: 0, g: 0.25, b: 0.5, a: 0.75) // works
let c3:RGBA = (x: 0, y: 0.25, z: 0.5, w: 0.75) // type errorLink: Make Numeric refine a new AdditiveArithmetic protocol
Vector2, Vector3, and Vector4 should support all arithmetic operators (+, -, *, /, %, etc), methods (rounded(), squareRoot(), etc), and conversion initializers their component types support. In addition, they themselves should conform to AdditiveArithmetic, but not its descendant protocols, since everything below Numeric requires ExpressibleByIntegerLiteral conformance (discussion thread). Top level functions like abs(_:) would also be overloaded on vector types with appropriate Scalar types.
% N = {2, 3, 4}
extension Vector{N}:AdditiveArithmetic where Scalar:AdditiveArithmetic
{
static var zero:Self { ... }
static func + (Self, Self) -> Self { ... }
static func += (inout Self, Self) { ... }
...
}
extension Vector{N} where Scalar:Numeric
{
static func * (Self, Self) -> Self { ... }
static func *= (inout Self, Self) { ... }
...
}
extension Vector{N} where Scalar:BinaryInteger
{
...
}
extension Vector{N} where Scalar:FloatingPoint
{
...
}
...In addition to the element-wise operators, a map(_:) method, subscript, and several cross-component methods are also useful.
infix operator <> :MultiplicationPrecedence // dot product
infix operator >< :MultiplicationPrecedence // cross product
infix operator ~~ :ComparisonPrecedence // distance test
infix operator !~ :ComparisonPrecedence // distance test
extension Vector{N}
{
func map<Result>(_ body:(Scalar) throws -> Result) rethrows -> Vector{N}<Result>
where Result:SIMDScalar
subscript(index:Int) -> Scalar { get set }
}
extension Vector2
{
func extend(with z:Scalar) -> Vector3 // (self.x, self.y, z)
}
extension Vector3
{
func extend(with w:Scalar) -> Vector4 // (self.x, self.y, self.z, w)
}
extension Vector{N} where Scalar:AdditiveArithmetic
{
var sum:Self { get } // self.x + self.y + ...
}
extension Vector{N} where Scalar:Numeric
{
static func <> (Self, Self) -> Scalar
var euclideanSquared:Self { get } // self <> self
var volume:Self { get } // self.x * self.y * ...
func scale(by factor:Scalar)
}
extension Vector2 where Scalar:Numeric
{
// fills z for the operands with 1, and returns the z of the result
static func >< (Self, Self) -> Scalar
}
extension Vector3 where Scalar:Numeric
{
static func >< (Self, Self) -> Self
}
extension Vector{N} where Scalar:Numeric & Comparable
{
static func < (Self, Scalar) -> Bool // self.euclideanSquared < r * r
static func <= (Self, Scalar) -> Bool // self.euclideanSquared <= r * r
static func ~~ (Self, Scalar) -> Bool // self.euclideanSquared == r * r
static func !~ (Self, Scalar) -> Bool // self.euclideanSquared != r * r
static func >= (Self, Scalar) -> Bool // self.euclideanSquared >= r * r
static func > (Self, Scalar) -> Bool // self.euclideanSquared > r * r
}
extension Vector{N} where Scalar:FloatingPoint
{
static func lerp(Self, Self, Scalar) -> Self
var length:Scalar { get } // self.euclideanSquared.squareRoot()
var normalized:Self { get } // self.scale(by: 1 / self.length)
var reciprocal:Self { get } // (1 / self.x, 1 / self.y, ...)
func clamp(to range:ClosedRange<Scalar> = 0 ... 1) -> Scalar
func addingProduct(Self, Scalar) -> Self
}Operators for dot product <> and cross product >< can be bikeshedded as needed. Possible alternatives for dot product are .. (could be confused with the range operator ...) and *+.
let cross:Vector3<Float> = a >< b
let facing:Bool = a <> b < 0
let facing:Bool = a .. b < 0
let facing:Bool = a *+ b < 0Vector<N:Int, T> should conform to Sequence. There are several benefits to this:
-
Fixed-size arrays will be able to use
for _ inloop syntax. -
Fixed-size arrays will inherit useful
Sequencemethods likecontains(_:),reduce(_:_:), andfirst(where:).
Because fixed-size arrays have a constant count, several optional methods and properties can be conditionally overriden to be non-optional.
extension Vector where N >= 2
{
func min() -> T
func min(by areInIncreasingOrder:(T, T) throws -> Bool) rethrows -> T
func max() -> T
func max(by areInIncreasingOrder:(T, T) throws -> Bool) rethrows -> T
}The map(_:) method should also be overriden with one that returns another fixed-size array.
extension Vector
{
func map<Result>((T) throws -> Result) -> Vector<N, Result>
}Fixed-size arrays cannot conform to Collection or above because they cannot possibly supply associated types like SubSequence. Many Collection/BidirectionalCollection/RandomAccessCollection methods should have fixed-size analogues though.
extension Vector
{
subscript(index:Int) -> T
var startIndex:Int { get }
var endIndex:Int { get }
var indices:Range<Int> { get }
func firstIndex(of:T) -> Int?
func firstIndex(where:(T) throws -> Bool) rethrows -> Int?
func last(where:(T) throws -> Bool) rethrows -> T?
func lastIndex(of:T) -> Int?
func lastIndex(where:(T) throws -> Bool) rethrows -> Int?
func reversed() -> Self
}
extension Vector where N >= 2
{
func randomElement() -> T
func randomElement<RNG>(using:inout RNG) -> T
}One drawback to fixed-size arrays not conforming to RandomAccessCollection is that such a conformance is required for significant compiler optimizations for operations like flatMap(_:) (discussion). Operations like makeIterator() and reversed() will also be difficult to implement efficiently due to fixed-size arrays being (trivial) value types. The optimizer will probably need to be modified to understand fixed-size arrays and emit efficient code for them.
Parameterized extensions on Vector will let us support transposition, matrix–matrix multiplication, and matrix–vector multiplication on 2x2, 3x3, and 4x4 matrices. There is also no reason why we can’t extend this to the irregular matrix shapes (2x3, 3x2, 2x4, 4x2, 3x4, 4x3), other than the high number of permuted methods we would have to add to the API.
extension<Scalar> Vector where N == 2, T == Vector2<Scalar>, Scalar:SIMDScalar
{
static func >< (Self, Self) -> Self
static func >< (Self, Vector2<Scalar>) -> Vector2<Scalar>
var transposed:Self { get }
}
extension<Scalar> Vector where N == 3, T == Vector3<Scalar>, Scalar:SIMDScalar
{
static func >< (Self, Self) -> Self
static func >< (Self, Vector3<Scalar>) -> Vector3<Scalar>
var transposed:Self { get }
}
extension<Scalar> Vector where N == 4, T == Vector4<Scalar>, Scalar:SIMDScalar
{
static func >< (Self, Self) -> Self
static func >< (Self, Vector4<Scalar>) -> Vector4<Scalar>
var transposed:Self { get }
}Code that uses vectors and matrices often also interfaces with C APIs which view them as buffers of scalars. A common idiom would be to take a raw buffer pointer to a matrix (or array of vectors) and bind it to its inner scalar type, and pass the typed pointer to the C API.
let matrix:Vector<4, Vector4<Float>>
withUnsafeBytes(of: matrix)
{
let elements:UnsafeBufferPointer<Float> = $0.bindMemory(to: Float.self)
glUniformMatrix4fv(location, 1, false, elements.baseAddress)
}
let vertices:[Vector3<Float>]
vertices.withUnsafeBytes
{
glBufferData(GL_ARRAY_BUFFER, $0.count, $0.baseAddress, GL_DYNAMIC_DRAW)
}We should provide layout guarantees so that such operations always work correctly.
Some vector/fixed-size array features depend on type system features not yet in the language.
| feature | depends on |
|---|---|
VectorN<Scalar> |
|
Vector<N:Int, T> |
generic multiplicity parameters |
ExpressibleByTupleLiteral |
compound type constraints |
| Vector API | |
| Fixed-size array API | |
| Matrix API | parameterized extensions |
A sketch for a implementation plan would add ExpressibleByTupleLiteral to the language first, as this allows people to start experimenting with vector syntax and API ergonomics, which could provide valuable information for the final design. Then Vector2, Vector3, and Vector4, and their APIs, could be added to the standard library. When generic multiplicity parameters become available, we can add general fixed-size arrays, and finally, matrix APIs.
-
Add
ExpressibleByTupleLiteralto the language. -
Add
VectorN<Scalar>and its operations to the language. -
Add
Vector<N:Int, T>and its operations to the language. -
Add matrix operations to the
Vector<N:Int, T>API.