The purpose of this programming project is to implement an interpreter, a
typechecker, and a compiler (down to a simple abstract machine) for a small
functional programming language equipped with (possibly parameterized)
algebraic data types. The following parts of the program are
provided: a lexer
and parser, a constraint solver for first-order unification constraints, an
abstract machine, and its execution engine.
The project can be implemented in any language of your choice, but we strongly
recommend using Caml, as the sources we provide are written in Caml.
http://gallium.inria.fr/~fpottier/menhir/. This tool
is required in order to produce parser.mli and parser.ml
out of parser.mly. (For those who don't want to install Menhir,
we do provide parser.mli and parser.ml, but you will
need to modify the Makefile in order to let make know
that these files are not generated and should not be destroyed.)
Linux, FreeBSD, MacOSX, or some other Unix-like system
The Makefile that we distribute has not been tested under Microsoft Windows. You
are on your own if you insist on using Windows.
Implement an interpreter for the source
language. The file to modify is interpreter.ml.
Implement a compiler from the source language to
the abstract machine. The file to modify is compiler.ml.
Study the specification that the constraint generator must meet,
which is found in generator.mli, and implement the generator. The
file to modify is generator.ml.
At the moment, the generator is incomplete and always produces an empty
unification problem, which means that the inferred type is always
“∀α.α”. It is up to you to construct a unification problem
that is necessary and sufficient for the code to be well-typed.
Note that, for simplicity, we only implement simple (that is,
monomorphic) type inference: no generalization will be performed at
let constructs. Only the data constructors can have (closed)
polymorphic type schemes, which are given by the dcenv parameter.
In order to better understand the entire type inference process, it is
recommended, although not strictly necessary, to have a look at the modules
UnionFind and Unification, which perform constraint solving.
For extra credit
Extend the program in any direction
you're interested in: additional language features, polymorphic type
inference, understandable type error messages, compiler optimizations, ...
Additional test files written in the small programming language,
if you wrote any.
If you implemented “extra credit” features, a README
file (written in French or English) describing these additional
features, how you implemented them, and where we should look in the
source code to see how they are implemented.