Final Exam, CSCI 3155
December 13th, 2003

You have 150 minutes to answer these questions.  Please read all questions before you start.  This is a closed-book exam.  Please remember that you are bound by the CU honor code.

  1. Object oriented languages, such as C++ and Java, use inclusion polymorphism whereas SML uses parametric polymorphism.
    1. [5 points] Define the term polymorphism.
    2. [10 points] Give example code that exhibits inclusion polymorphism in an object-oriented language of your choice.  Your code should be self contained (i.e., if you use any methods or types, besides built-in types, you need to give their definitions).  Explain why your code is polymorphic.
    3. [10 points] Give example code that exhibits parametric polymorphism in SML.  Your code should be self-contained (i.e., if you use any functions or types you use in your code except for built-in types and built-in operators, you need to give their definitions).  Explain why your code is polymorphic.
    4. [10 points] Even though Java already supports inclusion polymorphism, the next version of Java will also support generics.  Explain, illustrating your explanation with an example, why Java needs generics even though it already has inclusion polymorphism.
  2. [10 points] Explain why invoking a method on an interface-typed variable is more complicated to implement than invoking a method on a class-typed variable in Java.  Support your explanation with a concrete example.
  3. For this question you must give complete MYSTERY programs for each part.
    1. [7 points] Give a program that would produce different answers with pass-by-name parameter passing mechanism and pass-by-reference parameter passing mechanism. Explain why your program would produce different outputs with the two parameter passing mechanisms.
    2. [7 points] Give a program whose output would indicate whether or not MYSTERY uses short-circuit evaluation of AND.  Explain why your program would produce different outputs with and without short-circuit evaluation.
  4. Write BNF grammars for the following:
    1. [5 points] A language whose strings contain only an even number of occurrences of the letter 'a'.  The empty string is not in the language.

    2. [5 points] A language for arithmetic expressions, where the only arithmetic operators are "+" and "*" and the only operands are the numbers 0 through 9.  For example, 9+2, 9*3+5, and 9 would all be in the language.

    3. [5 points] Is your grammar for arithmetic expressions ambiguous?  Explain clearly why or why not.








       

  5. Consider the following code fragment in Java syntax:

    try {
      ... /* Try block */
    }
    catch (E1 e) { ... /* Catch block */ }
    finally {... /* Finally block */ }
    print("After try"); /* print does not throw any exceptions */

    1. [2 points] Explain broadly the purpose of the "finally" block in a try-catch-finally statement.

    For each of the following cases, indicate what code will be executed, in what order, and what exceptions, if any, will be thrown, and in what order.  A block "terminates normally" if it does not throw any exceptions and does not execute a "return" statement.

    1. [2 points] All the blocks (if executed) will terminate normally. 

    2. [2 points] The try block throws an exception of type E1, the catch block (if executed) will throw an exception of type E2, and the finally block (if executed) will terminate normally. 

    3. [2 points] The try block executes a "return" statement, the catch block and finally blocks (if executed) terminate normally. 

    4. [2 points] The try block terminates normally, the catch block (if executed) will throw an exception of type E2, and the finally block (if executed) will throw an  exception of type E3. 

  6. Consider the following two SML functions:

    fun f1(nil,v) = nil
      | f1(h::t,v) = if v=h then f1(t,v) else h::f1(t,v);

    fun f2(a,0) = a
      | f2(h::t,n) = f2(t,n-1)
      | f2(nil,n) = nil;

    1. [5 points] Clearly describe what function f1 does

    2. [3 points] Give the type that will be inferred for f1 by the SML compiler

    3. [5 points] Clearly describe what function f2 does

    4. [3 points] Give that type that will be inferred for f2 by the SML compiler