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 JavaScript. She also has a little bit of DNA from Racket, an untyped functional language descended from Lisp and Scheme.

Introduction

The JoCalf manual contains a brief tutorial on the features of JoCalf, followed by a description of each language feature in detail. The formal 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 implement references.

Assignment information

Objectives.

• 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.

Recommended reading.

• Lectures and recitations 16–18

Requirements.

• You must implement the interpreter as described below in Part 2.
• You must submit an overview document.
• 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.

Grading issues.

• Late submissions: Carefully review the course policies on submission and late assignments. 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. 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 file.

Git. 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 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 run it.

• 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 the parser.

• 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 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: Evaluation

Implement ast.ml, ast_factory.ml, eval.ml, and all 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, 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:

• 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.

Assessment

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?

Karma

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...

---

Acknowledgment: Inspired by The Essence of JavaScript, by 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.