King Fahd University of Petroleum and Minerals	
Department of Information and Computer Science	
ICS 313:  Fundamentals of Programming Languages	
Fall 1999-2000	
Date: 14-December-1999	Final Exam: Comprehensive	Time: 8:00  – 10:30 a.m.	
Duration: 135 minutes		Total Points: 250	

Major Exam Date, Time & Location:   
Tuesday 14-December-1999, 	8:00 a.m. - 10:30 a.m. in 	19 - 301 (Section 1), 19 - 416 (Section 2), 19 - 418 (Section 3)

A.	[Imperative Programming Paradigm (Chapters 3, 4, 5, 8 and 9)	( 100 points)]

A.	[General Concepts – (5*5 = 25 points)]
Briefly answer any five of the following:
i.	After naming the two most widely used type compatibility methods, explain briefly, what each of them means.
There are two widely used type compatibility rules. The first one is name type compatibility as in Pascal and the other one is structure type compatibility as in Algol or C. In the former, two variables are considered type compatible iff they are defined to be of the same type-name or are declared to be part of the same declaration list. According to the latter compatibility, two variables are considered to have compatible types, if they have identical structures. Note that the latter subsumes the former.  It is easy to implement the name-compatibility but very quickly it puts burden on the user in forcing him to invent names. The latter is harder to implement, in particular when one permits leniency in the ordering of the components.
------------------------------------------------------------------------------------------------------------------------------------------------------------------
One point each for naming the type compatibilities, one point each for their explanation, one point for comparison.

ii.	Explain the notion of garbage collection. How is garbage reclaimed in C programs and in Java programs? Compare and contrast those two alternatives.
Garbage collection refers to the process of reclaiming space that might have served its purpose and is no longer needed. In C-language there is no automated support for it. It is the job of the programmer, to keep track of which cells are in use and which might have ceased their utility and return the useless ones to free-pool. In contrast, in Java, the programmer is blissfully unaware of these issues, since a background thread makes reclamation of space that has lost its utility. To facilitate the task of determining when a particular cell became useless, the compiler assists by maintaining a reference counter that gets incremented every time a new access path is provided to that cell and decremented, for every loss of access to that cell.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Two points for explanation, one point each on how C and Java handle, one point for comparison.

iii.	Describe the significant differences in costs (or benefits) between the two features listed in each of the following pairs. 
(a)	call by reference versus call by value 
(b)	structural type equivalence versus name type equivalence 
(c)	static scoping versus dynamic scoping 
(a)	Call by reference implements the user-perception accurately for parameters to be passed back and forth (inout mode). It also tends to be more efficient when large structures need to be passed only a few of whose components are accessed, since no new memory is allocated. However each individual access will be an indirect access costing more. Call by value (in mode) is purer in terms of side effects and aliasing problems. It can also be efficient in access time for smaller sized data items that get accessed frequently inside the called routine. Extra space is needed for the copy and time is needed to make a copy in return for the freedom from side effects as well as the more efficient element accesses.
(b)	Harder to determine structural equivalence and hence more expensive for a compiler to do that determination. But it offers better flexibility to the programmer. See (i). At runtime however there is no difference in costs for either of the alternatives in terms of execution time costs.
(c)	In static scoping, visibility rules are dictated by static level of nesting and the program structure. In contrast in dynamic scoping, the actual sequence of routine invocations determines the visibility and binding of variables. It is harder to the compiler writer to implement static scoping rules. However in return it makes things far easier for the programmer to trace and also make the execution time faster due to the avoidance of excessive search. Dynamic scoping is easier to implement but has the drawback of delaying problems and making results unexpected from one execution to another. For a given reference, the cost is fixed for static scoping and varies with call sequence for dynamic scoping. 
---------------------------------------------------------------------------------------------------------------------------
Two points each for the three parts. Yes it might fetch up to six points.

iv.	Disregarding optimizations, which variable access technique uses fewer memory references to access a variable at a static distance greater than 3. Justify your answer. 
(a)	a display
(b)	static chaining.
Since the context is for about accessing variables at a static distance of more than 3, a display approach will be better. 
The reason for this is as follows: With static chaining, a minimum of three accesses, due to static-link chasing, are needed before the variable’s address can be located. But with a display approach, one indexing operation into the display stack, and another into the activation record pointed to by the accessed display entry (and possibly one more table look up in the ARI for languages that permit variable-sized data structures as parameters) will take us directly to the desired variable, regardless of the differences in static depths between the current context and the nesting level of the variable to be accessed.
---------------------------------------------------------------------------------------------------------------------------------------
One  two points for saying display is better depending upon the level of detail. Reason/justification carries 3  4 points.

v.	Which of the following best describes the static link of an activation record for a procedure P (for a compiler that uses static chaining): 
(a)	P’s static link points to the activation record for the most recent activation of P’s caller 
(b)	P’s static link points to the activation record for the most recent activation of the block or procedure that lexically encloses P 
(c)	P’s static link points to the activation record for the most recent activation of the block or procedure that lexically encloses P’s caller.
Choice (b) is the appropriate one for static chaining. This follows from the definition of a static link and how it differs from a dynamic link.

vi.	Explain the parameter passing by name? How can it be implemented in a compiled language?
When parameter passing is done by name, the actual arguments are treated as if they are textually passed and substituted for each occurrence of the formal parameter before use/evaluation. This is a consequence of late binding. This is implemented by realizing each argument expression in a call to a subprogram, as a parameter less local procedure whose execution amounts to reevaluating the argument expression. In the called routine, every access to the formal parameter is actually a call to the parameter less routine before the final simplification and evaluation. Such parameter-less routines are referred to as thunks.
---------------------------------------------------------------------------------------------------------------------------------------
Two points for the explanation of the technique. One point for mentioning late binding. Two points for the realization using thunks.

vii.	After listing three fundamental data type construction techniques, briefly explain each.
The three most widely used data type construction techniques are: (a) homogeneous aggregation, i.e., arrays (b) heterogeneous aggregation, i.e., records or structures, and (c) references, i.e., pointers/addresses. Arrays are used to model situations where a mechanism is needed to group a number of elements of the same type. Records are for keeping track of diverse kinds of elements. References (Addresses/Pointers) to refer to an appropriate place or object.
---------------------------------------------------------------------------------------------------------------------------------------
Two points to mention them. One point each for their explanation.

B.	[Formal Syntax and Semantics – (25 points)]

i.	[Syntactic Description Methods (15 points)]
Consider the following grammar.

	<E> ::= <bool exp> | <int exp>
	<bool exp> ::= <bool var> | not <bool exp> 
	<bool var> ::= <id> 
	<int exp> ::= <int var>  { <op> <int exp> } | ( <int exp> )
	<int var> ::= <id>
	<id> ::= x | y | z 
	<op> ::= ‘+’ | ‘-’ | ‘*’ | ‘/’

a)	Briefly explain the major differences between BNF (Backus-Naur Form) and Extended BNF as formal methods for describing syntax.	(3 points)
EBNF is a mere extension of the basic BNF with three metasymbols for option, [],  choice, () and  repetitions, {}. The metasymbols of EBNF are meant to overcome the complexity problem associated with  the BNF  notation when describing non-trivial syntaxes.  However, both BNF and EBNF have the same expressive power.  The advantage of EBNF over BNF is that the former is said to provide syntax descriptions that are more readable. EBNF is usually used by compiler writers as a basis for implementation.

b)	Write two different sentences in the language generated by the above grammar.	(6 points)
Examples: x, not y, x+y*z

c)	Prove that the above grammar is ambiguous, by exhibiting a sentence with two or more derivations.	(6 points)

The ambiguity of the above grammar may be proven, for example, by showing that the sentence, x+y*z,  has two distinct derivation sequences:
First note that the EBNF rule  
<int exp> ::= <int var> {<op> <int exp>} | (<int exp>)
can be expanded to have the following instances, for example :

<int exp> ::= <int var> 	R1
<int exp> ::= <int var> <op> <int exp>	R2
<int exp> ::= <int var> <op> <int exp> <op> <int exp>	R3
Now using left-most derivation, we can derive the sentence x+y*z by first applying rule R2 or by applying R3 first:

<E> ::= <int var> <op> <int exp>     applying rule R2
•	<id> <op> <int exp>
•	x <op> <int exp>
•	x + <int exp>
•	x + <int var> <op> <int exp>  applying R2 again
•	x + <id> <op> <int exp>
•	x + y <op> <int exp>
•	x + y * <int exp>
•	x + y * <int var>
•	x + y * <id>
•	x + y * z
Alternatively, we could derive this sentence by first applying rule R3 followed by other rules :

          <E>  ::= <int var> <op> <int exp> <op> <int exp>  applying R3
•	<id> <op> <int exp> <op> <int exp>
•	x <op> <int exp> <op> <int exp>
•	x + <int exp> <op> <int exp>
•	x + <int var> <op> <int exp>
•	x + <id> <op> <int exp>
•	x + y <op> <int exp>
•	x + y * <int exp>
•	x + y * <int var>
•	x + y * <id>
•	x + y * z

ii.	[Semantic Description Methods (10 points)]
a)	Briefly explain one of the three major semantic models for describing meanings of programs.	(3 points)
Operational Semantics:  In this approach, the meaning of a program is described by executing its statements on a simulated or actual machine. A virtual machine is required to describe the semantics of a high-level language because a hardware pure interpreter would be too expensive and a software pure interpreter is also not without problems. For example, the detailed characteristics of the particular computer would make actions difficult to understand. Furthermore, such a semantic definition would be machine-dependent.
Overall operational semantics can be good if used informally but can be extremely complex otherwise (e.g., VDL).
Axiomatic Semantics: This approach is based on formal logic (first order predicate calculus). It was originally meant for formal program verification.  The meaning of a program is defined in terms of axioms (hence the name) or inference rules defined for
each statement type in the language (to allow transformations of expressions to other expressions). Logical assertions are placed before and after (i.e., preconditions and postconditions) program statements.
Developing axioms or inference rules for all of the statements in a language is difficult.  The proof process easily becomes complex even for simple programs.  Axiomatic sementics is a good tool for correctness proofs, and an excellent framework for reasoning about programs, but it is not as useful for language users and compiler writers
Denotational Semantics: This approach is the most abstract semantics description method.  It is based on recursive function theory (originally developed by Scott and Strachey, 1971).  The reasoning process here consists of defining a mathematical object for each language entity and a mapping function that maps instances of the language entities onto instances of the corresponding mathematical objects. This approach provides a framework for thinking about programming in a highly rigorous way.
Because of the complexity of denotational descriptions, they are of little use to language users.  However, it provides an excellent method of concisely describing a language.

b)	Assuming you are given the following simple instructions of a virtual machine:
{label:}	statement;	if   cond   goto label	expr1 = expr2	goto label  
Write down the operational semantic definition of the for statement of the Java language.	(7 points)

	for (e1; e2; e3) {	e1;
	    STMTS	Label 1:	if e2 = 0 goto Label 2
	}	STMTS
	restSTMTS	e3;
	goto Label 1;
	Label 2:	restSTMTS

C.	[Parameters Handling in Subprogram – (25 points)]

Consider the following program in a C/Java-like language. What will be printed in each of the parts (i), (ii) and (iii).

void main() {
	int par1 = 2, array[3] = {5, 7, 9} ;
	printf (”Before calling the subprogram P %d %d %d %d\n”, par1, array);
	P(par1, array[2]);
	P(array[0], array[1]);
	printf (”After calling the subprogram P %d %d %d %d\n”, par1, array);
} 

void P(by_value int p1, by_value int p2) {
	int result;
	if (p1 <= p2) { 
	result = p2;
	p2 = p1;
	p1 = result;
  }
}

i)	Assuming that parameters are passed by value.
Before calling the subprogram P 2 5 7 9 
After calling the subprogram P 2 5 7 9

ii)	Assuming that parameters are passed by reference instead of by value.
Before calling the subprogram P 2 5 7 9
After calling the subprogram P 9 7 5 2

iii)	Assuming that parameters are passed by name instead of by value.
Before calling the subprogram P 2 5 7 9
After calling the subprogram P 9 7 5 2

D.	[Subprograms Implementation – (25 points)]
Using static chaining, draw the run­time stack (growing upwards), for the following Pascal program when execution reaches the point marked. Include in your drawing the static links (labeled SL), dynamic links (labeled DL), arrows showing where each link points, variable names (labeled with the variable name), and variable values (including parameters). Use a heavy line between activation records. Be sure to label each activation record with the name of the procedure it is for, and clearly indicate to which activation record each static or dynamic link points. {If you need more space then use the facing page to show your solution}

program p; 
	function r(n: integer): integer; 
	begin (* of r *)
	    (*   draw stack when control reaches here *)
	    r := n 
	end; (* of r *)

	procedure q(m: integer); 
	var v: integer; 
	begin (* of q *)
	    if m >= 2 
	    then q(m­1) 
	    else v := r(m) 
	end; (* of q *)
begin (* of p *)
	q(3) 
end (* of p *).

				
			
Stack top

	local			
	parameter	1	n	
ARI for r	dynamic link			
	static link			
	return (to q)			
	local		v	
	parameter	1	m	
ARI for q	dynamic link			
	static link			
	return (to q)			
	local		v	
	parameter	2	m	
ARI for q	dynamic link			
	static link			
	return (to q)			
	local		v	
	parameter	3	m	
ARI for q	dynamic link			
	static link			
	Return (to main, i.e., p)			
	local			
				
ARI for p				
	.			
	stack			

Incorrect static link –5 points. Incorrect dynamic link –5 points. Incorrect value for local variable v –5 points. No explicit return mentioned to a particular routine –3 points. Each missing ARI –5 points.

2.	[Objected-Oriented Programming Paradigm (Chapters 10 and 11)	( 62.5 points)]

A.	[General Concepts of Object Oriented Programming – (25 points)]
Answer any five of the following.
.	Explain the concept of inheritance. Comment on the advantages and disadvantages of inheritance. What are the different kinds of inheritance that are available in the widely used languages?
Inheritance refers to the ability to make use of the functionality of a piece of software by extending it and either refining or redefining or masking or adding new behavior to the previously defined one. Such a facility enables better code organization through the reduction of code duplication while having the provision of building up the necessary sophistication of functionality in gradual stages. The primary drawback of inheritance is the unnecessary or undesirable functionality inherited as part of the desired inheritance. It is that combination of unwanted or undesirable inheritance with the desired, which distorts the picture. Also, changes to parent/ancestor classes usually affect descendant classes, due to dependency through inheritance. Inheritance is a dependency and constraint binding a subclass with its ancestor classes. Any such constraint imposes its own restrictions in permitting arbitrary changes to a class.
There are two kinds of widely available inheritance: Single inheritance in which case each class can have at most one parent class and Multiple inheritance, in which case a class can inherit from more than one class directly. There is yet another classification that is introduced in languages like Java: interface inheritance (purely for the purpose of specifying functionality) and implementation inheritance. These two are respectively supported by multiple inheritance using interfaces and single-inheritance using classes in Java.
---------------------------------------------------------------------------------------------------------------------------------------
Two points for inheritance, 1 point each for advantage and disadvantage, 1 point for different kinds of inheritance.

.	Explain polymorphism with an example in a language such as Java or C++. How does that relate to dynamic binding?
Polymorphism refers to the multiplicity of operations in response a method invocation of an object. For example, a draw() method of different graphic shapes may initiate different kinds of actions based on which object (shape) we are talking to. 
One consequence of polymorphism is the simplification of naming by avoiding giving different names for additional methods that refer to the same concept. Also,
•	A polymorphic variable can be defined in a class that is able to reference (or point to) objects of    the class and objects of any of its descendants
•	When a class hierarchy includes classes that override methods and such methods are called    through a polymorphic variable, the binding to the correct method must be dynamic
class Shape {
    void draw() { * * * } 
}
class Line extends Shape {
    void draw() { code to draw a line }
}
class Circle extends Shape {
    void draw() { code to draw a circle }
}
Shape obj = new Circle(…);
obj.draw();
obj = new Line(…);
obj.draw();
 Since the methods are based on objects and the objects themselves may not be known until run time, Polymorphism is related to dynamic binding of methods in response to a message.
---------------------------------------------------------------------------------------------------------------------------------------
Three points for Polymorphism and two for dynamic binding.

iii.	Briefly explain the difference between static and dynamic type checking. What kind of type checking does Java have: static or dynamic?
If for every operation, the types of operands can be inferred and checked to permit only appropriate application of an operation, at compile time, then it is referred to as static type checking. Note that this is a one-shot operation performed by the compiler. There is no more need to do this checking at run time, every time an operation is performed.
On the other hand in many object-oriented systems, it may not be possible to know the actual object that comes in as a parameter or might have been instantiated dynamically. So the type checking has to be deferred until the time of actual application of operation. This results in dynamic type checking. Unlike static type checking, there is a heavy price to be paid in the dynamic type checking, as the necessary checks need to be performed each time an operation is performed. However, modern object oriented systems, for the sake of flexibility offer this when needed, despite the price to be paid performance wise.
Java language attempts to achieve the best of both. It employs static type checking for primitive types and the objects whose classes can be figured out at compile time, leaving out the remaining ones or explicitly cast objects to be checked at run time.
---------------------------------------------------------------------------------------------------------------------------------------
Two points each for each of the two kinds of type checking. One point about how Java handles the situation.

iv.	Briefly explain the difference between overloading and overriding of methods in Java. Give an example.
Overloading refers to the process of giving different definitions to different methods all sharing the same name, but having different number and types of arguments (signature). Such a facility is a highly desirable feature in terms of language usability as the programmer need not invent artificial names for similar concepts just because they require different kinds of handling based on the number and types of parameters. Note that this can equally be a feature of an imperative language.
Overriding on the other hand comes into picture in the object-oriented framework as a consequence of inheritance. When a subclass redefines by giving a new body to a method that it inherited from one of its ancestor classes, the old definition is considered overridden. The new definition is the overriding definition.
class A {
    int m1(int j) { some body } 
    int m2(int j) { some body }
}
class B extends A {
    int m1(int j, float f) { body for a new case } 
    int m2(int j) { some new body }
}
The method m1(int j, float f) of B  overloads m1(int j) of A, by adding a new definition with a new signature.
The method m2(int j) of B overrides m2(int j) of A, with a new definition. The descendants of B will inherit this newly overridden definition for m2(int j).
---------------------------------------------------------------------------------------------------------------------------------------
Two points each for the explanation of overloading and overriding. One point for an example.

v.	Explain the terms information-hiding and encapsulation. What is their relationship to each other?
1.	Encapsulation: which is the grouping of subprograms and the data they manipulate into a single unit.
Some of the advantages are:
* Better organization of programs
* Modification to the code or data are done in a single area.

2.	Information Hiding: which is ability of hiding the internal details of the ADT from its users (clients).
Some of the advantages are:
* Clients code is independent on the details of these ADT.
* Provides better reliability, as clients cannot change the internal data or code of the ADT.

Information hiding is a good engineering principle for the construction of maintainable systems. Encapsulation on the other hand is an enforcement mechanism of visibility rules on the part of a language.
At the same time the two are separate issues. One can practice good information hiding principles even in languages (such as C) that do not support module level encapsulation. A poor structuring/design may expose several access paths even when using a language with module level encapsulation. To achieve enforceable information hiding, instead of the one achieved through conventions, encapsulation is necessary.
---------------------------------------------------------------------------------------------------------------------------------------
Two points each for each for the explanation of information hiding and encapsulation. One point for explaining the relationship between them.

vi.	What is a constructor? What is a destructor? When will they get invoked?
Constructors are functions/methods to initialize the data members of instances created. They do not create the objects themselves. They may allocate storage if part of the object is heap-dynamic. They can include parameters to provide parameterization of the objects. They are implicitly called when an instance is created. They may or may not be callable explicitly depending upon the language. Usually, they have the same name as that of its class.

Destructors are functions/methods to cleanup after an instance is destroyed; usually just to reclaim heap storage. They are usually implicitly called when the object’s lifetime ends. In languages like C++, they can be explicitly called. They use a name, which is obtained by prepending a tilde (~) to the classname.
---------------------------------------------------------------------------------------------------------------------------------------
One and a half point each for each of the two methods. One point each about the time when they get invoked.

vii.	Explain the notions of interfaces, abstract classes, and concrete classes in the context of Java language. Justify the roles of each in the development of a large application.
An interface in the Java language is a collection of signatures spelling out certain functionality or for designing a contract. It does not provide any implementation. Interfaces can inherit signatures from one or more interfaces (multiple inheritance). 
An abstract class is a class that has one or more methods labeled as abstract for which no functionality is provided. Due to the incompleteness of functionality, abstract classes cannot be instantiated. However, they serve to provide generic functionality independent of particular data representation.
A concrete class is one that does not have any abstract methods. It can be instantiated.
Classes in Java inherit from other classes using single-inheritance, i.e., one parent class only.

In the development of a large application, early on it is important to work with interfaces to evolve communicating subsystems that interact through the standards set by interfaces. Since there is really no coding at that stage, it tends to be a cheap operation but resulting in clear specifications for subsystems. Abstract classes enable bulk of the generic functionality development without bothering too much about tuning or alternatives. Concrete classes fill in that detail. Since the level of the detail greatly increases as we move from purely the subsystem decomposition at the interface level to concrete classes, it is appropriate that a developer concentrates on increasingly narrowed down version of the problem.
---------------------------------------------------------------------------------------------------------------------------------------
Two points each for each of the three notions and one more point if anybody addressed the issue of roles of all these notions in a large application.

B.	 [Object Oriented Program Design  – (3* 12.5 = 37.5 points)]
In this problem you’ll be sketching the implementation of binary tree data structures. Begin with by structuring the functionality needed as an interface hierarchy. Proceed with the realization of functionality by sketching abstract classes that do not worry about the representation details. Finally complete the details by providing one of the several alternative implementations for the Binary search trees. You may use the syntax of Java language to facilitate expression of your design.
(a)	Define interfaces for (i) a Collection of data items that can be compared, ordered, sorted, and enumerated (ii) a BinarySearchTree that extends a collection with at least an additional four methods that are specific to binary search trees.
(b)	Design an abstract class AbstractBinarySearchTree that implements the interface BinarySearchTree. It will assume the methods: Object getRootContent(), BinarySearchTree getLeftChild(), BinarySearchTree getRightChild(), void setRootContent(Object), void setLeftChild(BinarySearchTree), void setRightChild(BinarySearchTree)  and implements the rest.
(c)	Sketch the details of one of the two implementation alternatives: (i) ArrayBinarySearchTree, an array of records, one for each node in the tree (ii) LinkedBinarySearchTree, a dynamically allocated collection of Node objects that are maintained through links or object references.

(a)	The following interfaces are appropriate
//====================== Interfaces =========================================

interface Iterator {
	Object next();
	Object previous();
	boolean hasMore();
}

interface Node {
	boolean equals(Object);
	boolean isLess(Object);
	boolean isGreater(Object);
}

interface Visitor {
	void apply(Node);
}

interface Collection {
	boolean isEmpty();
	int size();

	boolean equals(Collection);

	Collection sorted();

	boolean add(Node);
	boolean drop(Node);
	boolean exists(Node);

	boolean addAll(Collection);
	boolean dropAll(Collection);
	
	Iterator iterate();
}

interface BinarySearchTree extends Collection {
	Object getNode();
	boolean setNode(Object);
	BinarySearchTree getLeftChild();
	boolean setLeftChild(BinarySearchTree);
	BinarySearchTree getRightChild();
	boolean setRightChild(BinarySearchTree);

	Collection preOrderSequence();
	Collection inOrderSequence();
	Collection postOrderSequence();

	void preOrderTraversal(Visitor);
	void inOrderTraversal(Visitor);
	void postOrderTraversal(Visitor);

	boolean isNil();
	boolean isALeaf();
	int height();
	int leaves();
	int nodes();

	boolean isIsomorphic(BinarySearchTree);

	BinarySearchTree fromCollection(Collection);
	BinarySearchTree clone();
	BinarySearchTree mappedClone(Visitor);

}

(b)	The abstract class AbstractBinarySearchTree provides most of the generic functionality as needed by the BinarySearchTree interface.
//====================== Abstract Class =====================================

public abstract class AbstractBinarySearchTree implements BinarySearchTree {
	abstract Node getNode();
	abstract boolean setNode(Node);
	abstract BinarySearchTree getLeft();
	abstract boolean setLeft(BinarySearchTree);
	abstract BinarySearchTree getRight();
	abstract boolean setRight(BinarySearchTree);
	
	Collection preOrderSequence() {
		ArrayList nodes = new ArrayList();
		if (!this.isNil()) {
			nodes.add(this.getNode());
			nodes.addAll(this.getLeft().preOrderSequence());
			nodes.addAll(this.getRight().preOrderSequence());
		}
		return nodes;
	}
	Collection inOrderSequence(); // similar to preOrderSequence
	Collection postOrderSequence(); // " "

	void preOrderTraversal(Visitor v) {
		if (this.isNil()) return;
		v.apply(this.getNode());
		getLeft().preOrderTraversal(v);
		getRight().preOrderTraversal(v);
	}
	void inOrderTraversal(Visitor);   // straightforward adaptation of preOrderTraversal
	void postOrderTraversal(Visitor); // " "

	boolean isNil() {
		return ((getNode() == null) && (getLeft() == null) && (getRight() == null));
	};

	boolean isALeaf() {
		return ((getNode() != null) && (getLeft() == null) && (getRight() == null));
	};

	int height() {
		if (this.isNil()) return 0;
		return 1 + Math.max(getLeft().height(), getRight().height());
	};
	int leaves(); // straighforward adaptation of height()
	int nodes(); // ""

	boolean isIsomorphic(BinarySearchTree t) {
		if (this.isNil() && t.isNil()) return true;
		// next line is only a speedup mechansim. Its omission won't affect correctness
		if (nodes() != t.nodes()) return false;

		if (getNode() != t.getNode()) return false;
		BinarySearchTree l = this.getLeft(), r = this.getRight(),
			lt = t.getLeft(), rt = t.getRight();
		if ( l.isIsomporphic(tl) && r.isIsomorphic(tr) ||
			 l.isIsomporphic(tr) && r.isIsomorphic(tl) ) return true;
		return false;
	}

	BinarySearchTree fromCollection(Collection); // not shown
	BinarySearchTree clone(); // " "
	BinarySearchTree mappedClone(Visitor); // " "
}

(c)	We pick LinkedBinarySearchTree. The following is an extension of AbstractBinarySearchTree

//====================== Concrete classes====================================

public class LinkedBinarySearchTree extends AbstractBinarySearchTree 
	implements BinarySearchTree {

	Node node = null;
	BinarySearchTree left = null, right = null;

	Node getNode() { return node };
	boolean setNode(Node node) { 
		this.node = node; 
		return true; // success.
	}
	BinarySearchTree getLeft() { return left; }
	boolean setLeft(BinarySearchTree t) { left = t; return true; }
	BinarySearchTree getRight() { return right; }
	boolean setRight(BinarySearchTree t) { right = t; return true; }
}

3.	[Functional Programming Paradigm (Chapters 13 (14) and Haskell Material)	( 62.5 points)]

A.	[General Concepts of Functional Programming – (20 points)]

Answer any four of the following with brief but adequate explanation.
i.	What is currying and where does it come from? Give an example.
Currying is named after the logician Haskell B. Curry, whose name also the Haskell functional programming language immortalizes. Currying is the process of viewing a function of n argument as a function of one argument that returns another function of (n-1) arguments.  As a simple example,
	Add3:: Int->Int->Int->Int
	add3 x y z = x+y+z
	value      = add3 7
Then value is a function (of type Int->Int->Int) requiring two arguments and (value 11) is a function (of type Int->Int) requiring one argument.  Applying a function to fewer arguments than it requires is called partial application. For a transformation called full laziness to be applied to functional sub-expressions, support for currying is a necessity.

ii.	An important concept in functional programming is referential transparency.  What does it mean? Give an example to support your answer.
Referential transparency.  Functional languages have no assignment and thus programs in them do not depend on global states. An expression E whose result solely depends on the values of its syntactically correct sub-expressions is said to be referentially transparent.  This property allows sub-expressions to be replaced, wherever they occur, by their values (i.e., results of evaluating the sub-expressions).
Notice that referential transparency cannot hold in languages that can have global states.  Consider the following C-like program:

f(x)
{
    return x+y  /* y is a global variable */
}

g(z)
{
  a = f(1);
  y = y+z
  return a+f(1) ;
}
Can we substitute a for f(1) in the return statement of g?  This is not possible because first f(1) and the second f(1) will return different values because of the change of state caused by the assignment y = y + z.

iii.	What is a higher-order function? Give a couple of examples.
Higher-order functions.  A higher-order function is a function that can take one or more function as argument and can return a function as its result or both.  Examples:
map f [] = []
map f (x:xs) = f x:map f xs
do g base = foldr g base
In the above examples, both f and g are function and, thus, map and do are both higher-order functions.

iv.	What is lazy-evaluation? How can it be used to cope up with infinite data structures in list-comprehensions?
Lazy evaluation. This is an evaluation regime that ensures that evaluation of expressions is delayed until as late as possible.  This provides the guarantee that expressions are evaluated when and only when they are needed.  This minimizes unwanted computations and can increase the expressive power of a programming language.  Note that all imperative languages perform eager evaluation where expressions are evaluated before their values are ascertained to be required.
Lazy evaluation can be used to manipulate potentially infinite data structures.  As a simple example we have
	natsFrom n = n:natsFrom (n+1)
This example generates the list of natural numbers starting at n.  Without lazy evaluation it will be unnatural or impossible to express such kinds of computations.

v.	Why are functional languages referred to as sugar-coated lambda-calculus?
Functional languages as sugared lambda calculus.  Functional languages are said to be sugar-coated lambda calculus because every functional program can be translated into an equivalent lambda calculus expression.  Functional languages simple add embellishing features as ‘syntactic sugaring’ on top of the bare lambda calculus.  These embellishing features do not add to the expressive power of the lambda calculus.  They are only added for the convenience of the programmers.

vi.	Briefly compare imperative programming and functional programming.
Imperative Languages and Functional languages compared
A Imperative Languages:
-	Efficient execution
-	Complex semantics
-	Complex syntax
-	Concurrency is programmer designed
-	Referentially opaque
-	Do not support lazy evaluation
-	Prescriptive; programmers must specify how a computation is to be performed
-	Abstractions of the von Neumann architecture
B Functional Languages:
-	Simple semantics
-	Simple syntax
-	Inefficient execution
-	Programs can automatically be made concurrent
-	Referentially transparent
-	Support lazy evaluation
-	Descriptive; programmers must specify only what is to be computed
-	Have lambda calculus as their computational foundation

B.	[Haskell Program Tracing – (12.5 points)]

Consider the following functions defined in Haskell’s Standard Prelude.

>null	:: [a] -> Bool
>null []	= True
>null (_:_)	= False

>tail	:: [a] -> [a]
>tail (_:xs)	= xs

>map	:: (a -> b) -> [a] -> [b]
>map f xs 	= [ f x | x <- xs ]

>take                :: Int -> [a] -> [a]
>take 0 _             = []
>take _ []            = []
>take n (x:xs) | n>0  = x : take (n-1) xs
>take _ _             = error "Prelude.take: negative argument"

These functions are used in the two programs below.  Study these programs carefully and then write down the result held in one of the names answerA  of part (i) or answerB of part (ii).

i)	
>myFilter xs      = [ x | x <- xs, null (tail [ y | y<-xs, x==y ]) ]
>answerA = myFilter [2,3,5,7,5,11,2]

[3,7,11]

ii)	
>idM :: Int -> [[Int]]
>idM 0 = []
>idM (n+1) = take (n+1) (1:[0,0..]) : map (0:) (idM n)
>answerB = idM 3

[[1,0,0],[0,1,0],[0,0,1]]

C.   [Writing Haskell Programs – (30 points)]
Answer any two of the following using Haskell language:

i)	Consider the following data type. 
> data Tree a = Atom a | List [Tree a] 
Define the function 
> mapTree :: (a -> b) -> Tree a -> Tree b 
The following are examples. 
mapTree (+ 1) (Atom 3) = (Atom 4) 
mapTree (+ 1) (List []) = (List []) 
mapTree (+ 10) (List [Atom 2, Atom 5, List [Atom 2], List [], Atom 1]) 
= (List [Atom 12, Atom 15, List [Atom 12], List [], Atom 11]) 
mapTree odd (List [Atom 2, Atom 5, List [Atom 2], List [], Atom 1]) 
= (List [Atom False, Atom True, List [Atom False], List [], Atom True])

Possible solution
>data Tree a = Atom a | List [Tree a]  deriving Show
>mapTree :: (a -> b) -> Tree a -> Tree b 
>mapTree f (Atom a) = Atom (f  a)
>mapTree f (List ts) = List (map (mapTree f) ts)

ii)	Write a function 
disjoint :: (Eq a) => [(a,b)] ­> [(a,b)] ­> Bool 
such that disjoint r1 r2 is true if no first element of a pair in r1 is also a first element of a pair in r2 and vice versa. For example: 
disjoint [] [(3,7), (9,2)] = True 
disjoint [(3,4), (5,7)] [(7,5), (4,3)] = True 
disjoint [(1,'a'), (3,'c'), (2,'b'), (4,'b')] [(5,'e'), (2,'f')] = False 
disjoint [(5,'e'), (2,'f')] [(1,'a'), (3,'c'), (2,'b'), (4,'b')] = False

Possible solution
>disjoint :: (Eq a) => [(a,b)] -> [(a,b)] -> Bool 
>disjoint list1 list2 = and [x1 /= x2 | (x1,y1) <- list1, (x2,y2)<-list2]

iii)	Define a function. 
> subseteq :: (Eq a) => [a] ­> [a] ­> Bool 
such that subseteq s1 s2 is true just when all elements of s1 are elements of s2. The following are examples. 
subseteq [] [3,4] = True 
subseteq [3,4] [] = False 
subseteq [3,4,4,3] [4,3] = True 
subseteq [3,4,4,3] [3,4,1] = True 

Possible solution. 
>subseteq :: (Eq a) => [a] -> [a] -> Bool 
>subseteq list1 list2 = and [elem x list2 | x <- list1]

iv)	Define a function 
> setProduct :: (Eq a, Eq b) => [a] ­> [b] ­> [(a,b)] 
that takes two lists, as and bs, and returns the list of all pairs of elements, with the first element of each pair from as and the second from bs. For example
setProduct ([]::[Char]) [1,3] = [] 
setProduct [2, 7, 10] [1, 3] = [(2,1), (2,3), (7,1), (7,3), (10,1), (10,3)] 
setProduct ['a', 'b', 'c'] [17, 21, 3, 4] = [('a',17), ('a',21), ('a',3), ('a',4), 
('b',17), ('b',21), ('b',3), ('b',4), ('c',17), ('c',21), ('c',3), ('c',4)] 

Possible solution. 
>setProduct :: (Eq a, Eq b) => [a] -> [b] -> [(a,b)] 
>setProduct list1 list2 = [(x,y) | x <- list1, y <- list2]

4.	[Logical Programming Paradigm (Chapter 14 (15) and Prolog Material)	( 25 points)]

A.	[General Concepts of Logic Programming – (15 points)]

Answer any three of the following short questions:
i)	Briefly explain how logic (Prolog) programs work?
The program stores all the given data in terms of facts and rules (clauses). When an answer (or a query) is required it is given to the program as a goal. The program negates his goal and add it to the clauses it has. Then the program applies the inference rule resolution on clauses to try to generate a contradiction., which indicates that the goal is satisfied. In this process some variables will be instantiated to some values which will returned as answers.

ii)	What is resolution and how does it work?
Resolution is an inference rules that is used by Prolog. It is applied on clauses to eliminate some clauses and their negations. The final objective is to obtain the embty clause, or the contradiction. Simply resolution takes a clause of the form C and a clause of the form C  A and produces the clause A.

iii)	What is meant by unification? How is it used in logic programming?
Unification is the process that takes two terms and tries to make them identical. It replaces variables in these terms by terms or other variables to unify these terms. It is used when resolution is applied between clauses to unify similar clause to make them identical. This can lead at the end to the elimination of negated clauses from the database.

iv)	Briefly define the following Prolog terms: clause, fact and query. 
A clause is logical formula of the form H:- C1, C2,  Cn where each of the C s is a term. H is the head of the clause and the conjunction C1, C2 …Cn represens the body. The clause states that H is true if C1, C2 …Cn  are all true.
A fact is a clause with no body. It is a predicate that states that some thing is true 
A query, or a goal, is a clause with no head. It is a conjunction of  predicates that need to be shown true. 

B.	 [Prolog Program Tracing – (10 points)]

Select either Choice I or II below and then answer both part (a) and (b) below:

Choice I	Choice II	
p1(X,[X|T]).	p3(X,[X|T]).	
p1(X,[H|T]) :- p1(X,T). 	p3(X,[H|T]) :- p3(X,T).	
		
p2([ ],S,S).	p4(X,L,L) :- p3(X,L).	
p2([H|T],S,R) :- p1(H,S), p2(T,S, R).	p4(X,[H|T],[X,H|T]) :- X<H.	
p2([H|T],S,[H,U]) :- p2(T,S,U).	p4(X,[H|T],[H|L]) :- p4(X,T,L).	

a)	Briefly describe the functionality of program p2 in Choice I, or program p4 in Choice II
p2 is a predicate that takes two sets and returns their union.
p4 is a predicate that takes an element and a list and inserts the element in the right place in the list provided that the list does not already contain that element.

b)	Trace the program and show the output of  p2([3], [1,2,4], AnswerA) , for Choice I, or 
 p4(3, [1,2,4] ], AnswerB)  , for Choice II.

For p2([3], [1,2,4] ], AnswerA) AnswerA is [3,1,2,4]
For p4(3, [1,2,4] ], AnswerB) AnswerB is [1,2,3,4]