Computer Science 3675
Fall 2002
Solutions to practice questions for quiz 3

  1. What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra ()))))?

    zebra

  2. Write a Scheme function called drop so that (drop n L) returns the result of removing the first n members from list L. If L has fewer than n members, then (drop n L) should return the empty list. For example, (drop 2 '(4 8 3 5 7)) = (3 5 7) and (drop 3 '(5 2)) = (). Be careful to use Scheme syntax correctly. 

      (define (drop n L)
    (cond
       ((eq? n 0)  L)
       ((null? L)  ())
       (else       (drop (- n 1) (cdr L)))
    )
  )

    3. Write the filter function in Scheme. That is, write a filter function so that (filter p L) returns a list of all members x of list L such that (p x) is true. Do not try to make it lazy. 

        (define (filter p L) 
       (cond
          ((null? L) ())
          ((p (car L)) (cons (car L) (filter p (cdr L))))
          (else (filter p (cdr L))
       )
    )

  3. True/False

    1. Type checking was first introduced to programming languages so that compilers could detect type errors made by programmers. false

    2. C++ uses name equivalence of types defined using typedef. false

    3. In a typeless language, all type checking done at run time. true

    4. In a strongly typed language, type errors can never occur at run time. true

    5. Polymorphism is most useful in designing custom applications, and is rarely used in function libraries. false

  4. 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].

  5. 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]).

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

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

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