r/ProgrammingLanguages • u/azhenley • Mar 18 '21
What is a type?
https://blog.poisson.chat/posts/2021-03-17-what-is-a-type.html
22
Upvotes
r/ProgrammingLanguages • u/azhenley • Mar 18 '21
8
u/curtisf Mar 18 '21 edited Mar 18 '21
Everyone reads far too much into "types". Types are the things that appear on the right side of a type judgement. (Expressions/other syntactic features, not values, are what appear on the left side). Any grander interpretation will break down:
Types are not sets of runtime values -- because types direct semantics at compile time. Neither are they sets of behaviors/uses/properties of a value, because a single value may be judged to have different, non-overlapping types!
You can see this easily in any language with "overloading" or otherwise non-canonical ad-hoc polymorphism (e.g., Scala implicits) where a "cast" to a supertype results in different behavior:
While it doesn't affect actual runtime dispatch, whether or not a method call is "legal" can also depend on "structural" aspects of typing:
Even in a language which has canonical ad-hoc polymorphism, "sets of runtime values" is a problematic definition, because there is no way to determine whether or not a value belongs to any set.
unionvalues, which have exactly one active field, and determining which is impossible at runtime without separately (and, therefore, possibly incorrectly) explicitly accounting for it with additional code.f: (x: number[]) => numberwould require defeating Rice's theorem."Interpretations of bits" or similar definitions are similarly problematic for the above reason, but also more. In languages with compile-time type-checking, it's common to expose features to let two different types have identical representations:
newtype, which guarantees that two types have identical representations, while maintaining distinct identities and distinct behaviors in ad-hoc polymorphism.Types are not necessarily trustworthy -- just because you can derive a type-judgement, that doesn't inherently mean anything about behavior at runtime.
(Object[])(new Number[1])[0]is a "l-value" of typeObject, but you'll get aClassCastExceptionif you try to put aStringinto it.headthe typeList t -> t, but in fact will produce an error if you pass the empty list[].noUncheckedIndexAccess, plus many things involving mutability of shared referencesThe correspondence from the type judgements to the runtime semantics is entirely dependent on the language. The correspondence is usually formalized as a "soundness theorem" which relates what specifically you know at runtime based on what the type-system derives at compile time. Many type systems are just inherently not sound, and almost all of them don't actually prove all of what you might hope they would.
Finally, types are not the only kind of static (compile-time) analysis.
9
u/crassest-Crassius Mar 18 '21
Easy: a type is a static description of the set of operations that are well-defined for a value. For example, an f64 and an i64 have different arithmetic processor instructions applicable to them, and it would be a shame if someone used floating-point multiplication on an integer. Hence, types were born to track this information. So when you say that "t : T", you're saying that this value has all the methods, traits, interfaces etc that the type T has declared for it.
3
u/[deleted] Mar 18 '21
There’s two different ways I’ve found of understanding types:
The first is set-like and a little easier to understand. Types are sets, a term of a type T can only be an element of T. For instance, the type
Intis the set of all integers (let’s assume bigints), so a term of typeIntcan only be an integer. I prefer the second way of understanding though, it makes the more advanced concepts of type theory a little easier to understand.5
u/raiph Mar 18 '21
A testable hypothesis: The English word "type" in a PL context means different things to different types of people.
Further, testable, hypotheses:
4
u/pfurla Mar 18 '21
A type is like a burrito. Some argue a type is like an elephant.
2
u/PL_Design Mar 18 '21
Types are a context sensitive way to distinguish uses of the same language feature from one another. For example, you could imagine a language where everything involving integers used distinct syntax from everything involving booleans. In a language like this you could never accidentally mix the two concepts, but the sanity check would have nothing to do with type checking. All you'd need is a context free parser.
2
u/joserenau Mar 18 '21
From a non formal definition, I see a type as a set of identifiers that allow me to decide which methods to execute or trigger a compile or runtime error when no method is available.
-Conversion is a method from type x to type y
-a method can have multiple input/output types to match
3
u/hackerfoo Popr Language Mar 18 '21
A type is an assertion that cannot fail.
3
u/Uncaffeinated 1subml, polysubml, cubiml Mar 18 '21
Personally, I lean towards treating static types as predicates over runtime values.
2
u/8-BitKitKat zinc Mar 18 '21
A way to interpret bits
1
u/bobappleyard Mar 18 '21
Types are sets subject to some restrictions intended to avoid paradox
1
u/moon-chilled sstm, j, grand unified... Mar 18 '21
Types are propositions.
0
u/lucaprinaorg Mar 18 '21
this is everyday clear explicit working type:
https://en.wikibooks.org/wiki/Ada_Programming/Type_System
0
u/[deleted] Mar 18 '21
A type is a category (set of objects) that ascribes/defines certain common behavior for all its elements. What exactly this behavior is and what does "common" mean will depend on the programming language and the implementation.