We don't intend for these assignments to take too long. If you have spent five hours on any part of this assignment please stop and check in with the TAs.
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 described below.
To complete this assignment, you must implement the
desugar consumes an abstract syntax tree (i.e., an
parse), replaces all instances of
sugar-let with desugared equivalents, and returns the result.
consumes the desugared abstract syntax tree and returns a Paret
fun desugar(expr :: C.Expr) -> C.Expr%(is-desugared) fun interp(expr :: C.Expr%(is-desugared)) -> C.Value
We have pre-defined all the error cases that you should run into for this assignment.
data InterpError: | err-if-got-non-boolean(val :: Value) | err-bad-arg-to-op(op :: Operator, val :: Value) | err-unbound-id(name :: String) | err-not-a-function(val :: Value) end
You can throw an error by using
raise and providing the correct
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
interp function can assume that
it's given an expression with no
ors in it; it does not have
to check. Your interpreter should short-circuit when possible. For example, if the first argument
and evaluates to
false then you should evalute the
branch without evaluating the second arugment.
should accept a single id value pair and a body. The
let expression should evaluate the value, bind it to id, and then evaluate the body. For example:
(let (x 1) (+ x 2))
should evauate to 3
Your implementation should disallow recursive definitions. That is, in
(let (<id> <expr>)
<id> should be bound in
<body> but not in
let may not be obvious, but let us give you a hint: it
You will use an environment for your interpreter to keep track of the
values of identifiers in scope. From the data definitions you can see that
Env is a
This means you can use Pyret's built in
string-dict functions on your
Env (See the documentation at pyret.org/docs/latest).
Your interpreter should allow identifier shadowing, meaning that if you bind an identifier that is already bound, the new binding takes precendence.
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 an
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 takes an
operator name (of type
Operator) and returns the actual function (Pyret procedure)
that performs the corresponding operation. Having a single rule like this,
accompanied by a mapping, 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 an
error for non-boolean "test" values, where
val is the "test" value it was given.
Functions in Paret should take exactly one argument. Here's are some examples of functions and their applications:
((lam x (+ x 3)) 2)
((lam y 5) 1)
(These should both evaluate to 5.)
There are a couple error cases that may arise when interpreting functions and function applications:
First, it's possible that when attempting to perform a function
application, the value being applied isn't actually a function; e.g.,
you might have
(1 2). In this case you should raise an
err-not-a-function exception, where
val is the value that was
1. Please raise this exception only after evaluating
the function and its arguments.
Second, you might get to an identifier and realize that it's not
bound. In this case you should raise an
err-unbound-id exception with
with name of the identifier.
<expr> ::= | <num> | <bool> | <string> | (+ <expr> <expr>) | (++ <expr> <expr>) | (num= <expr> <expr>) | (str= <expr> <expr>) | (if <expr> <expr> <expr>) | <id> // identifier (a.k.a. variable) | (lam <id> <expr>) // anonymous function | (<expr> <expr>) // function application | (and <expr> <expr>) | (or <expr> <expr>) | (let (<id> <expr>) <expr>)
type Env = StringDict<Value> data Value: | v-num(value :: Number) | v-str(value :: String) | v-bool(value :: Boolean) | v-fun(param :: String, body :: Expr, env :: Env) 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) | e-lam(param :: String, body :: Expr) | e-app(func :: Expr, arg :: Expr) | e-id(name :: String) | sugar-and(left :: Expr, right :: Expr) | sugar-or(left :: Expr, right :: Expr) | sugar-let(id :: String, value :: Expr, body :: Expr) end data Operator: | op-plus | op-append | op-str-eq | op-num-eq end data InterpError: | err-if-got-non-boolean(val :: Value) | err-bad-arg-to-op(op :: Operator, val :: Value) | err-unbound-id(name :: String) | err-not-a-function(val :: Value) end
To get started, you can open the code stencil and the
test stencil in
To check that a program raises a particular exception, 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
You can also be less specific, and not specify the details of the error message:
eval("(+ 1 \"str\")") raises-satisfies C.is-err-bad-arg-to-op
Programs can evaluate to functions. Since your implementation, through desugaring and how you choose to implement environments, affects the representation of functions, in your test submission you should only test whether the program returns a function, not which specific function it returned. Likewise, if you're testing for an exception, make sure not to test that it contains a specific function value.
So do write this:
eval("(lam x 5)") satisfies C.is-v-fun
But don't write this:
eval("(lam x 5)") is C.v-fun("x", C.e-num(5), [list:])
(Although it's fine to write that test in your code file.)
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
or work correctly.)
Please submit a zip file containing two files: "interp-code.arr" and "interp-tests.arr" that contain your code and tests.
Link to submit your code & tests