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 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.