John Boyland

Alias Killing: Unique Variables Without Destructive Reads

An unshared object can be accessed without regard to possible conflicts with other parts of a system, whether concurrent or single-threaded. A unique variable (sometimes known as a ``free'' or ``linear'' variable) is one that either is null or else refers to an unshared object. Being able to declare and check which variables are unique improves a programmer's ability to avoid program faults.

In previously described uniqueness extensions to imperative languages, a unique variable can be accessed only with a destructive read, which nullifies it after the value is obtained. This approach suffers from several disadvantages: the use of destructive reads increases the complexity of the program which must continually restore nullified values; adding destructive reads changes the semantics of the programming language; and many of the nullifications are actually unnecessary.

We demonstrate instead that uniqueness can be preserved through the use of existing language features. We give a modular analysis that checks (nonexecutable) uniqueness annotations superimposed on an imperative programming language without destructive reads.


June 9, 1999
3:30pm
Wean 8220