# A4: JoCalf
**Deadline:** Wednesday, 11/08/17, 11:59 pm
*This assignment may be done as an individual or with one partner. The
use of a partner is optional. Sharing of code is permitted only between
you and your partner; sharing among larger groups is prohibited.*
A baby camel is called a *calf*. In this assignment you will implement
an interpreter for JoCalf, a young language whose parents are OCaml and
functional language descended from Lisp and Scheme.
The [JoCalf manual][manual] contains a brief tutorial on the features
of JoCalf, followed by a description of each language feature in detail.
The [formal semantics][semantics] gives a precise, mathematical description
of the language.
Parsing and lexing has been implemented for you in the release code, as
has a REPL. You will implement the rest of the interpreter in two phases:
* **Desugaring**, which transforms the *surface syntax* of the language
into a *core syntax*. This phase of interpretation is fairly short,
and it deals almost exclusively with objects. Desugaring is detailed
at the end of the language manual.
* **Evaluation**, which implements the formal semantics. That semantics
uses the big-step environment model. It extends the model we saw in
class by adding a *state* to the machine configuration. The state is
used to implement references.
## Assignment information
* Know the design of an interpreter.
* Implement a big-step environment model semantics, including closures.
* Better understand OCaml itself by implementing some of its features.
* [Lectures and recitations 16–18][web]
* You must implement the interpreter as described below in Part 2.
* You must submit an [overview document][overview].
* You must use Git as part of your development process.
**What we provide.**
See below under Part 1 for a description of the release code.
* **Late submissions:** Carefully review the course policies on
[submission and late assignments][late]. Verify before the deadline on CMS
that you have submitted the correct version.
* **Environment, names, and types:** You are required to adhere to the names and
types of the functions and modules specified in the release code. Your
solution must pass the `make check` described below in Part 0.
Otherwise, your solution will receive minimal credit.
* **Code style:** Refer to the [CS 3110 style guide][style].
Ugly code that is functionally correct will nonetheless be penalized.
Take extra time to think and find elegant solutions.
**Permitted OCaml features.**
Imperative features are now permitted. Side effects are not necessarily
bad! But we urge you to think carefully before choosing to use
imperative features. It is quite possible to implement all of
desugaring and evaluation without using any imperative features at all,
and in fact that is how the staff reference solution is coded.
Your solutions may not require linking any additional
libraries/packages beyond those in the provided `_tags` file.
*Private repos are of the utmost importance.* A public repo would
share your code with the entire world, including your classmates, thus
violating the course policy on academic integrity. Therefore we require
that you keep all your CS 3110 related code in private repos.
You are strongly encouraged to use the [Cornell CIS
GitHub][cisgithub] rather than the public GitHub (whose URL we
deliberately omit here). The main reason for this is that the CIS
GitHub allows unlimited private repositories.
## Part 0: Makefile
As usual, we provide a makefile.
* `make check` will check your OCaml environment and the names and types of your required
functions. Run that early and often and always before submitting your solution.
* `make test` or simply `make` will build your OUnit test suite in `test.ml` and
* `make repl` will build the REPL and run it.
* `make zip` will build the zip file containing your source code for submission to CMS.
* `make zipcheck` will check your zip file for a common mistake that people sometimes
make if they create the zip with their OS's file browser instead of with `make zip`.
* `make clean` will delete generated files produced by the make and build systems.
## Part 1: Read the release code
Your first task is to familiarize yourself with the structure of
the release code we have shipped to you.
* `lexer.mll` and `parser.mly` contain a lexer and parser that have already
been implemented for you. You do not need to change these files at all,
and in fact changing them would be a massively bad idea, because it would
change the syntax of JoCalf, almost certainly making your interpreter
incompatible with the course staff's test suite.
* `ast.ml` contains a few types that are predefined, because the parser needs them,
as well as some types that are currently defined as `unit`, as a placeholder.
Those types are what you need to define for yourself to represent the JoCalf AST.
We deliberately do not provide an `ast.mli`, so that all the values defined
in `ast.ml` are exposed.
* `Ast_factory` is a compilation unit that the parser relies on to construct
AST nodes. You need to implement the functions in `ast_factory.ml`. There
are many of them, but they are all very short.
* `Parse` is a helper module already implemented for you that runs
* `Desugar` is a compilation unit that is the next phase of the interpreter
after parsing. You need to implement several functions in `desugar.ml`.
* `Eval` is the next phase after desugaring. You need to implement
a couple functions in `eval.ml`. The vast majority of the work in this assignment
is implementing and testing `Eval.eval_expr`, which is the function that
evaluates JoCalf expressions.
* `Main` is a module already implemented for you that coordinates all the phases
of the interpreter: taking in a string, parsing it, desugaring, evaluating,
and converting the result of evaluation back to a string.
* `Repl` is a REPL already implemented for you. In addition to evaluating
expressions and definitions, it supports three directives: `#quit`,
`#state` (which displays the contents of the state), and `#env`
(which display the contents of the environment).
* `test.ml` is the beginning of a test suite. We have supplied some
public test cases that it is crucial your implementation passes.
* `.ocamlinit` will automatically load and open `Main` for you. Feel
free to modify this file to test however you wish. Using the provided
REPL, however, is likely to be just as useful.
## Part 2: Desugaring and Evaluation
Implement `ast.ml`, `ast_factory.ml`, `desugar.ml`, and `eval.ml`.
And implement test cases in `test.ml`.
The best way to do this work is to implement individual syntactic forms,
rather than to try to complete each file individually. For example,
you could decide to implement constants, or let expressions, or
dereferences. Regardless, implement that syntactic form by defining
AST types for it in `ast.ml`, makers for it in `ast_factory.ml`,
desugaring for it in `desugar.ml`, evaluation for it in `eval.ml`,
and test cases for it in `test.ml`. Then move on to another syntactic form.
There is no ideal order in which to implement the syntactic forms,
but the order in which they are given in the BNF is not bad. We do
recommend leaving objects until last. Also, many of the staff test
cases will use the `+` binary operator in its various overloaded forms,
so make sure to get it done, and done right.
## What to turn in
Submit files with these names on [CMS][cms]:
* `a4src.zip`, containing your solution code. Create this file with
`make zip`, and check it with `make zipcheck`.
* `overview.pdf`, containing your overview document. We also accept
`.txt` and `.md` files.
* `gitlog.txt` containing your Git log. Create this file
with `git log --stat > gitlog.txt`.
Although you should most certainly build a test suite (and we provide
you with the start of one in `test.ml`), we will not be grading your
test suite as part of this assignment. We've taught you a lot
about testing: now we rely on you to use that knowledge effectively.
The course staff will assess the following aspects of your solution.
The percentages shown are the approximate weight we expect each to receive.
* **Correctness.** [75%] Does your solution compile against and correctly pass
the course staff's test cases?
As a rough guide, we expect to assign approximately 10-15%
of the correctness points to each of the following
parts of our test suite: constants, operators, let expressions,
control flow, functions and application, references, exceptions
and handling, objects, and external functions.
* **Code quality.** [10-15%] How readable and elegant is your source code? How
readable and informative are your specification comments? All functions,
including helper functions, must have specification comments.
* **Git.** [<5%] Did you submit a git log as required?
* **Overview.** [10%] Did you complete the overview document? Does it provide
all the required information?
We don't have any karma in mind for this assignment. If you want
to go above and beyond the call of 3110 duty, feel free to tell
us about what you have done in your overview document. The
orange camels are calling...
* * *
Arjun Guha, Claudiu Saftoiu, and Shriram Krishamurthi, corrected
version of October 3, 2015. Prof. Guha was a postdoc at Cornell
approx. 2013, supervised by Prof. Nate Foster.