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.
We left a couple of things unspecified in the assignment. First, should you evaluate left-to-right or right-to-left, or some other order? Second, should 'and' and 'or' short-circuit or not?
Your 'interp' function, when you implement it, can make whatever decisions it wants with respect to this unspecified behavior.
However, our solution, which we'll use to grade your tests, evaluates from left-to-right, and does do short-circuiting for 'and' and 'or'. So if you have test cases that make an assumption about one of these decisions, make sure they agree with this. (Or just remove the offending tests; you don't need to test this behavior at all). If you've already submitted test cases, and they test that evaluation happens right-to-left, or if they test that 'and' and 'or' don't short-circuit, let us know so we don't dock you points for those tests.
We'll make sure to fully specify future assignments so that you don't have to worry about unspecified behavior like this.
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
language.
To complete this assignment, you must implement the interp
and desugar
functions. desugar
consumes an abstract syntax tree (i.e., an Expr
, as
returned by parse
), replaces all instances of sugar-and
and sugar-or
with desugared e-if
equivalents and then returns the result. interp
consumes the desugared
abstract syntax tree and returns a Paret Value
.
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 eval
function,
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 InterpError
.
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 (num=
),
as well as string appending (++
) and string equality testing
(str=
). You may define these operations in terms of their counterparts
in Pyret.
Evaluation should raise a err-bad-arg-to-op
error for non-numeric values
passed to +
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 +
, num=
,
++
, and str=
, we will define a single syntactic rule for all binary
operators. parse
converts these operators into the e-op
datatype
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 err-if-got-non-boolean
error for non-boolean "test" values, where val
is the "test" value it was given.
and
takes two booleans and evaluates to true
if they are both true
or to false
otherwise.or
takes two booleans and evaluates to true
if either one is true,
or to false
otherwise.Your desugar
function should convert and
and or
into equivalent
expressions that do the same thing. Your interp
function can assume that
it's given an expression with no and
s or or
s in it; it does not have
to check.
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
only because 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 C.
.
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 stencil
and the
test stencil
in 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
test cases for the interpreter using eval
. You can 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:
https://www.captain-teach.org/brown-cs173/assignments/
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' code. 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 parse
(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 and
and or
work
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.
interp
To submit your implementation, return to the captain-teach assignments page:
https://www.captain-teach.org/brown-cs173/assignments/
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.