CS 4120: Introduction to Compilers
Fall 2009

Problem Set 3: Semantic Analysis and IR Generation

due: Thursday, October 15, 11:59PM

1. For each of the following Iota₉ terms, give a typing context in which it type-checks, or else explain why it can't be done.
   1. if (x + 2 == 4) return x;
   2. while (f(x,y)) x = x+f(y,x);
   3. (a: int[], _) = (b, ((3, f) y));
2. Show the full typing derivation for the following Iota₉ statement:

   (x:int, _) = ((1,2,3) 1, 0==1-1)

3. Show how to translate the Iota₉ short-circuit or operation, e₁|e₂, to IR. In particular, define C⟦e₁|e₂, t, f⟧. (Hint: look at the translation of &.)
4. Suppose that Iota is extended with a new "foreach" statement:
   

       foreach (x 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 x bound to the array element at index i−1 on iteration i. For example, this program:

       use io
       main(args: string[]): int = {
         i: int = 0;
         a: int[] = (3,4,5);
         foreach (x in a) {
   	println(unparseInt(x*10));
         }
       }

   
   would produce this output:

       30
       40
       50
       

   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.