Higher-Order Concurrency

Concurrent programming is a useful technique for structuring many important classes of applications such as interactive systems. This dissertation presents an approach to concurrent language design that provides a new form of linguistic support for constructing concurrent applications. This new approach treats synchronous operations as first-class values in a way that is analogous to the treatment of functions as first-class values in languages such as ML. The mechanism is set in the framework of the language Concurrent ML (CML), which is a concurrent extension of Standard ML. CML has a domain of first-class values, called events, that represent synchronous operations. Synchronous message passing operations are provided as the base-event values, and combinators are provided for constructing more complex events from other event values. This mechanism allows programmers to define new synchronization and communication abstractions that are first-class citizens, which gives programmers the flexibility to tailor their concurrency abstractions to their applications. The dissertation is organized into three technical parts. The first part describes the design and rationale of CML and shows how first-class synchronous operations can be used to implement many of the communication mechanisms found in other concurrent languages. The second part presents the formal operational semantics of first-class synchronous operations and proves that the polymorphic type system used by CML is sound. The third part addresses practical issues. It describes the use of CML in non-trivial applications, describes the implementation and performance of CML on a single-processor computer, and discusses issues related to the use and implementation of CML on a shared-memory multiprocessor