Published: 7th February 2017|
|Preface Jeremy Yallop and Damien Doligez|
|Generating Code with Polymorphic let: A Ballad of Value Restriction, Copying and Sharing Oleg Kiselyov||1|
|GADTs and Exhaustiveness: Looking for the Impossible Jacques Garrigue and Jacques Le Normand||23|
|System Description: Dependent Types for Multi-Rate Flows in Synchronous Programming William Blair and Hongwei Xi||36|
|System Description: Specialization of Generic Array Accesses After Inlining Ryohei Tokuda, Eijiro Sumii and Akinori Abe||45|
We are pleased to present the joint post-proceedings of the 2015 edition of the ML Family Workshop and OCaml Users and Developers Workshop, held in Vancouver, British Columbia, Canada. In consultation with the programme committees we invited the authors of selected presentations at the two workshops to expand their submissions into full papers for inclusion in the post-proceedings. The submissions underwent a fresh round of reviewing by external experts before revision and acceptance.
The four papers in this volume reflect the breadth of the material at the workshops, which bring together theorists and practitioners, language designers, implementers and users, from many different language communities.
The first paper, Generating Code with Polymorphic let: A Ballad of Value Restriction, Copying and Sharing (Oleg Kiselyov), revisits a question that lies at the heart of the Hindley-Milner type system found in all ML-family languages, namely the generalization of type variables in polymorphic let bindings. The paper presents a surprisingly simple translation from a multi-stage to an unstaged language; it is the first such translation with support for polymorphic let. Besides its use as an implementation technique, the translation elucidates a known soundness problem that arises from the combination of mutable values, let-polymorphism and cross-stage persistence.
The second paper, GADTs and Exhaustiveness: Looking for the Impossible (Jacques Garrigue and Jacques Le Normand), investigates the interaction of two long-standing ML language features — exhaustiveness checking for pattern matching, and abstract types — with a more recent addition, generalized algebraic data types (GADTs). The paper shows via an encoding of Horn clauses that adding GADTs to ML turns exhaustiveness checking into an undecidable problem, and describes a small extension to pattern matching (supported in recent OCaml releases) that improves practicality and usability.
The third paper, Dependent Types for Multi-Rate Data Flows in Synchronous Programming (William Blair and Hongwei Xi), describes an implementation of the synchronous programming language Prelude using the type system of the ML-family language ATS. Synchronous programming, used to develop embedded real-time systems, involves combining data flows that may produce values at different rates. Prelude supports flow composition by means of operators that harmonise these rates. The paper describes the encoding of these operators as dependently-typed functions in ATS, illustrating the flexibility and practicality of advanced ML-based type systems.
The final paper, Specialization of Generic Array Accesses After Inlining (Ryohei Tokuda, Eijiro Sumii and Akinori Abe), describes the implementation of an optimization in the OCaml compiler that extends the intermediate language with array type information to avoid runtime type dispatch. Starting from a design based on System F-style type abstraction and application, the authors extended the OCaml compiler to pass array type information from instantiation sites into inlined polymorphic functions, ensuring that read and write operations are compiled efficiently. The change to the OCaml compiler is relatively modest, and leads to significant performance increases for some array-heavy programs.
As with all such endeavours, this volume represents the work of many people. We are grateful to the authors, the workshop participants, both programme committees, the external reviewers, and the EPTCS editorial board and staff for their contributions to its publication. We hope that you find this volume a stimulating and useful resource.
University of Cambridge
ML 2015 Programme Chair
OCaml 2015 Programme Chair