ML with Concurrency

Both functional and concurrent programming are relatively new paradigms with great promise. In this book, a survey is provided of extensions to Standard ML, one of the most widely used functional languages, with new primitives for concurrent programming. Computer scientists and graduate students will find this a valuable guide to this topic.

1 Introduction.- 2 The Essence of Concurrent ML.- 2.1 Introduction.- 2.2 The Fundamental Ideas.- 2.2.1 Abstraction, Choice, and Synchronization.- 2.2.2 Scoping and Mobility.- 2.2.3 Polymorphism.- 2.3 Overview of CML.- 2.4 The Semantics of Mini-CML.- 2.4.1 Syntax.- 2.4.2 Typing Rules.- 2.4.3 Dynamic Semantics.- 2.5 Events and Their Algebra.- 2.6 Expressiveness.- 2.7 Implementing Concurrency Abstractions in CML.- 2.7.1 Buffered Channels.- 2.7.2 Swap Channels.- 2.8 Conclusions and Related Work.- 3 Concurrency in Poly/ML.- 3.1 Introduction.- 3.1.1 Concurrency.- 3.2 The Poly/ML Concurrency Primitives.- 3.2.1 Design Criteria.- 3.2.2 Process Communication.- 3.2.3 Process Creation.- 3.2.4 Interrupts from the Console.- 3.3 The Uniprocessor Implementation.- 3.3.1 Process Creation.- 3.3.2 Communication.- 3.3.3 Input/Output.- 3.4 A Shared Memory Multiprocessor Implementation.- 3.4.1 Threads and Processes.- 3.4.2 Garbage Collection.- 3.5 The Development of a Distributed Implementation.- 3.5.1 Additional Primitives.- 3.5.2 Implementation of a Distributed System.- 3.6 Implementation on LEMMA.- 3.6.1 LEMMA.- 3.6.2 Implementation of Poly/ML on LEMMA.- 3.6.3 Experience with LEMMA.- 4 CCS Programming in an ML Framework: An Account of LCS.- 4.1 Introduction.- 4.1.1 From Process Calculi to Process Languages.- 4.1.2 The LCS Project.- 4.1.3 Overview of the Chapter.- 4.2 Features of LCS.- 4.2.1 Functions, Behaviors, and Processes.- 4.2.2 Naming.- 4.2.3 Compositions.- 4.2.4 Derived Combinators.- 4.2.5 Exceptions and Events.- 4.2.6 Higher-Order Process Passing and Link Passing.- 4.2.7 References, Light and Strong Compositions.- 4.2.8 Timers and Other Imperative Features.- 4.2.9 User Interface.- 4.3 Typing Behavior Expressions.- 4.3.1 Types for Behaviors.- 4.3.2 An Overview of Tagged Types.- 4.3.3 Type Reconstruction in LCS.- 4.4 Operational Semantics.- 4.4.1 Core LCS.- 4.4.2 The Observation Relation $$\xrightarrow{\mu }$$.- 4.4.3 Behavior Reduction (?) and Functional Reduction (?).- 4.4.4 Exceptions, Divergence, and Message-Passing Strategies.- 4.4.5 Light and Strong Processes.- 4.4.6 Equality of Programs.- 4.5 The Implementation Model.- 4.5.1 From Observations to Reduction.- 4.5.2 Channels.- 4.5.3 Flattening the Structure of Threads, Preemption.- 4.5.4 Store Segments.- 4.5.5 Localizing Communications.- 4.5.6 Abstract Machines.- 4.5.7 Implementations.- 4.6 Conclusion.- 4.6.1 Related Work.- 4.6.2 Conclusion and Further Work.- 5 FACILE―From Toy to Tool.- 5.1 Introduction.- 5.1.1 The FACILE Approach.- 5.2 Design and Development of FACILE.- 5.2.1 Integration of Programming Paradigms.- 5.2.2 Simplicity and Coherence.- 5.2.3 Uniformity of Values.- 5.2.4 Object Lifetime.- 5.2.5 Concurrency and Distribution.- 5.2.6 Design Alternatives and Tradeoffs.- 5.3 Language Features.- 5.3.1 Concurrency.- 5.3.2 Distributed Programming.- 5.3.3 Modules in FACILE.- 5.3.4 Dynamic Connectivity.- 5.4 Implementation.- 5.4.1 Nodes.- 5.4.2 Concurrent Processes.- 5.4.3 Channels.- 5.4.4 Transmission of Values.- 5.4.5 Object Sharing.- 5.4.6 Node Server.- 5.4.7 Demanding and Supplying of Modules.- 5.5 Applications.- 5.5.1 Calumet.- 5.5.2 Collaborative Interior Design.- 5.5.3 Mobile Service Agents.- 5.6 Conclusion.- 5.6.1 Type System Based on Effect Analysis.- 5.6.2 Effect-Based Analysis.- 5.6.3 Interoperability.- 5.6.4 New Communication Paradigms.- 5.6.5 The Future of ML with Concurrency.- 6 A Semantic Theory for ML Higher-Order Concurrency Primitives.- 6.1 Motivation and Background.- 6.2 Related Work.- 6.2.1 Typing.- 6.2.2 Denotational Models.- 6.3 Informal Presentation.- 6.4 Static Semantics.- 6.5 Dynamic Semantics.- 6.5.1 Typed Dynamic Semantics.- 6.5.2 Acceptance Trees Model.- 6.5.3 Dynamic Domains.- 6.5.4 Semantics Presentation.- 6.6 Conclusion.- Appendix 6.A Semantic Functions.- Appendix 6.B Semantic Rules.- 7 Communication Analysis for Concurrent ML.- 7.1 Introduction.- 7.2 Extracting the Communication Topology.- 7.2.1 Types, Behaviors, and Regions.- 7.2.2 Ordering on Behaviors.- 7.2.3 The Type and Behavior Inference System.- 7.2.4 Subject Expansion Properties.- 7.3 Semantics.- 7.3.1 Semantics of CML.- 7.3.2 Semantics of Behaviors.- 7.3.3 Simulation Ordering on Behaviors.- 7.4 Subject Reduction Property.- 7.4.1 Sequential Correctness.- 7.4.2 Correctness of Matching.- 7.4.3 Concurrent Correctness.- 7.5 Decidability Issues.- 7.5.1 Undecidability of the Simulation Ordering.- 7.5.2 Decidability of the Syntactic Ordering.- 7.6 Conclusion.- Appendix 7.A Syntactic Properties of the Typing System.- Appendix 7.B Semantic Properties of the Ordering.- Appendix 7.C Semantic Properties of the Typing System.- Appendix 7.D Decidability Issues Concerning the Orderings.- References.