ICS 313:  Fundamentals of Programming Languages	
Fall 1999-2000	
Date: 13-November-1999	Key to Major Exam II: Imperative Programming Paradigm & Abstract Data Types 	Time: 5:00  – 6:30 p.m.	
Duration: 90 minutes		Total Points: 100	

1.	[Short Questions – (7*5 = 35 points)]
Briefly answer any seven of the following:
.	Define narrowing and widening conversions.

A narrowing conversion is one that converts an object to a type that cannot include all the values of the original type, e.g. double to float, while a widening conversion one that converts an object to a type that can include at least approximation of all the values of the original type, e.g. int to float,

.	What is short-circuit evaluation?

A short-circuit evaluation of an expression is one in which the result is determined without evaluating all of the operands and/or operators

.	What is the definition of a control structure and a block?

A control structure is one that allows the selection among alternatives or allows the repetition of statements. A block is a compound statement, a collection of statements that can be abstracted as a single statement, with data declaration.

.	What are the design issues for counter-controlled loop statements?

•	What is the type and scope of the loop variables?
•	What values does the loop variable have at loop termination?
•	Should it be legal for a loop parameter to be changed in the loop, and if so does this affect loop control?
•	Should the test for completion be at the top or at the bottom of the loop?
•	Should the loop parameters be evaluated only once, or once for every iteration?

.	What are the advantages and disadvantages of keyword parameters?

The main advantage is that the order of the parameters in the call statement is not important, while the main disadvantage is that the user of the subprogram must know the names of the formal parameters.

.	What are the two fundamental design considerations for parameter-passing methods?

1.	Efficiency: Passing addresses of parameters in some cases, as for arrays, is more efficient than passing values.
2.	Good development rules encourages minimizing subprogram access to outside.

.	Define shallow and deep binding for referencing environments of subprograms that have been passed as parameters.

Shallow binding is the case in which the referencing environment of a subprogram that is passed as parameter is of that program who passed it, while deep binding is the case in which the referencing environment is of the program that declared it.

.	Present four reasons why implementing subprograms as in ALGOL-like languages is more difficult than implementing subprograms as in FORTRAN 77?

1.	Subprograms can be recursive.
2.	Variables are dynamically allocated and de-allocated during the call to and return from the program.
3.	Handling of references to non-local variables.
4.	Activation records are created and destroyed dynamically.

.	What are the two steps in locating a non-local variable in a static scoped languages?

1.	Locating the actual activation record in which the variable is defined (Chain Offset).
2.	Locating the actual position of the variable within the activation record (local-offset).

.	Explain two methods of implementing blocks.

1.	Handling them as subprograms with no parameters. So activation records are dynamically created for them.
2.	Reserving a separate area for block variables within the ARI of the procedure in which they are defined

.	What are the two parts of the definition of abstract data type? Discuss their advantages.

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 since clients cannot change the internal data or code of the ADT.

.	What are the language design issues for abstract data types?

1.	Encapsulate a single type, or something more?
2.	What types can be abstract?
3.	Can abstract types be parameterized?
4.	How are imported types and operations qualified?

2.	[Loops parameters and Arrays – (10 points)]
Consider the following C program segment:
int sum, n, y, x, A[100] ;
sum = 0;
n = 1;
y = 16;
for (x = 1; x < y; x = x + n) {
	sum = sum + A[x];
	n = n + x;
	y = y – n;
}
Which elements of the array A will be summed under each of the following evaluation strategies for evaluation of variable n and y in the iteration head?
a)	Evaluate y once on initial entry; evaluate n once on entry and again after each execution of the body.
n=1	y=16
x=1	x < y = 1 < 16 = true	sum = 0+A[1]	n=2	y=14
x=x+n =1+2=3	x < y = 3 < 16 = true	sum = 0+A[1]+A[3]	n=5	y=9
x=x+n =3+5=8	x < y = 8 < 16 = true	sum = 0+A[1]+A[3]+A[8]	n=13	y=-4
x=x+n =1+2=21	x < y = 21 < 16 = false	sum = 0+A[1]+A[3]+A[8]	n=13	y=-4

b)	Evaluate both n and y on entry and re-evaluate after each execution of the body.
n=1	y=16
x=1	x < y = 1 < 16 = true	sum = 0+A[1]	n=2	y=14
x=x+n =1+2=3	x < y = 3 < 14 = true	sum = 0+A[1]+A[3]	n=5	y=9
x=x+n =3+5=8	x < y = 8 < 9 = true	sum = 0+A[1]+A[3]+A[8]	n=13	y=-4
x=x+n =1+2=21	x < y = 21 < -4 = false	sum = 0+A[1]+A[3]+A[8]	n=13	y=-4

3.	 [Expression Evaluation – (10 points)]
Let the function FUN be defined as

function FUN (var K : integer) : integer;
    begin
        K := K + 4;
        FUN := 3 * K – 1;
        K := K - 6;
    end;

Suppose FUN is used in a program as follows:

…
Ind1 := 12;
S1 := (Ind1 / 4) + FUN (Ind1);
Ind2 := 12;
S2 := FUN (Ind2) + (Ind2 / 4);
What are the values of S1 and S2
a.	if the operands in the expressions are evaluated left to right?
Value of S1 = 3 + (3*16-1) = 50	Value of S2 = (3*16-1) + 10/4 = 49.5
b.	if the operands in the expressions are evaluated right to left?
Value of S1 = (3*16-1) + 10/4 = 49.5	Value of S2 = 3 + (3*16-1) = 50

4.	 [Parameters handling in Subprogram – (16 points)]
Consider the following naïve program that attempts to print two times each of the given the numbers given by its user until a zero is provided. It also returns the square of that number. You may assume the availability of a library routine getInt() that reads and returns an integer from a given channel, i.e., stdin or keyboard in this case.

int getInt();	// prototype of the library function

int printSquare(byvalue int n) {
    int square = n * n;
    printf(“(%d * %d) = %d”, n, n, square);
    return square;
} 

int main(int argc, char * argv[]) {
    int result = 0;
    printf(“Give numbers whose squares you want.\n”);
    printf(“A zero terminates the program.\n”);

    while ( (result = printSquare( getInt() ) ) > 0 )
        printf(“\tresult = %d\n”, result);
} 

a)	Explain the technique of parameter passing by name.
Parameter passing by name is achieved through late binding the formal parameters as they occur in the body of a called subprogram to those of actual arguments at the time of use. In a way it has the effect that is similar to that of macro-expansion at the place of call prior to execution. 
Usually this scheme is implemented using parameter evaluating routines called thunks. Each thunk is like a wrapper providing the proper actual argument in place of formal parameter for each use.

b)	Show the output produced on an input sequence of 1, 2, 3, 4, 5, 6, 7, 0, assuming that the parameter to printSquare() is passed by value.
In the following a tab is shown by ………………
Notice the last line that stops after the third zero.

(1 * 1) = 1………………result = 1
(2 * 2) = 4………………result = 4
(3 * 3) = 9………………result = 9
(4 * 4) = 16……………result = 16
(5 * 5) = 25……………result = 25
(6 * 6) = 36……………result = 36
(7 * 7) = 49……………result = 49
(0 * 0) = 0

c)	Answer part (ii) again, if the parameter passing by name is employed for printSquare() instead?
In the case of call by name, due to late binding, the effect is as if the actual parameter getInt() is invoked every time the formal parameter n is used. This produces rather unexpected behavior on the part of the program as shown below. Notice the last line that stops after the third zero.

(3 * 4) = 2………………result = 2
(7 * 0) = 30

5.	 [Nonlocal variables handling in Subprogram – (14 points)]
Show the stack with all activation record instances, including static and dynamic chains, when execution reaches position 1 in the following skeletal program:

program main;
	procedure C; forward;
    var i   : integer;
	procedure A( flag : boolean, i : integer );
        var j   : integer;
            k   : static integer := 0; 
                (* initilaized to zero at the time of space allocation *)
    	procedure B(i : integer);
            var el  : integer;
    	begin (* of B *)
            el := k + i;
            A(false, el);
    	end; (* of B *)
	begin (* of A *)
        j := i + k;
        k := j + k;
        if (flag) then B(j)
                  else C(k);
	end; (* of A *)

	procedure C( i : integer);
        var m   : integer;
            n   : static integer := 2;
    	procedure D(i : integer);
            var j   : integer;
    	begin (* of D *)
            m := j + n;
            (* <============== 1   *)
    	end; (* of D *)
	begin (* of C *)
        i := m + n;
		D(i);
	end; (* of C *)

begin (* of main *)
    i := 3;
	A(true, i);
end. (* of main *)

				
			
Stack top

	local	0	j	
	parameter	2	i	
	dynamic link			
ARI for D	static link			
	return (to C)			
	local	0  2	m	
	parameter	12  2	i	
	dynamic link			
ARI for C	static link			
	return (to A)			
	local	9	j	
	parameter	6	i	
	parameter	F	flag	
	dynamic link			
ARI for A	static link			
	return (to B)			
	local	6	el	
	parameter	3	i	
ARI for B	dynamic link			
	static link			
	return (to A)			
	local	3	j	
	parameter	3	i	
ARI for A	parameter	T	flag	
	dynamic link			
	static link			
	Return (to main)			
ARI for main	local	3	i	
Static variable n	2			
Static variable K	0  3  12			
	.			
	stack			

6.	[Subprogram – (15 points)]
Answer only one of the following two parts, i.e. either part (a) or part (b).
a)	Trace the following program and show what it will print.

program main;
	var x	: integer;
	procedure Q( var i : integer; function R(j : integer):integer );
	begin (* of Q *)
	x := 4;
	writeln("In Q before call to R: i = ", i, " x = ", x);
	i := R(i);
	writeln("In Q after call to R: i = ", i, " x = ", x);
	end; (* of Q *)

	procedure P;
		var i 	: integer;

		function fun( k : integer ):integer;
		begin (* of fun *)
			x := x + k;
			fun := i + k;
			writeln("In fun(): i = ", i, " k = ", k, " x = ", x);
		end; (* of fun *)
	begin (* of P *)
		i := 2;
		Q(x, fun);
		writeln("In P after call to Q: i = ", i, " x = ", x);
	end; (* of P *)

begin (* of main *)
	x := 7;
	P;
	writeln("In main: x = ", x);
end. (* of main *)

In Q before call to R:	i = 7	x = 4
In fun():	i = 2	k = 7	 x = 11
In Q after call to R:	i = 9	x = 11
In P after call to Q:	i = 2	x = 11
In main:	x = 11

b)	Suppose that you are writing a compiler for some block-structured language X, which supports static scoping. Using pesudo code write a procedure CALL_PROCESSING that represents all activities performed by a program when there is a call to some subprogram. In a similar fashion, write a procedure RETURN_PROCESSING that represents all activities performed by a program as part of its return to a calling routine. Clearly state all your assumptions.

Assumptions:
	ARI_Stack: is an array with a maximum size of Max-Size used to hold the ARI of the subprograms.
	CREATE_ARI: is a procedure that will create a new ARI with the appropriate number of cells.
	The static link of a subprogram is already determined by the compiler and ready for storage.

	CALL_PROCESSING (Called Subprogram)	(9 points)
	Begin
	If (local variables are dynamic) then
	Allocate space for all local variables of Called Subprogram)
	Bind local variables to allocated space
	End if
	Save the current status of the calling program.
	CREATE_ARI(Called Subprogram)
	Store the Return Address of the calling program in the first available position in the ARI
	Store the static link of the called subprogram in the second position of the ARI
	Store the dynamic link of the called subprogram in the third position of the ARI
	Store all actual parameters of the called subprogram into the ARI. If the subprogram is a function allocate a space in the ARI to receive its value later
	Based on the Parameter passing mode pass either copies, addresses or names of actual arguments to the elements in the stack.
	Allocate free slots in the ARI for all the local variables of the called subprogram
	Execute the first statement in the Called subprogram
	End {/* CALL_PROCESSING /*}

RETURN_PROCESSING	(6 points)
	Begin
	If (in-out mode is implemented) then
	Copy back all the out values from local to the actual parameters.
	End if
	If the subprogram is a function then return its value to the calling subprogram.
	If (local variables are dynamic) then
	De-allocate space of all local variables to the storage heap
	End if
	Retrieve the return address from the bottom of the ARI and Remove the ARI from the top of the ARI-Stack.
	Restores the status of the calling program as it was before the call.
	Execute the statement whose address was retrieved.
	End {/* RETURN_PROCESSING /*}

7.	 [Java Material  {BONUS} – (15 points)]
Answer the following in the context of Java language and the Java Development Environment. Answer only one of the following two parts, i.e. either part (a) or part (b).
(a)	Answer briefly the following questions.	– [((3*1) + (2*1+2) + (2+4*0.5) + (4) = 15 points)]
i.	What is CLASSPATH? Who uses it? Why is it needed?
ii.	What do you need to do in order to produce documentation automatically? Which tool produces it? How should you write your comments to allow a documentation generator to do its job?
iii.	What are Applets? Give four important methods of an Applet and explain their significance.
iv.	Give a Java program that counts the number of tables in an HTML page at a given URL. (Hint: A Table in HTML is surrounded by: <table> contents </table>).

i.	It is an environment variable whose value is a sequence of pathnames separated by semicolons. These pathnames refer to directories containing class files. Various JDK tools like javac, java, javadoc, jdb, javah etc. use this to locate, read and load dynamically those class files when needed.
ii.	By appropriately documenting a program as per specifications (see Chapter 18 of Java Language Specification by Gosling, Joy, and Steele) the javadoc tools can produce a hyperlinked document. One should however put those comments that should appear in the documentation using the documentation comment:
iii.	/** comment in html according to the structure defined in chapter 18 of JLS */ 
iv.	Such comments are to appear in front of packages, classes, fields in classes, and methods in classes.
v.	An applet is a restricted java application expected to run in a controlled environment, usually provided by a browser. As such it will be having a substantial functionality obtained through inheritance from its ancestor classes, namely, Object, Component, Container, Applet. However, it is restricted in terms of what it can do with the local resources. The following is the sample skeleton of an applet.

    import java.applet.*;
    import java.awt.*;
    
    public class BasicApplet extends Applet {
        public void init() {
            // Called once by the browser when it starts the applet.
        }
        public void start() {
            // Called whenever the page containing this applet is made visible.
        }
        public void stop() {
            // Called whenever the page containing this applet is not visible.
        }
        public void destroyed() {
            // Called once when the browser destroys this applet.
        }
        public void paint(Graphics g) {
            // Called whenever this applet needs to repaint itself.
        }
    }

vi.	import java.io.*;
vii.	import java.net.*;
viii.	import java.util.*;
ix.	
x.	/** 
xi.	 * CountTablesInAnHTMLPage is a simple utility that counts the number of tables in a URL.
xii.	 * @see java.io.BufferedReader#readLine()
xiii.	 * @see java.net.URL#openStream()
xiv.	 * @version 0.0.1alpha
xv.	 */
xvi.	
xvii.	class CountTablesInAnHTMLPage {
xviii.	    public static void main(String[] args) {
xix.		if (args.length != 1) {
xx.			System.err.println("Usage: \n\tjava CountTablesInAnHTMLPage url");
xxi.			System.exit(1);
xxii.		}
xxiii.	
xxiv.		StringBuffer contents = new StringBuffer();
xxv.		try {
xxvi.		    URL url = new URL(args[0]);
xxvii.		    BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()));
xxviii.	
xxix.		    String str;
xxx.		    while ((str = in.readLine()) != null)
xxxi.		        contents.append(str + "\n");
xxxii.		    in.close();
xxxiii.	} catch (MalformedURLException e) {
xxxiv.		} catch (IOException e) {
xxxv.		}
xxxvi.		String str = contents.toString().toLowerCase();
xxxvii.	int count = 0;
xxxviii.	int nextMatchPosition = -1;
xxxix.		while ( (nextMatchPosition = str.indexOf("<table", nextMatchPosition+1)) > 0 )
xl.			count++;
xli.		System.out.println("Ignoring comments, the URL " + args[0] + " has " + count + " tables.");
xlii.		}
xliii.	}

(b)	Answer briefly the following questions. 	– [((5*1) + 10 = 15 points)]
i.	With a one line description of each, provide the operations on an abstract data type: stack of general objects 
ii.	Give a Java class that implements a stack. Also develop a main() routine that can illustrate a few operations on stacks.

import java.io.*;
import java.util.*;

/** 
 * inplements the familiar stack datastructure.
*/

public interface Stackable {
	public void push(int) throws StackException {}
	public int pop() throws StackException {}
	public int top() throws StackException {}
	public boolean isEmpty() {}
}

class StackException extends Exception {
}

class Stack implements Stackable {
	public static final int DEFAULT_SIZE = 100;
	private int[] elements;
	private int	count = 0;
	private int size;

	// constuctors
	Stack() { this(DEFAULT_SIZE); }
	Stack(int size) {
		if (size <= 0 || size > 100000)
			throw new StackException("Stack size too little or too much.");
		this.size = size;
		elements = new int[size];
	}

	public void push(int element) throws StackException {
		if (count == size)
			throw new StackException("Attempt to insert into an already full stack. Overflow");
		elements[count++] = element;
	}

	public int pop() throws StackException {
		if (count == 0)
			throw new StackException("Attempt to pop an element from an empty stack. Underflow");
		return elements[--count];
	}

	public int top() throws StackException {
		if (count == 0)
			throw new StackException("Attempt to read the top of an empty stack. Underflow");
		return elements[count-1];
	}

	public boolean isEmpty() {
		return (count == 0);
	}

    public static void main(String[] args) {
		try {
			Stack s = new Stack();
			for (int i = 0; i < 10; i++)
				s.push(i*i);
			while (!s.isEmpty()) {
				System.out.print("top = " + s.pop());
				if (!s.isEmpty) System.out.print("top = " + s.top());
				System.out.println();
			}
		}
   	}