True or false.
In a typeless language, all type checking done at run time. True
Standard ML is a strongly statically typed language. Therefore, in Standard ML, it is not possible to get a type error at run time. True. In a strongly statically typed language, all type checking is done at compile time, and no type errors can go undetected.
Java is strongly statically typed. False. Java requires some type checking to be done at run time.
Polymorphism is most useful in designing custom applications, and is rarely used in function libraries. False. Polymorphism is most useful in general purpose libraries, since, while writing a library, you do not know how, or with which types, somebody else will use the library.
Why do most modern languages employ name equivalence instead of structural equivalence for types? Name equivalence allows stronger type checking.
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. (Try an example. What kind of thing makes sense?) Type: (a,[b]) -> [b], where a and b are type variables.
What is the most general polymorphic type of the Cinnameg function filter? Use type variables. Filter is defined so that (filter p L) returns a list of all members x of list L such that p(x) is true. For example, if predicate positive returns true on a positive number and false on a nonpositive number, then (filter positive [9,-2,-3,6]) = [9,6]. Notice that p is a predicate. Type: (a -> Boolean) -> [a] -> [a], where a and b are type variables. Notice that filter takes a predicate (type a -> Boolean) and produces a function that takes a list of a's (the list to filter) and produces another list of a's (the filtered list).
Polymorphism without type variables typically requires dynamic type checking. Give an example where a run-time (dynamic) type check is required when there are no type variables, but where type variables would allow the compiler to perform static type checking.
Suppose that you compute head(x) + 1, where x is a list. If there are no type variables, polymorphic lists need to be defined with the idea that each member of a list can be anything. (Lists will necessarily allow a mixture of different things.) The compiler cannot know what kind of thing is in list x, and so it cannot know that head(x) + 1 is sensible. With type variables, the compiler will know that x is a list of numbers, so it will know that head(x) is a number (assuming that head(x) + 1 is a well-typed expression).
Suppose that a tree type is defined in Cinnameg with two constructors, as follows.
Species Tree =
leaf String
| node (Tree,Tree)
%Species
Using primitive recursion, write a definition of a function that
takes a tree and returns the total number of nodes (leaves and
internal nodes) in the tree.
In a simple equational style (which is
acceptable):
numnodes(leaf(s)) = 1
numnodes(node(a,b)) = 1 + numnodes(a) + numnodes(b)
In Cinnameg syntax (which is also acceptable):
Define
case numnodes(leaf(?)) = 1
case numnodes(node(?a,?b)) = 1 + numnodes(a) + numnodes(b)
%Define
Using the same type as in the preceding exercise, again using primitive recursion, write a function that takes a tree and returns the concatenation of all of the strings in the leaves in the tree, from left to right.
In a simple equational style (which is
acceptable):
catleaves(leaf(s)) = s
catleaves(node(a,b)) = catleaves(a) ++ catleaves(b)
In Cinnameg syntax (which is also acceptable):
Define
case numnodes(leaf(?s)) = s
case numnodes(node(?a,?b)) = catleaves(a) ++ catleaves(b)
%Define