CS 4120: Introduction to Compilers
Fall 2011

Problem Set 3: Semantic Analysis

due: Friday, Sept 23, 11:59PM

changes: (Sept.20) Problems 1c and 2 were changed to bring the code more into line with Xi.

For each of the following Xi 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]))
Assume that f is declared with this signature:
```
f(x: bool, y: bool): int, int[]
```
Show the full typing derivation for the following Xi statement:
```
x:int, _ = f((true,false,true)[1], 0==1-1)
```
Suppose that Xi 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 conv
    use io
    main(args: int[][]) {
      a: int[] = (3,4,5)
      foreach (x in a)
        println(unparseInt(x*10))
    }
```
would produce this output:
```
    30
    40
    50
    
```
Give a suitable inference rule to describe the typing of this new statement form.