Description
PROBLEM 1 (20 points) Consider the following type declarations:
TYPE
T1 : int
T2 : structure {a: float;}
T3 : structure {b: int; a: pointer to T4;}
T4 : structure {a: T1; b: pointer to T3;}
T5 : function of T3 returns T7;
T6 : function of T4 returns T8;
T7 : array [1][10] of T6
T8 : array [1][10] of T5
1. (10 points) Which types are structurally equivalent? Show the step by step table.
Now Consider the following variable declarations in conjunction to the above type declarations:
VAR
x : T2;
y : T2;
z : T3;
w : T4;
u, v : pointer to T1;
p : pointer to T4;
2. (10 points, 2.5 points each) Assume that assignments between variables are allowed
if the types of the variables are equivalent. For each of the following, list all type
equivalence schemes under which the expression is valid. Consider name equivalence,
internal name equivalence, and structural equivalence for each case. Assume that if two
variables are equivalent under name equivalence, they are also equivalent under
internal name equivalence.
• x = y;
• u = v;
• w = z;
• p = w.b;
PROBLEM 2 (20 points, 4 points each)
fun f (a, b, c, d) = a(c,d) + b[c[d]] > 1.1
The abstract syntax tree of f is the following:
Fill in the blank, reducing all types to basic types and type constructors if possible:
• Type of a =
• Type of b =
• Type of c =
• Type of d =
• Type of f =
PROBLEM 3 (20 points) Consider the following code in C syntax (use static scoping):
# include <stdio.h>
int g (int n)
{
n = 2;
return n*2;
}
int f (int x, int y)
{
int i;
int j;
i = x * y;
j = y;
x = x * 3;
y = i – 2;
return g(x);
}
int main ()
{
int a[3] = {1, 0, 3};
int b = 2;
int c = f(a[b], b);
printf (“%d -%d -%d -%d -%d\n”, b, a[0], a[1], a[2], c);
return 0;
}
• (10 points) If parameters are passed by value, the output of this program is (Explain by
showing the call arguments to each function)
• (10 points) If parameters are passed by reference, the output of this program is (explain
with box and circle)
PROBLEM 4 (20 points, 4 points each) Fully b-reduce the following expressions, show b
reduction steps.
1. (𝜆𝑎. 𝜆𝑒. 𝑎 𝑒) (𝑎 𝑒 𝑥)
2. (𝜆𝑎. 𝜆𝑖. 𝑎 𝑖) (𝜆𝑎. 𝑖 𝑎)
3. (𝜆𝑒. 𝜆𝑥. 𝜆𝑦. 𝑏 (𝑎 𝑏 𝑐)) (𝜆𝑎. 𝜆𝑖. 𝑎 𝑖)
4. (𝜆𝑎. 𝜆𝑖. 𝑖 𝑎) (𝑎𝑙𝑝ℎ𝑎)(𝜆𝑎. 𝑎 𝑎)
5. ((𝜆𝑒. 𝑒 𝑒) (𝜆𝑎. 𝑎)) (𝑎 𝑒)
