Most of you have worked with Java at some point in your Computer Science careers. You may have noticed that the languages that you have built so far have been quite different from Java. Now you get the chance to see how Java is made!

The Language

Your programs will now consist of a list of classes and a expression which is your program's main function.

A class consists of a class name, a super class, a list of fields, and a list of methods. Each class must have a super class (it is not optional), but there is implicitly a top-level class called Object that has no fields or methods. Each field has a name and a type associated with it and each method has a return type, name, parameter name, and parameter type associated with it. For simplicity we have made methods single-arity, so methods can only take in one argument and must return a value. For example, to make a class called Foo that extends Object with number field named x and a method named bar that takes in a number and returns the sum of x with the input number would be:

(class Foo extends Object
  (fields (x Num))
  (methods (method Num bar (Num y) (+ (get this x) y))))

The grammar for fields is similar to the one that you have seen in records and the grammar for a method is similar to methods in java:

(method <return-type> <method-name> (<param-type> <param-name>) <method-body>)


Just like Java, the language has subtyping from inheritance. Subclasses are subtypes of superclasses. Any type is also a subtype of itself.

When inheriting from a superclass, a subclass can override methods defined in the superclass. The return type of the overriden method must be a subtype of the return type in the superclass, and the argument type in the superclass must be a subtype of the argument type in the subclass. (This is called covariance/contravariance.) Here is an example:

  (class A extends Object
    (methods (method A foo (B x) (...))))
  (class B extends A
    (methods (method B foo (A x) (...)))))

There is no method overloading (i.e., there cannot be two methods in the same class with the same name). Duplicate method names will be rejected by the parser.

It is possible for a class to declare a field with the same name as a field in one of its superclasses.

You can instantiate an instance of a class with

(new <class-name>)

Static vs. Dynamic Types

The static type of an object is the type that it is declared to have, whereas the dynamic type of an object is the type that is was instantiated with at runtime. So for instance, in the Java program:

A ac = new C();

the static type of ac is A, while the dynamic type of ac is C. This example can also be written in this assignment:

(let (A ac (new C)) ...code-that-uses-ac...)

Fields and Methods

The fields of an object can be set by calling (set <object-expr> <field-name> <value-expr>) and accessed by calling (get <object-expr> <field-name>). (set ...) should return the new value being assigned. Both get and set should use the field given by the static type of the object.

To call a method on an object, you can use (call <object-expr> <method-name> <arg-value>). The method called is determined by the dynamic type of the object it is called on.

Instantiation (new)

When an instance of an object is instantiated, all of its number field values should be initialized to 0 and all of its object field values should be initialized to null. null in this language is a little different than in Java since it takes a type. This makes the type checking portion of the assignment much easier.


Fields and methods of a certain class can reference its own class. Therefore, we can have a class, Foo, which has a field named f of type Foo. Methods can also have recursive calls and call other methods within the class by passing the this keyword as the object-expr to the call function.


Other types of expressions such as addition and do work as in Paret. ifzero works like if from previous assignments, except that instead of checking weather the condition is true, it checks weather it is 0. (So, for example, (ifzero 0 1 2) should evaluate to 1.)

Compiler/Type Checker

Before interpreting a Java program, you need to check its types and compile it to a mostly untyped representation. Unlike in type-checker you must implement subtyping with inheritance as in Java. Also, objects are automatically upcasted whenever a superclass is expected.

The following errors can be raised during type checking:

When compiling get and set expressions, you have to add the static type of the object whose field is being accessed.


The interpreter takes in a program and interprets its main method.

There are a couple of tricky parts of the semantics to note:


<program> ::=
    | (program (classes <class> ...) <expr>)

<class> ::=
    | (class <class-name> extends <class-name>
        (fields <field> ...)
        (methods <method> ...))

<field> ::=
    | (<field-name> <type>)

<method> ::=
    | (method <type> <method-name> (<type> <id>) <expr>)

<expr> ::=
    | <num>
    | <id>
    | (+ <expr> <expr>)
    | (do <expr> <expr> ...)
    | (let (<type> <id> <expr>) <expr>)
    | (ifzero <expr> <expr> <expr>)
    | (get <expr> <field-name>)
    | (set <expr> <field-name> <expr>)
    | (call <expr> <method-name> <expr>)

    | (new <class-name>)
    | this
    | (null <class-name>)

<type> ::=
    | Num
    | <class-name>

Abstract Syntax

### Source language (before compilation) ###

data JProgramSrc:
  | src-program(classes :: List<JClassSrc>, psvm :: JExprSrc)

data JClassSrc:
  | src-class(name :: String, superclass :: String,
            fields :: List<JFieldSrc>, methods :: List<JMethodSrc>)

data JMethodSrc:
  | src-method(ret-type :: JType, name :: String,
      arg-type :: JType, arg :: String, body :: JExprSrc)

data JFieldSrc:
  | src-field(name :: String, field-type :: JType)

data JExprSrc:
    # Fields & Methods:
  | src-get-field(obj :: JExprSrc, field :: String)
  | src-set-field(obj :: JExprSrc, field :: String, val :: JExprSrc)
  | src-method-call(obj :: JExprSrc, meth :: String, arg :: JExprSrc)
    # Objects:
  | src-new(class-name :: String)
  | src-this
  | src-null(class-name :: String)
    # Basic Language Stuff:
  | src-let(arg-type :: JType, arg :: String, val :: JExprSrc, body :: JExprSrc)
  | src-num(num :: Number)
  | src-plus(left :: JExprSrc, right :: JExprSrc)
  | src-ifzero(cond :: JExprSrc, consq :: JExprSrc, altern :: JExprSrc)
  | src-do(exprs :: List<JExprSrc>)
  | src-id(var-name :: String)

### Core language (after compilation) ###

data JProgram:
  | j-program(classes :: List<JClass>, psvm :: JExpr)

data JClass:
  | j-class(name :: String, superclass :: String,
            fields :: List<JField>, methods :: List<Method>)

data JMethod:
  | j-method(name :: String, arg :: String, body :: JExpr)

data JField:
  | j-field(name :: String, field-type :: JType)

data JExpr:
    # Fields & Methods:
  | j-get-field(obj :: JExpr, class-name :: String, field :: String)
  | j-set-field(obj :: JExpr, class-name :: String, field :: String, val :: JExpr)
  | j-method-call(obj :: JExpr, meth :: String, arg :: JExpr)
    # Objects:
  | j-new(class-name :: String)
  | j-this
  | j-null
    # Basic Language Stuff:
  | j-let(arg :: String, val :: JExpr, body :: JExpr)
  | j-num(num :: Number)
  | j-plus(left :: JExpr, right :: JExpr)
  | j-ifzero(cond :: JExpr, consq :: JExpr, altern :: JExpr)
  | j-do(exprs :: List<JExpr>)
  | j-id(var-name :: String)

### Shared ###

data JType:
  | t-num
  | t-obj(class-name :: String)

type TEnv = List<TEnvCell>

data TEnvCell:
  | t-env-cell(name :: String, var-type :: JType)

type Env = List<EnvCell>

data EnvCell:
  | env-cell(name :: String, val :: JVal)

data JVal:
  | v-num(num :: Number)
  | v-null
    # `class-name` is the dynamic type of the object.
    # `field-sets` stores all of the object's fields, grouped by class.
  | v-object(class-name :: String, field-sets :: List<FieldSet>)

data FieldSet:
    # Since fields are stored in a MutableStringDict,
    # you don't need to use store-passing style like you did for interp-state.
  | field-set(class-name :: String, fields :: D.MutableStringDict<String, JVal>)

data TypeError:
  | err-class-not-found(class-name :: String)
  | err-field-not-found(field-name :: String)
  | err-method-not-found(method-name :: String)
  | err-type-mismatch(expected :: JType, found :: JType)
  | err-this-outside-of-method
  | err-non-object(val :: JType)
  | err-unbound-id(id :: String)
  | err-if-branches(then-type :: JType, else-type :: JType)

data DynamicError:
  | null-pointer-exception


To get started, open the code stencil and test stencil in


First submit your test cases (named "java-tests.arr") in Captain Teach:

Finally, submit a zip file containing both your test and code files for java. Call the files "java-tests.arr" and "java-code.arr".