Version stamps for functional arrays and determinacy checking : two applications of ordered lists for advanced programming languages

This dissertation describes the fat-elements method for providing functional arrays and the LR-tags method for determinacy checking. Although these topics may seem very different, they are actually closely linked: Both methods provide reproducibility in advanced programming languages and share many implementation details, such as tagging data using version stamps taken from an ordered list. The fat-elementsmethod provides arrays as a true functional analogue of imperative arrays with the properties that functional programmers expect from data structures. It avoids many of the drawbacks of previous approaches to the problem, which typically sacrifice usability for performance or vice versa. The fat-elements method efficiently supports array algorithms from the imperative world by providing constant-time operations for single-threaded array use. Fully persistent array accesses may also be performed in constant amortized time if the algorithm satisfies a simple requirement for uniformity of access. For algorithms that do not access the array uniformly or single-threadedly, array reads or updates take at most O(log n) amortized time for an array of size n. The method is also space efficient?creating a new array version by updating a single array element requires constant amortized space. The LR-tags method is a technique for detecting indeterminacy in asynchronous parallel programs?such as those using nested parallelism on shared-memory mimd machines?by checking Bernstein?s conditions, which prevent determinacy races by avoiding write/write and read/write contention between parallel tasks. Enforcing such conditions at compile time is difficult for general parallel programs. Previous attempts to enforce the conditions at runtime have had non?constant-factor overheads, sometimes coupled with serial-execution requirements. The LR-tags method can check Bernstein?s (or Steele?s generalized) conditions at runtime while avoiding some of the drawbacks present in previous approaches to this problem. The method has constant-factor space and time overheads when run on a uniprocessor machine and runs in parallel onmultiprocessormachines, whereas the best previous solution, Cilk?s Nondeterminator (a constant-space and nearly constant-time approach), requires serial execution. Both parts of the dissertation include theoretical and practical material. Tests from implementations of both techniques indicate that the methods should be quite usable in practice.