Computer Science 3675
Fall 2005
Solutions to practice questions for quiz 5

1. True or false.

   1. In a typeless language, all type checking done at run time. True

   2. 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

   3. Java is strongly statically typed. False

   4. Polymorphism is most useful in designing custom applications, and is rarely used in function libraries. Frue

2. Why do most modern languages employ name equivalence instead of structural equivalence for types?

   Name equivalence lets the compiler perform stricter type checking, which will find more conceptual errors in programs.

3. 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?)

   Using a and b as a type variables, the most general polymorphic type of f is (a,[b]) -> [b]. (Clearly, f takes an ordered pair x, because f computes right(x). But right(x) must be a list, since f takes the tail of it. The result is the tail of that list, so it has the same type as the right-hand member of x.

4. What is the most general polymorphic type of the Astarte 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 function 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.

   The most general polymorphic type of filter is (a -> Boolean) -> ([a] -> [a]).

5. 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 provided with the idea that each member of a list can be anything. (Lists will necessarily allows a mixture of different things.) The compiler cannot know what kind of thing is in 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).

6. Suppose that a tree type is defined in Astarte 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 simple equational style (which is acceptable):

        numnodes(leaf(s)) = 1
        numnodes(node(a,b)) = 1 + numnodes(a) + numnodes(b)
   

   In Astarte syntax (which is also acceptable):

        Define
          case numnodes(leaf(?)) = 1
          case numnodes(node(?a,?b)) = 1 + numnodes(a) + numnodes(b)
        %Define