betaFeedback

WorksComputer Science

Formalizing einsum\mathsf{einsum} with Named Tensor Notation

Abstract

Einstein notation (einsum\mathsf{einsum}) is a widely adopted tensor operation that has proven useful in areas such as machine learning and quantum computing. But it had no formal semantics until recently, and its properties had no mechanized verification. We formalize the denotational semantics of a language of tensors (multi-dimensional arrays) that supports einsum\mathsf{einsum} and repeated tensors (expand\mathsf{expand}). With this semantics, we verify equational rewriting rules about einsum\mathsf{einsum} and expand\mathsf{expand} that improve the performance of tensor computation. Whereas typical languages use unnamed tensors, whose shape is a sequence of natural numbers, we found it advantageous for mechanization to use named tensors, whose shape is a finite map from names to natural numbers. To our knowledge, this is the first time that the semantics and rewriting rules of einsum\mathsf{einsum} are mechanized in a proof assistant. Our solution is agnostic to proof assistants; we have implemented it in Lean and partially in Agda.

Introduction

Originating from physics as a shorthand on paper, Einstein notation has since been implemented in libraries for practical computation and found expanded use in popular domains such as machine learning [2, 17, 24], probabilistic programming [9, 11], and quantum computing [4, 16]. Also known as einsum, it can be thought of as a generalized multiplication that produces a tensor (a multi-dimensional array) from a list of tensors. It is versatile: for instance, it subsumes elementwise, matrix, and vector inner and outer product. Indeed, it can operate on any number of tensors, each with any number of dimensions. These dimensions are named in order to specify which sum-product, indexing, or broadcasting operations to perform [29]. For example, given an input matrix MM, we can compute the matrix product MMTMM^{T} by specifying einsum(Mij,Mkj→ikM_{ij}, M_{kj} \to ik) using the names i,j,ki,j,k.

Unfortunately, the many implementations of einsum do not agree entirely with each other. For instance, only some implementations allow multiple dimensions of the same input tensor to receive the same name. In PyTorch [2], we can extract the diagonal of a square matrix NN by writing einsum(Nii→iN_{ii} \to i), but the same expression causes a runtime error in another library Semiring Einsum [11]. Similarly, only some implementations allow multiple output dimensions with the same name. According to Weng et al. [29], we can make a diagonal matrix from a vector VV by writing einsum(Vi→iiV_i \to ii), but this expression is rejected by many implementations. These inconsistencies arise because library implementers follow an intuitive understanding of what einsum does, but there was no formal definition of what counts as a valid einsum expression.

To address these inconsistencies, researchers recently proposed a formal semantics for einsum [29]. They specify how to treat multiple dimensions with the same name. Furthermore, they use their semantics to prove a couple of rewriting rules for einsum, making it possible for future implementers to optimize einsum computations. But their formalization is not mechanized. Moreover, they do not discuss how einsum interacts with other common tensor operations.

In the present work, we mechanize the syntax and semantics of einsum. In doing so, we face challenges presented by the semantics of tensors and the syntax of names. Traditionally, the dimensions of a tensor are ordered and unnamed. Thus, the shape of a tensor and an index into a tensor are both lists of numbers. To operate on such a tensor, each einsum would introduce arbitrary names and associate them with the ordered dimensions. It is in each einsum—not in each tensor—that names like i,j,ki,j,k above are associated with dimensions. In order to specify well-formed einsum expressions, our mechanization would need to track these associations. And because the output dimensions are ordered, it would need to express the permutation of names.

To avoid these complications, we use named tensors [10] instead. The dimensions of a named tensor are unordered, and named independently of any operation. Thus, the shape of a tensor and an index into a tensor are both finite maps from names to numbers. Thanks to this representation, dimension names become intrinsic to tensors, so the syntax of einsum doesn’t need to associate names to dimensions separately. And because dimensions are unordered, names do not need to be permuted: a tensor of shape {i↦3,k↦4}\{i \mapsto3,k \mapsto4\} is as good as a tensor of shape {k↦4,i↦3}\{k \mapsto4,i \mapsto3\}, because these two shapes are simply the same finite map.

Based on this idea, we design a core tensor language with einsum. To show that named tensors are just as expressive as

Authors’ Contact Information: Yafei Yang, [email protected]; Chung-chieh Shan, [email protected], Indiana University, Bloomington, Indiana, USA. unnamed tensors, we translate unnamed tensor expressions to named ones. To study how to optimize einsum when it interacts with other tensor operations, we include another widely implemented operation expand, which repeats the contents of a tensor along new dimensions. We mechanize the semantics of our language and prove rewriting rules about einsum and expand. Our contributions are as follows.

  1. We mechanize a language with named tensors, einsum, and expand, as well as its denotational semantics.

  2. We show how the language we mechanize preserves the expressivity of a language with unnamed tensors.

  3. We prove rewriting rules about einsum and expand.

  4. We identify key definitions and properties needed to mechanize named tensors and their einsum.

  5. We carry out our mechanization in Lean and partially in Agda, demonstrating that our technique is not limited to a specific proof assistant.

In § 2, we give motivating examples of tensor operations. In § 3, we define a language of unnamed tensors and mechanize a language of named tensors. In § 4, we give the denotational semantics and demonstrate that it is preserved by a translation from the unnamed tensor language to the named tensor language. In § 5, we describe the definitions and properties of named shapes and indices that underpin our mechanization. In § 6, we state and prove the rewriting rules about einsum and expand. We conclude with related work in § 7.

Motivating Examples

We give a series of examples to illustrate the tensor operations we mechanize and their interactions. For each example, we write down an equation between the operation and the expected result. If necessary, we write down an intermediate step to explain the operation in the equation.

In our terms, an unnamed tensor is an array whose shape is a list of natural numbers (u1,…,un)(u_1,\ldots,u_n). The length nn of this list is the rank of the tensor. Each number uju_j in the list is the size of a dimension. An index into the tensor is a list (i1,…,in)(i_1,\ldots,i_n) of numbers such that 0≤ij<uj0 \le i_j < u_j. A rank-0 tensor is a scalar. A rank-1 tensor is a vector. A rank-2 tensor is a matrix.

einsum

The einsum operation expresses a wide range of multiplications in linear algebra [8, 29]: inner product of two vectors, outer product of two vectors, matrix product, matrix transposition, Hadamard product, Kronecker product, etc.

This operation takes a list of tensors, specifies a name for each of their dimensions, and picks output dimensions from the specified names. We use the form einsum(E[x⃗],…→z⃗)(E[\vec{x}],\ldots\to\vec{z}), where each input E[x⃗]E[\vec{x}] pairs an unnamed tensor EE with a corresponding list of dimension names x⃗\vec{x}, and z⃗\vec{z} is the list of dimension names corresponding to the output. For example, scaling a vector [3 2][3\ 2] by 5 can be written as:

einsum⁡([3 2][x],5[]→x)=[15 10](1)\operatorname{einsum}([3\ 2][x],5[] \to x)=[15\ 10] \tag*{(1)}

Here, the vector [3 2][3\ 2] has one dimension, which we name xx. The scalar 5 has no dimension to name.

We can also express the inner product between [3 2][3\ 2] and [20 10][20\ 10] by eliminating output dimension names:

einsum⁡([3 2][x],[20 10][x]→)=∑x[3 2]x⋅[20 10]x=80(2)\operatorname{einsum}([3\ 2][x],[20\ 10][x] \to)=\sum_x [3\ 2]_x\cdot[20\ 10]_x=80 \tag*{(2)}

Here we use the subscript xx to mean indexing a tensor by x∈{0,1}x \in\{0,1\}. The dimension xx is eliminated from the output and thus summed out. If we keep the output dimension xx instead, we get elementwise multiplication:

einsum⁡([3 2][x],[20 10][x]→x)=[60 20](3)\operatorname{einsum}([3\ 2][x],[20\ 10][x] \to x)=[60\ 20] \tag*{(3)}

The output of einsum cannot introduce new dimensions. For example, the einsum below is invalid, since its output uses a name yy that doesn’t occur as any input dimension:

einsum⁡([3 2][x],[20 10][x]→y)(4)\operatorname{einsum}([3\ 2][x],[20\ 10][x] \to y) \tag*{(4)}

If we use yy as the dimension name of [20 10][20\ 10], we get a valid einsum operation:

einsum⁡([3 2][x],[20 10][y]→y)=[∑x20⋅[3 2]x, ∑x10⋅[3 2]x]=[100 50](5)\begin{aligned} \operatorname{einsum}([3\ 2][x],[20\ 10][y] \to y) \\ &=\left[\sum_x 20\cdot[3\ 2]_x,\ \sum_x 10\cdot[3\ 2]_x\right]=[100\ 50] \tag*{(5)} \end{aligned}

The dimension name xx is again eliminated from the output, so elements along this dimension are summed up. In contrast, when we use both xx and yy in the output dimensions, we get the outer product of [3 2][3\ 2] and [20 10][20\ 10]:

einsum⁡([3 2][x],[20 10][y]→xy)=[60304020](6)\operatorname{einsum}([3\ 2][x],[20\ 10][y] \to xy)= \begin{bmatrix} 60 & 30\\ 40 & 20 \end{bmatrix} \tag*{(6)}

Returning to the opening example, given any matrix MM, the expression einsum⁡(M[i j],M[k j]→ik)\operatorname{einsum}(M[i\ j],M[k\ j] \to ik) computes a square matrix MMTMM^T, of which each element [i,k][i,k] is the sum-of-product ∑jM[i,j]M[k,j]\sum_j M[i,j]M[k,j]. The first dimension of MM is named both ii and kk by the einsum operation, even though MM itself does not come with dimension names.

expand

The expand operation adds dimensions to a tensor by repeating its contents. It is implemented either by making multiple elements point to the same memory location [2, 17] or by copying existing elements to new memory locations [24].

This operation takes a tensor, specifies a distinct name for each of its dimensions, and adds new dimensions to it. We use the form expand(E[x⃗]→z⃗)(E[\vec{x}] \to\vec{z}), where EE is an unnamed tensor, and x⃗,z⃗\vec{x},\vec{z} are the input and output lists of dimension names. For example, a scalar 4 can be expanded to a vector:

expand⁡(4[]→x(2))=[4 4](7)\operatorname{expand}(4[] \to x^{(2)})=[4\ 4] \tag*{(7)}

The size 2 of the new dimension, indicated by the superscript (2)(2), is actually part of every dimension name but often elided. A vector can be expanded to a matrix in various ways:

expand⁡([3 2][x(2)]→x(2)y(2))=[3322](8)\operatorname{expand}([3\ 2][x^{(2)}] \to x^{(2)}y^{(2)}) = \begin{bmatrix} 3 & 3 \\ 2 & 2 \end{bmatrix} \tag*{(8)}
expand⁡([3 2][x(2)]→z(2)x(2))=[3232](9)\operatorname{expand}([3\ 2][x^{(2)}] \to z^{(2)}x^{(2)}) = \begin{bmatrix} 3 & 2 \\ 3 & 2 \end{bmatrix} \tag*{(9)}
expand⁡([3 2][x(2)]→x(2)w(3))=[333222](10)\operatorname{expand}([3\ 2][x^{(2)}] \to x^{(2)}w^{(3)}) = \begin{bmatrix} 3 & 3 & 3 \\ 2 & 2 & 2 \end{bmatrix} \tag*{(10)}

The different results in (8) and (9) show that order matters. The expanded matrix (10) can be further expanded:

expand⁡(expand⁡([3 2][x]→xw)[xw]→zxw)=[[333222][333222]](11)\operatorname{expand}(\operatorname{expand}([3\ 2][x] \to xw)[xw] \to zxw) = \left[ \begin{bmatrix} 3 & 3 & 3 \\ 2 & 2 & 2 \end{bmatrix} \begin{bmatrix} 3 & 3 & 3 \\ 2 & 2 & 2 \end{bmatrix} \right] \tag*{(11)}

We can merge the two nested expands above into one:

expand⁡([3 2][x]→zxw)=[[333222][333222]](12)\operatorname{expand}([3\ 2][x] \to zxw) = \left[ \begin{bmatrix} 3 & 3 & 3 \\ 2 & 2 & 2 \end{bmatrix} \begin{bmatrix} 3 & 3 & 3 \\ 2 & 2 & 2 \end{bmatrix} \right] \tag*{(12)}

Nesting einsum and expand

Let E=[60304020]E = \begin{bmatrix} 60 & 30 \\ 40 & 20 \end{bmatrix} be the result of (6). We can use einsum to combine it with the result of (12):

einsum⁡(expand⁡([3 2][x]→zxw)[zxw],E[xy]→zxwy)=[[[180901809018090][804080408040]][[180901809018090][804080408040]]](13)\operatorname{einsum}(\operatorname{expand}([3\ 2][x] \to zxw)[zxw], E[xy] \to zxwy) = \left[ \left[ \begin{bmatrix} 180 & 90 \\ 180 & 90 \\ 180 & 90 \end{bmatrix} \begin{bmatrix} 80 & 40 \\ 80 & 40 \\ 80 & 40 \end{bmatrix} \right] \left[ \begin{bmatrix} 180 & 90 \\ 180 & 90 \\ 180 & 90 \end{bmatrix} \begin{bmatrix} 80 & 40 \\ 80 & 40 \\ 80 & 40 \end{bmatrix} \right] \right] \tag*{(13)}

This result, a tensor of shape (2,2,3,2)(2, 2, 3, 2), can also be obtained by applying einsum and expand in the opposite order:

expand⁡(einsum⁡([3 2][x],E[xy]→xy)[xy]→zxwy)(14)\operatorname{expand}(\operatorname{einsum}([3\ 2][x], E[xy] \to xy)[xy] \to zxwy) \tag*{(14)}

The reordering is possible because the einsum in (13) doesn’t need any summation. We say this einsum is summation-free. This swap makes einsum operate on a smaller tensor, which improves the performance of the whole operation.

The general case of einsum computes a sum product. To illustrate this, change the output dimensions in (13) to xwxw:

einsum⁡(expand⁡([3 2][x]→zxw)[zxw],E[xy]→xw)=[540540540240240240](15)\operatorname{einsum}(\operatorname{expand}([3\ 2][x] \to zxw)[zxw], E[xy] \to xw) = \begin{bmatrix} 540 & 540 & 540 \\ 240 & 240 & 240 \end{bmatrix} \tag*{(15)}

Again let us apply einsum and expand in the opposite order:

expand⁡(einsum⁡([3 2][x],E[xy]→x)[x]→xw)=[270270270120120120](16)\operatorname{expand}(\operatorname{einsum}([3\ 2][x], E[xy] \to x)[x] \to xw) = \begin{bmatrix} 270 & 270 & 270 \\ 120 & 120 & 120 \end{bmatrix} \tag*{(16)}

The results in (15) and (16) differ by a factor of 2, which is the size of the zz dimension. We need to make up for the factor to preserve the result when swapping einsum with expand. Based on this idea, we prove the general commutativity rule between einsum and expand.

The Syntax of a Tensor Language

We give the syntax of our tensor language, in two versions. In the first version, expressions denote tensors with unnamed dimensions, as conceived usually in tensor libraries and illustrated in Section 2. In the second version, expressions denote tensors with named dimensions. We mechanize the second version, and we specify the necessary conditions to guarantee well-formedness in a dependently typed proof assistant.

To show the correspondence between the two versions, we give a translation in Section 4.3.

An Unnamed Tensor Language

The syntax of an unnamed tensor language is shown in Figure 1. A tensor expression can be a literal scalar α\alpha, a zero tensor of a specified shape (s,…)(s,\ldots), a tensor scaled by a natural number, a sum of two tensors, a tensor variable, a binding, an expand, or an einsum. To specify the input and output of expand and einsum, we use index variable sequences, which are lists of index variables. Below we explain each construct in turn.

The syntax of an unnamed tensor language

Figure 1. The syntax of an unnamed tensor language

Constants

3.1.1 Constants. Constant tensors include scalars and zero tensors. We require that a scalar range over a semiring S\mathbb{S}. A scalar always has the shape (). Therefore, the scalar 0 can either be written as a scalar 0 or a zero tensor 0()0^{()}.

A zero tensor is specified by a shape (s,…)(s,\ldots), a list of natural numbers. All of its elements are 0 in the semiring. A zero tensor can also be expressed by expanding a scalar:

0(s1,…,sn)=expand⁡(0[ ]→x1(s1)⋯xn(sn))(17)0^{(s_{1},\ldots,s_{n})} = \operatorname{expand}(0[\,] \to x_{1}^{(s_{1})}\cdots x_{n}^{(s_{n})}) \tag*{(17)}

Scaling

3.1.2 Scaling. A scaling expression n⋅En \cdot E multiplies each element in EE by the natural number nn. Here multiplication means repeated addition, so we can express it by using + repeatedly. We can also express it using einsum and expand:

n⋅E=einsum⁡(expand⁡(1[ ]→x(n))[x(n)],E[y⃗]→y⃗)(18)n \cdot E = \operatorname{einsum}(\operatorname{expand}(1[\,] \to x^{(n)})[x^{(n)}], E[\vec{y}] \to\vec{y}) \tag*{(18)}

where xx is a name that doesn’t occur in y⃗\vec{y}.

Addition

3.1.3 Addition. The expression E+FE + F performs semiring addition elementwise. EE and FF must have the same shape.

Tensor variables and let

3.1.4 Tensor variables and let. A tensor variable tt is introduced by a let expression. As explained in Section 4.1, a tensor variable denotes an unnamed tensor, whose shape is a list of natural numbers. To use the variable, we simply name it, but we assume that its shape is correct and known. For example, in a tensor expression t1+t2t_{1} + t_{2}, we assume that t1t_{1} and t2t_{2} have the same shape, which can be looked up from the let expressions where t1t_{1} and t2t_{2} are bound.

expand

As shown in Section 2.2, an expand expression transforms a tensor to a higher rank by repeating its contents. In the general form expand⁡(E[x⃗]→z⃗)\operatorname{expand}(E[\vec{x}] \to\vec{z}), the input index variables in x⃗\vec{x} must be distinct, the output index variables in z⃗\vec{z} must be distinct, and every index variable occurring in x⃗\vec{x} must also occur in z⃗\vec{z}.

einsum

As shown in Section 2.1, einsum defines each output element as a sum of products of input elements. To specify which dimensions to sum over and which to multiply together, einsum uses index variables to relate the input tensors’ dimensions to the output tensor’s dimensions.

In the general form einsum⁡(E[x⃗],…→z⃗)\operatorname{einsum}(E[\vec{x}], \ldots\to\vec{z}), variables in each input variable sequence x⃗\vec{x} must be distinct, but one index variable can occur in multiple input index variable sequences. The output index variables in z⃗\vec{z}, if any, must be distinct and must each appear at least once among the input x⃗\vec{x} sequences. These restrictions rule out the problematic sequence iiii in Section 1.

Index variables

Index variables. An index variable x(s)x^{(s)} is a name xx together with an upper bound ss. It tells expand and einsum which tensor dimensions to operate on. For instance, in expand⁡([3 2] [x(2)]→x(2)w(3))\operatorname{expand}([3\ 2]\ [x^{(2)}] \to x^{(2)}w^{(3)}) from (10), the variable x(2)x^{(2)} specifies the only dimension of the input tensor [3 2][3\ 2] to be of size 2 and names it as xx. The variable w(3)w^{(3)} specifies where to add the new dimension and its size 3. It is an error to operate on a tensor whose shape does not match the upper bound of the index variable, as in expand⁡([3 2] [w(3)]→x(2)w(3))\operatorname{expand}([3\ 2]\ [w^{(3)}] \to x^{(2)}w^{(3)}).

The index variable x(s)x^{(s)} iterates over integers between 0 and s−1s - 1. We write ∣x(s)∣\lvert x^{(s)} \rvert for the upper bound ss.

We write x⃗\vec{x} or y⃗\vec{y} or z⃗\vec{z} for an index variable sequence. We notate concatenation of sequences by juxtaposition: x⃗y⃗\vec{x}\vec{y}. We define the union sequence x⃗∪y⃗\vec{x} \cup\vec{y} to be the concatenation x⃗y⃗\vec{x}\vec{y} with duplicates removed (leaving the first occurrence of each index variable, say, so xy∪xzx=xyzxy \cup xzx = xyz). We write #x⃗\#\vec{x} for the number of index variables in x⃗\vec{x}. We write ∣x⃗∣\lvert\vec{x} \rvert for the list of upper bounds of the index variables in x⃗\vec{x}.

Index variables in different operations are interpreted in separate scopes. For instance, the nested expand from Eq. (11) can be rewritten as

expand⁡(expand⁡([3 2] [x]→xw) [zw]→xzw).(19)\operatorname{expand}(\operatorname{expand}([3\ 2]\ [x] \to xw)\ [z w] \to xzw). \tag*{(19)}

The underlined xx is interpreted as a new dimension added to the input of the outer expand, rather than referring to the one without underline from the inner expand.

Thus, when nesting one expand inside another, the index variable sequences for the inner output and the outer input may use different names. In (19) for example, the inner output x(2)w(3)x^{(2)}w^{(3)} and the outer input z(2)w(3)z^{(2)}w^{(3)} specify the same shape ∣x(2)w(3)∣=∣z(2)w(3)∣=[2,3]\lvert x^{(2)}w^{(3)} \rvert= \lvert z^{(2)}w^{(3)} \rvert= [2, 3] but have different names. For two index variable sequences x⃗\vec{x} and y⃗\vec{y}, as long as ∣x⃗∣=∣y⃗∣\lvert\vec{x} \rvert= \lvert\vec{y} \rvert, we can rename index variables between x⃗\vec{x} and y⃗\vec{y}. This idea is used in Section 4.3 to translate the unnamed tensor language to a named version and eliminate alpha-conversion.

A Named Tensor Language

The syntax of a named tensor language in Lean is shown in Figure 2. In this definition, a TExpr is an inductive type parameterized by a value type SS and indexed by a Context and an Is. It represents a well-formed tensor whose dimensions are named. We require that SS be an instance of Semiring.

The syntax of a named tensor languageVector (PDF)
inductive TExpr {S : Type} [Semiring S] :
  Context → Is → Type where
  | scalar {Γ : Context} : S → TExpr Γ empty
  | zero {Γ : Context} (xs : Is) → TExpr Γ xs
  | scale {Γ : Context} {xs : Is} :
    ℕ → TExpr Γ xs → TExpr Γ xs
  | add {Γ : Context} {xs ys : Is} :
    TExpr Γ xs → TExpr Γ ys → xs ⊎ ys →
    TExpr Γ xs
  | let {Γ : Context} {xs : Is} :
    (dims : List IVar) → (neq : Unique dims) →
    (rhs : TExpr Γ (fromList dims neq) →
    body : TExpr Γ (, (dims.map Prod.snd)) xs) →
    TExpr Γ xs
  | var {Γ : Context} :
    (dims : List IVar) → (neq : Unique dims) →
    (dims.map Prod.snd ∈ᵘ Γ) →
    TExpr Γ (fromList dims neq) →
  | expand {Γ : Context} {xs zs : Is} :
    TExpr Γ xs → xs ⊆ zs → TExpr Γ zs
  | einsum {Γ : Context} {xss : List Is} {zs : Is} :
    TExpr Γ xss →
    (xssCompat : IssCompat xss) →
    zs ⊆ ⋃ xssCompat →
    TExpr Γ zs

Figure 2. The syntax of a named tensor language

A Context stores the shapes of tensor variables in de Bruijn style. It is defined as the following inductive data type:

inductive Context : Type where
  | nil : Context
  | snoc : Context → List UpperBound → Context
infixl:55 " ∙ " => Context.snoc

As List UpperBound above indicates, a shape in a Context is a list of unnamed dimension sizes. Here UpperBound is an alias for natural numbers that store a dimension size:

abbrev UpperBound := ℕ

An Is is a finite map that represents the shape of a tensor whose dimensions are named. Therefore, we use named shape to mean an Is for TExpr below. For example, the named shape of (12) in the named tensor language can be written as

{w↦3,x↦2,z↦2}.(20)\{w \mapsto3, x \mapsto2, z \mapsto2\}. \tag*{(20)}

We leave the details of Is to Section 5. Because a TExpr is indexed by an Is, we always have the dimension names and sizes for any given tensor. Thus, the type of (12) in the empty Context nil can be written as

TExpr (S := ℕ) nil {w ↦ 3, x ↦ 2, z ↦ 2}

The constructors of TExpr correspond to each case of tensor expressions in Figure 1. We explain the constraints introduced by each constructor below.

Constants

The constructor scalar takes a value of type S. Its named shape is the empty map. The constructor zero simply takes a named shape xs.

Scaling

The constructor scale takes a factor n and a tensor of named shape xs. The result also has shape xs.

Addition

The constructor add takes two tensors, of named shapes xs and ys. Here we require that xs and ys be equivalent, written xs≈ysxs \approx ys: for any index variable name x, if x is in xs and has the size up, then x is in ys and also has the size up, and vice versa. For example,

{w ↦ 3, x ↦ 2, z ↦ 2} ≈ {z ↦ 2, x ↦ 2, w ↦ 3}

This definition makes it possible to avoid explicit permutations between different Ises. Since xs and ys are equivalent, we can pick either as the result shape. Here we choose xs.

Tensor variables

The way tensor variables are introduced and used reflects the fact that, whereas a tensor denoted by an expression has named dimensions, a tensor associated with a variable has unnamed dimensions. This distinction is that between R-values and L-values [13].

Tensor variables are introduced by the constructor let. Since tensor variables are encoded with de Bruijn indices, let doesn’t need to take a tensor variable name to bind. Instead, it takes a list of index variables, which are defined as a product of an index variable name and a dimension size:

abbrev IVar := Id × UpperBound

We encode index variable names as Strings:

abbrev Id := String

The next argument neq is a proof that names in dims have no duplicates. We can construct an Is with fromList dims neq, which is the named shape of the right hand side tensor of let. The body of let is a tensor in a larger Context (Γ⊢,(dims.mapProd.snd))(\Gamma\vdash, (dims.map Prod.snd)) with the named shape xs.

To refer to a tensor variable, we use var, which takes three explicit arguments. First, dims lists the index variables with which to index the tensor. Second, neq requires the names in dims to be unique. Finally, the argument of type dims.map Prod.snd ∈ᵘ Γ specifies which tensor variable to use, and requires the upper bounds in dims to match. The relation ∈u\in^{u} specifies the lookup of a de Bruijn-style variable:

inductive CtxMem : List UpperBound → Context →
  Type where
| here {Γ : Context} {dims : List UpperBound} :
  CtxMem dims (Γ ↝, dims)
| there {Γ : Context} {dims dims' : List UpperBound} :
  CtxMem dims Γ → CtxMem dims (Γ ↝, dims')

Note that the index variable names in let and in var can differ, so a tensor variable can be used multiple times with different index variable sequences. For example, suppose M is a matrix introduced by a let whose dims is [("a", 2), ("b", 3)]. Then, to compute MMTMM^{T} by einsum (Mij,Mkj→ik)(M_{ij}, M_{kj} \to ik) as in Section 1, we can refer to M twice by var, with the dims [("i", 2), ("j", 3)] and [("k", 2), ("j", 3)] respectively.

expand

The constructor expand takes a tensor of named shape xs and returns a tensor of named shape zs. We require that xs be a subset of zs, written xs⊆zsxs \subseteq zs: for any index variable name x, if x is in xs and has the size up, then x is in zs and also has the size up. For example,

{x ↦ 2, z ↦ 2} ⊆ {z ↦ 2, x ↦ 2, w ↦ 3}

einsum

The constructor einsum takes a sequence of tensor expressions of named shapes xss and returns a tensor of named shape zs. A sequence of tensor expressions is defined as an inductive data type TExprSeq indexed by a Context and a list of Is:

inductive TExprSeq {S : Type} [Semiring S] :
  Context → List Is → Type where
| nil {Γ : Context} : TExprSeq Γ []
| cons {Γ : Context} {xs : Is} {xss : List Is} :
  TExpr Γ xs → TExprSeq Γ xss →
  TExprSeq Γ (xs :: xss)

We require the Ises in xss to be pairwise compatible. Two Ises xs and ys are compatible, written xs∼ysxs \sim ys, if every index variable name x occurs either in xs or ys, or in only one of xs and ys, or in both xs and ys with the same size. So

{x ↦ 2, z ↦ 2} ∼ {z ↦ 2, x ↦ 2, w ↦ 3}

but

{x ↦ 2, z ↦ 2} ≁ {z ↦ 3, x ↦ 2, w ↦ 3}

We also require the result shape zs to be a subset of the union of xss. The union of a list of compatible Ises, written ⋃xss\bigcup xss, is defined recursively using the union of two Ises xs and ys, written xs∪ysxs \cup ys: for any index variable name x, if x occurs in xs ∪ ys, then x occurs either in xs or ys with the same size, and vice versa. For example,

{x ↦ 2, y ↦ 4, z ↦ 2} ∪ {z ↦ 2, x ↦ 2, w ↦ 3} ≈ {z ↦ 2, y ↦ 4, x ↦ 2, w ↦ 3}

Denotational Semantics

In this section, we give the denotational semantics of the two versions of our tensor language. The semantics of the unnamed version is given in Section 4.1. The semantics of the named version is given in Section 4.2. We give a semantics-preserving translation between the unnamed version and the named version in Section 4.3.

⟦α⟧γ[()]=α(21)\llbracket\alpha\rrbracket_\gamma[()] = \alpha \tag*{(21)}
⟦0(s,…)⟧γ[I]=0(22)\llbracket0^{(s,\ldots)} \rrbracket_\gamma[I] = 0 \tag*{(22)}
⟦n⋅E⟧γ[I]=n⋅⟦E⟧γ[I](23)\llbracket n \cdot E \rrbracket_\gamma[I] = n \cdot\llbracket E \rrbracket_\gamma[I] \tag*{(23)}
⟦E1+E2⟧γ[I]=⟦E1⟧γ[I]+⟦E2⟧γ[I](24)\llbracket E_1 + E_2 \rrbracket_\gamma[I] = \llbracket E_1 \rrbracket_\gamma[I] + \llbracket E_2 \rrbracket_\gamma[I] \tag*{(24)}
⟦let⁡t=E1in⁡E2⟧γ[I]=⟦E2⟧γ;t,⟦E1⟧γ[I](25)\llbracket\operatorname{let} t = E_1 \operatorname{in} E_2 \rrbracket_\gamma[I] = \llbracket E_2 \rrbracket_{\gamma;t,\llbracket E_1 \rrbracket_\gamma}[I] \tag*{(25)}
⟦t⟧γ[I]=γ(t)[I](26)\llbracket t \rrbracket_\gamma[I] = \gamma(t)[I] \tag*{(26)}
⟦expand⁡(E[x⃗]→z⃗)⟧γ[I]=⟦E⟧γ[{z⃗↦I}(x⃗)](27)\llbracket\operatorname{expand}(E[\vec{x}] \to\vec{z}) \rrbracket_\gamma[I] = \llbracket E \rrbracket_\gamma[\{\vec{z} \mapsto I\}(\vec{x})] \tag*{(27)}
⟦einsum⁡(E1[x⃗1],…,Ek[x⃗k]→z⃗)⟧γ[I]=∑δ∈funs⁡(⋃i=1kx⃗i∖z⃗)∏i=1k⟦Ei⟧γ[(δ∪{z⃗↦I})(x⃗i)](28)\begin{aligned} \llbracket\operatorname{einsum}(E_1[\vec{x}_1],\ldots,E_k[\vec{x}_k]\to\vec{z}) \rrbracket_\gamma[I] &= \sum_{\delta\in\operatorname{funs}(\bigcup_{i=1}^{k}\vec{x}_i\setminus\vec{z})} \prod_{i=1}^{k}\llbracket E_i \rrbracket_\gamma[(\delta\cup\{\vec{z}\mapsto I\})(\vec{x}_i)] \tag*{(28)} \end{aligned}

The Semantics of the Unnamed Tensor Language

The denotational semantics of the unnamed tensor language is shown in Figure 3. The denotation ⟦E⟧γ\llbracket E \rrbracket_\gamma of an unnamed tensor expression EE in an environment γ\gamma is an unnamed tensor. An environment is a function from tensor variable names to unnamed tensors. An unnamed tensor is a function that takes an index II and returns a value from the semiring S\mathbb{S}. An index is a list of natural numbers.

The denotations of unnamed tensor expressions

Figure 3. The denotations of unnamed tensor expressions

The first four cases of Figure 3 are simple. (21) says that a literal scalar has value α\alpha. (22) says that a zero tensor has value 0 for any index II. (23) says that the denotation of n⋅En \cdot E is the denotation of EE multiplied by nn. (24) requires that the two tensors have the same shape and adds the elements at the location specified by II.

(25) says that we get the denotation of the right hand side E1E_1 of the let expression in γ\gamma, extend γ\gamma with tt bound to the denotation of E1E_1, and then get the denotation of E2E_2 in the extended environment. (26) says that we look up a tensor variable tt in γ\gamma and pass II to its tensor value.

To define the denotation of expand and einsum, we first introduce named indices. A named index is a function δ\delta from some index variables to non-negative integers, such that 0≤δ(x(s))<s0 \le\delta(x^{(s)}) < s for each x(s)x^{(s)} in the domain of δ\delta. Let x⃗=x1(s1)⋯xr(sr)\vec{x} = x_1^{(s_1)} \cdots x_r^{(s_r)} be a sequence of rr index variables, not necessarily distinct. If δ\delta is a named index whose domain includes x⃗\vec{x}, then we write δ(x⃗)\delta(\vec{x}) for the index (δ(x1),…,δ(xr))(\delta(x_1),\ldots,\delta(x_r)), which can be used to index a tensor of shape (s1,…,sr)(s_1,\ldots,s_r). Conversely, if II is (i1,…,ir)(i_1,\ldots,i_r), then we write {x⃗↦I}\{\vec{x}\mapsto I\} for the named index {x1↦i1,…,xr↦ir}\{x_1\mapsto i_1,\ldots,x_r\mapsto i_r\}; here we do require the index variables in x⃗\vec{x} to be distinct. We also define the set funs⁡(x⃗)\operatorname{funs}(\vec{x}) to consist of all named indices whose domain is x⃗\vec{x}.

(27) says, to look up an element of an expanded tensor, we look up the corresponding element of the original tensor, by removing from the index the new dimensions introduced by expand. For instance, the element of ⟦expand⁡(E[x]→xy)⟧γ\llbracket\operatorname{expand}(E[x] \to xy) \rrbracket_\gamma at (i,j)(i,j) is the element of ⟦E⟧γ\llbracket E \rrbracket_\gamma at ii.

def denote {S : Type} [Semiring S]
    {Γ : Context} {xs : Is}
    (t : TExpr (S := S) Γ xs)
    (env : Env (S := S) Γ)
    (idx : NIndex xs) : S :=
  match t with
  | .scalar r => r
  | .zero => 0
  | .scale n t => n * denote t env idx
  | .add t₁ t₂ xs_ys =>
      (denote t₁ env idx) +
      (denote t₂ env (idx →ᵢ xs_ys))
  | .let dims neq rhs body =>
      let rhsNamed := denote rhs env
      let rhsUnnamed idx' :=
        rhsNamed (NIndex.fromUnnamed dims neq idx')
      denote body (env, rhsUnnamed) idx
  | .var dims neq v =>
      lookupUnnamed v env
        (NIndex.toUnnamed dims neq idx)
  | .expand t xs_zs => denote t env (idx ↓ᵢ xs_zs)
  | .einsum t xs_zs => sts xsComp zss xs_zs
      have zs_disjoint : zs ⟂ (⋃ xssComp \ zs) :=
        minusIs_disjoint
      have zs_union :
        zs ∪ (⋃ xssComp \ zs) ≈ ⋃ xssComp :=
          minusIs_union eq_zs_xss
      sum (⋃ xssComp \ zs)
        (fun idx' =>
          denotes ts xssComp
            (ISubset_refl (xs := ⋃ xssComp)) env
            ((⋃ᵢ zs_disjoint id idx') →ᵢ zs_union))

Equation (28) defines the denotation of an einsum expression by iterating over all indices and summing out those index variables that do not appear in the output z⃗\vec{z}. (Recall that our syntax requires z⃗\vec{z} to be a subset of ⋃i=1kx⃗i\bigcup_{i=1}^{k}\vec{x}_i.) For instance, multiplying two matrices E1E_1 and E2E_2 is denoted by einsum⁡(E1[xy],E2[yz]→xz)\operatorname{einsum}(E_1[xy], E_2[yz] \to xz), because (28) amounts to

⟦einsum⁡(E1[xy],E2[yz]→xz)⟧γ[(i,k)]=∑j⟦E1⟧γ[(i,j)]⟦E2⟧γ[(j,k)].(29)\llbracket\operatorname{einsum}(E_1[xy], E_2[yz] \to xz) \rrbracket_\gamma[(i,k)] = \sum_j \llbracket E_1 \rrbracket_\gamma[(i,j)]\llbracket E_2 \rrbracket_\gamma[(j,k)]. \tag*{(29)}

The Semantics of the Named Tensor Language

The denotational semantics of the named tensor language is shown in Figure 4. In this definition, the function denote is parameterized by a Semiring SS, a Context Γ\Gamma, and a named shape xs. It then takes a tensor expression t, an environment env, and a named index idx of type NIndex xs, before returning a value of type S. Therefore, the denotation of a named tensor expression is a named tensor, which is a function that takes a named index and returns a value from the semiring S. We explain the arguments and definition of denote below.

Figure 4. The denotations of named tensor expressions

Environment

The environment env has type Env (S := S) Γ, which depends on the Context Γ. Each unnamed shape dims in Γ calls for an unnamed tensor in env, whose type UnnamedTensor dims we define shortly.

def Env {S : Type} [Semiring S] : Context → Type
  | .nil => Unit
  | Γ `, dims =>
    Env (S := S) Γ × UnnamedTensor (S := S) dims

An UnnamedTensor of unnamed shape dims is a function from an index of type UIndex dims to a value of type S:

abbrev UnnamedTensor {S : Type} [Semiring S]
    (dims : List UpperBound) :=
  UIndex dims → S

An (unnamed) index, or UIndex, of shape dims is a sequence of natural numbers, each bounded by the corresponding element d of dims:

def UIndex (dims : List UpperBound) : Type :=
  match dims with
  | [] => Unit
  | d :: ds => Fin d × UIndex ds

Named indices

Conceptually, a named index is a finite map from names to numbers that are bounded by a named shape. For example, if xs is the named shape {z ↦ 2, x ↦ 2, w ↦ 3}, then the argument idx : NIndex xs in Figure 4 can be the named index {z ↦ 1, x ↦ 0, w ↦ 2}ᵢ. The type NIndex xs is defined as a structure with a field get. This field is a function that takes an index variable name x and a dimension size u. If get looks up x in xs and finds the value u, it returns a number bounded by u:

structure NIndex (xs : Is) where
  get : ∀ {x : Id} {u : UpperBound},
    lookup xs x = some u → Fin u

Here, lookup is a function that takes a named shape xs and an index variable name x. It returns an Option UpperBound to indicate if x is found in xs:

def lookup (xs : Is) (x : Id) : Option UpperBound

The definition of denote

The definition of denote in Figure 4 closely follows the definition of ⟦⟧ in Figure 3. The first three cases are simple. A scalar always has the value r. A zero tensor always has the value 0. The denotation of a scaled tensor is the denotation of the tensor multiplied by a natural number.

The denotation of add t₁ t₂ xs_ys at a named index idx depends on the denotations of t₁ and t₂. For t₁, we simply use the index idx, which is of t₁’s shape. For t₂, since its shape is equivalent to t₁’s, we use →ᵢ to convert idx from t₁’s shape to t₂’s shape. Since this conversion is based on the equivalence of two shapes, we do not need to explicitly define permutation between indices.

The key to tensor variable binding and reference is a pair of functions that converts between a named index and an unnamed index, NIndex.fromUnnamed and NIndex.toUnnamed. For example, given an unnamed shape (2, 2, 3) and a corresponding unnamed index (1, 0, 2), if we know the three dimensions are named as z, x, w, then we can get a named index {z ↦ 1, x ↦ 0, w ↦ 2}ᵢ. Similarly, given a named shape {w ↦ 3, x ↦ 2, z ↦ 2} and a named index {w ↦ 2, x ↦ 0, z ↦ 1}ᵢ, if we know the dimension order is (z, x, w), we can construct an unnamed index (1, 0, 2).

The let case first gets the denotation of rhs in env, which is a named tensor rhsNamed. Then it constructs an unnamed tensor rhsUnnamed from rhsNamed by converting an unnamed index idx′ to a named index with NIndex.fromUnnamed. Finally, it evaluates body in env extended with rhsUnnamed.

The var case first invokes lookupUnnamed to retrieve the value stored for v in env, which is an unnamed tensor. Then it converts the given named index idx to unnamed with NIndex.toUnnamed. Finally, it passes the unnamed index to the unnamed tensor.

The expand case uses ↓ᵢ to remove from the named index idx the dimensions that are not in t₁’s shape, then gets the denotation of t₁.

Finally, the einsum case performs summation using a helper function sum, which has the following type:

def sum {S : Type} [Semiring S]
    (xs : Is) (f : NIndex xs → S) : S

Given a named shape xs, it enumerates all possible indices of xs and passes them to f, a function that takes a named index of xs and returns a value. Then it sums up all values returned by f together.

In denote, the first argument to sum is the named shape returned by a function ∨, which removes zs from ⋃ xss, the union of all input shapes. The second argument to sum is a function that computes the product of all input tensors, using the helper function denotes, whose type is below:

def denotes {S : Type} [Semiring S]
    {Γ : Context} {xss : List Is} {ys : Is}
    (ts : TExp Γ (⋃ xss) Γ ys)
    (xssCompat : IssCompat xss)
    (h : ⋃ xssCompat ⊆ ys)
    (env : Env (S := S) Γ) (idx : NIndex ys) : S

The function denotes takes a sequence of tensor expressions ts of named shapes xss, a named index idx of shape ys, and a proof that the union of xss is a subset of ys. When doing recursion on ts, we keep the invariant that the union of xss is a subset of ys. For each tensor in the sequence, it gets the denotation of the tensor at the subset of idx that matches the tensor’s shape. It multiplies the denotations of all tensors together.

On the last line of Figure 4, the index that denote passes to denotes is the union (written ⋃i\bigcup_i) of idx (whose shape is zs) and idx′ (whose shape is ⋃\bigcup xss ∖\setminus zs). Note that these two shapes are disjoint (written ⊥\perp), meaning they share no index variable name. Hence they are compatible, and that is why it makes sense to take the union of the two shapes and of the two indices. Since the shape zs ∪\cup (⋃\bigcup xss ∖\setminus zs) is equivalent to the shape ⋃\bigcup xss, we can convert idx ∪i\cup_i idx′ from the former shape to the latter. With the proper indices, denotes can find values in each input tensor and complete the multiplication.

Translating from Unnamed to Named

The unnamed tensor language models what tensor libraries implement, but the named tensor language is what we mechanize. It is thus reasonable to ask, as with all language mechanizations, whether our TExpr type faithfully captures the expressivity, complexity, and interaction of tensor operations. To address this question, we translate the unnamed language to the named language. Our translation takes an unnamed tensor expression EE, say of shape (s1,…,sr)(s_1,\ldots,s_r), and also takes a sequence of distinct names x1,…,xrx_1,\ldots,x_r. It produces a named tensor expression tt, of shape dims =x1(s1)⋯xr(sr)=x_1^{(s_1)}\cdots x_r^{(s_r)}, such that for any environment γ\gamma and index II we have

⟦E⟧γ[I]=denote⁡ t env⁡ idx⁡(30)\llbracket E\rrbracket_\gamma[I] = \operatorname{denote}\ t\ \operatorname{env}\ \operatorname{idx} \tag*{(30)}

where env consists of the unnamed tensors in γ\gamma stored in de Bruijn style, and idx = NIndex.fromUnnamed dims neq II, where neq is the proof of Unique dims.

Consider how the translation should work on the expression E=einsum⁡(Mij,Mkj→ik)E=\operatorname{einsum}(M_{ij},M_{kj}\to ik) from Section 1. Say that MM has shape (2,3)(2,3), so EE has shape (2,2)(2,2), and the given sequence of distinct names (that is, the domain of idx in (30)) is ["x","w"]. We will translate EE to a TExpr of the form

einsum (cons (var [("x",2), ("y",3)] _ _)
  (cons (var [("w",2), ("y",3)] _ _) nil)) _ _

in which the var subexpressions are produced by recursively translating the tensor variable expression MM at two different sequences of distinct names, ["x","y"] and ["w","y"]. Producing this result requires mapping from ii to "x", from kk to "w", as well as from the summed-over jj to a fresh name "y". Thus, the translation operates on name maps using the helpers create_dict to create mappings, freshen to extend mappings, and rename to apply mappings. In particular,

create_dict⁡(ik,["x","w"])=σ(31)\operatorname{create\_dict}(ik, [\text{"x"},\text{"w"}])=\sigma \tag*{(31)}
freshen⁡(ijk,σ)=σ′(32)\operatorname{freshen}(ijk,\sigma)=\sigma' \tag*{(32)}
rename⁡(ij,σ′)=["x","y"](33)\operatorname{rename}(ij,\sigma')=[\text{"x"},\text{"y"}] \tag*{(33)}

where we abbreviate the name maps

σ={i↦"x",k↦"w"}(34)\sigma=\{i\mapsto\text{"x"},k\mapsto\text{"w"}\} \tag*{(34)}
σ′={i↦"x",k↦"w",j↦"y"}.(35)\sigma'=\{i\mapsto\text{"x"},k\mapsto\text{"w"},j\mapsto\text{"y"}\}. \tag*{(35)}

"y" is a fresh name, and we omit the sizes and uniqueness proofs of dimensions. Fresh names also need to be generated at the top level and for the rhs of each let expression, so we introduce one more helper gendim, which can generate fresh names like ["x",2], ("w",2)] from a shape (2,2)(2,2).

Figure 5 defines the translation more formally. See Appendix A for the definitions of the helper functions shape, gendim, create_dict, freshen, and rename.

The translator from the unnamed tensor language to the named tensor languageVector (PDF)
trans(E) = (dims, comp_T(E, dims))
where dims = gendim(shape_r(E))

comp_T(α, []) = scalar α
comp_T(0^(s_...), dims) = zero (fromList dims _)
comp_T(n · E, dims) = scale n comp_T(E, dims)
comp_T(E₁ + E₂, dims) =
  add comp_T(E₁, dims) comp_T(E₂, dims)
comp_T(let t = E′ in E, dims) =
  let d′ _ comp_T(E′, d′) comp_T_{t,d′}.map Prod.snd(E, dims)
  where d′ = gendim(shape_r(E′))
comp_T(t, dims) = var dims _ Γ(t)
comp_T(expand(E[⃗x] → ⃗z), dims) =
  expand comp_T(E, rename(⃗x, dict)) _
  where dict = create_dict(⃗z, dims)
comp_T(einsum(E₁[⃗x₁],..., → ⃗z), dims) =
  einsum [comp_T(E₁, rename(⃗x₁, dict)),...] _ _
  where dict = freshen(⃗x₁ ∪ ···, create_dict(⃗z, dims))

Figure 5. The translator from the unnamed tensor language to the named tensor language

The main function trans takes a tensor expression EE. It first generates a list dims of IVAr corresponding to EE's shape. Then it invokes comp to recursively translate EE. The expand and einsum cases use name maps to consistently replace the names in an index variable sequence with names in dims as described above. We omit the lengthy proofs of Unique and subset relations between Ises.

If we let tt in (30) be comp⁡T(E,dims⁡)\operatorname{comp}_T(E,\operatorname{dims}), then we can prove the equation by induction on EE.

Representing Shapes and Indices

In this section, we give the details of representations of named shapes. We first introduce the representation of named shapes and the operations on them in Section 5.1. Then we introduce the operations on named indices in Section 5.2. Finally we give the properties of these operations in Section 5.3. These properties are key to the proofs in Section 6.

Representing Named Shapes

The definition of Is.

As explained in § 3.2, an Is represents a finite map from index variable names to dimension sizes. It can be encoded in many ways, such as as a function or a data structure [13]. A proper encoding of Is should satisfy the following two requirements. First, we need an Is to have the behavior of a finite map: when we look up any index variable name, there should be only one possible dimension size. Second, since einsum needs to enumerate indices corresponding to those dimensions that occur in the input but not in the output, we should be able to enumerate all the dimensions from a given Is. Based on the two requirements, we define Is as a structure with two fields: an association list pairs of IVar and a proof noDup that index variable names in pairs have no duplicates:

structure Is where
  pairs : List IVar
  noDup : (pairs.map Prod.fst).Nodup

We also define the lookup operation of Is:

def lookupPairs (pairs : List IVar) (x : Id) :
  Option UpperBound :=
  (pairs.find? fun dim => dim.1 == x).map Prod.snd

def lookup (xs : Is) (x : Id) : Option UpperBound :=
  lookupPairs xs.pairs x

Based on lookup, we can define relations and operations on Is.

Equivalence, subset, compatibility, and disjointness.

Once we define lookup, we can define the equivalence, subset, and compatibility of two Ises:

def IsEq (xs ys : Is) : Prop :=
  ∀ i , lookup xs i = lookup ys i
notation xs " ≈ " ys => IsEq xs ys

def IsSubset (xs ys : Is) : Prop :=
  ∀ i , ∀ u , lookup xs i = some u →
    lookup ys i = some u
notation xs " ⊑ " ys => IsSubset xs ys

def IsCompat (xs ys : Is) : Prop :=
  ∀ i, (lookup xs i) ∼ᵢ (lookup ys i)
notation xs " ∼ " ys => IsCompat xs ys

We define the compatibility of Option UpperBound as follows. Two Option UpperBounds are compatible if they are the same or one of them is none:

inductive CompatVal : Option UpperBound →
  Option UpperBound → Prop where
  | nn : CompatVal none none
  | vv (v : UpperBound) : CompatVal (some v) (some v)
  | nv (v : UpperBound) : CompatVal none (some v)
  | vn (v : UpperBound) : CompatVal (some v) none
notation v₁ " ∼ᵢ " v₂ => CompatVal v₁ v₂

Two Ises are disjoint if no index variable name can be found in both of them:

def disjointIs (xs ys : Is) : Prop := (i : Id) →
  (lookup xs i = none) ∨ (lookup ys i = none)
notation xs " ⊥ " ys => disjointIs xs ys

It is easy to see that xs ∼ ys if xs ⊥ ys.

Union, intersection, and difference.

We can define the union ∪, intersection ∩, and difference \ of two Ises. Their type declarations are as follows:

def unionIs (xs ys : Is) (h : xs ∼ ys) : Is
def intersectIs (xs ys : Is) (h : xs ∼ ys) : Is
def minusIs (xs ys : Is) : Is

All three functions can be defined by recursion on xs.pairs, following the usual definitions of union, intersection, and difference. For ∪ and ∩, two Ises should be compatible to avoid the case where one index variable name is associated with two different sizes. For xs \ ys, we simply remove an IVar from xs if its index variable name is found in ys.

Union, intersection, and difference of dimension sizes.

We can also define the union, intersection, and difference of two Option UpperBounds. Their types follow the same pattern of the operations on Is: union and intersection require a proof that their arguments are compatible, while difference does not. The union of v₁ and v₂ is some v if either is some v, or none otherwise. The intersection is some v if both are some v, or none otherwise. The difference is none if v₂ is some v, or v₁ otherwise. We give their types and notations here. These operations make it possible to prove the distributivity of lookup, as can be seen in Theorem 5.4.

def unionVal (v₁ v₂ : Option UpperBound)
  (h : v₁ ∼ᵢ v₂) : Option UpperBound
notation v₁ " ⊔ᵤ " v₂ => unionVal v₁ v₂

def intersectVal (v₁ v₂ : Option UpperBound)
  (h : v₁ ∼ᵢ v₂) : Option UpperBound
notation v₁ " ⊓ᵤ " v₂ => intersectVal v₁ v₂

def minusVal (v₁ v₂ : Option UpperBound) :
  Option UpperBound
notation v₁ " \ᵤ " v₂ => minusVal v₁ v₂

Representing Named Indices

Equivalence of named indices.

As introduced in § 4.2, named indices are represented as a structure with a function field. Two named indices are equivalent if they are equal pointwise:

def NIndex.Compat {xs : Is} (idx₁ idx₂ : NIndex xs) :
  Prop := ∀ {x : Id} {v : UpperBound}
    (hx : lookup xs x = some v),
idx1.get hx = idx2.get hx
notation idx1 " ≈ᵢ " idx2 => NIndex.Compat idx1 idx2

Conversion between named indices

Given xs, ys : Is and idx : NIndex xs, if xs ≈ ys, we can convert idx to an NIndex ys:

def NIndex.eq_cast {xs ys : Is} (idx : NIndex xs)
  (xs_ys : xs ≈ ys) : NIndex ys
notation idx " →ᵢ " xy => NIndex.eq_cast idx xy

If ys ⊑ xs, we can also convert idx to an NIndex ys by removing all dimensions that occur in xs but not in ys:

def NIndex.subst_cast {xs ys : Is} (idx : NIndex xs)
  (ys_xs : ys ⊑ xs) : NIndex ys
notation idx " ↓ᵢ " yx => NIndex.subst_cast idx yx

Conversion between named and unnamed indices

In Section 4.2, we already know that UIndex is a sequence of natural numbers in terms of an unnamed shape dims. Given the order of dimensions, we can convert between named and unnamed indices:

def NIndex.fromUnnamed
  (xs : List Dim) (neq : Unique xs)
  UIndex (xs.map Prod.snd) :
  NIndex (fromList xs neq)
def NIndex.toUnnamed
  (xs : List Dim) (neq : Unique xs)
  NIndex (fromList xs neq) :
  UIndex (xs.map Prod.snd)

These two functions can be defined by recursion on xs.

Properties of Named Shapes and Indices

It is easy to see that named shapes have the following properties by the definitions of ≈\approx, ⊑\sqsubseteq, and ∼\sim:

Theorem 5.1. The equivalence relation ≈\approx of two named shapes is reflexive, symmetric, and transitive.

Theorem 5.2. The subset relation ⊑\sqsubseteq of two named shapes is reflexive and transitive.

Theorem 5.3. The compatibility relation ∼\sim of two named shapes is reflexive and symmetric.

We can also prove that looking up in the results of ∪\cup, ∩\cap, and \\backslash can be obtained by combining the results of looking up in the operands of ∪\cup, ∩\cap, and \\backslash:

Theorem 5.4. The operation lookup distributes over union, intersection, and difference of named shapes.

lookup⁡(xs∪ys) x=lookup⁡ xs x∪ulookup⁡ ys x(36)\operatorname{lookup}(xs \cup ys)\ x = \operatorname{lookup}\ xs\ x \cup_{\mathrm{u}} \operatorname{lookup}\ ys\ x \tag*{(36)}
lookup⁡(xs∩ys) x=lookup⁡ xs x∩ulookup⁡ ys x(37)\operatorname{lookup}(xs \cap ys)\ x = \operatorname{lookup}\ xs\ x \cap_{\mathrm{u}} \operatorname{lookup}\ ys\ x \tag*{(37)}
lookup⁡(xs\ys) x=lookup⁡ xs x\ulookup⁡ ys x(38)\operatorname{lookup}(xs \backslash ys)\ x = \operatorname{lookup}\ xs\ x \backslash_{\mathrm{u}} \operatorname{lookup}\ ys\ x \tag*{(38)}

This theorem can be proved by induction on xs.pairs. It is key to proving Theorem 6.2 without explicitly defining permutation of index variable sequences.

An important property of named indices is their equality:

Theorem 5.5. Given a named shape xs and two indices idx₁, idx₂ of xs, idx₁ = idx₂ if idx₁ ≈ᵢ idx₂.

To prove this property, we use the functional definitions of idx₁, idx₂ and function extensionality. With this property, when we pass a tensor of shape xs and two equivalent indices of xs to denote respectively, we can rewrite one index to the other and thus prove that the two sides are equal to each other:

theorem denote_congr {S : Type} [Semiring S]
  {Γ : Context} {xs : Is}
  (t : TExpr Γ xs) (env : Env (S := S) Γ)
  (idx₁ idx₂ : NIndex xs) (h : idx₁ ≈ᵢ idx₂) :
  denote t env idx₁ = denote t env idx₂

Optimization by Rewriting

Having defined the named tensor language and proved the properties of named shapes and indices, we can finally prove some rewriting rules of expand and einsum correct. In Sections 6.1 and 6.2, we present the informal statements of our theorems and sketch their mechanized proofs. We discuss some details about the mechanized proofs in Section 6.3.

Thanks to the fact that all shapes are named and satisfy the necessary equivalence, subset, or compatibility relations, these theorems can be stated and proven mostly using set-theoretical properties of the operations of named shapes. There is no need to rename or explicitly permute dimensions.

The Fusion of expand

Theorem 6.1. Two expands can be merged into one:

⟦expand⁡(E[x⃗]→x⃗y⃗)[x⃗y⃗]→x⃗y⃗z⃗⟧γ[I]=⟦expand⁡(E[x⃗]→x⃗y⃗z⃗)⟧γ[I](39)\llbracket\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y})[\vec{x}\vec{y}] \to\vec{x}\vec{y}\vec{z} \rrbracket_{\gamma[I]} = \llbracket\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y}\vec{z}) \rrbracket_{\gamma[I]} \tag*{(39)}

Named tensors help us avoid the bookkeeping of renaming and permutation in the statement and proof of this theorem. The informal statement (39) contains the operand

expand⁡(E[x⃗]→x⃗y⃗)[x⃗y⃗],\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y})[\vec{x}\vec{y}],

but unnamed tensors would call for the more general

expand⁡(E[x⃗]→x⃗y⃗)[u⃗v⃗],\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y})[\vec{u}\vec{v}],

where x⃗\vec{x} and y⃗\vec{y} are renamed to u⃗\vec{u} and v⃗\vec{v} respectively. To prove the theorem in the unnamed language, we would need to do the bookkeeping of renaming. In the named version, since names are intrinsic to shapes and we define an equivalence relation between named shapes, we do not need to worry about dimension renaming.

Similarly, the output shape x⃗y⃗z⃗\vec{x}\vec{y}\vec{z} in (39) is chosen as a representative, but the actual output shape can be y⃗x⃗z⃗\vec{y}\vec{x}\vec{z}, z⃗x⃗y⃗\vec{z}\vec{x}\vec{y}, or any other permutation of x⃗y⃗z⃗\vec{x}\vec{y}\vec{z}. Since the shape of an unnamed tensor is an ordered list of numbers, we have to encode permutation if we want to prove the theorem about unnamed tensors. In the named version, since shapes are finite maps from names to dimension sizes, we can avoid permutation.

Proof sketch. Following the denotational semantics, the equation reduces to the form

⟦E⟧γ[...]=⟦E⟧γ[...]\llbracket E\rrbracket_{\gamma}[...] = \llbracket E\rrbracket_{\gamma}[...]

For the left hand side, we first convert II from a named index of x⃗y⃗z⃗\vec{x}\vec{y}\vec{z} to x⃗y⃗\vec{x}\vec{y}, then to x⃗\vec{x}. For the right hand side, we convert II directly from x⃗y⃗z⃗\vec{x}\vec{y}\vec{z} to x⃗\vec{x}. Both conversions remove the same dimensions from II, so they leave the same dimensions in II. Therefore, both sides have the same index. Since EE, γ\gamma, and named indices are the same, the two sides are equal. □

The mechanized theorem statement adds the necessary side conditions.

theorem expand_fuse {S : Type} [Semiring S]
  {Γ : Context} {xs ys zs : Is}
  (t : TExpr Γ xs) (xy : xs ⊑ ys) (yz : ys ⊑ zs)
  (env : Env (S := S) Γ) (idx : NIndex zs) :
  denote (.expand (.expand t xy) yz) env idx =
  denote (.expand t (IsSubset_trans xy yz)) env idx

Since the subset relation between input and output shapes of expand is guaranteed by the well-formedness of named tensor expressions, we can specify the output shape of expand directly rather than using the juxtaposition x⃗y⃗\vec{x}\vec{y}. We do not need to worry about the dimension renaming allowed by the unnamed tensor language when nesting expressions, such as expand(expand(E[ $\vec{x}$] → $\vec{x}\vec{y}$) [$\vec{x}\vec{y}'$] → $\vec{x}\vec{y}\vec{z}$), where ∣y⃗∣=∣y⃗′∣|\vec{y}| = |\vec{y}'|. In a sense, the translator in § 4.3 consistently renames the index variables ahead of time.

The Commutativity of expand and einsum

Theorem 6.2. The operations einsum and expand commute up to a factor:

⟦einsum⁡(expand⁡(E[x⃗]→x⃗y⃗)[x⃗y⃗],F[z⃗]→w⃗)⟧γ[I]=⟦expand⁡(f⋅einsum⁡(E[x⃗],F[z⃗]→u⃗))[u⃗]→w⃗)⟧γ[I](40)\llbracket\operatorname{einsum}(\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y})[\vec{x}\vec{y}], F[\vec{z}] \to\vec{w})\rrbracket_{\gamma}[I] = \llbracket\operatorname{expand}(f \cdot\operatorname{einsum}(E[\vec{x}], F[\vec{z}] \to\vec{u}))[\vec{u}] \to\vec{w})\rrbracket_{\gamma}[I] \tag*{(40)}

where

u⃗=w⃗∖(y⃗∖z⃗),v⃗=(y⃗∖z⃗)∖w⃗,f=∏i∈v⃗∣i∣.(41)\vec{u} = \vec{w} \setminus(\vec{y} \setminus\vec{z}), \qquad\vec{v} = (\vec{y} \setminus\vec{z}) \setminus\vec{w}, \qquad f = \prod_{i \in\vec{v}} |i|. \tag*{(41)}

As with Theorem 6.1, names intrinsic to tensors help us state and prove this theorem without renaming and permutation bookkeeping. When einsum and expand meet in the unnamed tensor language, the two occurrences of x⃗y⃗\vec{x}\vec{y} in (40) may not match, nor the two occurrences of u⃗\vec{u}. Also, the concatenation x⃗y⃗\vec{x}\vec{y} may be permuted. To prove the more general theorem in the unnamed language, we would need to interleave bookkeeping with reasoning about sums and products. In contrast, our named shapes can be thought of as unordered sets; we visualize them as such in Appendix § 11.

Proof sketch. The denotation on the left hand side of (40) is a summation over indices of shape (x⃗y⃗∪z⃗)∖w⃗(\vec{x}\vec{y} \cup\vec{z}) \setminus\vec{w}. This shape turns out to be the disjoint union of § 5.1 of two shapes: v⃗\vec{v} consists of the dimensions that are not used to index any input tensor, and (x⃗∪z⃗)∖u⃗(\vec{x} \cup\vec{z}) \setminus\vec{u} consists of the dimensions that are used to index some input tensors. The main argument, then, is to split the summation into two nested summations. One of them ranges over indices of shape v⃗\vec{v}, and reduces to the constant factor ff because v⃗\vec{v} is unused.

Specifically, using the conditions x⃗⊥y⃗\vec{x} \perp\vec{y} and w⃗⊆x⃗y⃗∪z⃗\vec{w} \subseteq\vec{x}\vec{y} \cup\vec{z}, the two sides of (40) separately reduce to

∑δ′∈efuns⁡(v⃗)∑δ∈efuns⁡((x⃗z⃗)∖u⃗)⟦E⟧γ[(δ′∪δ∪{w⃗↦I})(x⃗)]⋅⟦F⟧γ[(δ′∪δ∪{w⃗↦I})(z⃗)]=(∏i∈v⃗∣i∣)⋅∑δ∈efuns⁡((x⃗z⃗)∖u⃗)⟦E⟧γ[(δ∪{w⃗↦I})(x⃗)]⋅⟦F⟧γ[(δ∪{w⃗↦I})(z⃗)].(42)\begin{aligned} \sum_{\delta' \in\operatorname{efuns}(\vec{v})} \sum_{\delta\in\operatorname{efuns}((\vec{x}\vec{z})\setminus\vec{u})} \llbracket E\rrbracket_{\gamma}[(\delta' \cup\delta\cup\{\vec{w} \mapsto I\})(\vec{x})] \cdot \llbracket F\rrbracket_{\gamma}[(\delta' \cup\delta\cup\{\vec{w} \mapsto I\})(\vec{z})] \\ &= \left(\prod_{i \in\vec{v}} |i|\right) \cdot \sum_{\delta\in\operatorname{efuns}((\vec{x}\vec{z})\setminus\vec{u})} \llbracket E\rrbracket_{\gamma}[(\delta\cup\{\vec{w} \mapsto I\})(\vec{x})] \cdot \llbracket F\rrbracket_{\gamma}[(\delta\cup\{\vec{w} \mapsto I\})(\vec{z})]. \tag*{(42)} \end{aligned}

Since v⃗\vec{v} doesn’t contain dimensions from x⃗\vec{x} or z⃗\vec{z}, we know v⃗\vec{v} is not used to index the denotations of EE and FF. Thus, the named index δ′\delta', whose domain is v⃗\vec{v}, is not used in the first summation in (42). Therefore, that summation reduces to the constant factor ∏i∈v⃗∣i∣\prod_{i\in\vec{v}} |i| on the right hand side. □

The mechanized version of Theorem 6.2 follows the informal statement and proof above. Since it requires a lot of side conditions, we use a helper function EinsumExpandCommEq to produce the desired equation between two denotations.

theorem einsum_expand_comm_two
  {S : Type} [Semiring S]
  {Γ : Context} {xs ys zs ws : Is}
  (t₁ : TExpr Γ xs) (t₂ : TExpr Γ zs)
  (xy : xs ⊥ ys)
  (xyz : unionIs xs ys (disjointIs_compat xy) ~ zs)
  (w_xys : ws ⊑ ⋃ (IsCompat_two xyz))
  (env : Env (S := S) Γ) (idx : NIndex ws) :
  EinsumExpandCommEq t₁ t₂ xy xyz w_xys env idx

Corollary 6.3. Summation-free einsum and expand commute:

⟦einsum⁡(expand⁡(E[x⃗]→x⃗y⃗)[x⃗y⃗],F[z⃗]→x⃗∪z⃗)⟧γ=⟦expand⁡(einsum⁡(E[x⃗],F[z⃗]→x⃗∪z⃗))[x⃗∪z⃗]→x⃗∪y⃗z⃗)⟧γ(43)\llbracket\operatorname{einsum}(\operatorname{expand}(E[\vec{x}] \to\vec{x}\vec{y})[\vec{x}\vec{y}], F[\vec{z}] \to\vec{x}\cup\vec{z})\rrbracket_{\gamma} = \llbracket\operatorname{expand}(\operatorname{einsum}(E[\vec{x}], F[\vec{z}] \to\vec{x}\cup\vec{z}))[\vec{x}\cup\vec{z}] \to\vec{x}\cup\vec{y}\vec{z})\rrbracket_{\gamma} \tag*{(43)}

Proof sketch. Since the einsum expression is summation-free, w⃗≈(x⃗y⃗∪z⃗)\vec{w} \approx(\vec{x}\vec{y}\cup\vec{z}). Therefore, v⃗=(y⃗∖z⃗)∖w⃗=y⃗∖(z⃗∪w⃗)=y⃗∖(z⃗∪x⃗y⃗)=(),\vec{v} = (\vec{y}\setminus\vec{z})\setminus\vec{w} = \vec{y}\setminus(\vec{z}\cup\vec{w}) = \vec{y}\setminus(\vec{z}\cup\vec{x}\vec{y}) = (), and f=1f = 1. By Theorem 6.2, the two sides are equal. □

Notes on the Mechanization

We mechanized the proofs in Lean 4.27.0 and Agda 2.7.0.1. For Lean, we used Mathlib’s Semiring infrastructure. For Agda, we used N\mathbb{N} as the scalar value type. The Lean proof uses helper theorems provided by Mathlib about summation; we have not proven Theorem 6.2 in Agda. Both versions follow the same design as described above. We took advantage of Agda’s customized syntax and hole system to explore the design of the tensor language. Then we ported the proof to Lean and generalized it to an arbitrary semiring. We also used Codex to search for related theorems from Mathlib.

Despite the fact that Codex can give proofs of lemmas, it often generated dense proofs that did not take advantage of lemmas we have proven. For Agda, it tended to generate large equational reasoning expressions that used a lot of transitivity and symmetry without extracting intermediate steps. Occasionally it did generate very concise proofs. When we split the proof into multiple steps, the proofs it generated became more readable.

Related Work

Both einsum and tensor description languages have a large number of implementations and applications. We discuss the implementation, optimization, and formalization of einsum. We also briefly introduce the work on named tensor notation, and on verifying tensor description languages.

Implementation and Optimization of einsum

Different forms of einsum have been implemented in various languages and libraries. Matrix multiplication, arguably the most common case of einsum, is fundamental to scientific computing [7] and thus has been implemented in many tensor libraries, including the well-known NumPy [17], PyTorch [2], and TensorFlow [24]. Because matrix multiplication is so fundamental, these libraries also optimize its performance targeting specific hardware or even specific matrix sizes [18, 19]. We refer readers to Golub and Loan [15] for a more detailed introduction to this topic.

For the general form of einsum, many languages have their own implementations [1, 6, 26, 30]. There are also implementations that focus more on the algebraic properties of tensors [5, 28]. It is well-known that finding the most efficient way (contraction path) of computing einsum is NP-hard [20]. Therefore, many libraries for optimizing the performance of einsum are implemented [4, 8, 11, 14, 31]. In the context of quantum computing, einsum is often expressed as tensor network contraction. There are also a lot of efforts to optimize the performance of tensor network contraction [12, 16].

Formalization of einsum

Even though einsum has been used by physicists for over a century and adopted by the machine learning community for over a decade, its formalization is pretty recent work.

Wenig et al. [29] give a clear semantics for einsum. Their formalization, unlike ours, allows repeated index names for both inputs and outputs. However, they don’t consider the interaction between einsum and other tensor operations or provide a mechanized proof.

Mahathevan et al. [23] use einsum expressions for fuzzing sparse tensor compilers, but they don’t consider the formalization of einsum per se.

Tooby-Smith [28] formalizes the tensor notation used in physics, where the Lean syntax is used to represent index names. But their formalization does not consider the form of einsum based on multi-dimensional arrays. They also provide no rewriting rules for einsum.

Named Tensor Notation

It is not new to name dimensions of tensors. For example, the definition of einsum inherently requires names for tensor dimensions. In tensor network libraries like Quimb [16], tensors can be constructed with dimension names. As discussed by Chiang et al. [10], several tensor libraries have implemented this notation. Chiang et al. [10] formalize the idea with semantics and working examples, but their concern is not mechanization.

The mechanization of Tooby-Smith [28] does support named dimensions. But tensor contraction is done by pairing dimensions. Only a pair of dimensions can be contracted at one time. If we want to express einsum that sums over multiple dimensions, we have to manually choose the contraction order and write einsum as a nested sequence of contractions.

Verification of Tensor Languages

As discussed above, based on what “tensor” means, the formalization of einsum can also have different meanings. Therefore, the formalization of einsum always follows a formalization of a tensor description language, which has a much richer literature [3, 21, 22, 25, 27, 28]. It is possible to translate einsum into these formalized tensor languages by composing the operations in them. There are two reasons why we do not formalize einsum this way. First, most mechanized tensor languages use unnamed tensor notation, which means we still need to find a way to guarantee the correctness of naming dimensions. Second, translating einsum into existing operations makes it less obvious to find the rewriting rules.

Conclusion

We mechanize a tensor language that supports einsum and expand with named tensor notation. We give the syntax and the denotational semantics of the unnamed version of the language on paper and the named version mechanized in a proof assistant. We provide a translation from the unnamed tensor language to the named tensor language. We prove that the translation preserves the semantics of the unnamed language. We discuss the techniques required to support named tensors and how they are used to mechanize einsum. We prove the rewriting rules about einsum and expand that can improve the efficiency of einsum calculation.

References

Translation Helper Functions

shape

The shape of an unnamed tensor is returned by shapeshape, which takes a context Γ\Gamma and an unnamed tensor expression EE. It returns a list of upper bounds. The definition is shown below.

shapeΓ(α)=()shape_{\Gamma}(\alpha) = ()
shapeΓ(0(s,…))=(s,…)shape_{\Gamma}(0^{(s,\ldots)}) = (s,\ldots)
shapeΓ(n⋅E)=shapeΓ(E)shape_{\Gamma}(n \cdot E) = shape_{\Gamma}(E)
shapeΓ(E1+E2)=shapeΓ(E1)shape_{\Gamma}(E_{1} + E_{2}) = shape_{\Gamma}(E_{1})
shapeΓ(let⁡t=E1in⁡E2)=shapeΓ;t,shapeΓ(E1)(E2)shape_{\Gamma}(\operatorname{let} t = E_{1}\operatorname{ in} E_{2}) = shape_{\Gamma;t,shape_{\Gamma}(E_{1})}(E_{2})
shapeΓ(t)=Γ(t)shape_{\Gamma}(t) = \Gamma(t)
shapeΓ(expand⁡(E[x⃗]→z⃗))=∣z⃗∣shape_{\Gamma}(\operatorname{expand}(E[\vec{x}] \to\vec{z})) = |\vec{z}|
shapeΓ(einsum⁡(E1[x⃗1],…,Ek[x⃗k]→z⃗))=∣z⃗∣shape_{\Gamma}(\operatorname{einsum}(E_{1}[\vec{x}_{1}],\ldots,E_{k}[\vec{x}_{k}] \to\vec{z})) = |\vec{z}|

gendim

To generate an IVar list dd and a proof nn that names in dd have no duplicates, we invoke gendimgendim. It takes a list of upper bounds and returns a pair consisting of an IVar list and a no-duplicate proof. Here, we rely on a function gensymgensym to generate a fresh name and a proof that the name doesn’t occur in dd.

gendim(())=[]gendim(()) = []
gendim(s:s∗)=(x′,s):gendim(s∗)gendim(s : s^{*}) = (x',s) : gendim(s^{*})

where x′x' is a fresh name

create_dict

We represent a name map as an association list. To construct a name map, create_dictcreate\_dict takes an index variable sequence x⃗\vec{x} and a corresponding IVar list dd. It zips the names of x⃗\vec{x} and dd to get a map from names in the former to the latter. Here, we use x⃗.vars\vec{x}.vars to represent the list of names in x⃗\vec{x}. The definition of create_dictcreate\_dict is shown below.

create_dict(x⃗,d)=zip(x⃗.vars,d.map Prod.fst⁡)create\_dict(\vec{x},d) = zip(\vec{x}.vars,d.map\ \operatorname{Prod.fst})

freshen

The function freshenfreshen takes an index variable sequence and a name map. It returns a name map.

freshen((),dict)=dictfreshen((),dict) = dict
freshen(x(s)x⃗,dict)∣x∈dict=freshen(x⃗,dict)freshen(x^{(s)}\vec{x},dict) \mid x \in dict = freshen(\vec{x},dict)
freshen(x(s)x⃗,dict)∣x∉dict=freshen(x⃗,dict.insert((x,x′)))freshen(x^{(s)}\vec{x},dict) \mid x \notin dict = freshen(\vec{x},dict.insert((x,x')))

where x′x' is a fresh name

rename

The function renamerename takes an index variable sequence x⃗\vec{x} and a name map dictdict. It returns an IVar list. Since it is guaranteed that every name in x⃗\vec{x} occurs in dictdict, renamerename simply looks up the name and replaces it with the associated name.

rename((),dict)=[]rename((),dict) = []
rename(x(s)x⃗,dict)=(dict(x),s):rename(x⃗,dict)rename(x^{(s)}\vec{x},dict) = (dict(x),s) : rename(\vec{x},dict)

Visualizing Named Shapes in thm:einsum-expand

The reader may find the picture below useful for tracking named shapes and their relations in Theorem 6.2.

Visualizing named shapes and their relations

Figure 1 (PDF p. 14).

References

  1. [1]Constantin Ahlmann-Eltze and Koki Tsuyuzaki. 2026. Einstein Summation. https://cran.r-project.org/web/packages/einsum/index.html
  2. [2]Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burkovski, Geeta Chauhan, Anjali Choudia, Will Constable, Alban Desmaison, Zachary DeVito, Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, CK Luk, Bert Maher, Yunjie Pan, Christian Puh́rsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang, Xiaodong Wang, William Wen, Shunting Zhang, Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala. 2024. PyTorch 2: Fast Machine Learning through Dynamic Python Bytecode Transformation and Graph Compilation. In 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’24). ACM. doi:10.1145/3620665.3640366DOI
  3. [3]Jai Arora, Sirui Lu, Devansh Jain, Tianfan Xu, Farzin Houshmand, Phitchaya Mangpo Phothilimthana, Mohsen Lesani, Praveen Narayanan, Karthik Srinivasa Murthy, Rastislav Bodik, Amit Sabne, and Charith Mendis. 2025. TensorRight: Automated Verification of Tensor Graph Rewrites. Artifact for “TensorRight: Automated Verification of Tensor Graph Rewrites” 9, POPL (Jan. 2025), 29:832–29:863. doi:10.1145/3704865DOI
  4. [4]Harun Bayraktar, Ali Charrara, David Clark, Saul Cohen, Timothy Costa, Yao-Lung L. Fang, Yang Gao, Jack Guan, John Gunnells, Azzam Haidar, Andreas Hehn, Markus Hohnerbach, Matthew Jones, Tom Lubowe, Dmitry Lyakh, Shinya Morino, Paul Springer, Sam Stanwyck, Igor Terentyev, Satya Varadhan, Jonathan Wong, and Takuma Yamaguchi. 2023. cuQuantum SDK: A High-Performance Library for Accelerating Quantum Science. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, Bellevue, WA, USA, 1050–1061. doi:10.1109/QCE57702.2023.00119
  5. [5]Jean-Philippe Bernardy and Patrik Jansson. 2025. Domain-Specific Tensor Languages. Journal of Functional Programming 35 (2025), e9. doi:10.1017/S0956796825000048DOI
  6. [6]Mark Blacher, Julien Klaus, Christoph Staudt, Sören Laue, Viktor Leis, and Joachim Giesen. 2023. Efficient and Portable Einstein Summation in SQL. Proceedings of the ACM on Management of Data 1, 2 (June 2023), 121:1–121:19. doi:10.1145/3589266DOI
  7. [7]L. Susan Blackford, James Demmel, Dongarra Dongarra, Duff Duff, Sven Hammarling, Greg Henry, Michael Heroux, Linda Kaufman, Andrew Lumsdaine, Antoine Petitet, Roldan Pozo, Karin Remington, and R. Clint Whaley. 2002. An Updated Set of Basic Linear Algebra Subprograms (BLAS). ACM Transactions on Mathematical Software (TOMS) 28, 2 (June 2002), 135–151. doi:10.1145/567806.567807
  8. [8]Alexander Breuer, Mark Blacher, Max Engel, Joachim Giesen, Alexander Heinecke, Julien Klaus, and Stefan Remke. 2025. Einsum Trees: An Abstraction for Optimizing the Execution of Tensor Expressions. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 275–292. doi:10.1145/3676641.3716254DOI
  9. [9]David Chang, David Riley, Grant Exley, Kenneth Sible, Yafei Yang, and Chung-chieh Shan. 2024. Factor Graph Grammars in Python. https://github.com/diprispm/fgs
  10. [10]Dingyong Chiang, Alexander M Rush, and Boaz Barak. 2023. Named Tensor Notation. Transactions on Machine Learning Research (2023). https://openreview.net/forum?id=hVT7Shlix
  11. [11]Brian DuSell. 2026. Semiring Einsum. https://github.com/bdusell/semiring-einsum
  12. [12]E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, Jonathan Romero, and Alán Aspuru-Guzik. 2018. QTorch: The Quantum Tensor Contraction Handler. PLOS ONE 13, 12 (Dec. 2018), e0208510. doi:10.1371/journal.pone.0208510DOI
  13. [13]Daniel P. Friedman and Mitchell Wand. 2008. Essentials of Programming Languages (3rd ed.). MIT Press, Cambridge, MA.
  14. [14]Daniel G. A. Smith and Johnnie Gray. 2018. Opt_einsum - A Python Package for Optimizing Contraction Order in Einsum-like Expressions. Journal of Open Source Software 3, 26 (June 2018), 753. doi:10.21105/joss.00753DOI
  15. [15]Gene H. Golub and Charles F. Van Loan. 2013. Matrix Computations (4th ed.). Johns Hopkins University Press. doi:10.56021/9781421407944DOI
  16. [16]Johnnie Gray. 2018. Quimb: A Python Package for Quantum Information and Many-Body Calculations. Journal of Open Source Software 3, 29 (Sept. 2018), 819. doi:10.21105/joss.00819DOI
  17. [17]Charles R. Harris, K. Jarrod Millman, Stefan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020. Array Programming with NumPy. Nature 585, 7825 (Sept. 2020), 357–362. doi:10.1038/s41586-020-2649-2DOI
  18. [18]Chetan Jhurani and Paul Mullowney. 2013. A GEMM Interface and Implementation on NVIDIA GPUs for Multiple Small Matrices. arXiv:1304.7053. doi:10.48550/arXiv.1304.7053arxiv.org/abs/1304.7053
  19. [19]Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler. Proceedings of the ACM on Programming Languages 1, OOPSLA (Oct. 2017), 1–29. doi:10.1145/3133901DOI
  20. [20]Chi-Chung Lam, P. Sadayappan, and Rephael Wenger. 1997. On Optimizing a Class of Multi-Dimensional Loops with Reduction for Parallel Execution. Parallel Processing Letters 07, 02 (1997), 157–168. doi:10.1142/S0129626497000176DOI
  21. [21]Amanda Liu, Gilbert Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2024. A Verified Compiler for a Functional Tensor Language. Proceedings of the ACM on Programming Languages 8, PLDI (June 2024), 320–342. doi:10.1145/3656390DOI
  22. [22]Amanda Liu, Gilbert Louis Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2022. Verified Tensor-Program Optimization via High-Level Scheduling Rewrites. Proceedings of the ACM on Programming Languages 6, POPL (Jan. 2022), 55:1–55:28. doi:10.1145/3498717DOI
  23. [23]Kabilan Mahathevan, Yining Zhang, Muhammad Ali Gulzar, and Kirshanthan Sundararajah. 2026. TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report). CoRR abs/2603.18372 (2026). arXiv:2603.18372 doi:10.48550/ARXIV.2603.18372DOI
  24. [24]Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Végas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-scale Machine Learning on Heterogeneous Systems. https://www.tensorflow.org/arxiv.org/abs/1603.04467
  25. [25]Daniel Nezamabadi, Magnus O. Myreen, and Yong Kiam Tan. 2026. Verified VCG and Verified Compiler for Dafny. In Proceedings of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs. ACM, Rennes France, 171–186. doi:10.1145/3779031.3779092DOI
  26. [26]Le Niu. 2026. Hhlo. https://github.com/overshiki/hhlo
  27. [27]Artjoms Sinkarovs and Troels Henriksen. 2025. Correctness Meets Performance: From Agda to Futhark. Proc. ACM Program. Lang. 9, ICFP, Article 255 (Aug. 2025). doi:10.1145/3474752DOI
  28. [28]Joseph Tooby-Smith. 2024. Formalization of Physics Index Notation in Lean 4. arXiv:2411.07667 [cs.LO] doi:10.48550/arXiv.2411.07667
  29. [29]Maurice Wenig, Paul G. Rump, Mark Blacher, and Joachim Giesen. 2025. The Syntax and Semantics of Einsum. arXiv:2509.20020 [cs] doi:10.48550/arXiv.2509.20020DOI
  30. [30]Alex Williams. 2026. Einsum.Jl. https://github.com/ahwillia/Einsum.jl
  31. [31]Alexandros Nikolaos Ziogas, Grzegorz Kwasniewski, Tal Ben-Nun, Timo Schneider, and Torsten Hoefler. 2022. Einsum: Practically I/O Optimal Multi-Linear Algebra. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC ’22). IEEE Press, Dallas, Texas, 1–15. https://dl.acm.org/doi/10.5555/3571885.3571918DOI

Paper details

vlnc:W_2jwsw5ey
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents