Computer Science 3675
Summer 2000
Practice questions for final exam

The final exam will be closed book. You will have 90 minutes. Many of the questions will be true/false or multiple-choice. For this practice test, the questions are short essay questions instead.

  1. What is a declarative program? What is an imperative program?

  2. Explain what a garbage collector does.

  3. What are some advantages of interpreters over compilers? Of compilers over interpreters?

  4. How does the lvalue of a variable differ from the rvalue of the variable?

  5. What is the main difference between object-based programming and object-oriented programming.

  6. A prolog interpreter is a theorem prover. What kind of proofs does it do?

  7. What is the form of axioms that are allowed in a logic program?

  8. What is the difference between a lexeme and a token?

  9. What list representation is good for performing the :: operator efficiently? What list representation is good for performing indexing efficiently?

  10. Using map and lfold and possibly a helper function, write an expression whose value is 0 + 2 + 4 + 8 + ... + n.

  11. What is the most general polymorphic type of function f defined by f(x,y) = y::tail(x)?

  12. What is the most general polymorphic type of function g define by g x y = x(head y)?

  13. What kind of thing is g x, where g is the function of the preceding problem?

  14. What is a strongly typed language? A weakly typed language? An untyped language?

  15. What is the value of Scheme expression (f '(a b c)) if function f is defined by 
        (define (f x)
      (if (null? x) x
          (cons (car x) (cons (car x) (f (cdr x))))
      )
    )

  16. What is does the dispatcher do in the implementation of an object-oriented programming language?

  17. What is a virtual function?

  18. In Java, what is the major difference between a protected variable and a private variable?

  19. How are variables inherited in single-inheritance object-oriented languages? What is the mechanism?

  20. How is a Java interface like a class? How does it differ?

  21. What does the word static mean in Java? What does the word final mean?

  22. In the implementation of programming languages, how does a function find its nonlocal variables?

  23. What is a function closure?

  24. If you unify g(f(X,a),Y) with g(Z,h(W)), what is the result of the unification? Does it succeed? Here, upper case letters are variables and lower case letters are constants.

  25. Consider the following BNF grammar. 
        <S>  ->  a<S> a
    <S>  ->  b<S> b
    <S>  ->  c
    Show that string abbcbba can be derived from <S> by showing a parse tree for it.

  26. What does a cut do in a backtracking program?

  27. Function twist is defined by the following two equations. 
        twist([]) = []
    twist(a::b::c) = b::a::twist(c)
    (Twist is not defined for every list.) Show an evaluation by substitution of expression twist [2,3,4,5,6,7].

  28. Write an equational definition of a function called lefts that takes a list of ordered pairs and produces a list of the left-hand members of those ordered pairs. For example, lefts([(2,4), (3,5), (7,6)]) = [2,3,7]. Do not use the map function.

  29. The append predicate is defined as follows in Prolog. 
           append([], X, X).
       append([H|T], X, [H|Y]) :- append(T, X, Y).
    (Recall that [H|T] is the list whose head is H and whose tail is T, and that :- is the reverse implication, <=.) Show a proof tree, with variable bindings on the branches, for goal append(X, [3,4], [1,2,3,4]). Show all branches of the computation, including failed branches. Be sure to copy variables where copying is required.