Ecole Polytechnique Fédérale de Lausanne
Code Assignment: FJ implementation
English only

Code Assignment: Implementation of FJ

You are asked to implement the FJ language, as described in this grammar:

Source Language Values
CL ::= class C extends C { C f; M }

M  ::= C m(C x) { return E; }

E  ::= x
       new C(e)
V ::=  new C(V)

An overlined element indicates sequences, as in

class C { 
  A a; 
  B b; 
  E meth(C c, D d) { 
    return new E(a,b,c,d)

x stands for variables names, C for class names, m for method names, f for field names.

Note that we omit constructors from the source language, because these are completely determined by the fields of the class and its superclasses.

More explanations, the typing and evaluation rules can be found in Igarashi, Pierce and Wadler's Featherweight Java paper, page 6, or in chapter 20 in the TAPL book.

You may use the partial implementation, which provides a parser, an abstract syntax tree representation and a main object. The tree representation makes extensive use of Scala collection classes (esp. scala.collection.Map, scala.collection.immutable.ListMap).

The parser will automatically turn field references into select expressions.

Your program must:

  • type check class definitions, method definitions and expressions
  • interpret programs, computing their result

Hint 1: The paper talks about a global "class table". It is helpful to implement such a thing.

Hint 2: The Symbol cannot be directly used to link to their definitions. If this is desired, one has to modify the parser.

You receive bonus points for implementing contra-covariant method override and an example FJ program that uses this.

Deadline: 2004-12-08 at 17h00

Send an archive with your complete source code by email to Burak.Emir@epfl.ch

If you added contra-covariant method override, include also a fj source file that uses this feature.


1. Moser / Rubli
2. Devittori / Jermini
3. Monney / Dietrich
4. Theoduloz / Maye
5.* Voelkle / Dyke / Susa
6. Zbinden / Caffaro


Here are the results. Every point corresponds to a testfile.

group1 group2 group3 group4 group5 group6 possible
test.plain (score on correct FJ programs) 17 13 17 17 15 13 17
test.neg (score on incorrect FJ programs) 25 15 21 22 24 14 27
total = (plain + neg) * 3 126 84 114 117 117 81 132
test.override (score on correct FJ programs w/ cc-oride) 9 9 9 9 9 9
test.override.neg (score on incorrect FJ programs w/ cc-oride) 3 3 3 3 3 3
bonus = test.override + test.override.neg 12 12 12 12 12 12
fulltotal = total + bonus 138 84 126 129 129 93 144

The "fulltotal" score is relative to 132.

You can find out [here] where exactly your program failed, plus some individual feedback.

The test files themselves can be found [here] for a little while (many are taken from your submissions, but sometimes I changed them to test something else or differently).

I was lenient with respect to "stupid cast" - signaling type errors and warnings was both graded as correct (though signaling type errors is the right choice -- the stupid cast are just a technicality of the calculus). What is not correct is to let such things pass at runtime, they must lead to an exception, or to stuck evaluation.

If you are interested in looking at another solution, here is an [FJ interpreter (v1.1)] that should pass all the tests.