Note: this assignment will have test-case reviews. Turn them in by 11:59pm on Thursday.
For this assignment, you will modify your "Paret with Records" to use
call-by-need (i.e. lazy) evaluation. (There's one other small change:
has been removed from the language, however, since you have now seen why it is
a bad idea to have.)
This means that arguments to functions should not be evaluated if they are not
used in the body. As a result, many places your interpreter that used to work
with values, will instead work with
data Computation: | c-suspend(body :: Expr, env :: Env) | c-value(value :: Value) end
Computation is either a
c-suspend, which represents an argument that has
not yet been evaluated, or a
c-value, which has.
Function calls and the
rec constructor must be lazy: that is, a function
must not evaluate its argument if it is not used, and a record must not
evaluate its field if it in not used.
However, other primitives in the language should force their arguments to be
evaluated. Specifically, binary operators, unary operators, and
should force their arguments to be evaluated,
if should force its condition
to be evaluated, and
extend should force the record being extended to be
evaluated (but not the computations in its field). Likewise, the toplevel
interpreter should force its result to be evaluated (This is why
the code stencil, returns a
Value rather than a
For efficiency, when a computation is forced, its result should be cached so
that it doesn't have to be computed a second time. We have done this for you
in the code stencil with the
force function. It uses structural mutation to
make sure that a computation is only performed once (
ref marks a field as
mutable in Pyret):
data RefComputation: | r-comp(ref comp :: Computation) end
As before, you should avoid writing test cases in your test file that return v-recs, since there are multiple valid representations.
(On the other hand, you can safely put test cases that return v-recs in your code file.)
The data definitions are identical to those of your records interpreter,
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>) end data Computation: | c-suspend(body :: Expr, env :: Env) | c-value(value :: Value) end data RefComputation: | r-comp(ref comp :: Computation) end data FieldVal: | v-field(field-name :: String, value :: RefComputation) end data EnvCell: | env-cell(name :: String, value :: RefComputation) 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) | sugar-and(left :: Expr, right :: Expr) | sugar-or(left :: Expr, right :: Expr) | sugar-let(bindings :: List<Binding>, 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
Here is the 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>) <field> ::= (<id> <expr>) // field name, followed by field value
Here is the code stencil and the test stencil.
First submit your test sweep (named "interp-lazy-tests.arr") in Captain Teach:
You must do this Thursday night at 11:59pm.
Finally, submit a zip file containing both your test and code files for
interp-lazy. Call the files "interp-lazy-tests.arr" and