For this Assignment, you will be adding functions and
let to Paret. This
will involve adding an environment to your interpreter.
Your updated interpreter should be eager and use deferred substitution. It
should use left-to-right evaluation order. Additionally,
or should short-circuit: that is, none of them should evaluate more of
their subexpressions than they need to.
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 list of
EnvCell which takes a
String name and
This means you can use Pyret's built in list functions on your
Your interpreter should allow identifier shadowing, meaning that if you bind an identifier that is already bound, the new binding takes precendence.
Extend Paret to include functions. Your functions should be able to take zero or more arguments. All arguments to the function must evaluate with the same deferred substitutions. Here's an example of a function and its application:
((lam (x y) (+ x y)) 2 3)
(This should evaluate to 5.)
We would also like you to add
let to Paret as syntatic sugar.
should accept a list of one or more bindings of names to values. (The
parser will check that it gets at least one binding, so you don't have
to.) Each binding should be surrounded by parentheses:
(let ((x 1) (y 2)) (+ x y))
(This should evauate to 3.)
let expression should behave as described in the book, and 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
Adding functions to the language introduces a few more ways for things to go wrong.
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, when applying a function it might get the wrong number of
arguments. If this happens, you should raise an
found-arity is the number of arguments it was given,
expected-arity is the number of arguments it was supposed to be
given. Please raise this exception only after evaluating the
Third, 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> ::= | <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> ...) // function application | (and <expr> <expr>) | (or <expr> <expr>) | (let ((<id> <expr>) (<id> <expr>) ...) <expr>)
type Env = List<EnvCell> data Value: | v-num(value :: Number) | v-str(value :: String) | v-bool(value :: Boolean) | v-fun(params :: List<String>, body :: Expr, env :: Env) end data EnvCell: | env-cell(name :: String, value :: Value) 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(params :: List<String>, body :: Expr) | e-app(func :: Expr, args :: List<Expr>) | e-id(name :: String) | sugar-and(left :: Expr, right :: Expr) | sugar-or(left :: Expr, right :: Expr) | sugar-let(bindings :: List<Binding>, body :: Expr) end data Binding: | binding(name :: String, expr :: Expr) end data Operator: | plus | append | str-eq | 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-arity-mismatch(expected-arity :: Number, found-arity :: Number) | err-not-a-function(val :: Value) end
To get started, you can open the code stencil and the
test stencil in
Programs can now evaluate to functions. Since your implementation, though desugar 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 () 5)") satisfies C.is-v-fun
But don't write this:
eval("(lam () 5)") is C.is-v-fun([list:], C.e-num(5), [list:])
(Although it's fine to write that test in your code file.)
Feel free to re-use your test cases from the previous interpreter. Your focus should be on adequately testing the new stuff, but your old tests are still perfectly valid.
You will be submitting both code and tests: we will grade your code by running our test suite against it, and grade your tests by running them against good and bad solutions that we have written to see whether your tests can tell the difference. Feel free to write implementation-specific test cases in your code submission: we won't run these, but they can be helpful to you.
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, 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
Please submit a zip file containing two files: "interp-fun-code.arr" and "interp-funtests.arr" that contain your code and tests.
Link to submit your code & tests