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, if, and, and
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
an Env is a list of EnvCell which takes a String name and Value.
This means you can use Pyret's built in list functions on your Env.
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. let
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.)
The let expression should behave as described in the book, and should
disallow recursive definitions. That is, in (let ((<id> <expr>))
<body>), <id> should be bound in <body> but not in <expr>. The
desugaring of let may not be obvious, but let us give you a hint: it
involves e-lam and e-app.
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
applied; e.g. 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 err-arity-mismatch
exception, where found-arity is the number of arguments it was given,
and expected-arity is the number of arguments it was supposed to be
given. Please raise this exception only after evaluating the
arguments.
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 code.pyret.org.
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 parse
(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 and and or work
correctly.)
Please submit a zip file containing two files: "interp-fun-code.arr" and "interp-funtests.arr" that contain your code and tests.