Lecture
In computer science, a data type or simply a type is a classification of information entities (such as values or expressions) that determines the possibility of using them within a given formal system. The concept has several definitions, which may partially overlap or lead to identical content. There are two most fundamentally distinguishable, though not contradictory, definitions:
The declarative definition is most often used in imperative programming, the procedural one — in parametric polymorphism. Object-oriented programming uses the procedural definition when describing the interaction of program components, and the declarative one — when describing the implementation of these components on a computer, considering, respectively, «class-as-behavior» and «class-as-object-in-memory».
The operation of assigning a type to information entities is called typing. The assignment and checking of type agreement can be performed in advance (static typing), directly at the point of use (dynamic typing), or combine both methods. Types can be assigned «once and for all» (strong typing) or allowed to change (weak typing) — see strong and weak typing.
Type theory formally studies types and the results of their assignment. Type systems, which use types to provide one degree or another of type safety, are an integral part of most programming languages. Only a few languages can be considered fully typed; most languages provide only some level of typedness.
The concept of type safety relies predominantly on the procedural definition of type. For example, an attempt to divide a «number» by a «string» will be rejected by most languages, since no corresponding behavior is defined for these types. Weakly typed languages tend toward the declarative definition. For example, «number» and «record» have different behavior, but the value of the address of a «record» in computer memory may have the same low-level representation as a «number». Weakly typed languages provide the ability to violate[en] the type system by assigning this value the behavior of a «number» through a type-cast operation. Such tricks can be used to improve program efficiency, but they carry the risk of crashes, and are therefore not allowed in safe languages.
The procedural definition does not apply to data description languages that are not Turing-complete (such as SGML).
Uniform processing of data of different types is called polymorphism.
There are various classifications of types and the rules for assigning them.
For example, types are divided into primitive and aggregate (the latter are also called composite, compound, or structural). Examples of primitive types are real, integer, boolean, and others. Examples of aggregate types are tuples, arrays, lists, and others. Predefined auxiliary types, useful for industrial development, are also common, such as «time», «calendar date», etc.
Structural (aggregate) types should not be identified with data structures: some data structures are directly embodied by certain structural types, but others are built through their composition, most often recursive. In the latter case, one speaks of recursive data types[en]. An example of data structures that are almost always built through the composition of objects of a recursive type are binary trees.
According to another classification, types are divided into independent and dependent. Important varieties of the latter are reference types, a particular case of which, in turn, are pointers. References (including pointers) are a non-composite dependent type whose values are the address in computer memory of another value. For example, in the C language the type «pointer to unsigned integer» is written as «unsigned *», in the ML language the type «reference to unsigned integer» is written as «word ref».
Types are also divided into monomorphic and polymorphic (see type variable).
A type can be parameterized by another type, in accordance with the principles of abstraction and parametricity. For example, to implement a function for sorting sequences there is no need to know all the properties of its constituent elements — it is only necessary that they admit a comparison operation — and then the composite type «sequence» can be defined as parametrically polymorphic. This means that its components are defined not using concrete types (such as «integer» or «array of integers»), but type parameters. Such parameters are called type variables (type variable) — they are used in the definition of a polymorphic type in the same way as value parameters in the definition of a function. Substituting concrete types as actual parameters for a polymorphic type produces a monomorphic type. Thus, a parametrically polymorphic type is a type constructor, that is, an operator over types in type arithmetic.
Defining a sorting function as parametrically polymorphic means that it sorts an abstract sequence, that is, a sequence of elements of some (unknown) type. In this case, the function only needs to know two properties of its parameter — that it is a sequence, and that a comparison operation is defined for its elements. Treating parameters procedurally rather than declaratively (i.e., using them based on behavior rather than value) allows one sorting function to be used for any sequences — for sequences of integers, for sequences of strings, for sequences of sequences of boolean values, and so on — and significantly increases the code reuse ratio. Dynamic typing provides the same flexibility, however, unlike parametric polymorphism, the former incurs overhead. Parametric polymorphism is most developed in languages typed according to Hindley — Milner, that is, descendants of the ML language. In object-oriented programming, parametric polymorphism is commonly called generic programming.
Despite the obvious advantages of parametric polymorphism, there is sometimes a need to provide different behavior for different subtypes of one common type, or similar behavior for incompatible types — i.e., various forms of ad hoc polymorphism. However, there is no mathematical justification for it, so the requirement of type safety[en] has long made its use difficult. Ad hoc polymorphism was implemented within a parametrically polymorphic type system by means of various tricks. For this purpose, either variant types[en], or parametric modules (functors), or so-called «type-indexed values» (type-indexed values), which in turn also have a number of implementations, were used. Type classes, which appeared in the Haskell language, provided a more elegant solution to this problem.
If the information entity under consideration is a type, then assigning it a type leads to the notion of a «type of a type», or «metatype». In type theory, this notion is called a «kind of type» (kind of a type or type kind). For example, the kind «*» includes all types, and the kind «* -> *» includes all unary type constructors. Kinds are explicitly used in full-typed programming — for example, in the form of type constructors in languages of the ML family.
Extending a safe polymorphic type system with classes[en] and kinds of types made Haskell the first fully typed language. The resulting type system influenced other languages (for example, Scala, Agda).
A limited form of metatypes is also present in a number of object-oriented languages in the form of metaclasses. In descendants of the Smalltalk language (for example, Python), every entity in a program is an object having a type, which is itself also an object — thus, metatypes are a natural part of the language. In C++, separately from the language's main type system, an RTTI subsystem is implemented, which also provides type information in the form of a special structure.
Dynamically determining metatypes is called reflection (also known as reflexivity or introspection).
In mathematics, logic, and computer science, type theory is considered to be any formal system that serves as an alternative to naive set theory, accompanied by a classification of the elements of such a system by means of types forming a certain hierarchy. Type theory is also understood as the study of such formalisms.
Type theory — a mathematically formalized basis for designing, analyzing, and studying data type systems in the theory of programming languages (a branch of computer science). Many programmers use this term to refer to any analytical work studying type systems in programming languages. In academic circles, type theory most often refers to a narrower branch of discrete mathematics, in particular typed λ-calculus.
Modern type theory was partly developed in the process of resolving Russell's paradox and is largely based on the work of Bertrand Russell and Alfred Whitehead «Principia mathematica»
The most notable difference between real-world programming and formal information theory is that questions of efficiency are considered not only in terms of O-notation, but also from the standpoint of the economic feasibility of implementing certain requirements in a physically manufactured computer. And first of all, this affects the permissible precision of computations: the notion of «number» on a computer is in practice not identical to the notion of number in arithmetic. A number on a computer is represented by a memory cell whose size is determined by the computer's architecture, and the range of values of the number is limited by the size of this cell. For example, Intel x86 architecture processors provide cells whose size in bytes is given by a power of two: 1, 2, 4, 8, 16, and so on. Setun architecture processors provided cells whose size in trits was given by a multiple of three: 1, 3, 6, 9, and so on.
An attempt to write into a cell a value exceeding the maximum permissible limit for it (which is known) leads to an overflow error. When calculations on larger numbers are needed, a special technique called long arithmetic is used, which, due to its considerable resource consumption, cannot be performed in real time. For the computer architectures most widespread today, the «native» cell size is 32 and 64 bits (that is, 4 and 8 bytes).
In addition, integer and real numbers have different representations in these cells: non-negative integers are represented directly, negative integers — in two's complement, and real numbers are encoded in a special way. Because of these differences, adding the numbers «1» and «0.1», which in theory yields the value «1.1», is not directly possible on a computer. To carry it out, a type conversion must first be performed, producing, based on the integer value «1», a new value of real type «1.0», and only then adding «1.0» and «0.1». Due to the specifics of implementing real numbers on a computer, such a conversion is not carried out with absolute precision, but with a certain degree of approximation. For the same reason, strongly typed languages (for example, Standard ML) treat the real type as «not admitting an equality check[en]».
The notion of data alignment is also of great importance.
Comments