Pitch: Vector, Matrix and Shaped Types

Introduction

I would like to pitch a design for how vector and matrix types could look in Swift. The type system would be upgraded to be able reason about a type's shape.

Motivation

Currently the Swift language does not have built in vector or matrix types. A user can create their own vector or matrix types but they will end up creating a separate type for every shape of vector and matrix they intend to use, and it is not possible to write functions that are generic over shape. For example the procedure for matrix multiplication of a matrix A with i rows and k columns, and a matrix B with k rows and j columns is identical for any values of i,j, and k but as it stands in Swift you would end up repeating the implementation for each specific combination.

Proposed Solution

It is proposed to introduce generic shape parameters as follows.

struct Matrix<T,shape(I,J)>

struct Vector<T,shape(I)>: Matrix<T,shape(I,1)>

The parameters of the shape keyword represent an arbitrary integer value. A vector is a special case of matrix where the second shape parameter is unity. These shape parameters can be referred to in code in an analogous way as generic type parameters. Matrix multiplication could therefore be implemented generically over shape as follows.

func matmul(a: Matrix<T,shape(I,K)>, b: Matrix<T,shape(K,J)>) -> Matrix<T,shape(I,J)> {
    var m = Matrix<T,shape(I,J)>.zero
    for i in 0..<I {
        for j in 0..<J {
            for k in 0..<K {
                m[i,j] += a[i,k] * a[k,j]
            }
        }
    }
    return m
}

Notice the special way the I, J,and K shape parameters are repeated in the function signature. This means that matmul is defined when the number columns of the first matrix are equal to the number of rows of the second matrix, and returns a matrix having the same number of rows as the first and the same number of columns as the second - as is required.

A positive feature of this design is that it is essentially the same as the suffix notation† ubiquitously used in physics and applied mathematics to represent vectors, matrices, and tensors. If you have ever read through a physics paper and come across equations that look like the following then the weird subscripts and superscripts are equivalent to the shape parameters in this pitch.

Shape parameters for vector and matrix types would be inferred from literal assignment, and subscripts for matrix types would be automatically synthesised based on shape.

let v1: Vector<Double> = [2.0, 3.4, 4.0, 1.0] //shape inferred to be shape(4)

let θy = 0.64
let roty: Matrix<Double> = [[ cos(θy), 0, sin(θy), 0], //shape inferred to be shape(4,4)
                            [       0, 1,       0, 0],
                            [-sin(θy), 0, cos(θy), 0],
                            [       0, 0,       0, 1]]

let v2 = matmul(roty, v1) //v1 rotated 0.64 radians about the y-axis

It would also be possible to write extensions to the matrix type based on its shape like this.

extension Matrix<T,shape(I,J)> { //2d matrix
    //methods available on general 2d matrices
    func transposed() -> T {
        var m: Matrix<T, shape(J, I)>.zero
        for i in 0..<I {
            for j in 0..<J {
                m[j,i] = self[i,j]
            }
        }
        return m
    }
}

extension Matrix<T,shape(I,I)> { //2d square matrix
    //methods only available on square matrices
    func trace() {
        var t: T = 0
        for i in 0..<I {
            t += self[i,i]
        }
        return t
    }

    func adjoint() {
        var adj = Matrix<T, shape(I, I)>.zero
        for i in 0..<I {
            for j in 0..<I {
                adj[i,j] = self.cofactor(i,j)
            }
        }
        return adj
    }
}

Source compatibility

This is an additive feature

Effect on ABI stability

I believe this would be purely additive

Effect on API resilience

don't know

Remarks

I am not aware of any current language that has shaped types like this. The language Idris has something called dependent types but that is a far more general and complicated concept. I think that shaped types would be far more straightforward for the type system to reason about. The solution proposed would feel familiar to any physicist or applied mathematician and would be an attractive feature of Swift over the usual scientific software languages of Python, Julia, Pascal, and Fortran.

† If you are curious to know more about suffix notation and why the suffixes are sometimes subscripts and sometimes superscripts then I recommend reading the first chapter of 'Vector and Tensor Analysis with Applications' by Borisenko and Tarapov.

2 Likes

This is related to the Vector Manifesto and related discussions of generic multiplicity parameters.

2 Likes

I’m very suspicious if we’re trying to merge vectors and matrices into a single type (dubious?), and still insisting on row-major literal notation. vectors as matrix columns is way more useful than vectors as matrix rows.

1 Like

I'm really glad that people are interested in this, but I'm going to be the party pooper who points out that pitches can't move forward now without implementations, and this requires significant changes to the language and type system. So any proposal along these lines would need to pitch and implement those changes first.

This would be neat if it worked. However, I have no idea how easy it would be for the type system to reason about—it's still a form of dependent typing (albeit limited), and I think that can cause all sorts of issues with type inference?

Some other remarks:

  • In order for any of this to make sense the generic types of matrix/vector elements need to be reasonably constrained; in fact, your matrix multiplication code wouldn't work, because there is no multiplication defined on generic T. Usually, in linear algebra, matrices are defined over rings (although you lose some operations, like row reduction, if you're not in a field), whereas vectors are defined over fields. Obviously, one would have to find a suitable restriction within the current (or future?) Swift type hierarchy.
  • "Vector" in mathematics is a more general concept than component vectors, although to be fair, for most engineering/programming tasks, abstract vector spaces are probably not that important. However, both row and column vectors are actually quite common (for example, the dot product of two column vectors x, y, can also be written as the matrix multiplication x.transposed * y), so I'm not sure if the unification with matrices is wise; maybe one should have separate types and then define .asRowVector, .asColumnVector on Vector?
1 Like

+1 for contributing to and merging discussion into existing threads. To clarify, implementations are not required for "pitch" threads or general discussions here.

3 Likes