Problem 1
---------


(a) In C++, "x" represents a Complex object while in Java, it
    represents a reference to a Complex object.


(b) Cut is used to prune a PROLOG search tree: as a goal, it always succeeds
    and if the search has reached the "cut" point of a rule, it will continue
    with that rule and will not try other rules.

    Example:

    not(X) :- X, !, fail.
    not(_).


(c) A statement has side effects when it produces results that persist
    after it returns. e.g. modifying a global variable or printouts. SML
    avoid side effects to variables by allowing only value binding: after
    a value is bound to a variable, it cannot be changed by any means.


(d) structrured programs: flow of the program is evident from the program
    text; single entry/single exit


(e) arrays: a seqeunce of homogeneous objects.



Problem 2
---------

<Expr> ::= <Expr> + <Term> | <Expr> - <Term> | <Term>
<Term> ::= <Factor> ^ <Term> | <Factor>
<Factor> ::= (<Expr>) | <Id> | <Id>(<Expr>)
<Id> ::= a | b | c




Problem 3
---------

(a)	2 1 1
(b)	2 2 2
(c)	2 1 2
(d)	2 2 2




Problem 4
---------

(a) 
val foldL = fn : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val foldR = fn : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

(b) foldL append [ ] X;

(c) foldR append [ ] X;

(e)
foldL: take a function "g", and accumulate the results when "g" works on
each item of the list progressively from the left. (Like a left-associative
operation)

foldR: take a function "g", and accumulate the results when "g" works on
each item of the list progressively from the right. (Like a right-associative
operation)

In this case, right-associative foldR is more efficient because:
    
    foldL append [ ] [[1,2], [3,4], [5,6], [7,8], [9,10]]
    => foldL append (append [ ] [1,2]) [[3,4], [5,6], ...]
    => foldL append (append (append [ ] [1,2]) [3,4]) [[5,6], ...]
    => ...
    => append ... (append (append (append [ ] [1,2]) [3,4]) [5,6]) ...
    => complexity = O(n1+(n1+n2)+(n1+n2+n3)+...) 
       where nj = length of j-th item list
    

    foldR append [ ] [[1,2], [3,4], [5,6], [7,8], [9,10]]
    => append [1,2] (foldR append [ ] [[3,4], [5,6], [7,8], [9,10]])
    => append [1,2] (append [3,4] (foldR append [ ] [[5,6], [7,8], [9,10]]))
    => ...
    => append [1,2] (append [3,4] (append [5,6] ( ... (append [9,10] [ ]))))
    => complexity = O(n1+n2+n3+..) 

Problem 5
---------

Prolog loop: p:-p.

tree: p -> p -> p -> ...  



Problem 6 (Java programming)

(a)
class A {
  A(int x,String y) { number = x; name = y; }
  private int number;
  private String name;
}
class B {
  B(int x,String y) { number = x; name = y; }
  private int number;
  private String name;
}

class arrayTest {
    public static void main(String[] args) {
	A a1 = new A(3,"hello");
	A a2 = a1;
	A a3 = a1;
	B b1 = new B(3,"hello");
	B b2 = b1;
	B b3 = b1;
	A[] a = {a1,a2,a3};
	B[] b = {b1,b2,b3};
	System.out.println(arrayEqual(a,b));  // false
	A[] c = new A[1];
	B[] d = new B[1];
	System.out.println(arrayEqual(c,d)); // true
    }
    public static boolean arrayEqual(Object[] x, Object[] y) {
	if (x.length != y.length) return false;
	for (int i=0; i < x.length; i++)
	    if (x[i] != y[i]) return false;
	return true;
    }
}

(b) answer 1: yes, see arraytest(c,d) above; // this answer is correct but
					     // not what I expected when I 
					     // made up the question
    answer 2: no, because objects of different classes can never be equal.
	      // this one was the intended answer, but wrong. Thinking back,
	      // I should have formulated the question more carefully to
	      // rule out answer 1 and make this one the correct answer.
    Please take a look at how many people gave answers similar to 
    answer 2. If a lot of people did that, I would say that we give credits
    to both answers, what do you say?


::::::::::::::
p7-1.pl
::::::::::::::

/*

Problem 7. Prolog part: (13 points)

leaf(x) denotes a leaf with value x and tree([x1,...,xn]) denotes
a tree with children x1,...,xn
*/

evalIntTree(leaf(X), X) :- number(X), !.
evalIntTree(tree([]), 0) :- !.
evalIntTree(tree([H|T]), V) :-
	evalIntTree(H,V1), evalIntTree(tree(T), V2), V is V1 + V2, !.

evalIntTree(_,'Wrong Input').  % please deduct 3 points if this clause
			       % is not given correctly.

v(X) :- evalIntTree(tree([tree([leaf(1), tree([leaf(6)]), leaf(3)]),
		    tree([leaf(5)])]), X).



::::::::::::::
p7-2.pl
::::::::::::::

/*

Problem 7. Prolog part: (13 points)

x denotes a leaf, and [x1, x2, ..., xn] denotes an internal node or 
sub-tree with children x1,...,xn 

*/

evalIntTree(X, X) :- number(X), !.
evalIntTree([], 0) :- !.
evalIntTree([H|T], V) :- 
	evalIntTree(H, V1), evalIntTree(T, V2), V is V1 + V2, !.

evalIntTree(_,'Wrong Input').  % please deduct 3 points if this clause
			       % is not given correctly.

v(X) :- evalIntTree([[1, [6], 3], [5]], X).


Problem 7 (SML Part)
--------------------


datatype IntTree = leaf of int | node of IntTree list;


fun evalIntTree(leaf(x)) = x
  |  evalIntTree(node []) = 0
  |  evalIntTree(node(h::t)) = evalIntTree(h) + evalIntTree(node(t));

val x = node([
	       node([ leaf(1), node([leaf(6)]), leaf(3) ]),
      	       node([ leaf(5) ])
	     ]);

evalIntTree(x);


(* Alternative:

fun sum(f,[]) = 0
  | sum(f,x::y) = f(x) + sum(f, y);

fun evalIntTree(leaf(x)) = x
  | evalIntTree(node(treelist)) = sum(evalIntTree,treelist);

*)