An Approach to Array Shape Determination in MATLAB

Pramod G. Joisha, U. Nagaraj Shenoy, Prithviraj Banerjee

Abstract

One of the main hurdles that array-based languages such as MATLAB and APL pose to compilation is the lack of an explicit declaration for an array's shape. In programs written using these languages, the attributes of intrinsic type and shape for a variable are implicitly characterized by the defining expression for that variable. In addition, these attributes are allowed to change on the fly. On account of these complications, and others such as the dynamic binding of storage to names, interpreters are typically used to cope with their translation.

In this report, we address the problem of statically inferring the shape of an array in languages such as MATLAB. Inferred shapes are desirable from the standpoint of both program compilation and efficient interpretation because static knowledge of an array's shape could permit reductions in the number of run-time array conformability checks, enable memory preallocation optimizations, and facilitate efficient translations to ``scalar'' target languages such as C.

This report presents a framework for statically describing the shape of a MATLAB expression, using a methodology based on systematic matrix formulations. The representation exposes the algebraic properties that underlie MATLAB's shape semantics and exactly captures the shape that the expression assumes at run time. Some of the highlights of this framework are its applicability to a large class of MATLAB functions and the uniformity of its approach. We compare our methods with the traditional shadow variable scheme and demonstrate how the algebraic view permits powerful shape-related assertions and optimizations not possible in the conventional approach.

Gzipped Postscript version of the paper