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 be defined as a program rather than an expression. A program consists 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. (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>)

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. These fields 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. To call a method on an object, you can use (call <object-expr> <method-name> <arg-value>).

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.


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

    | (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-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-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:
  | 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)

data DynamicError:
  | null-pointer-exception

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


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

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


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


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

You must do this by the test deadline (11:59pm on Monday the 20th).

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