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

Code Assignment: Implementation of FGJ

This project deals with the implementation of an FGJ interpreter. You will write the type checker and the evaluation according to the rules in the paper by Igarashi, Pierce and Wadler (43 pages / July 14, 2000)

The language is only slightly changed:

  • no constructors (as before)
  • one must write C for the class C<> that takes no type parameters,
  • one can write class C<A> {...} instead of class C<A extends Object> extends Object {...}.

The partial implementation now includes Java/C++ comments can be used and tabstops handling. It accepts several sourcefile by default, treating each as a single entity (in file A, one cannot reference file B, each file has a top-level expression).

You are allowed to change any file (in particular Auxiliary, TypeAnalysis and Evaluator), but NameAnalysis should remain as it is. Outputs (what you may print) will be described in the following.

Here are further requirements (changes fromthe paper) for your interpreter - you will lose points if these are not respected.

  • "Stupid casts" count as error not warning.
  • Evaluation is done call-by-value (left-to-right).
  • Error messages may only be displayed through classes CompileError and RuntimeError. No console, no exceptions, no crashes, no log or status messages (disable them all before submitting your implementation).

Name Analysis

You are given a partial implementation which comes with a name analysis pass (needed to resolve some of those syntactic gimmicks above). Consequently, the main data structures are already given - you don't need to start from scratch.

What's more important is that you don't have to check for things like missing classes, circularity, etc. (These tasks are not very different from the FJ implementation). It's already (mostly) done. On the other side, this time you must base your implementation on the given fixed data structures.


The class table is managed through the use of symbols. One does not need to build a class table. Name analysis creates a unique class symbol for every class. This symbols is linked with the class definition, and references to that class are linked to that symbol. You never need to create an instance of Symbol yourself! Similarly, each method definitions receives a symbol of its own (MethodSym). Here however, the references to those methods(MSym) are not directly linked - one has to "pass through" a class symbol to get to a "full" method symbol. Details can be grasped by inspecting the code.

There is a facility for error reporting which you must use. Any other output or behaviour like exceptions, crashes, nontermination, log messages will lead to losses of points. The only output you might add is by adding a new type of error message in the appropriate place.

Instead of a "stupid warning", you must signal an error.


You can bonus points by adding erasure. In this case, each run of FGJ must produce the following output, after writing the result of direct semantics. 1. the result of erasure, i.e. an FJ program 2. the result of evaluating the FJ program.


Notice that there are three kinds of substitutions used in the typing rules: term substitution (applied to terms), type substitution (applied to types) and type substitution applied to (types in) terms.

Deadline: 2005-02-02 at 17h00 2005-02-04 (Friday) at 17h00

Here is the partial implementation(UPDATED) again.

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


group1 group2 group3 group4 group5 group6 possible
code 30 25 36 36 36 31 37
test.neg (score on incorrect FJ programs) 37 37 38 44 22 44
total = 14 + (plain + neg) * 2 111 64 123 124 130 94 132
erasure 35 40 40
fulltotal = total + bonus 146 64 123 164 130 84 172

The "fulltotal" score is relative 132.

The 14 points given for free are a 10% recompensation for the bugs in the partial framework.

If you're interested in details, send me an email. We can arrange for a meeting if necessary.


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