Quiz 2013

In this preparation we work only with static methods.

We explore basic code generation for nested pattern matching. To avoid discussing representations of types, we work with integer divisibility patterns, defined as follows.

If a is a positive integer constant and b is a non-negative integer constant, we will say that an integer v matches the pattern (a*x+b) if and only if: v is positive, and (v-b) is divisible by a. If it matches, the value bound to x is given by (v-b)/a.

Give rules to generate code for (possibly nested) integer divisibility patterns.

DivisibilityCodegen.txt

Discuss inefficiencies of the straightforward solution and suggest strategies for improvement.

Consider a language with method calls and method definitions that take type parameters. Assume the only primitive types are Int and Bool and the only expression is method call. Give type rules for this language.

BasicParametric.txt

The following Java program defines a Cell class, which stores an integer that can only be set once, and defines its subclass ReusableCell, which has additional functionality to reset the value. It then declares and assigns values to arrays of Cell and ReusableCell objects.

class Cell { int x;
boolean init;
 
    void set(int arg) {
	if (init) 
	    throw new RuntimeException("Initialized a cell twice");
	else {
	    x = arg;
	    init = true;
	}
    }
 
    int get() {
	if (init) 
	    return x;
	else 
	    throw new RuntimeException("Called get on uninitialized cell");
    }
}
class ReusableCell extends Cell {
    void reset(int arg) {
	x = arg;
	init = true;
    }
}
class Test {
    public static void main(String[] args) {
	ReusableCell[] rcells;
	Cell[] cells;
 
	rcells = new ReusableCell[2];
	rcells[0] = new ReusableCell();
	rcells[0].reset(42);
 
	cells = rcells;
	cells[1] = new Cell();
	cells[1].set(13);
 
	rcells[1].reset(7);
    }
}

Understand the program above and answer the following:

1. Do you believe this program should type check using Java compiler? Try and report result of compilation.
2. If needed, make the smallest possible modification to make the program compiles in Java and report any lines that you needed to modify, if any.
3. Run the resulting program and explain what happens. Pay attention to line numbers.
4. Can you suggest any alternative behavior of run-time virtual machine that would result in a different execution of this example?

Replace the array with a generic container type that can hold one element, which we can read (method get) and which we write (method set). Write signatures for these methods as well as the code analogous to the example above. Write one version in Java and one version in Scala. Sketch type rules for assignment, method calls, object creation, and subtyping rules.

Consult: http://docs.oracle.com/javase/tutorial/java/generics/subtyping.html