>
> HW2 Due 5/12/98
> 
> 1. For an elementary data type in a language with which you are
> familiar, do the following:
> 

	I used the programming language C, the type integer.

> (a) Explain the difference between the type itself, variables of that
> type, and constants of that type.

	The type itself is the semantic idea, consisting of the allowable
		values, allowed operators and the size of variables and
		costants.
	Variables of that type are references to locations in memory where 
		values of that type may be stored and manipulated.
	For constants of that type, the value is determined in
		the source.  Constants may not change.

> (b) Show a situation during the execution where a data object of that
> type exists that is neither a variable nor a constant.

	In the statement 

		a = b + foo(c);  /* Where foo returns type int */

		we see two examples, the return value of foo(c) and also the 
		intermediate result of b + foo(c) (which will eventually
		be stored in a).  During execution, neither is a variable 
		nor a constant.

[TA's comment: Some of you considered functions as such a data object.  
In some sense, this is also true, because you can treat functions as
data, and pass them as parameters.]
	
> (c) Explain the difference between data objects of that type and the
> values that those data objects may contain.

	Data objects of type int are the locations in memory
		which are interpreted to represent integers.
	The values that the data objects contain are some combination of
		bits (zeros and ones) which are meaningless without an
		associated type.

> 
> 2. For a language with which you are familiar and uses static type
> checking, give examples of two constructs that cannot be checked
> statically. For each construct, determine by running a test program
> whether the language implementation provides dynamic type checking or
> leaves the construct unchecked during execution.
> 

	The C language

	Example 1: Array bounds (they are unchecked).
	During Execution: The construct is unchecked during execution.
		
	Example 2: Subroutines may have a variable number of parameters.
	During Execution: If there are too many parameters, extras are
		ignored.  If there are too few, the subroutine leaves
		the parameters undefined (garbage results).

	Example 3: Unions.

[TA's Comment:  Some of you considered that's also the case for mixed 
arithmetic of long, short, or float.  Actually, in that case, the types are
checked, and coerced (i.e., implicit type conversion) according to a certain 
rule.  So there is type checking.  There is also type checking for overloaded
functions as well as polymophic (virtual in C++) functions.]

> 3. Suppose the declaration of a vector V is given using an enumeration
> type as the subscript range, e.g.
> 
>        ClassType = (Fresh, Soph, Junior, Senior, Graduate);
>        V: array[ClassType] of real;
> 
> (a) Show the storage representation (including descriptor) that would
> be appropriate for V and give the accessing formula for computing the
> location of a component of V[i].

	Represent ClassType as integers (0-4)
	Address(V[ClassType]) = Address(V[0]) + ClassType*Sizeof(real)

> (b) How would the storage representaion and accessing formula change
> is V were declared as:
>      
>        V:array [Junior .. Graduate] of real;

	Address(V[ClassType]) = Address(V[0] + (ClassType-2)*Sizeof(real)

[TA's Comment: It is important to interpret 
(Fresh, Soph, Junior, Senior, Graduate) as integers, otherwise, the compiler
cannot use the symbols to figure out the actual addresses.]

> 
> 4. Give the accessing formula for computing the location of component
> A[I,J,K] of a 3-D array A, declared as:
>          
>                A: array[LB1..UB1, LB2..UB2, LB3..UB3]
> 
> where A is stored 1) colwmn-major, and 2) row-major.

	1) A[I,J,K] = Address(A[LB1,LB2,LB3]) + 
		      [ (UB2-LB2+1)*(UB1-LB1+1)*(K-LB3) +
		        (UB1-LB1+1)*(J-LB2) +
		        (I-LB1) ] * SizeOf(Element)

	2) A[I,J,K] = Address(A[LB1,LB2,LB3]) + 
		      [ (UB2-LB2+1)*(UB3-LB3+1)*(I-LB1) +
		        (UB3-LB3+1)*(J-LB2) +
		        (K-LB3) ] * SizeOf(Element)

[TA's comment: Many of you just give me an alpha symbol, or the words
"starting address" without any explanation of what it is.  Because you
know the bounds of the array, you should be able to give me a more
concrete answer, i.e. Addr(A[LB1,LB2,LB3]).]

> 
> 5. In studying the premliminary design of language BL you note that BL
> includes a stack data structure and three operations:
> 
>     NewTop(S, E), which adds the element E to the top of the stack S,
>     PopTop(S), which deletes the top element of stack S, 
>     GetTop(S), which returns a pointer to the location in stack S of
> the current top element.
> 
> What is wrong with the design of these operations ? How could they be
> redefined to correct the problem ?
> 

	Problems:
	1) There is no way to initialize the stack.
	2) There is no bounds checking.
	3) You can affect the stack directly by manipulating the memory
		location returned by GetTop(S).

	Suggestions:
	1) Provide a way to initialize the stack, e.g. NewStack().
	2) a) Have PopTop return an error code when the stack is empty.
	   b) Have NewTop return an error code when there is no memory 
		available.
	   c) Haev GetTop return an error code when the stack is empty.
	3) Have two parameters for GetTop(S, E) where E is a place in
		the calling routines memory to store the top element.