A9: JoCalf
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.
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 using a big-step environment model. In CMS, you can
download a pre-compiled reference implementation of the interpreter
that will run on the 3110 VM (but not other operating systems); it’s the
file named jocalf
in the A9 assignment.
Parsing and lexing has already been implemented for you in the starter code, as has a read-evaluate-print loop (REPL). You will implement an evaluator based on the formal semantics.
Table of contents:
- Step 1: Team Maintenance
- Step 2: Explore the Starter Code
- Step 3: Evaluation
- Scope
- Coding Standards
- Submission
Step 1: Team Maintenance
You will do this assignment with the same team as the midterm project.
Before the team meeting, every team member should print out and fill out an Internal Evaluation for all other team members. These are meant to be anonymous, and to provide advice to team members on how they are fulfilling their teamwork obligations, as well as how to improve. At the end of the meeting, distribute the evaluations. Each team member should shuffle the papers they receive, so as to maintain anonymity. Team members should review the evaluations on their own after the meeting.
After this assignment is due, you will submit a performance evaluation of your teammates (covering A6 through A9) to the professor, and those evaluations will become part of team members’ grades.
Step 2: Explore the Starter Code
There is a makefile provided with the usual targets: build, test, check,
finalcheck, zip, docs, and clean. There is a new target, make repl
,
that will build the JoCalf REPL and run it.
We are back to an autograded assignment, hence your submission must pass
make check
. As always, if you’re ever in doubt about whether a change
is permitted or not, just run make check
: it will tell you whether you
have changed the interface in a prohibited way.
Here is a guided tour of the files in the starter code:
-
Files you will need to change:
-
ast.ml
contains a few types that are predefined, because the parser needs them, as well as some types that are currently defined asunit
, as a placeholder. Those types are what you need to define for yourself to represent the JoCalf AST. We deliberately do not provide anast.mli
, so that all the values defined inast.ml
are exposed. -
Ast_factory
is a compilation unit that the parser relies on to construct AST nodes. You need to implement the functions inast_factory.ml
. There are many of them, but they are all very short. -
Eval
implements the interpreter itself. You need to implement a few functions ineval.ml
. The vast majority of the work in this assignment is implementing and testingEval.eval_expr
, which is the function that evaluates JoCalf expressions. -
test.ml
is the beginning of a test suite. We have supplied some public test cases that it is crucial your implementation passes. -
The
Authors
compilation unit needs to be completed, as usual.
-
-
Files you will not need to change:
-
lexer.mll
andparser.mly
contain a lexer and parser that have already been implemented for you. 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. -
Parse
is a helper module already implemented for you that runs the parser. -
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). -
.ocamlinit
will automatically load and openMain
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.
-
Step 3: Evaluation
Implement evaluation by completing ast.ml
, ast_factory.ml
, and eval.ml
.
Here is an algorithm for how to do that:
-
Pick a syntactic form to implement—for example, boolean constants. There is no perfect order in which to implement the syntactic forms, but make sure to read the Scope section below to help you prioritize your efforts.
-
Implement a couple test cases for the form in
test.ml
. -
Extend the AST type in
ast.ml
with a constructor for that form. E.g., addEBool of bool
toexpr
. -
Implement the factory function in
ast_factory.ml
for the form. E.g.,let make_bool b = EBool b
. - If necessary, extend the
value
type ineval.ml
with a constructor. E.g., addVBool of bool
tovalue
. Also, make sure thatstring_of_value
andstring_of_result
are implemented ineval.ml
for whatever kind of value you just added. E.g., instring_of_value
, add a branch that reads| VBool b -> string_of_bool b
- Implement the
==>
rule for that form from the formal semantics. E.g., for Boolean constants that rule is<b, env, st> ==> <b, st>
, so ineval.ml
add a new branch toeval_expr
that reads| EBool b -> (RValue (VBool b), st)
(assuming that
RValue
is the constructor of yourresult
type that represents values, as opposed to exceptions). For any branch that takes more than a single line of code, we recommend that you factor out a helper function. - Implement more test cases for the form in
test.ml
.
Note that this algorithm is highly parallelizable among team members. But you will be editing the same definitions in the same files, so you must be meticulous in your use of Git to avoid conflicts or clobbering code written by other team members.
Scope
-
Satisfactory: The interpreter implements constants (excluding objects), variables, non-recursive let expressions and definitions, functions and application, and if expressions. The
+
operator is implemented for operands that evaluate to integers, and the&&
and||
operators are implemented for operands that evaluate to booleans. The remaining operators, as well as conversion of operands, are not yet implemented. -
Good: The interpreter implements recursive let expressions and definitions, sequences, while loops, references, and exceptions.
-
Excellent: The interpreter implements all unary and binary operators (including conversions), objects, and external functions.
Coding Standards
We will not assess coding standards on this assignment. We trust that you will use what you have learned in the rest of the semester to your advantage.
Submission
Make sure your team’s NetIDs are in authors.mli
, and set the
hours_worked
variable at the end of authors.ml
.
Run make zip
to construct the ZIP file you need to submit on CMS.
Any mal-constructed ZIP files will receive a penalty of 20 points.
The size of the the files is limited in CMS to 1 MB. Please stay
within the size allotted.
Submit your zipfile on CMS. Double-check before the deadline that you have submitted the intended version of your file.
Congratulations! Your new-born calf snuggles with you.
Acknowledgment: JoCalf was inspired by the paper 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.