Computer Science 3675
Fall 2003
Practice questions for quiz 4

  1. True or false.

    1. When a variable occurs in a logic programming goal, the interpreter is being asked whether that goal holds for all values of the variable.

    2. In logic programming, a variable in an axiom might be used as an input variable sometimes, and as an output variable at other times, when computation uses that axiom.

    3. Cuts are used to reduce memory requirements and to speed up computation.

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

    5. Standard ML is a strongly typed language. Therefore, in Standard ML, it is not possible to get a type error at run time.

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

    7. C++ uses name equivalence of types defined using typedef.

  2. Unification is a form of pattern matching. Which of the following is not a characteristic of unification?

    1. Unification never changes the binding of a bound variable.
    2. Unification is symmetric; unifying A with B has exactly the same effect as unifying B with A.
    3. Unification is very slow, and is only used rarely during computations of logic programs.
    4. Unification can bind unbound variables.

  3. In a logic programming style, write axioms for computing predicate samelength(X,Y), which is true just when X and Y are lists that have the same length.

  4. In a logic programming style, write axioms for computing predicate allsame(X), which is true just when all members of list X are the same. For example, allsame([5,5,5]) is true, as is allsame([a,a]), but allsame([2,4,4]) is false. Note that allsame([]) is true, and allsame([b]) is true.

  5. Show the logic programming search tree for goal (member(X,[3,4,5]), member(X,[4])), up to the point where a success is found. The definition of the member predicate is as follows, written in Prolog syntax. 

          member(M, [M|X]).
      member(M, [X|T]) :- member(M, T).

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

  7. 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. (A programmer defeats the type system by providing type information that is different from what the compiler would infer, such as in doing a cast; the compiler is expected to go along with this information without asking any questions.)

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

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