Skip to main content
Kent Academic Repository

Verifying Spatial Properties of Array Computations

Dominic, Orchard, Mistral, Contrastin, Matthew, Danish, Andrew, Rice (2017) Verifying Spatial Properties of Array Computations. Journal of Proceedings of the ACM on Programming Languages, 1 (OOPSLA). Article Number 75. ISSN 2475-1421. E-ISSN 2475-1421. (doi:10.1145/3133899) (KAR id:62274)


Arrays computations are at the core of numerical modelling and computational science applications. However, low-level manipulation of array indices is a source of program error. Many practitioners are aware of the need to ensure program correctness, yet very few of the techniques from the programming research community are applied by scientists. We aim to change that by providing targetted lightweight verification techniques for scientific code. We focus on the all too common mistake of array offset errors as a generalisation of off-by-one errors. Firstly, we report on a code analysis study on eleven real-world computational science code base, identifying common idioms of array usage and their spatial properties. This provides much needed data on array programming idioms common in scientific code. From this data, we designed a lightweight declarative specification language capturing the majority of array access patterns via a small set of combinators. We detail a semantic model, and the design and implementation of a verification tool for our specification language, which both checks and infers specifications. We evaluate our tool on our corpus of scientific code and give verification case studies of bug fixes that are detected by our approach. We found roughly 80,000 targets for specification across roughly 1.4 million lines of code, showing that the vast majority of array computations read from arrays in a pattern with a simple, regular, static shape.

Item Type: Article
DOI/Identification number: 10.1145/3133899
Uncontrolled keywords: Program analysis; Software testing and debugging; Domain specific languages; Just-in-time compilers; JavaScript; Data-driven program analysis; GPUs; Gradual Typing; OpenGL
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: Organisations -1 not found.
Depositing User: Dominic Orchard
Date Deposited: 10 Sep 2017 20:25 UTC
Last Modified: 04 Mar 2024 19:05 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.