Sample Final Exam, CMP521


  1. Draw the Abstract Syntax Tree for the following expression:

                      b*b-4*a*c

    1. Assuming that the standard operator precedence applies.

    2. Assuming that expressions are evaulated strictly left-to-right

  2. In any language of your choice, write the program (function) that computes the following function (for n >= 0):

                      f(n) = 0 if n=0

                      1 if n=1

                      f(n-1)+f(n-2) otherwise

    1. As a recursive function

    2. As an iterative function

  3. What is the ML type of each of the following functions? How are they related (how are they the same, how are they different)?

        1. fun P1 (m,n):int = if n=0 then 1 else m*P1(m,n-1);

          fun P2 m n:int = if n=0 then 1 else m*P2 m (n-1);

    2. What is the type of the function map below? What is its most general type?

            -val data = [(4,50,(5,6)];

            -map P1 data;

            val it = [1024,15625]:int list

  4. What is the difference between Call-by-Value and Call-by-Reference parameter passing? In a language that supported both (e.g. C++), when might you prefer one over the other? In general, function programming languages use which parameter passing semantics? Why?

  5. Name two advantages and two disadvantages of functional languages vs. imperative languages (in general).

  6. I've said the three principle/features of an object oriented language are: Encapsulation, Inheritance, Polymorphism. What does each refer to and why is it important (what are its major benefits)?

  7. In prolog, the predicate member is:

              member(X,[X|_]).

              member(X,[_|Y]) :-member(X,Y).

    1. Write the predicate for: subset(X,Y). Which means X is a subset of Y.

    2. Give a set of bindings, if possible, that unify the following pairs of expressions:

          • pred([a,b],[c,d,[e,f]]) pred(X,[Y|Z])

          • pred(X,Y) pred(pred(X,Y),john)

          • diffpred(X,[a,b,c]) pred(Y,Z)

  8. What is the difference between a virtual and a non-virtual method? Create a tiny example where the result of the invocation of a method depends on whether or not it was declared as a virtual function.