True/False
Type checking was first introduced to programming languages so that compilers could detect type errors made by programmers. false
C++ uses name equivalence of types defined using typedef. false
In a typeless language, all type checking done at run time. true
In a strongly typed language, type errors can never occur at run time. true
Polymorphism is most useful in designing custom applications, and is rarely used in function libraries. false
Polymorphism without type variables typically requires that a programmer defeat the compile-time type system. Give an example where the type system would need to be defeated without type variables, but where type variables would allow the compiler to perform type checking.
Suppose that you want to implement lists, and you want a function that takes the head of a list. If you use polymorphism without type variables, then the head function produces a value of type ANYTHING. The compiler cannot use type information about the result type, and so must do the type checking at run time. For example, you can write a list class in Java, with a head method. If you have created a list L, each of whose members you know is an Integer, you can write
Integer x = (Integer) L.head();
to compute the head of L. You must explicitly tell the compiler the
type of the result. This defeats the type system, because you might
be wrong. You are telling the compiler that you know more about the
types of things than it does, and that it should take your word for it.
The run-time system will check that you are right when this statement
is performed.
If you can use type variables then the head function takes a list of alphas and produces an alpha, where alpha is a type variable. If L has type "list of Integer" then the head of L has type Integer, and the compiler knows that. So the compiler does not need for the programmer to help it, and it does not need to defer a type check to run time.
What is the most general polymorphic type of function f defined by f (x) = tail(right(x))? Use type variables. Function right takes the right-hand member of an ordered pair.
Since you are taking right(x), x must be an ordered pair. You take the tail of right(x), so right(x) must be a list. For example, f (a,[b,c,d]) = [c,d]).
In the example, a can have any type. So say that a has type alpha. Values b, c and d can also have any type, but their types must be the same. Say that their type is beta. The parameter to f has type (alpha, [beta]) and the result has type [beta]. So f has type (alpha,[beta]) -> [beta].
What is the most general polymorphic type of the Astarte function filter? Filter is defined so that (filter f L) a list of all members x of list L such that f (x) is true. For example, if function positive returns true on a positive number and false on a nonpositive number, then (filter positive [9,-2,-3,6]) = [9,6].
Suppose the members of the list all have type alpha. The predicate f (positive in the example) must have type alpha -> boolean. Notice that (filter f ) is a function that takes a list of alphas and produces a list of alphas. So filter takes f (of type [alpha] -> boolean) and produces a function of type [alpha] -> [alpha]. So filter itself must have type ([alpha] -> boolean) -> ([alpha] -> [alpha]).
Types and functions can both be viewed as kinds of encapsulations. A function encapsulates an algorithm for solving a problem; it hides the details of the algorithm. What does a type encapsulate?
A type encapsulates how the data is representated.Why do most modern languages employ name equivalence instead of structural equivalence for types?
Name equivalence allows for stricter type checking, so that a compiler can detect and report some common errors.
When a compiler performs type inference, what is it doing? What information does it use as its source of information, and what information does it infer?
A compiler examines the way in which things are used in a program and reaches conclusions about the types that those things must have for consistency with the way in which they are used.