Type Erasure, Type Inference, Duck Typing and Type Casting

Type erasure

In programming languages, type erasure is a load-time process by which explicit type annotations are removed from a program before it is executed at run time . An operational semantics that does not require programs to be accompanied by types is called a type-erasure semantics , in contrast to a type-passing semantics . The ability to provide a type-erasure semantics is a kind of abstraction principle , guaranteeing that the run-time execution of a program does not depend on type information. In the context of generic programming, the opposite of type erasure is called reification .

Problems with type erasure

Generics are checked for type correctness at compile time. The generic type information is then removed in a process called type erasure . For example, will be converted to the non-generic type List, which normally contains arbitrary objects. The compile-time check guarantees that the resulting code is type-correct.

Because of type erasure, type parameters cannot be determined at run time. For example, when an ArrayList is examined at run time, there is no general way to determine whether, before type erasure, it was an or an . Many people are dissatisfied with this limitation. There are partial approaches. For example, one can examine individual elements to determine which type they belong to; for example, if an ArrayList contains an Integer, then that ArrayList could have been parameterized with Integer(however, it could have been parameterized with any superclass of Integer, such as Numberor Object).

To demonstrate this, the following code prints "Equal":

Another effect of type erasure is that a generic class cannot extend the Throwable class in any way, directly or indirectly:

The reason this is not supported is due to type erasure:

Because of type erasure, the runtime does not know which catch block to execute, so the compiler prohibits it.

Java generics differ from C++ templates . Java generics produce only one compiled version of a generic class or function, regardless of the number of parameterization types used. In addition, the Java runtime does not need to know which parameterized type is used, because the type information is checked at compile time and is not included in the compiled code. Consequently, instantiating a Java class of a parameterized type is impossible, because instantiation requires a call to a constructor, which is unavailable if the type is unknown.

For example, the following code cannot be compiled:

Because at run time there is only one copy per generic class, static variables are shared among all instances of the class, regardless of their type parameter. Consequently, a type parameter cannot be used in the declaration of static variables or in static methods.

Type inference

The reverse operation is called type inference . Although type erasure can be used as a simple way to define typing in implicitly typed languages (an implicitly typed term is well typed if and only if it is the erasure of a well-typed explicitly typed lambda term ), this does not always lead to an algorithm for checking implicitly typed terms.

Type inference is, in programming, the ability of a compiler to logically deduce the type of an expression's value on its own. The type inference mechanism was first introduced in the ML language, where the compiler always infers the most general polymorphic type for every expression. This not only reduces the size of the source code and makes it more concise, but also often improves code reuse .

Type inference is characteristic of functional programming languages, although over time it has been partially implemented in object-oriented languages as well (C#, D, Visual Basic .NET, Nim, C++11, Vala, Java^[a]), where it is limited to the ability to omit the type of an identifier in a definition with initialization (see syntactic sugar). For example:

var s = "Hello, world!";  // The type of the variable s (from string) is inferred from the initializer

Type inference algorithms

The Hindley-Milner algorithm

The Hindley-Milner algorithm is a mechanism for inferring the types of expressions, implemented in programming languages based on the Hindley-Milner type system, such as ML (the first language of this family), Standard ML, OCaml, Haskell, F#, Fortress and Boo. The Nemerle language uses this algorithm with a number of necessary modifications .

The type inference mechanism is based on the ability to automatically infer, fully or partially, the type of an expression obtained by evaluating some expression. Since this process is performed systematically during program translation, the translator can often infer the type of a variable or function without an explicit specification of the types of these objects. In many cases explicit type declarations can be omitted — this can be done for sufficiently simple objects, or for languages with simple syntax. For example, the Haskell language implements a fairly powerful type inference mechanism, so specifying function types in this programming language is not required. A programmer may specify a function's type explicitly in order to restrict its use to specific data types only, or for more structured formatting of the source code.

To obtain the information needed to correctly infer the type of an expression when there is no explicit declaration of that expression's type, the translator either gathers such information from the explicit type declarations of the subexpressions (variables, functions) that make up the expression under study, or uses implicit information about the types of atomic values. Such an algorithm does not always help to determine the type of an expression, especially when higher-order functions and parametric polymorphism of a sufficiently complex nature are used. Therefore, in complex cases, when there is a need to avoid ambiguities, it is recommended to specify the types of expressions explicitly.

The typing model itself is based on a type inference algorithm for expressions, which originates from the mechanism for obtaining expression types used in the typed λ-calculus, proposed in 1958 by H. Curry and R. Feys. Later, in 1969, Roger Hindley extended the algorithm itself and proved that it infers the most general type of an expression. In 1978, Robin Milner, independently of R. Hindley, proved the properties of an equivalent algorithm. Finally, in 1985, Luis Damas showed conclusively that Milner's algorithm is complete and can be used for polymorphic types. For this reason, the Hindley-Milner algorithm is sometimes also called the Damas-Milner algorithm.

The type system is defined in the Hindley-Milner model as follows:

1. Primitive types are types of expressions.
2. Parametric type variables α are types of expressions.
3. If and are types of expressions, then the type is a type of expressions.
4. The symbol is a type of expressions.

The expressions whose types are computed are defined in a fairly standard way:

1. Constants are expressions.
2. Variables are expressions.
3. If and are expressions, then () is an expression.
4. If is a variable and is an expression, then is an expression.

A type is said to be an instance of a type when there is some transformation such that:

It is usually assumed that the type transformations are subject to the following restrictions:

The type inference algorithm itself consists of two steps: generating a system of equations and then solving those equations.

Constructing the system of equations

The system of equations is constructed according to the following rules:

1. — if the binding is in .
2. — if , where and .
3. — if , where is with the binding added.

In these rules, the symbol {\displaystyle \Gamma } denotes a set of bindings of variables to their types:

Solving the system of equations

Solving the constructed system of equations is based on the unification algorithm. This is a fairly simple algorithm. There is some function {\displaystyle u} that takes a type equation as input and returns a substitution that makes the left and right sides of the equation identical (it "unifies" them). A substitution is simply a mapping from type variables to types. Such substitutions can be computed in various ways, depending on the specific implementation of the Hindley–Milner algorithm.

Duck Typing

Implicit typing, latent typing, or duck typing in object-oriented languages is the determination of whether an object implements a certain interface without any explicit declaration or inheritance of that interface, simply by the object's implementing the full set of its methods.

Origin of the name "duck typing"

The name of the term comes from the English "duck test", which in the original reads:

If it looks like a duck, swims like a duck, and quacks like a duck, then it is probably a duck.

If it looks like a duck, swims like a duck and quacks like a duck, then it probably is a duck.

The principle of duck typing

An object is considered to implement an interface if it contains all the methods of that interface, regardless of its relationships in the inheritance hierarchy and of its membership in any particular class. Thus, whether an object may correctly be used as a value of a particular interface is determined either statically, by the compiler, by analyzing the class to which the object belongs and checking that it implements the required set of methods, or dynamically, based on runtime type information.

This approach makes it possible to work polymorphically with objects that are not related in an inheritance hierarchy. It is enough that all these objects support the required set of methods.

Another closely related approach is structural subtyping in OCaml, where object types are compatible if the signatures of their methods are compatible, regardless of declared inheritance, and all of this is checked at program compile time.

Problems of hierarchical typing

Duck typing solves such problems of hierarchical typing as:

• the impossibility of explicitly indicating (through inheritance) the compatibility of an interface with all present and future interfaces with which it is conceptually compatible;
• an exponential increase in the number of links in the type hierarchy if one tries to do this even partially.

Duck typing is practically indispensable in applied scripting languages ("scripts"), where one has to work with documents external to the program (script) (web pages, text and spreadsheet documents) whose object hierarchy is not accessible.

Languages that support duck typing

Duck typing is supported, among others, in the following languages: Prolog, D, Perl, Smalltalk, Python, Objective-C, Ruby, JavaScript, TypeScript, Groovy, ColdFusion, Boo, Lua, Go, Scala.

Type Conversion

Description of type conversion

Type conversions are divided into:

• explicit;
• implicit.

An explicit conversion is specified by the programmer in the program text by means of:

• a language construct;
• a function that takes a value of one type and returns a value of another type.

An implicit conversion is performed by the translator (a compiler or interpreter) according to the rules described in the language standard. The standards of most languages prohibit implicit conversions.

In weakly typed object-oriented languages such as C++, the inheritance mechanism is implemented by converting the type of a pointer to the current object to the base class (in type-safe languages such as OCaml the notion of type conversion is fundamentally absent, and the validity of access to a subtype's component is controlled by the type-consistency checking mechanism at compile time, while direct access remains in the machine code).

Implicit type conversion

Implicit type conversion in C/C++

Implicit type conversion occurs in the following cases:

• after the operands of binary arithmetic, logical, and bitwise operations, comparison operations, and the 2nd or 3rd operand of the "?:" operation are evaluated; the values of the operands are converted to the same type;
• before an assignment is performed;
• before an argument is passed to a function;
• before a function returns its return value;
• after the expression of a switch construct is evaluated, the value is converted to an integer type;
• after the expressions of the if, for, while, do-while constructs are evaluated, the value is converted to the type bool.

For example, when a binary arithmetic operation is performed, the values of the operands are converted to a single type. With inheritance, pointers of a derived class are converted to pointers of the base class.

Consider an example in C.

When comparison operations and assignments are performed, variables of different types are implicitly converted to a single type.

Implicit conversions can have side effects. For example, when a floating-point number is converted to an integer type, the fractional part is truncated (no rounding is performed) . In the reverse conversion, precision may be lost because of differences between the representations of floating-point and integer numbers. For example, a variable of type float (a single-precision floating-point number according to the IEEE 754 standard) cannot store the number 16,777,217 without loss of precision, whereas a 32-bit integer variable of type int can. Because of the loss of precision, comparison operations on the same number represented by an integer and a floating-point type (for example, int and float) may give false results (the numbers may turn out to be unequal).

The code above will print the following, if the size of int is 32 bits and the compiler supports the IEEE 754 standard:

Explicit type conversion

Type conversions in C

For an explicit type conversion, the type name is specified in parentheses before the variable or expression. Consider an example.

int X;
int Y = 200;
char C = 30;
X = (int)C * 10 + Y; // variable C is converted to type int

To evaluate the last expression, the compiler performs roughly the following actions:

• first, the variable C of the character type char is explicitly converted to the integer type int by widening;
• the operands of the multiplication are evaluated. The left operand has type int. The right operand is the constant 10, and such constants have type int by default. Since both operands of the "*" operator have type int, no implicit type conversion is performed. The result of the multiplication also has type int;
• the operands of the addition are evaluated. The left operand, the result of the multiplication, has type int. The right operand, the variable Y, has type int. Since both operands of the "+" operator have type int, no implicit conversion to a common type is performed. The result of the addition also has type int;
• the assignment is performed. The left operand, the variable X, has type int. The right operand, the result of evaluating the expression to the right of the "=" sign, also has type int. Since both operands of the "=" operator have the same type, no implicit type conversion is performed.

But even so, errors are possible. The type char can be either signed (signed char) or unsigned (unsigned char); the result depends on the compiler implementation, and such behavior is permitted by the standard. A value of the unsigned type char may turn out to be negative when converted to the signed type int, owing to the way machine instructions are implemented on some processors. To avoid ambiguity, it is recommended to specify the signedness of the char type explicitly.

Type conversions in C++

C++ has five operations for explicit type conversion. The first, parentheses ((type_to)expression_from), is supported for compatibility with C. The other four operations are written in the form

Consider an example.

  // variable y will be assigned the value -2

The cumbersome keywords serve as a reminder to the programmer that type conversion is fraught with problems.

The static_cast operation

Purpose: valid type conversions.

The static_cast operation is similar to the "parentheses" operation with one exception: it does not convert pointers to unrelated types (the reinterpret_cast operation is used for that).

Uses:

• conversion between numeric types and enum, including when an implicit conversion is impossible (int → enum class) or results in a "possible loss of precision" warning (double → float);
• conversion of pointers to the type void* and back;
• conversion of pointers to derived types into pointers to base types and back;
• selection of one of several overloaded functions;

the constructor may have more arguments, but default values must be specified for them;

• type conversion in templates (the compiler decides which operations to use already when the template is specialized);
• conversion of the operands of the ternary conditional operation "?:" to a single type (the values of the 2nd and 3rd operands must have the same type);

Restrictions on expression_from: none.

Restrictions on type_to: there must be a way to convert the value of the expression expression_from to the type type_to, by means of operator type_to or a constructor.

Whether the static_cast operation produces code: in the general case, yes (for example, a call to an overloaded conversion operator or to a constructor).

Sources of logical errors: they depend on what you intend to do with the operation. Overflow, out-of-range values, and even (for pointer conversions) memory corruption are possible.

Examples.

The dynamic_cast operation

Purpose: downcasting in the inheritance hierarchy, with special behavior if the object does not have the required type.

The operation obtains information about the type of the object expression_from using RTTI. If the type is type_to or its subtype, the conversion is performed. Otherwise:

• for pointers, NULL is returned;
• for references, the exception std::bad_cast is thrown.

Restrictions on expression_from: the expression must be a reference or a pointer to an object that has at least one virtual function.

Restrictions on type_to: a reference or pointer to a type derived from the type of expression_from.

Whether the dynamic_cast operation produces code: yes.

Logical errors are possible if the operation is passed an argument that does not have the type type_to, and the pointer is not checked for equality to NULL (or, correspondingly, the exception std::bad_cast is not handled).

The const_cast operation

Purpose: removing/adding the modifier(s) const, volatile, and/or mutable. It is often used to work around a poor program or library design, to interface C with C++, to pass information through generic void* pointers, and to write const and non-const versions of a function at the same time (in C++14 there is a workaround via decltype(auto) ).

Restrictions on expression_from: the expression must return a reference or a pointer.

Restrictions on type_to: the type type_to must match the type of the expression expression_from up to the modifier(s) const, volatile, and mutable .

Whether the const_cast operation produces code: no.

Sources of logical errors: the program may modify an immutable object. Sometimes this can lead to a segmentation fault; sometimes a subroutine may not expect that the memory it provided for reading has suddenly been modified.

As an example, consider the code of a dynamic library.

When the library is loaded into memory, the process creates a new data segment in which the global variables are placed. The code of the function SomeDllFunction() resides in the library and, when called, returns a pointer to a hidden member of a global object of the class string. The const_cast operation is used to remove the const modifier.

The reinterpret_cast operation

Purpose: type punning, that is, assigning a different type to a memory location (not necessarily compatible with the given one) while preserving the bit representation.

The object returned by the expression expression_from is treated as an object of type type_to.

Restrictions on expression_from: the expression must return a value of an ordinal type (any of the integer types, the Boolean bool, or the enumeration enum), a pointer, or a reference.

Restrictions on type_to:

• If expression_from returns a value of an ordinal type or a pointer, the type type_to may be an ordinal type or a pointer.
• If expression_from returns a reference, the type type_to must be a reference.

Whether the reinterpret_cast operation produces code: no.

Sources of logical errors. The object returned by the expression expression_from may not have the type type_to. There is no way to check this; the programmer assumes full responsibility for the correctness of the conversion.

Consider some examples.

See also

• Dynamic cast
• Run-time type information (RTTI)
• Data typing
• Type punning
• Type theory