In computer science and logic, a dependent type is a type that depends on a value. Dependent types play a central role in intuitionistic type theory and in the design of functional programming languages like ATS, Agda and Epigram.
An example is the type of n-tuples of real numbers. This is a dependent type because the type depends on the value n.
Deciding equality of dependent types in a program may require computations. If arbitrary values are allowed in dependent types, then deciding type equality may involve deciding whether two arbitrary programs produce the same result; hence type checking may become undecidable.
The Curry–Howard correspondence implies that types can be constructed that express arbitrarily complex mathematical properties. If the user can supply a constructive proof that a type is inhabited (i.e., that a value of that type exists) then a compiler can check the proof and convert it into executable computer code that computes the value by carrying out the construction. The proof checking feature makes dependently typed languages closely related to proof assistants. The code-generation aspect provides a powerful approach to formal program verification and proof-carrying code, since the code is derived directly from a mechanically verified mathematical proof.
Read more about Dependent Type: Systems of The Lambda Cube, Comparison
Famous quotes containing the words dependent and/or type:
“It is vain to expect virtue from women till they are, in some degree, independent of men ... Whilst they are absolutely dependent on their husbands they will be cunning, mean, and selfish, and the men who can be gratified by the fawning fondness of spaniel-like affection, have not much delicacy, for love is not to be bought, in any sense of the words, its silken wings are instantly shrivelled up when any thing beside a return in kind is sought.”
—Mary Wollstonecraft (1759–1797)
“How is freedom measured, in individuals as in nations? By the resistance which has to be overcome, by the effort it costs to stay aloft. One would have to seek the highest type of free man where the greatest resistance is constantly being overcome: five steps from tyranny, near the threshold of the danger of servitude.”
—Friedrich Nietzsche (1844–1900)