Substructural type system

Substructural type systems are a family of type systems analogous to substructural logics where one or more of the structural rules are absent or only allowed under controlled circumstances. Such systems are useful for constraining access to system resources such as , locks, and memory by keeping track of changes of state that occur and preventing invalid states. Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction: Ordered type systems (discard exchange, weakening and contraction): Every variable is used exactly once in the order it was introduced. Linear type systems (allow exchange, but neither weakening nor contraction): Every variable is used exactly once. Affine type systems (allow exchange and weakening, but not contraction): Every variable is used at most once. Relevant type systems (allow exchange and contraction, but not weakening): Every variable is used at least once. Normal type systems (allow exchange, weakening and contraction): Every variable may be used arbitrarily. The explanation for affine type systems is best understood if rephrased as “every occurrence of a variable is used at most once”. Ordered types correspond to noncommutative logic where exchange, contraction and weakening are discarded. This can be used to model stack-based memory allocation (contrast with linear types which can be used to model heap-based memory allocation). Without the exchange property, an object may only be used when at the top of the modelled stack, after which it is popped off, resulting in every variable being used exactly once in the order it was introduced. Linear types corresponds to linear logic and ensures that objects are used exactly once. This allows the system to safely deallocate an object after its use, or to design software interfaces that guarantee a resource cannot be used once it has been closed or transitioned to a different state. The Clean programming language makes use of uniqueness types (a variant of linear types) to help support concurrency, input/output, and in-place update of arrays.