$29
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 le 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 Yll 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 fulYlling their teamwork obligations, as well as how to improve. At the end of the meeting, distribute the evaluations. Each team member should shu e 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
http://www.cs.cornell.edu/courses/cs3110/ fa/a9/ 1/5
12/21/ A9: JoCalf - CS 3110 Fall
(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 makeIle provided with the usual targets: build, test, check, nalcheck, 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 Jles in the starter code:
Files you will need to change:
ast.ml contains a few types that are predeHned, because the parser needs them, as well as some types that are currently de ned as unit , as a placeholder. Those types are what you need to de ne for yourself to represent the JoCalf AST. We deliberately do not provide an ast.mli , so that all the values de ned 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.
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.
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 and parser.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
http://www.cs.cornell.edu/courses/cs3110/ fa/a9/ 2/5
12/21/ A9: JoCalf - CS 3110 Fall
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 de nitions, 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 open Main for you. Feel free to modify this le 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., add EBool of bool to expr .
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 in eval.ml with a constructor. E.g., add VBool of bool to value . Also, make sure that string_of_value and string_of_result are implemented in eval.ml for whatever kind of value you just added. E.g., in string_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 in eval.ml add a new branch to eval_expr that reads
| EBool b - (RValue (VBool b), st)
(assuming that RValue is the constructor of your result 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
http://www.cs.cornell.edu/courses/cs3110/ fa/a9/ 3/5
12/21/ A9: JoCalf - CS 3110 Fall
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 deInitions in the same les, so you must be meticulous in your use of Git to avoid conicts or clobbering code written by other team members.
Scope
Satisfactory: The interpreter implements constants (excluding objects), variables, non-recursive let expressions and de nitions, 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 de nitions, 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 le you need to submit on CMS. Any mal-constructed ZIP
les will receive a penalty of 20 points. The size of the the Lles is limited in CMS to 1 MB. Please stay within the size allotted.
Submit your ziple on CMS. Double-check before the deadline that you have submitted the intended version of your le.
Congratulations! Your new-born calf snuggles with you.
Acknowledgment: JoCalf was inspired by the paper The Essence of JavaScript by Arjun Guha
http://www.cs.cornell.edu/courses/cs3110/ fa/a9/ 4/5
12/21/ A9: JoCalf - CS 3110 Fall
Claudiu Saftoiu, and Shriram Krishamurthi, corrected version of October 3, 2015. Prof. Guha was a postdoc at Cornell approx. 2013, supervised by Prof. Foster.