Note: this assignment will have test-case reviews. Turn them in by 11:59pm on Monday the 13th.
Note: 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, do, and rec-lam.
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!
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 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)
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:
((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 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.)
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
code stencil
and the
test stencil
in code.pyret.org.
First submit your test cases (named "interp-state-tests.arr") in Captain Teach:
https://www.captain-teach.org/brown-cs173/assignments/
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
"interp-state-code.arr".
https://www.captain-teach.org/brown-cs173/assignments/
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