Interp: Records

Note: this assignment will have test-case reviews. Turn them in by 11:59pm on Tuesday.

1. The Extended Language

For this assignment, you will be extending your interpreter to have record values. A record is a kind of value that keeps track of name/value pairs.

1.1 record

A record expression constructs a record value out of the given fields. Each of the fields' contents should be evaluated in order, and then a v-rec value should be constructed from the values produced. The parser will reject a record expression with duplicate field names, so you don't need to test this.

For example,

(record (a 1) (b 2))

should evaluate to a record with two fields, a and b, with values 1 and 2 respectively.

1.2 lookup

(lookup rec field-name) looks up a field name on a record value. It evaluates the rec, and, assuming the result is a v-rec, finds and returns the value of the field named field-name on it.

1.3 extend

(extend rec field-name new-value) extends a record value by adding a new field on to it. It evaluates rec to a v-rec, then evaluates new-value, and then produces a v-rec containing all of rec's fields, as well as a field named field-name with value new-value. If field-name is already on the given record then lookups on the new record should return new-value.

1.4 with

(with rec body) first evaluates rec to a record value, and then evaluates body with the record's fields added as bindings to the current environment. If an identifier is already bound in the environment, with should shadow it.

1.5 New Exceptions

There are two new kinds of errors:

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)

  | err-not-a-record(val :: Value)
  | err-field-not-found(rec :: Value, field-name :: String)

2. Notes on Testing

You should avoid writing test cases in your test file that return v-recs. There are many different valid ways to represent records. For instance, a record with fields mapping a to 1 and b to 2 could be represented either as

v-rec([v-field("a", v-num(1)), v-field("b", v-num(2))])

or as

v-rec([v-field("b", v-num(2)), v-field("a", v-num(1))])

depending on the implementation. Your tests must be agnostic to their representation to allow both of these possibilities. You may instead test that a record has the right shape by calling lookup on it.

(On the other hand, you can safely put test cases that return v-recs in your code file.)

3. The New Grammar

Here are the extended data definitions:

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)
  | v-rec(fields :: List<FieldVal>)

data FieldVal:
  | v-field(field-name :: String, value :: Value)

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)

  | e-rec(fields :: List<FieldExpr>)
  | e-lookup(rec :: Expr, field-name :: String)
  | e-extend(rec :: Expr, field-name :: String, new-value :: Expr)
  | e-with(rec :: Expr, body :: Expr)

  | sugar-and(left :: Expr, right :: Expr)
  | sugar-or(left :: Expr, right :: Expr)
  | sugar-let(bindings :: List<Binding>, body :: Expr)

data FieldExpr:
  | e-field(field-name :: String, value :: Expr)

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

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

And the extended grammar:

<expr> ::= <num>
         | true | false
         | <string>  # strings, surrounded by double quotes ""
         | (+ <expr> <expr>)    # addition
         | (++ <expr> <expr>)   # string append
         | (num= <expr> <expr>) # number equality
         | (str= <expr> <expr>) # string equality
         | (if <expr> <expr> <expr>)
         | (and <expr> <expr>)  # boolean and
         | (or <expr> <expr>)   # boolean or
         | (let ((<id> <expr>) (<id> <expr>) ...) <expr>)
         | <id>                    # identifier (a.k.a. variable)
         | (lam (<id> ...) <expr>) # anonymous function
         | (<expr> ...)            # function application

         | (record <field> ...) // each field must have a different name
         | (lookup <expr> <id>)
         | (extend <expr> <id> <expr>)
         | (with <expr> <expr>)

<field> ::= (<id> <expr>)   // field name, followed by field value

4. What to hand in

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

4.1 Test Cases

First submit your test cases (named "interp-record-tests.arr") in Captain Teach:

You must do this within the first two days of the assignment (so by Tuesday night at 11:59pm).

4.2 Reviews

Next, you will write and receive reviews like you did for interp-basic.

4.3 Test&Code Submission

Finally, submit a zip file containing both your test and code files for interp-records. Call the files "interp-record-tests.arr" and "interp-record-code.arr".