Uniqueness Typing Simplified
Also see: Where to Find Technical Support
Uniqueness Typing Simplified , by Edsko de Vries, Rinus Plasmeijer, and David M. Abrahamson.
We present a uniqueness type system that is simpler than both Clean’s uniqueness system and a system we proposed previously. The new type system is straightforward to implement and add to existing compilers, and can easily be extended with advanced features such as higher rank types and impredicativity. We describe our implementation in Morrow, an experimental functional language with both these features. Finally, we prove soundness of the core type system with respect to the call-by-need lambda calculus.
Uniqueness typing is related to linear typing, and their differences have been discussed here before. Linear types have many applications. This paper describes the difference between linear and unique types:
In linear logic, variables of a non-linear type can be coerced to a linear type (dereliction). Harrington phrases it well: in linear logic, “linear” means “will not be duplicated” whereas in uniqueness typing, “unique” means “has not been duplicated”.
In contrast to other papers on substructural typing, such as Fluet’s thesis Monadic and Substructural Type Systems for Region-Based Memory Management , this paper classifies uniqueness attributes by a kind system. This possibility was mentioned in Fluet’s thesis as well, Section 4.2, footnote 8, though the technique used here seems somewhat different.
