Besides element type and values, a multidimensional array is characterized by the number of axes (rank) and their respective lengths (shape vector). Both properties are essential for bounds checking and to compute linear offsets into heap memory at run time. In order to have an array's rank and shape available at any time during program execution, both are typically kept in an array descriptor that is maintained at run time in addition to the array itself. In this paper, we propose a different approach: we treat array rank and shape as first-class citizens themselves. Firstly, we use dependent types to reflect structural properties of arrays in the type system. Secondly, we annotate a program with the explicit array properties wherever necessary. This choice not only renders implicit run time array descriptors obsolete, but exposing all rank and shape computations explicitly in intermediate code also allows us to perform extensive compile time optimisation on them. We have implemented the proposed approach in our experimental array language Qube; preliminary experimental results indicate the suitability of the proposed approach.

Original languageEnglish
Title of host publicationImplementation and Application of Functional Languages
EditorsSven-Bodo Scholz, Olaf Chitil
Number of pages18
Volume5836 LNCS
Place of PublicationBerlin
PublisherSpringer Verlag
Publication date17.10.2011
ISBN (Print)978-3-642-24451-3
ISBN (Electronic)978-3-642-24452-0
Publication statusPublished - 17.10.2011
Event20th International Symposium on Implementation and Application of Functional Languages - Hatfield, United Kingdom
Duration: 10.09.200812.09.2008
Conference number: 86892


Dive into the research topics of 'Descriptor-free Representation of Arrays with Dependent Types.'. Together they form a unique fingerprint.

Cite this