CS 412/413
Introduction to Compilers
Spring 2001

Homework 3: Semantic Analysis & IR Generation

due: Friday, March 2, in class

1. For each of the following Iota statements or expressions, state whether it is well-typed in some type context and if so, what its type is. If it is well-typed, give a type context in which it has a type and provide the corresponding typing derivation. If it is not well-typed in any type context, show why.
   1. length(new int[2](0)) + 2
   2. a:int = 2 + (return 2)
   3. if ("abc" < x) 3 else false
   4. L & (("foo" + L) == "fool")
   5. !f(s)[length s]

2. Suppose that Iota is extended with a new "foreach" statement:
   
   foreach (id in E) S
   
   The expression E must evaluate to an array. The foreach statement executes the statement S once for each element of the array, with the variable id bound to the array element at index i-1 on iteration i. For example, the program:
   
   uses io.print, conv.itos
main(args:array[string]) : int = (
    i: int = 0;
    a: array[int] = new array[int][2]((i = i + 1));
    foreach (X in a) print(itos(X));
    0
)
   
   would produce this output:
       1
     2
   
   1. Give a suitable inference rule to describe the typing of this new statement form.
   2. Give a suitable syntax-directed translation rule or rules to describe intermediate code generation for this new statement form.
      
3. The language C supports pointer types. Given a type T, the type T* represents a pointer to a value of type T. A pointer is represented as a memory address. There are two operations associated with pointers:
   • the ampersand operator (&). The expression &E returns a pointer to its operand E.
   • the star operator (*). The expression *E, where E evaluates to a pointer, returns the value to which this pointer points. An expression of this form can also appear as the left-hand side of an assignment statement, in which case the assignment overwrites the location pointed to. (Confusingly, the star token is used in two different ways in C: as a unary operator on expressions (*E), and in the construction of pointer types (T*).)

   Suppose we were to extend Iota with pointer types in the manner of C. (We will ignore C's support for pointer arithmetic.) Here are some brief examples of how we might use these new features:

   swap(x:int*, y:int*) = (temp:int = *x; *x = *y; *y = temp)
a:int = 0; b:int = 1; swap(&a, &b); b==0
x:string = "foo"; z:string* = &x; *z = "bar"; x=="bar"

1. Give suitable inference rules for describing the typing of uses of the two new operators. Describe any modifications to the rest of the Iota type system needed to support pointer types.
2. Give suitable syntax-directed translation rules to extend intermediate code generation to these additional operators.