Problem 1 [7%] CFG

(a) [2%]
It is ambiguous because for the expression: ()()()
there are 2 leftmost derivation trees:

	  <S>
         /   \
       <S>   <S>
      /   \   /\
    <S>   <S>(  )
    /\    /\
   (  )  (  )
  

	  <S>
         /   \
       <S>   <S>
       /\   /   \
      (  ) <S>  <S>
           /\   /\
          (  ) (  )
  
<<< The solution consists of 3 things: the example expression and the 2
derivation trees. 1 mark for giving correct answers for 1 or 2 of the
three things. Full marks for giving all 3 correct answers. >>>


(b) [5%]
<S> ::= <S><A> | <A>
<A> ::= (<S>) | ()

<<< 3 marks for one of the rule, 5 marks for both together. >>>
-------------------------------------------------------------------------------------------

Problem 2 [12%] Concepts

(a) [4%]

The difference between static scope and dynamic scope lies in when the
binding of name occurrences to declaration takes place. In static
scope, binding occurs at compile time; and in dynamic scope, binding
occurs at run time.

Example in Pascal:
program dynamic_scope(input, output);
    var x : real;
    procedure show;
        begin write(x) end;
    procedure tricky;
        var x : real;
        begin x = 1.2; show end;

    begin x := 5.6; show; tricky; end.

If static scope rule is used, the output is:	5.6	5.6
If dynamic scope rule is used, the output is:	5.6	1.2

<<< 2 marks for example and 1 mark for explanation in each case >>>

(b) [4%]

(i)  dangling pointers: Example in C++:
int *x = new int[5];
int *y = x;
delete x;

/*
Now y is a dangling pointer, pointing to released memory which may
be reused for some other purposes
*/


(ii) pointers causing memory leaks: Example in C++:
int *x = new int[5];
int *y = new int[15];
y = x;

/*
Now the int array of size 5 allocated and pointed by pointer x is lost
resulting in memory leakage
*/

<<< 1 mark for example and 1 mark for explanation in each case >>>


(c) [2%]

strongly typed: SML
weakly typed:	PROLOG

<<< 1 mark for each case >>>

(d) [2%]

compilation:	C, C++, Pascal, Fortran
interpretation: SML, PROLOG, Java

<<< 1 mark for each case >>>
------------------------------------------------------------------------------------------

Problem 3 [10%]: SML I
fun distribute([x], [y]) = [[x,y]]
  | distribute([x], y::ys) = [x,y]::distribute([x], ys)
  | distribute(x::xs, L) = distribute([x], L)@distribute(xs, L);
------------------------------------------------------------------------------------------

Problem 4 [8%]: SML II

(a) [6%] 

mystery = fn: (`a * `a -> `a) * `a list -> `a
foo = fn: int * int -> int

(b) [2%]

mystery(foo, [20,16,78,90,10]) 
= foo(20, mystery(foo, [16,78,90,10]))
= foo(20, foo(16, mystery(foo, [78,90,10])))
= foo(20, foo(16, foo(78, mystery(foo, [90,10]))))
= foo(20, foo(16, foo(78, foo(90, mystery(foo, [10])))))
= foo(20, foo(16, foo(78, foo(90, 10))))
= foo(20, foo(16, foo(78, 9)))
= foo(20, foo(16, 87))
= foo(20, 12)
= 32
-------------------------------------------------------------------------------------------

Problem 5 [12%] Prolog Programming I

(a) [6%]

pop([H|T], H, T).
push(T, H, [H|T]).
num_items([], 0).
num_items([_|T], X) :- num_items(T, Y), X is 1+Y.

<<< 2 marks for each predicate >>>


(b) [4%]
push([], 'Y2k', S1), push(S1, 1999, S2), push(S2, bug, S3), pop(S3, X, S4), num_items(S4, N).

<<< Substract 1 mark for each wrong/missing subgoal >>>
<<< Must be in the right order: >>>
<<< so scan from left to right and stop at the first wrong subgoal. >>>
<<< Subtract 1 mark if "Y2K" is not inside single quotes, >>>
<<< but don't consider it a wrong subgoal. >>>


(c) [2%]
S1 = ['Y2k']
S2 = [1999, 'Y2k']
S3 = [bug, 1999, 'Y2k']
X = bug
S4 = [1999, 'Y2k']
N = 2

<<< Substract 0.5 marks for each wrong answer >>>
<<< But give 1 mark for 2 or 3 correct answers >>>
-------------------------------------------------------------------------------------------

Problem 6

(a) Search trees:

                      student(X), hates(X)
                s1, {X/a} /              \ s2, {X/b}
                      hates(a)            hates(b)
             h1, {_1/a} /       h1,{_3/b}   |         \  h2
loves(a,_2), !, is_true(0)  loves(b,_4),!,is_true(0)  succeed
    l1, {_2/b} /                |
         !, is_true(0)         fail
              |
          is_true(0)
              |
            fail



          hates(X), student(X)
        s1, {_1/X} /
     loves(X,_2), !, is_true(0), student(X)
    l1, {X/a,_2/b} |
            !, is_true(0), student(a)
                   |
               is_true(0), student(a)
                   |
                  fail


(b)
q1: yes.
q2: no.
-------------------------------------------------------------------------------------------

Problem 7

//(3pts)
interface MyNumber      // May be declared as abstract class
{  
    public void print(); //  "abstract" is ok
}

//(4pts)
class MyRational implements MyNumber 
{
    protected int nu;   // declared as "protected" so MyInteger can access it
    protected int de;   // may be declared as "private" for this question
    public MyRational(int x, int y) { nu = x; de = y; }
    public void  print() { System.out.print(nu + "/" + de + " "); }
}

//(6pts)
class MyInteger extends MyRational 
{
    public MyInteger(int x) { super(x,1); }  
    public void print() { System.out.print(nu + " "); }
}


class NumberTest
{
    public static void main(String[] args)
    {
        MyNumber[] x = new MyNumber[3];
        x[0] = new MyRational(10,11); // this gets a rational 10/11
        x[1] = new MyInteger(20);     // this gets an integer 20
        x[2] = new MyRational(10,7);  // this gets a rational 10/7

        for (int i = 0; i < 3; i++)   // this will print out the numbers
            x[i].print();             // one by one as: 10/11 20 10/7
    }
}

-------------------------------------------------------------------------------------------

Problem 8

import BM_Char;

class Unsupported_Exception extends Exception
{
    Unsupported_Exception() { super("Unsupported Class"); }
    
}

interface Comparable
{
    public int compare(Comparable y);
}

class BM_Int implements Comparable
{
    int data;
    BM_Int(int x) { data = x; }
    public int get() { return data; }
    public int compare(Comparable y) { return this.data - ((BM_Int)y).data; }
}

class BM_Double implements Comparable
{
    double data;
    BM_Double(double x) { data = x; }
    public double get() { return data; }
    public int compare(Comparable y) 
    {
        double diff =  this.data - ((BM_Double)y).data;
        return (diff > 0) ? 1 : ( (diff < 0) ? -1 : 0);
    }
}

class BM_Char implements Comparable
{
    char data;
    BM_Char(char x) { data = x; }
    public char get() { return data; }
    public int compare(Comparable y) 
        { return this.data - ((BM_Char)y).data; }
}


class BM_Str implements Comparable
{
    String data;
    BM_Str(String x) { data = x; }
    public String get() { return data; }
    public int compare(Comparable y) 
        { return data.compareTo(((BM_Str)y).data); }
}

class Max
{
    static Comparable max(Comparable x, Comparable y) 
        throws Unsupported_Exception
        {
            /* the syntax: <object> instanceof <class>
             * checks if <object> belongs to <class>
             */
            if (x instanceof BM_Int ||
                x instanceof BM_Double ||
                x instanceof BM_Str )
            {
                return (x.compare(y) > 0) ? x : y;
            }
            else
            {
                try
                {
                    throw new Unsupported_Exception();
                }
                catch (Unsupported_Exception e)
                {
                    System.out.println("Gotcha!");
                    throw e;
                }
                finally
                {
                    System.out.println("Good luck!");
                }
                    
            }
        }

    public static void main(String[] args) throws Unsupported_Exception
    {
        System.out.println(
            ((BM_Double)max(new BM_Double(3.4),new BM_Double(5.6))).get());
        System.out.println(
            ((BM_Int) max(new BM_Int(8), new BM_Int(6))).get());
        System.out.println(
            ((BM_Char) max(new BM_Char('r'), new BM_Char('m'))).get());
        System.out.println(
            ((BM_Str) max(new BM_Str("brian"), new BM_Str("mak"))).get());
    }
}