# A4: JoCalf
**Deadline:** Wednesday, 04/18/18, 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 read-evaluate-print loop (REPL). You will implement an
evaluator 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, which is used to
## 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 the interpreter without using any
imperative features at all, and in fact that is how the staff
reference solution is coded. Your solutions must not require linking
any additional libraries/packages beyond those in the provided `_tags`
*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
* `Eval` implements the interpreter itself. You need to implement a
few 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,
evaluating it, and converting the result of evaluation back to a
* `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: Evaluation
Implement `ast.ml`, `ast_factory.ml`, `eval.ml`, and all test cases in
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`, 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
* **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
* **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
* * *
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. Foster.