7.3.1 C:   Interpreter
On this page: Introduction Errors Stencil Code Features to Implement Environment Binary Operators Conditionals Functions Grammar Abstract Syntax Testing Submission
7.3.1 C: Interpreter Introduction Errors Stencil Code Features to Implement Environment Binary Operators Conditionals Functions Grammar Abstract Syntax Testing Submission Introduction

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 interp function. It consumes an abstract syntax tree (i.e., an Expr, as returned by parse) and returns a Paret Value. Here is the type signature of interp:
interp :: Expr -> Value

If you have an expression with multiple sub-expressions, you should evaluate the sub-expressions left-to-right. Errors

We have pre-defined all the error cases that you might run into for this assignment:
(define-type InterpError
  (err-if-got-non-boolean [val : Value])
  (err-bad-arg-to-op [op : Operator]
                     [val : Value])
  (err-unbound-id [name : Symbol])
  (err-not-a-function [val : Value]))

You can throw an error by using raise-error and providing the correct InterpError: for instance,
(raise-error (err-bad-arg-to-op (op-plus) (v-str "str")))
Pay careful attention to how evaluation order impacts which errors are thrown. Stencil Code Features to Implement 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 Env is aliased as a (Hashof Symbol Value). This means you can use Plait’s built-in hash table functions on your Env.For your environment, make sure you use hash, which creates immutable hash tables! What happens if you use make-hash, which creates mutable hash tables instead? Try replacing one with the other and see. If none of your tests fail... you aren’t testing enough! You should have at least one failing test, if not several, when you make this switch.

Your interpreter should allow identifier shadowing, meaning that if you bind an identifier that is already bound, the new binding takes precedence. When in doubt, your interpreter should behave just as SMoL would.

When your interpreter encounters an unbound identifier, it should raise the err-unbound-id exception with the name of the identifier. Binary Operators

Paret includes binary addition (+) and number equality testing (num=), as well as string appending (++) and string equality testing (str=).

Evaluation should raise a err-bad-arg-to-op error for non-numeric values passed to + 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 syntactic forms for each of +, num=, ++, and str=, we will define a single syntactic rule for all binary operators. parse converts these operators into the e-op datatype variant.

We recommend that you define an “operator lookup” function that takes an operator name (of type Operator) and returns the actual function 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. Conditionals

e-if-expressions in Paret have three parts:
  • cond, which is supposed to evaluate to a v-bool

  • consq, which evaluates if the cond evaluated to true

  • altern, which evaluates if the cond evaluated to false

They should short-circuit (i.e., evaluate only the relevant branch). Evaluation should raise a err-if-got-non-boolean error for non-Boolean cond values, where val is the offending value. Functions

Functions in Paret take exactly one argument. Here’s are two examples of functions and their applications:
((lam x (+ x 3)) 2)
((lam y 5) 1)
(These should both evaluate to 5.)

It’s possible that when attempting to perform a function application, the value in the function position isn’t actually a function; e.g., you might have (1 2). In this case you should raise a 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 argument. Grammar

<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 Abstract Syntax
(define-type-alias Env (Hashof Symbol Value))
(define-type Value
   [value : Number])
   [value : String])
   [value : Boolean])
   [param : Symbol]
   [body : Expr]
   [env : Env]))
(define-type Expr
   [value : Number])
   [value : String])
   [value : Boolean])
   [op : Operator]
   [left : Expr]
   [right : Expr])
   [cond : Expr]
   [consq : Expr]
   [altern : Expr])
   [param : Symbol]
   [body : Expr])
   [func : Expr]
   [arg : Expr])
   [name : Symbol]))
(define-type Operator
(define-type InterpError
  (err-if-got-non-boolean [val : Value])
  (err-bad-arg-to-op [op : Operator]
                     [val : Value])
  (err-unbound-id [name : Symbol])
  (err-not-a-function [val : Value]))

(For reference, feel free to look at the definitions file.) Testing

We care that you test programs well. Programming langauge implementations are expected to be rock-solid (when’s the last time you ran into an implementation bug?). You need to uphold this standard. This isn’t a course in something like AI, where we don’t even know what the right answer might be.

Observe that programs can evaluate to functions. You may have chosen a different representation for them than we did. Therefore, your tests should only check that such a program returned a function, and not rely on the specific function returned (because of the differences in representation). Thus, for instance, write
(test (v-fun? (eval `{lam x 5})) #t)
but don’t write
(test (eval `{lam x 5}) (v-fun 'x (e-num 5) (hash (list ))))
because our representation of closures may not match that. Submission

To submit your implementation and test cases, use the following Google Form to upload your files. Make sure that you put the right file to the right upload field. If you submit more than once, we will see your last submission.

Upload only your implementation file. Make sure you have not modified the support file in any way!