Interp: Lazy

Note: this assignment will have test-case reviews. Turn them in by 11:59pm on Thursday.

Your Task

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)

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)

2. Notes on Testing

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.)

3. The New Grammar

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>)

data Computation:
  | c-suspend(body :: Expr, env :: Env)
  | c-value(value :: Value)

data RefComputation:
  | r-comp(ref comp :: Computation)

data FieldVal:
  | v-field(field-name :: String, value :: RefComputation)

data EnvCell:
  | env-cell(name :: String, value :: RefComputation)

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)

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)

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

What to hand in

Here is the code stencil and the test stencil.

Test Submission

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

You must do this Thursday night at 11:59pm.

Test & Code Submission

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".