Modeling of languages for tensor manipulation

Numerical applications and, more recently, machine learning applications rely on high-dimensional data that is typically organized into multi-dimensional tensors. Many existing frameworks, libraries, and domain-specific languages support the development of efficient code for manipulating tensors and tensor expressions. However, such frameworks and languages that are used in practice often lack formal specifications. The present report formally defines a model language for expressing tensor operations. The model language is simple and yet general enough so that it captures the fundamental tensor operations common to most existing languages and frameworks. It is shown that the given formal semantics are sensible, in the sense that well-typed programs in the model language execute correctly, without error. Moreover, an alternative implementation of the model language is formally defined. The alternative implementation introduces padding into the storage of tensors, which may benefit performance on modern hardware platforms. Based on their formal definitions, the original implementation of the model language and the implementation with padding are proven equivalent. Finally, some possible extensions of the presented model language for tensor manipulation are discussed.