Last updated on

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:

  1. Extend an existing interpreter for a simple arithmetic language to handle a few new syntactic forms. This interpreter will use strict evaluation.
  2. 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/:

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)

src/main/scala/interpreter/Expr.scala

Just as a reminder:

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

src/main/scala/interpreter/Interpreter.scala

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

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

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.

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]

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

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:

  1. Your strict interpreter does not produce any errors when evaluating the expression;
  2. Your lazy interpreter produces the same value as the strict interpreter; and
  3. 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.

© 2023, 2024 EPFL. All rights reserved.