CSE 340 HOMEWORK 3: Type Checking

Problem 1. Consider the following type declarations

TYPE

  A1  :
integer;

  A2  :
pointer to real;

  A3  :
pointer to integer;

  T1  :
structure { x : integer; }

  T2  :
structure { x : A;       next : pointer
to integer; }

  T3  :
structure { a : integer; b    : float; }

  T4  :
structure { b : float;   a    : integer; }

  T5  :
structure { a : pointer to T5; b : pointer to T6; c : pointer to T7; }

  T6  :
structure { a : pointer to T6; b : pointer to T5; c : pointer to T5; }

  T7  :
structure { a : pointer to T6; b : pointer to T5; c : pointer to T9; }   T8  :
structure { a : pointer to T7; b : pointer to T7; c : pointer to T10; }

  T9  :
array [4][5] of T8;      // array 4 rows
5 columns

  T10 : array [4][5] of T7;

Assuming the most
permissive definition of structural equivalence, which types are structurally
equivalent?
 Therefor, A1, A2 and A3 are
NOT structurally equivalent to any type declarations T1-T10, nor are they
structurally equivalent to each other.
 Therefor, T1-T8 are not
structurally equivalent to A1, A2 or A3 as previously proven, nor are they
structurally equivalent to T9 or T10 as previously stated. Likewise, none of
the STRUCTs T1-T8 are structurally equivalent because each STRUCT shares a
different set of types, none of which being structurally equivalent to the
other.



T3 and T4 appear to be
ALMOST STRUCTURALLY EQUIVALENT, BUT THEY’RE NOT. The two types would be
considered different using a liberal interpretation of structural equivalence,
because the order of arguments is inconsistent between type declarations.

 Therefor, T9 and T10 are
not structurally equivalent to any former type declarations, as previously
proven. Likewise, T9 and T10 are not structurally equivalent since their types
are not structurally equivalent, as previously proven.


In total, none of the type
declarations are structurally equivalent.


—————————————

Consider the following
variable declarations in conjunction to the above type declarations


VAR                           // var declaration
section   s : T9;   t : T9;  
u : T10;

  v : array [5][4] of T8;   w, z : struct {            int a;            struct T5* next;

         };  
x, y : struct {            int
a;            struct T5* next;

         };


:
function of T9 returns int;


:
function of T9 returns A;  m : int;   n : A;Problem
2.
Consider the following
definition          fun f(a, b, c) = a[b] * c + 1

Using Hindley-Milner type inference, determine the type of f.
Powered by