CS 3110 Fall 2020
A4: JoCalf
Quick links: JoCalf manual | Formal semantics
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.
This assignment is about the same di culty as A3. On a similar assignment last year, the mean hours worked was 15.0, and the standard deviation was 7.0. Please get started right away and make steady progress each day. Please track the time that you spend. I will ask you to report it.
Collaboration policy: This assignment may be completed either as an individual or with a group. Groups must be formed in CMS within the rst couple days of the assignment, as in A3. Beyond your optional group, you may have only limited collaboration with other students as described in the syllabus.
What you¡¯ll do: Parsing and lexing has already been implemented for you in the starter code, as has a read-evaluate-print loop (REPL). All you have to do is implement an evaluator based on the formal semantics.
Table of contents:
Step -1: Install a Utility
Step 0: Form a CMS Group
Step 1: Get Acquainted with JoCalf Step 2: Explore the Starter Code Step 3: Evaluation
Rubric
Submission
Step -1: Install a Utility
You need to install rlwrap , which is a simple command-line utility to make I/O more pleasant. On Ugclinux, it¡¯s already installed. On WSL or the 3110 VM, run
$ sudo apt install rlwrap
On Mac, run either
or
depending on which package manager you have installed.
Con rm the utility is installed by running and noting the version number, which
$ sudo port install rlwrap
$ brew install rlwrap
rlwrap -v
currently is 0.43.
Step 0: Form a CMS Group
For your convenience, I have already copied your A3 group over into A4. But if you want to work with someone else, that is ne. As with previous partner assignments, you have until Saturday morning to form a partnership, and after that, the same penalties will be in place if you want to change partners. This is to ensure that if you work with a partner, you really do all the work together with them instead of one person getting credit at the last minute for the work of another person.
The deadline to form a CMS group is Wednesday, December 2, at 11:59 pm ET. There will be a short grace period. Starting on Thursday, December 3, you will no longer be able to form new groups. Instead, you will have to email one of your section TAs, cc¡¯ing your intended group members. The TA can then manually put you into a CMS group. However, there will be a penalty for late group formation: -5 points on Thursday and -10 points on Friday. The penalty applies to all group members¡ªno exceptions. Starting on Saturday, December 5, at 12:01 am ET, no new groups may be formed.
Step 1: Get Acquainted with JoCalf
First, read the tutorial in the rst section of the JoCalf manual. Follow along with it in your own terminal by downloading a pre-compiled reference implementation of the interpreter from CMS. The reference implementation provides a top-level for JoCalf that you can use to experiment and con rm your understanding of the language. There are two les provided. One is for Mac, the other is for Ubuntu (including WSL, Ugclinux, and the 3110 VM). Make sure to use the right le for
your OS. The best way to run it is with the utility , that is,
$ rlwrap ./jocalf-mac
or
That will make it possible to use some of the standard keyboard shortcuts you¡¯re used to from utop, such as up and down arrow to scroll back through old commands you¡¯ve issued. Replace
./ with whatever path you need to the location of the le if it¡¯s not in the current working directory.
If you get an error ¡°permission denied¡± when trying to run the reference implementation, it¡¯s because your OS is trying to protect you from running arbitrary code downloaded from the Internet. Just run chmod u+x
If on Mac you get an error ¡°cannot be opened because the developer cannot be veri ed¡±, it¡¯s again because your OS is trying to protect you from running arbitrary code downloaded from the Internet. In this case, run xattr -c jocalf-mac to x it.
Second, study the next sections of the language manual, titled Syntax, Values, and Evaluation. You will need a good grasp of those before going forward.
Third, skim through the rest of the manual (starting with the section titled Constants) to get a sense for what is there. You don¡¯t need to read it in detail yet. Instead, as you implement each language feature, come back and study the relevant section at that time.
Fourth, look at the formal semantics. It gives a precise, mathematical description of the language using a big-step environment model. Again, you don¡¯t need to read it in detail yet, but can come back as you implement each language feature.
As the Evaluation section of the language manual describes, there are three kinds of evaluation: expressions, de nitions, and phrases. The formal semantics accordingly uses three different big- step evaluation relations:
Expressions:
First, there is a state as part of the machine con guration on both sides of the relation. That state is used to model mutable memory locations. Think of it as a map from memory addresses to values, similar to how the environment is a map from identi ers to values. The
$ rlwrap ./jocalf-ubuntu
rlwrap
addresses to values, similar to how the environment is a map from identi ers to values. The state on the right-hand side might be different from the state on the left-hand side, because mutable language features will cause the state to change. Until you get to the Good Scope
(which is where mutability comes into play) the state won¡¯t be of much use. Just make sure to always return the right state according to the semantics, and you¡¯ll be ne.
Second, on the right-hand side, a result is produced. Results are either values or exceptions. You will be using exceptions even during the Satisfactory scope because of run-time errors that evaluation of this untyped language can produce.
De nitions:
Phrases: . A phrase is either an expression or de nition, and is evaluated according to one of those two evaluation relations.
There is a make le provided with the usual targets: build, test, check, nalcheck, zip, bisect, docs, and clean. There is a new target, , that will build the JoCalf REPL and run it.
As always, if you¡¯re ever in doubt about whether a change is permitted or not, just run
: it will tell you whether you have changed the interface in a prohibited way. Here is a guided tour of the les in the starter code:
The following are the les you will need to change. Take a moment to open and skim each of them.
contains a few types that are prede ned, because the parser needs them, as well as two types ( and ) 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. I deliberately do not provide an , so that all the values de ned in
are exposed.
is a compilation unit that the parser relies on to construct AST nodes. You need to implement the functions in . There are many of them, but most are trivial and all are short. Make sure you read the specs in . You don¡¯t have to do anything to handle hex, octal, or binary conversion. The only tricky part is handling unary negation and integers.
Step 2: Explore the Starter Code
make repl
make
check
ast.ml
Ast_factory
expr defn
ast.mli
ast_factory.ml
ast.ml
ast_factory.mli
il hi ilfY dil ffii
implements the interpreter itself. You need to implement a few functions in
. The vast majority of the work in this assignment is implementing and testing
Eval.eval_expr , which is the function that evaluates JoCalf expressions. Be sure to factor out helper functions, rather than making that one function be hundreds of line long. Also, make sure to read the specs in eval.mli , especially string_of_value and
string_of_result .
test.ml is the beginning of a test suite. I have supplied some public test cases that, with high probability, will also be in the course staff test suite when we autograde your submission. So, make sure that your interpreter gets exactly the expected output.
The Authors compilation unit needs to be completed, as usual.
You will not need to change any of the following les, and you really don¡¯t even need to read
them.
lexer.mll and parser.mly contain a lexer and parser that have already been implemented for you. Do not change them. That would change the syntax of JoCalf, which is not permitted.
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 de nitions, it supports three directives: #quit , #state (which displays the contents of the state), and (which display the contents of the environment). The latter two rely on and Eval.string_of_env , which you will need to implement.
.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 , eval.ml , and test.ml . Do this one language feature at a time, rather than trying to complete an entire le at once. Implement and test a language feature, then move on to the next. The rst couple you implement might take awhile as you get used to the code base. Then you hopefully will get into a rhythm and
Eval
eval.ml
#env
Eval.string_of_state
make steady progress through all the language features that are in common with Core OCaml. As
you get into new language features that weren¡¯t part of Core OCaml, make sure to study the language manual and formal semantics carefully.
Implementation order. In general, I recommend implementing language features in the same order they appear in the language manual. In more detail, here is a recommended order and some notes on the features:
Satisfactory scope: This level of scope corresponds roughly to the language features we covered in the textbook, lecture, and lab; you are of course free to re-use any of that code I gave you.
Constants: integers, strings, Booleans, and . You don¡¯t have to get the corner
undefined
cases of negative integer literals and and away; those are for Excellent scope.
Three basic operators: the plus operators on integers (e.g.,
Boolean operators (e.g., true && false ,
of the binary operators, as well as conversions to integers and Booleans from other types, for Excellent scope.
Let expressions and de nitions. This will require you to get environments working. Don¡¯t worry about recursion yet; leave that for Excellent scope, and just do non-recursive let for now. You do need to implement the run-time error associated with let now, rather than waiting until Good scope.
Anonymous functions and function application. This will require you to get closures working. You do need to implement the run-time errors associated with function application now, rather than waiting until Good scope.
If expressions.
Good scope: This level of scope involves adding mutability to the Satisfactory scope. It involves new features that we didn¡¯t cover before. The challenge here, therefore, is to use the formal semantics to guide your implementation.
Sequences (i.e., semicolon).
References. This is the rst language feature that will cause you to mutate states in an interesting way. You do need to implement the run-time error associated with assignment now, rather than waiting until ¡°Throw and try¡±, two bullet points below.
min_int
max_int
working correctly right
1+1
), and the short-circuit ). You can leave the rest
false || false
While loops. Be careful to implement these correctly, and not to accidentally turn every
ast.ml
value
test.ml
ast_factory.ml
EBool of bool
expr
let make_bool b
= EBool b
eval.ml
VBool of
bool
value
string_of_value
string_of_result
eval.ml
string_of_value
| VBool b -> string_of_bool b
==>
RValue result
eval.ml
eval_expr
| EBool b -> (RValue (VBool b), st)
test.ml
loop into an in nite loop. Throw and try.
Excellent scope: As always, you should regard the Excellent scope as a chance to dig deeper, rather than something mandatory.
All the remaining features: objects and external functions.
All the leftovers not nished above: negative and extremal integers; all the remaining binary and unary operators, including conversions between types; and recursive let expressions and de nitions.
Implementation strategy. Here is an algorithm you can follow to implement the evaluator. Pick a syntactic form to implement¡ªfor example, boolean constants.
Implement a couple test cases for the form in .
Extend the AST type in with a constructor for that form. E.g., add
to .
Implement the factory function in
.
If necessary, extend the type in
to
implemented in
Implement the
for the form. E.g.,
with a constructor. E.g., add
and are
rule for that form from the formal semantics. E.g., for Boolean
, so in add a new branch to
(assuming that is the constructor of your
opposed to exceptions). For any branch that takes more than a single line of code, I recommend that you factor out a helper function.
Implement more test cases for the form in .
. Also, make sure that
for whatever kind of value you just added. E.g., in
, add a branch that reads
constants that rule is that reads
type that represents values, as
Rubric
Rubric
25 points: submitted and compiles 50 points: satisfactory scope
20 points: good scope
5 points: excellent scope
The only function that the autograder test suite will directly call is Main.interp_expr . So feel free to test all you want in the REPL, which uses Main.interp_phrase , but to receive points you must ensure that Main.interp_expr is also working. The latter is the function that provided (and minimal) test suite already does test, and that you should test further.
The autograder test suite is engineered to do a good job of getting you partial credit on any language features you implement, as long as you follow the order described above. But it¡¯s not always possible to test each language feature completely in isolation, and of course we also need to test features in conjunction with one another to see whether they work together properly.
We will not assess coding standards or testing on this assignment. I trust that you will use what you have learned in the rest of the semester to your advantage. The provided make bisect target is an excellent way to check your test suite¡¯s code coverage and identify missing unit tests. To keep your code organized (and yourself sane), factor out helper functions aggressively. My solution has about 40 of them. Most are mutually recursive.
Each of the four language features in Good scope will be worth about the same number of points (5 each), and the same is true for the ve features in Excellent scope (1 each). So please don¡¯t feel as though you have to implement all the features: it¡¯s perfectly ne to stop early. If all you do is the Satisfactory scope, you will still have learned a lot about interpreters. The experience of implementing an interpreter is what¡¯s important, not accumulating all the points.
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.
DO NOT use your operating system¡¯s graphical le browser to construct the ZIP le.
Mal-constructed ZIP les will receive a zero from the autograder. If CMS says your ZIP le is too large, it¡¯s probably because you did not use make zip to construct it; the le size limit in CMS is plenty large for properly constructed ZIP les.
¡û¡ú
Ensure that your solution passes . Submit your zip le 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, Claudiu Saftoiu, and Shriram Krishamurthi, corrected version of October 3, 2015. Prof. Guha was a postdoc at Cornell ca. 2013, supervised by Prof. Foster.
make finalcheck
ý 2020 Cornell University