Alex - A Paradigm for Expressing and Compiling Matrix Functions

Abstract

This work presents formal and practical tools to support the Alex paradigm for expressing and compiling matrix functions. Alex programs are recursive definitions over matrices with the same flavor as the elegant FP languages of Backus. Many useful matrix algorithms can be expressed in both FP and Alex without any explicit index arithmetic. While FP is very difficult to compile to fast numerical codes, we show that Alex functions admit compile-time analyses and code generation techniques with efficient results. In particular, we give a type system that expresses matrix sizes and shapes, a sound and complete inference algorithm for these types, and a code generation algorithm that is space-efficient--storage is allocated only for user function parameters and results. Finally, we give an algorithm that determines when it is safe to replace call by value array parameters in the compiled code with call by reference. A compiler using these techniques generates C code from Alex programs which is at least as fast as code one would write by hand for some small problems. We conclude with discussion of how the fundamental techniques given here relate to previous work and how they should be extended to a general functional language or incorporated as a feature of an existing one.