3 Basic Interpreter
This assignment has you implement a simple interpreter for boolean and arithmetic expressions, and identifier binding via substitution.
3.1 Data Definitions
You’ll be implementing Paret, a small language. Its concrete syntax is:
exp := (<op> <exp> <exp>) |
| (let ((<id> <exp>) ...) <exp>) [where <id>'s are all different] |
| (if <exp> <exp> <exp>) |
| true |
| false |
| <number> |
|
op := + | - | * | / | < | > | == |
id := any symbol other than an op or true, false, let, if |
Some examples of Paret programs are:
(if true 32 45) |
|
(let ((x 5) (y 10)) (+ x y)) |
|
false |
|
(< 3 4) |
|
(if (== 2 3) false true) |
The abstract syntax of Paret is described by a few Pyret data definitions:
data Op: | op-plus | op-minus | op-times | op-divide | op-less | op-greater | op-equal end data Expr: | e-num(n :: Number) | e-bool(b :: Boolean) | e-op(op :: Op, left :: Expr, right :: Expr) | e-if(cond :: Expr, consq :: Expr, els :: Expr) | e-let(binds :: List<Bind>, body :: Expr) | e-id(x :: String) end data Bind: | bind(id :: String, expr :: Expr) end
This is mostly maps one-to-one with the pieces of concrete syntax, but it’s worth noting that the Bind datatype is used to describe let bindings, which are pairs of identifiers and expressions that will be substituted for them.
Paret programs can result in values or raise errors, which are described by two Pyret data structures:
data Error: | unbound-id | div-0 | not-a-num | not-a-bool end data Value: | v-num(n :: Number) | v-bool(b :: Boolean) end
The textbook and lecture have coverd Values. The causes of the errors are discussed more in the next section.
3.2 Paret Semantics
You will define an evaluator for Paret with a pair of functions:
fun interp(expr :: Expr) -> Value fun subst(expr :: Expr, id :: String, val :: Value) -> Expr
We’ll describe the semantics of each form in turn:
e-num and e-bool should evaluate directly to number and boolean values, respectively.
e-op expressions evaluate their sub-expressions and perform the corresponding operation. All the operations except op-equal are defined only for v-num arguments, and perform the corresponding Pyret operation on the underlying values. Arithmetic operations return numbers, and comparison operations return booleans. If those operators receive non-number values, they should raise not-a-num.
The equal operator op-equal should accept any two values and evaluate to a boolean, and never raises an error.
e-if evaluates its condition (the first position), and if it’s true, evaluates the then clause (second position), otherwise evaluates the else clause (third position). If the condition is not a boolean, not-a-bool should be raised.
e-let evaluates the expr position of each of its Binds, substitutes the resulting values into the body for the corresponding identifiers in the bindings list, and then evaluates the resulting body. An identifier should not be substituted into let expressions in the body if that identifier is in the bindings list.
e-id expressions get substituted by subst, and raise unbound-id if they are evaluated before being substituted with a value.
3.3 Logistics
You have been provided two files:
basic-interp-impl.arr, which contains your implementation of Paret. It exports only the function eval, defined at the bottom, which composes a helper (parse, provided in shared code), with your interpreter to evaluate strings to Values. You will write your implementation of interp and subst here, along with any unit tests for those functions.
basic-interp-tests.arr, which will hold your external tests for the evaluator. Tests should all use the eval function, which takes a String and produces a Value. It is set up initially to import the reference implementation and your implementation. There are examples in the file of running the tests against both your implementation and the reference implementation.
The files are at:
https://code.pyret.org/editor#share=0B32bNEogmncOU0MtNmJZaU5rTXM https://code.pyret.org/editor#share=0B32bNEogmncOS0NaM1g2aVlLRHc
Both files import the module interp-basic-defs.arr, which defines the data definitions and the helper function used by eval to parse strings to ASTs:
https://code.pyret.org/editor#share=0B32bNEogmncOSVRLYkx0NlRrMWs
You do not need to, and should not, change this file at all, it’s provided for reference only (if, for example, you get a line-number related error from that file, it can be useful to have it open).
You shouldn’t need to change the top few import lines of the tests and implementation files; they are just there to import the shared code. The tests file has an import line that looks like this:
import my-gdrive("basic-interp-impl.arr") as B
That line is importing your implementation (defined in basic-interp-impl.arr), and it pulls in the most-recently-saved copy of your implementation when run.
If you have a question about the semantics, you should formulate it as a test case and run it through the reference implementation.
If you have a question about the syntax, you should try running
parse("your program here")
Where parse is defined on the interp-basic-defs.arr module.
You are not responsible for testing parsing errors. You can tell which errors are parsing errors because they aren’t errors in the Error type, and parse will raise a (somewhat) descriptive error on strings that don’t match the concrete syntax.
3.3.1 Using Modules
Since the definitions are coming from the interp-basic-defs module, you will have to use I.name to get at the various constructors and types. For example, I.v-num(5) will construct a v-num. If you want, you can copy this boilerplate to get access to the identifiers directly; I don’t care which style you choose to use:
type Error = I.Error unbound-id = I.unbound-id div-0 = I.div-0 not-a-num = I.not-a-num not-a-bool = I.not-a-bool type Op = I.Op op-plus = I.op-plus op-minus = I.op-minus op-times = I.op-times op-divide = I.op-divide op-less = I.op-less op-greater = I.op-greater op-equal = I.op-equal type Expr = I.Expr e-num = I.e-num e-bool = I.e-bool e-op = I.e-op e-if = I.e-if e-let = I.e-let e-id = I.e-id type Bind = I.Bind bind = I.bind type Value = I.Value v-num = I.v-num is-v-num = I.is-v-num v-bool = I.v-bool is-v-bool = I.is-v-bool
3.3.2 Testing for Errors
Some of the expressions in Paret explicitly raise errors in the Error type. To test erroneous Paret programs, like "(+ 5 true)", you can uses raises-satisfies in conjunction with one of the is- predicates for the appropriate error. For example, you could add this to the check block:
eval("(+ 5 true)") raises-satisfies I.is-not-a-num
3.4 Testing and Submission Steps
A good way to start is by writing tests against the reference implementation to explore the behavior of the interpreter. You can do so at the REPL and in the provided check block. The more interesting cases you figure out, the easier it will be to test your interpreter when you start writing it.
By midnight Sunday (Feb 8), you should submit 5-10 of what you think are the most interesting tests to Captain Teach at the cs91-basic-interp link from:
https://www.captain-teach.org/swarthmore-cs091/assignments/
Submit a single Pyret file with your test cases filled into the check block in the template file. If you’re budgeting your time over the weekend, you shouldn’t need to spend more than about an hour playing with the interpreter to come up with some interesting cases.
By midnight Monday (Feb 9), you should submit any reviews you were assigned. You should feel free to complete the reviews at any time before then, and they will be assigned as submissions come in (so if multiple people submit on Saturday, reviewing can start then).
On Tuesday, a set of bad implementations will be released, with instructions for adding an import line to access and test the bad implementations.
Update: You can now include the bad intepreters in your test file by adding this line:
import shared-gdrive("basic-interp-bad-interps.arr", "0B32bNEogmncOVTBhMlpxa0FjTWs") as BI
The bad interpreters have names; the names might help you write appropriate tests (they also might not). They are:
if-true if-no-err if-both-branches reverse-comparisons homogeneous-args let-star let-rats const-op let-no-binding-subst no-shadow-check just-two-substs extra-shadow-check
You can access them with BI.bad-interps.<interp-name>, where <interp-name> is one of the above names.
By midnight Thursday (Feb 12), you should submit a completed implementation of the interpreter, and a final test suite. Use the same submission link as above, but submit to the code step, which will unlock after you complete your reviews.
3.5 Grading
Your grade will be in a few parts:
10% for submitting an interesting initial set of tests. "Interesting" isn’t a very high bar: the main goal is to get diversity of tests out there early on.
35% for the quality of your tests, based on the number of bad implementations they catch. I reserve the right to grade based on additional bad implementations that I don’t release, so catching the ones that are out there does not guarantee a perfect testing score.
55% for the quality of your implementation, based on its correctness, clarity, and style.
Peer reviews will not factor into your grade, though you are free to copy tests from others that you see during review. Please don’t share tests with one another outside of what’s provided during test review.