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: with
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 Computations
:
data Computation:
| c-suspend(body :: Expr, env :: Env)
| c-value(value :: Value)
end
A 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 lookup
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 eval
, in
the code stencil, returns a Value
rather than a Computation
.).
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,
modulo with
and Computations
.
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:
https://www.captain-teach.org/brown-cs173/assignments/
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
"interp-lazy-code.arr".