Implementing an Array Shape Inference System for MATLAB Using
Mathematica
Pramod G. Joisha, Prithviraj Banerjee
Abstract
In implicitly typed array-based languages such as MATLAB, APL and IDL,
advance determination of an array's shape empowers the execution of
efficient code. Static knowledge of an array's shape could sanction a
variety of code optimizations besides permitting compile-time
verification of shape correctness and serving as a debugging aid. This
report presents a symbolic array shape inference system for MATLAB, a
prototypical array-based language. Unlike prior efforts at array shape
determination that have used lattice-theoretic techniques, our methods
are based on algebraic systems that exploit properties associated with
MATLAB's shape semantics. This confers a unique advantage to our
approach in that useful shape information can be deduced even when the
actual array extents are compile-time unknowns. The shape inference
system has been implemented in Mathematica as part of MAGICA, a type
inference engine for MATLAB. We report array shape inference
measurements on a benchmark suite comprising programs that span the
published test suites of some recent research MATLAB compilers, and we
show how even when shapes are symbolic, our system detects the
equivalence of over 60% of these shapes in 5 out of 6 benchmarks, and
over 30% in the sixth. In all remaining situations, all array shapes
were inferred to be compile-time constants.
Gzipped Postscript version of the
paper