Interp: State

Note: Please assume left-to-right evaluation order!

For this assignment, you will add state to the Paret language by allowing variable mutation.

1. The Extended Language

The grammar and the abstract syntax have been extended with three new forms: set, do, and rec-lam.

1.1 set

set takes an identifier and an expression, evaluates the expression to a value, and assigns that value to the identifier by changing its value in the store. The result of a set expression is the new value of the identifier. For instance, the Paret program

(let ((x 1)) (set x 2))

should evaluate to 2.

If the identifier in a set expression is not in scope, you should raise an err-unbound-id exception -- it doesn't make sense to change the value of an identifier not bound in the environment!

1.2 do

do takes a sequence of expressions and evaluates them in order. It returns the value of the last expression in the sequence. do always has at least one subexpression. (The parser will enforce this.)

1.3 rec-lam

rec-lam is a new piece of syntactic sugar that defines a recursive function. It's very similar to lam, except that it also takes a function name which can be used in its body. More precisely,

(rec-lam f (v ...) b)

constructs a function with name f, arguments (v ...), and body b, where the function name f is bound inside the body.

To adapt an example from the book, you could define a function S that sums the numbers from 0 to n by writing:

(rec-lam S (n) (if (num= n 0)
                   (+ n (S (+ n -1)))))

This simply defines the function. To call it, you could write:

((rec-lam S (n) (if (num= n 0)
                    (+ n (S (+ n -1)))))

which should evaluate to 3+2+1 = 6.

You can also easily write infinite loops using rec-lam:

((rec-lam forever () (forever)))

Please don't submit tests that run forever, though.

You will define a desugaring for rec-lam in your desugar function. It can be desugared to first let-bind the function name to a dummy value (which will never be seen), then set it to the function it should be, and finally return the function. So the first example:

(rec-lam S (n) (if (num= n 0)
                   (+ n (S (+ n -1)))))

could desugar to:

(let ((S "dummy"))
  (set S (lam (n) (if (num= n 0)
                      (+ n (S (+ n -1)))))))

There's a problem, though: this expression has let in it, which is itself syntactic sugar. You can get around this by expanding the let expression with a recursive call to desugar. (This kind of recursion, where instead of just recurring on your arguments you build up a new thing and then recur on that, is called generative recursion.)

2. What to Do

Your task is to add state to Paret. You should closely follow the store-passing style we studied in class and that is presented in the book. We have added the following definition for the store:

type Store = List<StoreCell>

data StoreCell:
  | store-cell(loc :: String, val :: Value)

You will need to generate store locations, and can use the built-in gensym function to do so. You can call gensym("loc") to obtain a fresh name that starts with "loc".

2.1 Getting Started

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

2.2 Submission

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

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

3. The New Grammar

Here is the extended grammar:

<expr> ::= <num>
         | true | false
         | <string>
         | (+ <expr> <expr>) 
         | (++ <expr> <expr>)
         | (num= <expr> <expr>)
         | (str= <expr> <expr>)
         | (if <expr> <expr> <expr>)
         | (and <expr> <expr>)
         | (or <expr> <expr>)
         | (let ((<id> <expr>) (<id> <expr>) ...) <expr>)
         | <id>
         | (lam (<id> ...) <expr>)
         | (<expr> ...)
         | (record <field> ...)
         | (lookup <expr> <id>)
         | (extend <expr> <id> <expr>)
         | (with <expr> <expr>)

         | (set <id> <expr>)
         | (do <expr> <expr> ...)
         | (rec-lam <id> (<id> ...) <expr>)

<field> ::= (<id> <expr>)

And the extended data definitions:

(For reference, here they are in definitions)

type Env = List<EnvCell>

type Store = List<StoreCell>

data Result:
  | result(value :: Value, store :: Store)

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, loc :: String)

data StoreCell:
  | store-cell(loc :: String, val :: 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(record :: Expr, field-name :: String)
  | e-extend(record :: Expr, field-name :: String, new-value :: Expr)
  | e-with(record :: Expr, body :: Expr)

  | e-set(name :: String, val :: Expr)
  | e-do(stmts :: List<Expr>)

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

  | sugar-rec-lam(fun-name :: String, params :: List<String>, 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

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(record :: Value, field-name :: String)