7.3.1 C: Interpreter
7.3.1.1 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.
interp :: Expr -> Value
If you have an expression with multiple sub-expressions, you should evaluate the sub-expressions left-to-right.
7.3.1.2 Errors
(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]))
(raise-error (err-bad-arg-to-op (op-plus) (v-str "str")))
7.3.1.3 Stencil Code
7.3.1.4 Features to Implement
7.3.1.4.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 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.
7.3.1.4.2 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.
7.3.1.4.3 Conditionals
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
7.3.1.4.4 Functions
((lam x (+ x 3)) 2) ((lam y 5) 1)
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.
7.3.1.5 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 |
7.3.1.6 Abstract Syntax
(define-type-alias Env (Hashof Symbol Value)) (define-type Value (v-num [value : Number]) (v-str [value : String]) (v-bool [value : Boolean]) (v-fun [param : Symbol] [body : Expr] [env : Env])) (define-type 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 : Symbol] [body : Expr]) (e-app [func : Expr] [arg : Expr]) (e-id [name : Symbol])) (define-type Operator (op-plus) (op-append) (op-str-eq) (op-num-eq)) (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.)
7.3.1.7 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.
(test (v-fun? (eval `{lam x 5})) #t)
(test (eval `{lam x 5}) (v-fun 'x (e-num 5) (hash (list ))))
7.3.1.8 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!