Type inference for locality analysis of distributed data structures

Abstract

In languages with distributed heap data structures, the type system typically conveys only coarse locality information: whether a reference is local or possibly remote. Often, of interest to the optimizing compiler or the user is a more fine-grain information, such as whether two remote references point to objects in the same partition of the distributed heap. This paper proposes a dependent type system, called place types, to capture such fine-grain locality information. The type of each reference identifies the heap partition, called a place, that the reference points to. This type system is expressive enough to statically type several commonly used distributed data structures. It also accommodates a "dynamic" type when no suitable static type exists. We show how to embed this type system as type annotations in the X10 programming language. We also present a type inference algorithm for saving programmers from the burden of inserting type annotations. The type inference has been inspired by the use of type inference in functional programming languages such as ML. We have implemented the type inference algorithm in the X10 compiler. Experiments with small programs, but with the full set the relevant language features, have been successful in automatically finding the expected place types in these programs. Copyright © 2008 ACM.