Can Tensor Programming Be Liberated from the Fortran Data Paradigm?

29Oct
16:00 29th October 2021 ( week 3, Michaelmas Term 2021 )
Zoom

Classic Fortran programs used “GO TO” for control and (multi-dimensional) arrays for data. While these unstructured building blocks are adequate for encoding implementations, they fail to yield clear understanding of the essential nature of algorithms and their correctness. Although “GO TO” has largely disappeared from modern programming, arrays are still widely embraced for parallel programming and machine learning. The resulting programming style suffers in safety and compositionality, leading to code that is unnecessarily difficult to write, read, prove, and reuse.

The main message of this talk is that “array algorithms” are often not naturally array algorithms at all, but rather an error-prone, composition-resistant enmeshing of a safe, simple, and illuminating algorithm on a natural (non-array) data type, together with details of decoding from and encoding to arrays. By disentangling these natural data types and corresponding algorithms from their array encodings, we can gain deeper understanding of known algorithms and easily discover correct new algorithms, many of which are well-suited for the modern age of parallel hardware. Where desired, these clear, correct, and compositional algorithms can then be safely, correctly, and systematically (even automatically) converted to operate on arrays by applying a few simple principles in the form of well-known type isomorphisms.

Speaker bio

Conal Elliott has been working in functional programming since 1980. He especially enjoys applying semantic elegance and rigor to library design and optimized implementation. He invented the paradigm now known as “functional reactive programming” in the early 1990s, and then pioneered compilation techniques for high-performance, high-level embedded domain-specific languages, with applications including 2D and 3D computer graphics. The latter work included the first compilation of Haskell programs to GPU code, while maintaining precise and simple denotation and powerful composability, as well as a high degree of optimization. Conal earned a BA in math with honors from the College of Creative Studies at UC Santa Barbara in 1982 and a PhD in Computer Science from Carnegie Mellon University in 1990. He previously worked as software architect at Sun Microsystems, graphics researcher at Microsoft Research, principal engineer at Tabula Inc (on chip specification and compiling Haskell to hardware for massively parallel execution), and distinguished data/AI scientist at Target. He has also coached couples and led conscious relationship workshops together with his partner Holly Croydon, with whom he now lives on 20 acres in the woods in the California Gold Country. Conal is currently focused on formally verified hardware design (working in Agda) and is open to well-suited employment and collaboration opportunities. For publications, CV, professional blog, etc, see http://conal.net.