Linear Haskell: practical linearity in a higher-order polymorphic language
Linear type systems have a long and storied history, but not a clear path forward to integrate with existing languages such as Ocaml or Haskell. In this paper, we introduce and study a linear type system designed with two crucial properties in mind: backwards-compatibility and code reuse across linear and non-linear users of a library. Only then can the benefits of linear types permeate conventional functional programming. Rather than bifurcate types into linear and non-linear counterparts, we instead attach linearity to function arrows. Linear function types can receive inputs from linearly-bound values, but can also operate over unrestricted, regular values.
To demonstrate the efficacy of our linear type system—both how easy it can be integrated in an existing language implementation and how streamlined it makes it to write program with linear types—we implemented our type system in a branch of GHC, the leading Haskell compiler, and demonstrate, with it, two kinds of applications of linear types: making functions, that otherwise would be considered to have side effects, pure; and enforcing protocols in I/O-performing functions.