CS 6848 - Principles of Programming Languages

Homework 3: Java Structural Subtyping

If A,B are names of interfaces, then a subtype query is of the form

A <= B ?

This query has the answer Yes if A is a subtype of B in the structural subtyping order for Java described below, and No otherwise. A grammar for a list of Java interfaces together with a list of subtype queries is given in the file interface.jj. Specification can be found here

Use JTB/GJ and JavaCC and write in Java one or more visitors which decides the subtype queries. Your main file should be called P3.java, and if P contains an input file then

java P3 < P

should print a sequence of Yes and No, each on a new line. In this Homework, we view a Java interface as an infinite, regular tree which is obtained by replacing occurrences of interface names by their definition. A path is in the set

(Identifier {0,1})*

where the identifiers are method names, 0 denotes ''argument type'', and 1 denotes ''result type''. We use id to range over Identifier. Labels are from the set S = {Int,Bool,Void,->,Interface}. An interface can now be represented as a partial function

t : (Identifier {0,1})* -> S

with domain dom(t) satisfying

dom(t) is nonempty and prefix-closed;
if t(a) = ->, then a0, a1 are in dom(t);
if a0 is in dom(t), then t(a0) is in {Int,Bool,Void,Interface};
if a1 is in dom(t), then t(a1) is in {Int,Bool,Void,Interface};
if a id in dom(t), then t(a id) = ->.

We can now define a structural subtyping order of Java interfaces by combining the ideas from structural subtyping of function types with the idea that an interface with a certain number of fields should be a subtype of an interface with fewer fields. For example, we want to have

A <= B ?  // No
B <= A ?  // Yes
C <= D ?  // No
D <= C ?  // Yes

interface A {
  A m(int a);
}

interface B {
  B m(int a);
  void p(boolean a);
}

interface C {
  int q(B a);
}

interface D {
  int q(A a);
  void r(int a);
}

Note, your program must take input from standard input and write to standard output (so that we can use the redirection).

A sample Main.java can be found here.

Grading policy
Your homework will be graded for a total of 100 marks. Of these 50 marks will be for the public testcases and 50 marks for the TAs testcases.