Assignment 8 ANSWERS, Fall 2007, CS314

Imagine that in a programming language, arrays have their bounds as 
part of their type; that is, [1:10]int is the not the same type as [0:9]int.


	/* type definitions */
	type vector [1:10] int;
    type matrix [1:10] vector;
    type mm [1:10,1:10] int;
    type zz [1:10] vector;
	type yy [0:9] vector;
	type ss 1..10;
	type tt 5..7
	type integ int
	type s struct {int a1; ss t};
	type z struct {ss t1, ss t2};
	type w struct {int v, int u}
	type q struct {integ a2; ss a3};

	/* variable declarations */
    mm c,d;
    zz a,b;
	yy e,f
    vector v1,v2;
    matrix m1, m2;
	ss t1,t2;
	tt t3,t4;
	int t5;
	integ t6;
	s c1;
	z c3;
	w c4;
	q c2;
	

a. If we use structural equivalence for comparing types, group these
variables into sets where each set of variables has the same type:
{c,d,a,b,e,f,v1,v2,m1,m2,t1,t2,t3,t4,t5,t6,c1,c2,c3,c4}.

**********Answer***********
To decide structural equivalence, we need to know whether or not 
	1. array bounds matter (i.e., are part of the type)
	2. array dimensions matter
	3. the field names in a struct type matter
	4. the struct tag matters (as in C and the textbook)

The problem statement said YES to 1, and 2 is implied by 1. That
leaves (3) & (4), which were left open. 

First, let's consider the answer if a struct type INCLUDES field names
as part of the type.  In that case, the only two type definitions that
are structurally equivalent are matrix and zz. As a result, the
following variables are grouped, showing those of the same type in the
same group: {c,d} {a,b,m1,m2} {e,f} {v1,v2} {t1,t2} {t3,t4} {t5,t6}
{c1} {c2} {c3} {c4}.

Second, let's assume that a struct type DOES NOT INCLUDE field names
as part of the type; this makes s and q also structurally
equivalent. In that case, the following variables are grouped showing
those of the same type in the same group: {c,d} {a,b,m1,m2} {e,f}
{v1,v2} {t1,t2} {t3,t4} {t5,t6} {c1,c2} {c4} {c3}

Finally, consider the issue of struct tags. The rule (as explained in
the text and is in C) is that each anonymous tag is replaced by a new,
internal name. So types s,z,w,q would automatically be different, so
that the correct grouping would again be {c1} {c2} {c3} {c4}.

And the types
	type s1 = struct name1 {int a1; ss t};
	type s2 = struct name2 {int a1; ss t};
are structurally equivalent, name inequivalent, and inequivalent in C also.

 ******************************

b. Show the groupings of the variables which would occur if we used
name equivalence: {c,d,a,b,e,f,v1,v2,m1,m2,t1,t2,t3,t4,t5,t6,c1,c2,c3,c4}.

************Answer**************

For comparing types using name equivalence, we have the following answer:
{c,d} {a,b} {e,f} {v1,v2} {m1,m2} {t1,t2} {t3,t4} {t5} {t6} {c1} {c2} {c3} {c4}

Note, that in this example, name equivalence is the same a
'declaration equivalence', that is, appearing in the same declaration
statement.  If we had included the additional declaration "s c5;" in our
example, then {c1,c5} would be name equivalent, but not declaration
equivalent. 

Finally, if we added the declarations "type w ww; ww c6;", then the
correct answer for name (and declaration) equivalence would be {c6} {c4},  
rather than  {c4,c6}.

*****************************

c. Assume that the following statements are legal in some programming
  language.  For each statement, tell if it could be type checked at
  compile-time or run-time; briefly give a reason for your answer.
  (Note: the general rule is coercion can occur if there is no loss of
  precision in the implicit conversion.)


m1[t1] = m2[t2];  
       ** compile-time checkable and valid because i) indices of type
       ss=1..10 can be coerced into 1..10, and ii) r-value and l-value
       are both of type vector.

v1[t1] = v2[t2];
   **compile-time checkable because i) indices are ok (ss can be coerced
   to 1..10), and ii) values being assigned are ok (lhs and rhs are
   both int)

t2 = t4;
    **although t2 is an integer range type, which normally requires
    runtime checking, in this assignment statement, provided the value
    of t4 was the result of previously  checked operations, it is
    clear that a value from 5..7 can be assigned to t2 which can have
    values 1..10; therefore, this statement is compile-time checkable
    by a smart compiler.
			
t5 = t3;
    **compile-time checkable (can store an integer interval value
          in an integer variable) 
	
c1.a1 = c4.v;
      **compile-time checkable: i) can verify that both c1 and c4 have
      appropriate fields (a1 and v respectively) , and ii) assignment
      of an int value  into an int location is valid
	
c1.a1 = m1[t5,t5+1];
      **syntax error in the subscript of m1 (should be m1[t5][t5+1])
		
c4.v = c3.t1;

      **compile-time checkable (same as above)
	
t3 = t1;
      **runtime but not compile-time checkable (type tt is 5..7, type
      ss is 1..10 so one can't be sure that t1 has a value in the more
      restricted range until runtime)
	
t5 = v1[2];
   **compile-time checkable, because i) index is in the right range
   1..10, and ii) int is being assigned to an int