Paret the parrot has been spending too much time on Captain Teach's shoulder, and is starting to talk like him. While Blackbeard's speech (being Pyret-talk) is too complex to decipher, some insight may be gained by interpreting Paret's simpler syntax.
You will write an interpreter for the Paret language, as described below.
We have provided a function
parse, which consumes an expression in the
language's concrete syntax and returns the abstract syntax representation
of that expression.
parse accepts expressions in the grammar of the
To complete this assignment, you must implement the
desugar consumes an abstract syntax tree (i.e., an
parse), replaces all instances of
e-if equivalents and then returns the result.
consumes the desugared abstract syntax tree and returns a Paret
You will submit and review test cases for
interp before writing the
actual function. Please submit your test cases within the first 48 hours
of the assignment: this will give sufficient time for reviews to take
place. You should write your test cases in terms of the
which is defined simply to call
parse followed by
desugar and then
interp. Your tests cases should fully cover the behavior of the Paret
language. We have pre-defined all the error cases that you should run into
for each assignment.
data InterpError: | err-if-got-non-boolean(val :: Value) | err-bad-arg-to-op(op :: Operator, val :: Value) end
You can throw an error with
raise and provide the correct
To test error cases, you may use the syntactic form
eval("(+ 1 \"str\")") raises-satisfies lam(err): err == C.err-bad-arg-to-op(C.op-plus, C.v-str("str")) end
to check that a program raises a particular exception. You can also be less specific, and not specify the details of the error message by saying:
eval("(+ 1 \"str\")") raises-satisfies C.is-err-bad-arg-to-op
Paret includes binary addition (
+) and number equality testing (
as well as string appending (
++) and string equality testing
str=). You may define these operations in terms of their counterparts
Evaluation should raise a
err-bad-arg-to-op error for non-numeric values
+ and num= operations, and for non-string values passed to
++ and str= operations. The
op part of the error is the operator that
was called, and
val is the value it was given that had the wrong type.
In place of having separate rules (and syntactic forms) for
str=, we will define a single syntactic rule for all binary
parse converts these operators into the
variant, shown in the data definition below.
We recommend that you define an "operator lookup function" that maps
operator names (of type
Operator) to actual functions (Pyret procedures)
that perform the corresponding operation. Having a single rule like this,
accompanied by a table, makes it very easy to add new operators to your
language: you need only add them to the operator lookup function.
If-statements in Paret are composed of three parts:
If statements should short circuit and evaluation should raise a
error for non-boolean "test" values, where
val is the "test" value it was given.
andtakes two booleans and evaluates to
trueif they are both true or to
ortakes two booleans and evaluates to
trueif either one is true, or to
desugar function should convert
or into equivalent
expressions that do the same thing. Your
interp function can assume that
it's given an expression with no
ors in it; it does not have
Your interpreter should evaluate in left-to-right order.
You should implement short-circuiting for
(e.g., when interpreting a statement like
(or true <expr2>),
<expr2> is not evaluated).
The concrete syntax of the Paret language with these additional features can be captured with the following EBNF:
<expr> ::= <num> | true | false | <string> # strings, surrounded by double quotes "" | (+ <expr> <expr>) # addition | (++ <expr> <expr>) # string append | (num= <expr> <expr>) # number equality | (str= <expr> <expr>) # string equality | (if <expr> <expr> <expr>) | (and <expr> <expr>) # boolean and | (or <expr> <expr>) # boolean or
There are some differences between Paret's concrete syntax (given by the
grammar above), and its abstract syntax (given by the variants of the
Expr data type below). In particular,
if parses into a
e-if. This is
if is a reserved word in Pyret.
The abstract syntax for Paret is given below. These constructors will be
available on the module
C (imported at the top of your file), so for
instance you can write
C.v-num(3) to construct a
v-num. When writing
cases statements, however, omit the
data Value: | v-num(value :: Number) | v-str(value :: String) | v-bool(value :: Boolean) end data Expr: | e-num(value :: Number) | e-str(value :: String) | e-bool(value :: Boolean) | e-op(op :: Operator, left :: Expr, right :: Expr) | e-if(cond :: Expr, consq :: Expr, altern :: Expr) | sugar-and(left :: Expr, right :: Expr) | sugar-or(left :: Expr, right :: Expr) end data Operator: | op-plus | op-append | op-num-eq | op-str-eq end
To get started, you can open the
code.pyret.org, and save copies of both for yourself. You will first
submit just your test cases (within the first 48 hours the assignment is
out), and then later submit your code and test cases together.
In the test file you just opened, write a "sweep" of about 5 (and no more than 10) test cases. They should highlight the interesting characteristics of whatever you're testing. To stay within the limit, you will probably need to avoid redundancy. You should run these test cases to make sure they are well-formed (e.g., that there are no syntax errors), though of course they will all fail since the interpreter is not yet implemented.
To submit your test case file, first save it locally by clicking "More / Download this file" in the code.pyret.org editor. Call your file "interp-basic-tests.arr". Next, visit the captain-teach assignments page:
and click the "Next Step" link for the interp-basic assignment. This will direct you to upload a file. Select the "interp-basic-tests.arr" file you just saved. You will have just one chance to submit your tests, because when you do they will be sent out for review by other students.
Right after submitting, the page should say that the submission was successful, and give you a "Continue" link. Click "Continue" and complete the three reviews of other students' tests. You can complete reviews in any order (and view them all at the same time), but you must complete all three reviews before moving on to the next step.
When you receive reviews from your classmates, there is a form on the page that shows the review that you can use to use to submit feedback on the review. This feedback is only for the course staff and has no effect on your grade. We're interested in hearing if the review was particularly helpful or unhelpful, or if you think it was wrong. Also, if you feel the review you receive is in any way inappropriate, you can flag it to bring the problem to our attention.
Some notes on testing:
Do not change the type signatures of the functions in the stencils, or
our test suites will not run on your handin. You shouldn't test
(because we're providing it for you). Also, you need not write test cases
that violate the type signature of a function: for instance, if a function
is annotated to take a list of strings, there's no reason to test giving
it a list of numbers. All of this is true for future assignments as well.
Also, if you test
desugar, please put those tests in your code
submission, not in your test submission. There's good reason for this:
there is more than one correct desugaring, so any tests you write may be
implementation-specific. (And, of course, your submitted test cases should
indirectly test desugaring, because you'll test that
correctly.) Additionally, if you write helper functions in your code file
(which we encourage you to do), please only test them in your code file
and not in your test file. We will grade your tests against our own
solutions, and our solutions won't have defined the same helper functions
that you did.
To submit your implementation, return to the captain-teach assignments page:
and click "Next Step" again. This time, save and then upload a zip file of both "interp-basic-tests.arr" and "interp-basic-code.arr". You are allowed to update your tests for this final submission, and will get some credit if they have improved. Even if you haven't modified your tests from the first submission, though, please submit the file anyways, since we will use it for grading.
After you submit your implementation, you'll have one further step to complete. We want you to answer a quick two-question survey about what (if any) impact the peer review process had on your final submission. The interface will look similar to the review interface, and once you submit your answers to the two questions there, you're done. Again, this feedback will have no effect on your grade -- we're interested in hearing about your experience with the review process.