Last updated on Friday, December 19, 2025

Lazy evaluation interpreter

Points: 40 pts
Topics: Lazy evaluation, Interpreters, Program semantics
Files to submit: src/main/scala/interpreter/StrictInterpreter.scala; src/main/scala/interpreter/LazyInterpreter.scala

Overview

Your task in this exercise is to:

Extend an existing interpreter for a simple arithmetic language to handle a few new syntactic forms. This interpreter will use strict evaluation.
Write another interpreter for the same language that uses lazy evaluation.

The code for this exercise is organized as follows, in src/main/scala/interpreter/:

StrictInterpreter.scala and LazyInterpreter.scala contain the respective interpreters and are the only two files that will be considered for grading.
Expr.scala and Interpreter.scala contain common definitions that are used in both interpreters. In particular, both interpreters extend the trait Interpreter, take instances of the enum Expr as input expressions, and produce instances of the enum Result as output.
playground.worksheet.sc is for your convenience to test your interpreters as you work through this exercise. The playground, and the tests under src/test/, rely on ExprGen.scala and InterpreterWithCounter.scala. You do not need to understand the code in those two files. As usual, you can run the tests with test in sbt.

Recap: Arithmetic expressions with named variables

In one of the exercise sets in this course, you implemented an interpreter for arithmetic expressions with named variables. The interpreter kept track of variables in an environment or context that was passed around as an implicit parameter. We have provided a very similar strict interpreter that handles the following constructs in Expr.

enum NumOp:
  case Add
  case Sub
  case Mul
  case Div

enum Expr:
  case Num(n: Int)
  case NumExpr(op: NumOp, left: Expr, right: Expr)
  case Var(name: String)
  case Let(name: String, e: Expr, body: Expr)

lazyinterp/src/main/scala/interpreter/Expr.scala

Just as a reminder:

Let(name, e, body) binds the name name to the value of e in the current environment, and evaluates body in the resulting environment, such that…
Var(name) looks up the value associated with the name name in the given environment. This can result in an UnboundVariable error if the name was not previously bound with a Let. Looking up the value does not reevaluate the expression that produced the value.

The result of evaluating any expression is either a value or an error. The value of these simple expressions is always a number, and the error is one of a few cases of a custom enum.

enum Result[+V]:
  case Value(v: V)
  case InterpreterError(e: ErrorType) extends Result[Nothing]
  def success = this match
    case Value(v)            => true
    case InterpreterError(e) => false

enum ErrorType:
  case DivisionByZero
  case UnboundVariable(name: String)
  case NumOpOnNonNum

lazyinterp/src/main/scala/interpreter/Interpreter.scala

type StrictResult = Result[StrictValue]
enum StrictValue:
  case NumV(n: Int)

lazyinterp/src/main/scala/interpreter/Interpreter.scala

For instance, Let("x", NumExpr(Add, Num(1), Num(2)), NumExpr(Add, Var("x"), Var("x"))) evaluates to Value(NumV(6)). The expression NumExpr(Add, Num(1), Num(2)) is only evaluated once to bind the name "x" to the value Value(NumV(3)). On the other hand, Let("x", NumExpr(Div, Num(1), Num(0)), NumExpr(Add, Var("x"), Var("x"))) evaluates to Error(DivisionByZero).

Pairs and a conditional expression

In the language above, the value of any expression is a number or an error. Your task in this question is to extend the language with a new kind of value, pairs, and add a conditional expression.

enum StrictValue:
  // [...]
  case PairV(first: StrictValue, second: StrictValue)

enum Expr:
  // [...]
  case Pair(first: Expr, second: Expr)
  case PairExpr(op: PairOp, e: Expr)
  case IsPair(e: Expr)
  case If(cond: Expr, thene: Expr, elsee: Expr)

enum PairOp:
  case First
  case Second

Pair(first, second) evaluates to the value PairV(firstV, secondV) where firstV and secondV are the values of the expressions first and second, respectively, in the current environment. If either expression results in an error, the entire pair evaluates to that error. If both expressions result in an error, the entire pair evaluates to the error of first.
PairExpr(First, e) evaluates to the first component of the value of e if e evaluates to a pair. If not, the evaluation produces a PairOpOnNonPair error. PairExpr(Second, e) does the same but for the second component.
IsPair(e) evaluates to NumV(1) if e evaluates to a pair and NumV(0) otherwise.
If(cond, thene, elsee) is a conditional that first evaluates cond. If its value is a nonzero number, then the value of the entire expression is the value of thene, else it is the value of elsee. If the value of cond is not a number, the evaluation produces a IfCondNotNum error.

Question 1

Fill in the missing pieces in StrictInterpreter.scala marked with ??? to implement the behavior described above. topLevelEvaluate is the entry point to the interpreter, which calls the recursive function evaluate. A correct implementation will pass all the strict evaluation tests in TestInterpreter.scala. Run these tests with testOnly interpreter.TestInterpreter -- *strict*. Do not modify topLevelEvaluate.

A lazy interpreter

Now, you will work on a second interpreter for the same language that introduces laziness in two ways.

Let(name, e, body) will not immediately evaluate e to bind the value to name, but will defer that evaluation until the value is actually needed. It will proceed to evaluate body.
- Then, if body contains a Var(name), only then will e be evaluated to produce a value and proceed with the computation. Even if body refers to this name multiple times, e will be evaluated only the first time; but if body never refers to this name, e will never be evaluated.
Pair(first, second) will not immediately evaluate first and second, but will defer their evaluation until their values are actually needed. Let p refer to this pair.
- Then, the first time that PairExpr(First, p) is evaluated, first will be evaluated to produce a value and proceed with the computation. Again, it will be evaluated at most once, and it won’t be evaluated if it is never accessed. The same is independently true for Second.

Take a close look at the value, result, and environment types for the lazy interpreter.

enum LazyValue:
  case NumV(n: Int)
  case PairV(first: DeferredExpr, second: DeferredExpr)

case class DeferredExpr(e: Expr)(using Env):
  lazy val result: LazyResult = evaluate(e)

type LazyResult = Result[LazyValue]
type EvalResult = LazyResult
type Env = Map[String, DeferredExpr]

lazyinterp/src/main/scala/interpreter/LazyInterpreter.scala

Question 2

Fill in the missing pieces in LazyInterpreter.scala marked with ??? to implement the behavior described above. A correct implementation will pass all the lazy evaluation tests in TestInterpreter.scala. Run these tests with testOnly interpreter.TestInterpreter -- *lazy*. Do not modify topLevelEvaluate or force.

Then, run all tests with test in sbt. The “property-based tests” are explained below.

Tips for checking your work

Should the strict and lazy interpreters always agree?

When the strict interpreter evaluates an expression without errors, the lazy interpreter always produces the same value. But if the strict interpreter results in an error, the lazy interpreter may behave differently in some cases.

For example:

Let("x", NumExpr(Div, Num(1), Num(0)), Num(1))

lazyinterp/src/main/scala/interpreter/ExprGen.scala

With strict evaluation, the division expression is evaluated when the variable is bound, which produces Error(DivisionByZero). However, since the variable is never used in the body, the division expression is never evaluated under lazy evaluation, and the whole expression evaluates to Value(NumV(1)).

How do we know that lazy evaluation is indeed saving us unnecessary work?

The tests count how many recursive calls each interpreter makes for evaluating an expression. (You can also check these counts in the playground worksheet. You do not need to understand how the counters are implemented.) By evaluating expressions which are known to have unnecessary computations—variables that are never referenced, pairs whose components are never accessed—the tests assert that the lazy interpreter recurses fewer times than the strict interpreter.

Property-based testing

The tests in TestInterpreterProperties.scala generate random “safe” expressions that should not result in any errors, and test three properties for each expression:

Your strict interpreter does not produce any errors when evaluating the expression;
Your lazy interpreter produces the same value as the strict interpreter; and
Your lazy interpreter recurses fewer times than your strict interpreter.

If an expression does not verify these three properties, it will be reported in the test output. We recommend copying it into the worksheet and applying the usual debugging techniques to fix the issue.