Substructural Type System

Get Substructural Type System essential facts below. View Videos or join the Substructural Type System discussion. Add Substructural Type System to your Like2do.com topic list for future reference or share this resource on social media.

## Different substructural type systems

### Linear type systems

### Affine type systems

### Relevant type system

### Ordered type system

## Programming languages

## See also

## Notes

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Substructural Type System

This article relies largely or entirely on a single source. (February 2018) |

**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 files, locks and memory by keeping track of changes of state that occur and preventing invalid states.^{[1]}^{[2]}

Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction:

exchange | weakening | contraction | use | |
---|---|---|---|---|

linear | allowed | -- | -- | exactly once |

affine | allowed | allowed | -- | at most once |

relevant | allowed | -- | allowed | at least once |

ordered | -- | -- | -- | exactly once in order |

**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.**Ordered type systems**(discard exchange, contraction, and weakening): Every variable is used exactly once in the order it was introduced.

The explanation for affine type systems is best understood if rephrased as "every *occurrence* of a variable is used at most once".

**Linear types** corresponds to linear logic and ensures that objects are used exactly once, allowing the system to safely deallocate an object after its use.^{[3]}

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.^{[4]}

Linear type systems allow references but not aliases. To enforce this, a reference goes out of scope after appearing on the right-hand side of an assignment, thus ensuring that only one reference to any object exists at once. Note that passing a reference as an argument to a function is a form of assignment, as the function parameter will be assigned the value inside the function, and therefore such use of a reference also causes it to go out of scope.

A linear type system is similar to C++'s unique_ptr class, which behaves like a pointer but can only be moved (i.e. not copied) in an assignment. Although the linearity constraint is checked at compile time, dereferencing an invalidated unique_ptr causes undefined behavior at run-time.^{[5]}

The single-reference property makes linear type systems suitable as programming languages for quantum computation, as it reflects the no-cloning theorem of quantum states. From the category theory point of view, no-cloning is a statement that there is no diagonal functor which could duplicate states; similarly, from the combinator point of view, there is no K-combinator which can destroy states. From the lambda calculus point of view, a variable *x* can appear exactly once in a term.^{[6]}

Linear type systems are the internal language of closed symmetric monoidal categories, much in the same way that simply typed lambda calculus is the language of Cartesian closed categories. More precisely, one may construct functors between the category of linear type systems and the category of closed symmetric monoidal categories.^{[7]}

**Affine types** are a version of linear types allowing to *discard* (i.e. *not use*) a resource, corresponding to affine logic. An affine resource *can* only be used once, while a linear one *must* be used once.

**Relevant types** correspond to relevant logic which allows exchange and contraction, but not weakening, which translates to every variable being used at least 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).^{[8]} 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.

The following programming languages support linear or affine types:

**^**Walker 2002, p. X.**^**Walker 2002, p. 4.**^**Walker 2002, p. 6.**^**Walker 2002, p. 43.**^**std::unique_ptr reference**^**John c. Baez and Mike Stay, "Physics, Topology, Logic and Computation: A Rosetta Stone", (2009) ArXiv 0903.0340 in*New Structures for Physics*, ed. Bob Coecke,*Lecture Notes in Physics*vol.**813**, Springer, Berlin, 2011, pp. 95-174.**^**S. Ambler, "First order logic in symmetric monoidal closed categories", Ph.D. thesis, U. of Edinburgh, 1991.**^**Walker 2002, pp. 30-31.

- Walker, David (2002). "Substructural Type Systems". In Pierce, Benjamin C.
*Advanced Topics in Types and Programming Languages*. MIT Press. pp. 3&ndash, 43. ISBN 0-262-16228-8.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Top US Cities

United States

Like2do.com was developed using defaultLogic.com's knowledge management platform. It allows users to manage learning and research. Visit defaultLogic's other partner sites below: