Interp: Functions and Let

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.

1. New Features

1.1 Environment

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.

1.2 Multi-arity Functions

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.)

1.3 Let

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.

1.4 New Exceptions

Adding functions to the language introduces a few more ways for things to go wrong.

2. Grammar

<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>)

3. Abstract Syntax

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)

data EnvCell:
  | env-cell(name :: String, value :: Value)

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)

data Binding:
  | binding(name :: String, expr :: Expr)

data Operator:
  | op-plus
  | op-append
  | op-str-eq
  | op-num-eq

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)

4. What to hand in

To get started, you can open the code stencil and the test stencil in

4.1 Test cases

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

But don't write this:

eval("(lam () 5)") is[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 let, and, and or work correctly.)

4.2 Submissions

Please submit a zip file containing two files: "interp-fun-code.arr" and "interp-fun-tests.arr" that contain your code and tests.

Link to submit your code & tests