Functional collection programming with semi-ring dictionaries
summary
A new intermediate language implements semi-ring dictionaries and a statically typed DSL SDQL that represents sets, multisets, vectors, matrices and sparse tensors as key→value maps with semiring values. It unifies DB and linear-algebra optimizations (push aggregates, matrix chain ordering, CSR/CSC layouts), adds equality-saturation for sparse tensor compilation, AD rules and autotuning, and runs a handful of hybrid DB/LA benchmarks where SDQL is competitive with or outperforms Typer, Tectorwise, SciPy, taco, Trance, LMFAO and Morpheus.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:07Structured data role
- 3:34Database vs linear algebra
- 6:07Semi-ring dictionaries
- 8:59What is a semi-ring dictionary
- 11:11Semantics and programming
- 13:39Loop optimizations
- 15:27Recent developments
- 16:31Conclusion
- 16:53Q&A
related talks
05mRelational Programming
48mCompositional, Expressive, Performant Database Queries: Choose 3
09mA DSL for My NoSQL Database
21mA Typed Multi-Level Datalog IR and its Compiler Framework
36mOptimizing Relational Programs II
33mA (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation
01h 02mAlgebraic Structures in Logic and Query Evaluation 3
14mRhyme: A Multi-Paradigm Declarative Query Language