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.