Note: this assignment will have test-case reviews. Turn them in by 11:59pm on Monday the 13th.
rec is now a keyword in Pyret, so you may have to rename some
identifiers/field-names in your interp-records interpreter.
For this assignment, you will add state to the Paret language by allowing variable mutation.
The grammar and the abstract syntax have been extended with three new forms:
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
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!
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.)
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
(v ...), and body
where the function name
f is bound inside the body.
To adapt an example from the book, you could define a function
sums the numbers from
n by writing:
(rec-lam S (n) (if (num= n 0) 0 (+ n (S (+ n -1)))))
This simply defines the function. To call it, you could write:
((rec-lam S (n) (if (num= n 0) 0 (+ n (S (+ n -1))))) 3)
which should evaluate to 3+2+1 = 6.
You can also easily write infinite loops using
((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) 0 (+ n (S (+ n -1)))))
could desugar to:
(let ((S "dummy")) (set S (lam (n) (if (num= n 0) 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
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.)
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) end
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".
To get started, you can open the
First submit your test cases (named "interp-state-tests.arr") in Captain Teach:
You must do this by the test deadline (11:59pm on Monday the 13th).
Finally, submit a zip file containing both your test and code files for
interp-state. Call the files "interp-state-tests.arr" and
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 code.pyret.org: definitions)
type Env = List<EnvCell> type Store = List<StoreCell> data Result: | result(value :: Value, store :: Store) end 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>) end data FieldVal: | v-field(field-name :: String, value :: Value) end data EnvCell: | env-cell(name :: String, loc :: String) end data StoreCell: | store-cell(loc :: String, val :: Value) end 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) end data FieldExpr: | e-field(field-name :: String, value :: Expr) end data Binding: | binding(name :: String, expr :: Expr) end data Operator: | op-plus | op-append | op-str-eq | op-num-eq end 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) end