This paper is concerned with the idea of extending the typing system of a programming language to include the idea of sets of data structures, where corresponding nodes within the structures must coordinate. An example of a place where this idea could be useful would be in adding new fields within the context of legacy code. The paper discusses adding this in the context of programming language theory, using &lgr;-calculus. This will probably make the paper difficult to read for most individuals who do not have a background in programming language research.

The paper is divided into several sections. First, the authors describe how to implement coordinated data structures as extensions to a polymorphic typed &lgr;-calculus. Following that, they create a small programming language to demonstrate how to implement their extensions. The syntax and operational semantics are presented. The authors support a Web site in conjunction with this paper that has a downloadable interpreter (written in O’Caml) for the language created, as well as several example programs.

Initially, a subset of the final language is discussed. Next, the authors show that two existing languages, LX and guarded recursive datatypes, also support coordinated data types. Then, the authors examine how their results interact with singleton-integer types, and present the full language and an example (the code is available from the authors’ Web site).

While this paper requires a good deal of background knowledge from the reader, it is quite interesting, and worthwhile reading for people interested in programming languages.