Interp: Basic

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.

Note: Some Unespecified Behavior

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.

1. Interpreter

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

2. Features to Implement

2.1 Binary Operators

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.

2.2 Conditionals

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.

2.3 And/Or

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 ands or ors in it; it does not have to check.

3. Grammar

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.

4. Abstract Syntax

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

5. Setup and Submission

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.

5.1 Writing Test Cases

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.

5.2 Implementing 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.