Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs
Scott Kovach, Praneeth Kolichala, Tiancheng Gu, Fredrik Kjølstad
Abstract
We introduce indexed streams, a formal operational model and intermediate representation that describes the fused execution of a contraction language that encompasses both sparse tensor algebra and relational algebra. We prove that the indexed stream model is correct with respect to a functional semantics. We also develop a compiler for contraction expressions that uses indexed streams as an intermediate representation. The compiler is only 540 lines of code, but we show that its performance can match both the TACO compiler for sparse tensor algebra and the SQLite and DuckDB query processing libraries for relational algebra.
Topics & Concepts
CompilerComputer scienceProgramming languageIntermediate languageContraction (grammar)Tensor algebraRepresentation (politics)Tensor (intrinsic definition)Theoretical computer scienceAlgebra over a fieldAlgebra representationMathematicsPure mathematicsPoliticsMedicinePolitical scienceLawInternal medicineJordan algebraAdvanced Database Systems and QueriesDistributed systems and fault toleranceParallel Computing and Optimization Techniques