Homework 06: Type Checking Arrays

Problem 1: Java's type system

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;
	    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();
	cells = rcells;
	cells[1] = new Cell();

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?

Problem 2

Please read first the subtyping rules for the language in your project.

Next, consider the same language extended with arrays:
In the syntax, add the rules

 Expressions ::= new Identifier[Expression]
 Type :== Identifier[]

What should the new typing rules be, in order to prevent all runtime errors. Note that Java's type system doesn't prevent all of them.

Write down all the rules you need to add. You might want to consider expression of the form e1[e2], e1.length, new ID[e], e1[e2]=e3, and (very important) the subtyping rules for arrays.