Last updated on Monday, October 14, 2024

Lab 3: calculator

Introduction

Before starting to do this lab, check the callback for find lab first!

In this lab, you will craft a calculator that understands and evaluates arithmetic expressions. You can feed expressions to it, like 1/2+5*5. In response, it will reply with 25.5:

> 1/2+5*5
25.5
>

You will start from a basic calculator that evaluates simple arithmetic expressions. As you progress, you add features to the calculator, including divisions and variables. In the end, the calculator can not only evaluate an expression but also simplify it. For instance, a * (3 - 2) can be simplified to a.

Throughout this lab, you will:

• Sharpen your Scala programming basics;
• Exercise your understanding of classes and enums;
• Use pattern matching to analyze enum values;
• Reason about recursive data structures (represented as enums) and implement functions on them.

Logistics

• Before we begin, make sure you are familiar with our course policies concerning lab assignments, plagiarism, grading, etc.
• Ready to get started? You can grab the materials by executing the command in your terminal:

git clone https://gitlab.epfl.ch/lamp/cs-214/calculator.git

• Once you are done, submit the following files to Moodle:

src/main/scala/calculator/tiny/TinyPrinter.scala
src/main/scala/calculator/tiny/TinyEvaluator.scala
src/main/scala/calculator/basic/BasicEvaluator.scala
src/main/scala/calculator/full/FullEvaluator.scala
src/main/scala/calculator/full/AlgebraicSimplifier.scala
src/main/scala/calculator/full/ConstFoldSimplifier.scala
src/main/scala/calculator/full/FullSimplifier.scala
src/main/scala/HowManyHoursISpentOnThisLab.scala

Expressions as Trees

Arithmetic expression is a minimal form of a programming language. Surprisingly, the methodologies and principles employed to construct the calculator in this lab bear significant resemblance to those utilized in programming language interpreters and compilers.

How a calculator evaluates an expression? Let’s start with a concrete example: 1 + 2 * 3. The calculator’s first job is to parse it. To parse is similar to understand the structure of the expression: the calculator scans the text, understands how it forms a expression, and then turns it into a tree—what we call an Abstract Syntax Tree (AST).

For instance, the AST of 1 + 2 * 3 looks like the following:

• The nodes representing operations, such as + and *, are branches in the tree.
• Each branch has two child nodes, that stand for the operands. For instance, the + node branches out to the node for 1 and the subtree for 2 * 3.
• At the bottom of the tree are the leaf nodes, which represents numbers. As you advance, these could represent variables as well.

Want to see more examples? Type your own arithmetic expression below and its AST will be displayed.

Representing Trees as Enums

We have seen with examples how expressions can be parsed and represented as trees. How to get these trees into our Scala code?

Scala’s enums are perfect for this. With them, you can encode recursive structures, just like the expression trees. The following enum represents ASTs.

enum Expr:
  case Number(v: Double)
  case Add(e1: Expr, e2: Expr)
  case Minus(e1: Expr, e2: Expr)
  case Mul(e1: Expr, e2: Expr)
  case Div(e1: Expr, e2: Expr)
  case Neg(e: Expr)

The enum mirrors the structure of ASTs with remarkable fidelity:

• An Add case corresponds to a + node, with its two fields, e1 and e2, representing the two children respectively.
• A Number case is a leaf node.

As a concrete example, to represent the AST of 1 + 2 * 3, you would write:

Add(Number(1), Mul(Number(2), Number(3)))

Add(Number(1), Mul(Number(2), Neg(Add(Number(3), Number(4)))))

Neg(Add(Mul(Number(1), Number(2)), Mul(Number(3), Add(Number(4), Number(5)))))

Warmup: Printing Expressions

Before jumping into crafting your calculator, let’s exercise a bit to get a feeling of expressions. You will write two functions that print expressions—but in very different styles.

Printer 1: show (not graded)

The first task: print the expression just like how you see it in Scala. This is called an in-order traversal. For instance, 1 + 2 should be printed as Add(Number(1.0),Number(2.0)). In fact, this is how the built-in toString method prints the expression enum. To see it in action, check the worksheet at src/main/scala/printers.worksheet.sc.

Here is the skeleton to be completed:

  /** Re-implement the `toString` function of TinyExpr. */
  def show(e: TinyExpr): String =
    "42" // TODO: modify this

You could use the worksheet to experiment with your implementation. Test cases prefixed with show: can be used to test your code. To run these tests, open the sbt console and enter testOnly -- "*show:*".

  /** Re-implement the `toString` function of TinyExpr. */
  def show(e: TinyExpr): String =
    e match
      case Number(value) => f"Number($value)"
      case Add(e1, e2)   => f"Add(${show(e1)},${show(e2)})"
      case Minus(e1, e2) => f"Minus(${show(e1)},${show(e2)})"
      case Mul(e1, e2)   => f"Mul(${show(e1)},${show(e2)})"
      case Neg(e)        => f"Neg(${show(e)})"

Printer 2: toPolish

One of the optional exercises in week 1 looked at polish notation.

Let’s generate Polish notation expressions, rather than evaluating them.

For example, 1 + 1 should be printed as + 1 1 and 1 + 2 * 3 be printed as + 1 * 2 3.

Specially, use -- for negation to disambiguate negation and subtraction. For instance, (1 + -2) - 3 should be printed as - + 1 -- 2 3.

Now, complete the following function:

  /** Print the expression in Polish notation. */
  def toPolish(e: TinyExpr): String =
    "42" // TODO: modify this

Feel free to experiment with it in the worksheet. Your objective: passing all the tests prefixed by toPolish:.

Evaluating Simple Arithmetic Expressions

Now you are ready to start working with the calculator: your task is to complete the missing parts in it. The infrastructure of the calculator is in place, including components such as the parser and a simple command-line interface. What is missing is the core components that understands and processes the ASTs. For instance, the evaluator. Your job is to flesh them out.

📝 Important: don’t forget to fill in how many hours you spent on this lab in HowManyHoursISpentOnThisLab.scala to pass the last test.

Interacting with Your Calculator

Before you diving into coding, let’s first seeing your calculator lively! You have two ways to interact with it.

Terminal

This is a calculator console running inside the terminal. To run it, first start sbt within the top directory of the lab. When sbt is active, run runMain cs214.cli.main to bring the calculator console up and running. The following exemplifies what you could expect:

> 1
1.0
> 1+1
2.0
> 1+1-2
0.0
> 1+2*3
7.0
> 1+
Error:
 1 | 1+
      ^
      unexpected EOF, expecting start of expression

>

Webpage

If you prefer a visual interface, go for the web-based UI! To start it, run runMain cs214.ui.main in the sbt console. Then, open http://127.0.0.1:8080 in your browser.

Fleshing out the Evaluator

Give your calculator a try by typing something in it! For instance, 1 + 2 * 3 and 100 * 100. You may already notice that the calculator invariably responds with 42.0. This is because the evaluator is not yet implemented, and rectifying it is your first task!

We will start simple with the evaluator for TinyExpr, which includes numbers, addition, subtraction, multiplication and negation. You can find its definition in tiny/TinyExpr.scala.

Now, complete the evaluate function:

  /** Evaluate an expression to its value. */
  def evaluate(e: TinyExpr): Double =
    42 // TODO: modify this

Experiment with the calculator and tweak your implementation as needed. When you are confident it is working, test it by commanding testOnly -- "*TinyEvaluator:*" in the sbt console.

In case any test fails, do not worry too much! The error message shows the expression that makes your calculator behave incorrectly. Use that counter-example to pinpoint the problem in your evaluator.

Division by Zero?

So, you have built a calculator. It adds, it subtracts, it multiplies. But what about division? The challenge with division is that dividing by zero is mathematically undefined. It this section, you will extend your calculator so that it handles that gracefully.

The following enum, BasicEvaluator.Result, will serve as the result type of our next evaluate function:

enum Result:
  case Ok(v: Double)
  case DivByZero

It has two cases, one returning the evaluated result when the evaluation succeeds, the other indicating that a division-by-zero error occured.

You have already completed the evaluate function for TinyExpr. Now you will finish the one for BasicExpr, which includes the division operation.

  /** Evaluate an expression to its value. */
  def evaluate(e: BasicExpr): Result =
    Ok(42) // TODO: modify this

The result type is BasicEvaluator.Result. Use the DivByZero case to signal an error when needed!

Your code should pass all tests prefixed by BasicEvaluator:.

Here Come Variables

Now, your calculator supports basic arithmetics and gracefully handles division-by-zero. Now it’s time to add another exciting new feature: variables!

Think of a variable like a placeholder in an expression, a slot reserved for a value we not yet know. For instance, in a * a + 2 * a * b + b * b, a and b are variables. When we want to evaluate an expression containing variables, we “plug in” numbers for these variables to get a numerical answer. Let’s say we assign a with 1 and b with -1, a * a + 2 * a * b + b * b yields the result 0.0.

How do we associate variables with values? Contexts! A context is like a dictionary that tells us what each variable stands for. In this week’s exercise, we have seen two ways to represent contexts: an enum, or a function.

Pick your favorite one! Replace Unit with your chosen type for context representation in the following line:

  type Context =
    Unit // TODO: modify this

enum MyContext:
  /* cases */

type Context =
  MyContext

enum LookupResult:
  /* cases */

type Context =
  String => LookupResult

Next, implement two functions for your context: empty and cons.

Context.empty returns an empty context:

def empty: Context =
  () // TODO: modify this

Context.cons adds a new variable and its value into the context:

def cons(name: String, value: Double, tail: Context) =
  () // TODO: modify this

Now you are ready to accommodate variables in the evaluator. Complete the evaluate function in FullEvaluator to evaluate FullExpr, which is the expression type that includes variables:

  /** Evaluate an expression to its value. */
  def evaluate(e: FullExpr): Result =
    Ok(42) // TODO: modify this

Note that the Context used for evaluating the expression is passed as ctx, a class parameter of the FullEvaluator class.

The objective: your code should pass all the tests prefixed by FullEvaluator:.

Expression Simplification

You have conquered basic arithmetics and variable handling. The next step is even more interesting: expression simplification. We have designed minimalist test cases to help you debug your implementation. We recommend working through these tests carefully: if a test fails, run the algorithm by hand, for this test, on paper, and see when and why things go wrong.

Why Simplify?

Expressions with variables can represent formulas that are invoked repeatedly with variables being set to different values. For instance, 2 * 3.1415 * r is a formula for the perimeter of circles.

Simplifying them results in smaller expressions that saves redundant calculation. Imagine evaluating an expression like a * (1 + 0 * (b + c + d)). Even without knowing the values of a, b, c, and d, we can tell that this is the same as just a. Also, 2 * 3.1415 * r can be simplified to 6.2830 * r, saving the redundant calculation of the constant part each time the formula is used.

Senior track

Three Types of Simplifications

We will explore three expression simplifiers, each simplifying expressions in different ways.

Constant Folding

Let’s start with constant folding! It simplifies constant sub-expressions. You have already seen the example for the perimeter of circles. More examples: a + 2 * 3 can be constant folded into a + 6; a + b * (3 + 3) can be simplified to a + b * 6.

Complete the function below:

def simplify(e: FullExpr): FullExpr =
  e // TODO: modify this

Your objective is to pass the all tests prefixed by ConstFoldSimplifier:.

To interact with your simplifier:

• Terminal: :constfold in calculator console or runMain cs214.cli.main constfold in sbt.
• Webpage: select Full as the expression type. The two tabs Constfolded and Constfolded (AST) show the results.

Algebraic Simplification

The second simplifier manipulates expressions in a more interesting way. It simplifies them as much as possible based on the following algebraic rules:

• 0 + e = e + 0 = e
• 0 - e = -e
• e - 0 = e
• 0 * e = e * 0 = 0
• 1 * e = e * 1 = e
• e / 1 = e
• e - e = 0
• -(-e) = e

For instance, the expression a * 1 - a / 1 can be simplified to 0.0 with these rules.

However, is this set of rules complete? What else could we simplify?

Your task:

def simplify(e: FullExpr): FullExpr =
  e // TODO: modify this

To interact with your simplifier, switch to the algebraic mode of the calculator console. On the web UI, select the Full expression type and there are two tabs, Algebraic Simplified and Algebraic Simplified (AST), show the simplified expression and its AST.

Run testOnly -- "*AlgebraicSimplifier:*" to test your simplifier. If any test fails, try working with pen and paper to break down the process and pinpoint where your simplifier goes astray.

Combined Simplification

In this section, you will create a new simplifier that combine the bests of both worlds: constant-folding and algebraic simplification.

Sometimes, one method of simplification opens the door for another. For instance, the expression (3 - 2) * (a * 1) - a gets constant-folded to 1 * (a * 1) - a, and algebraically simplified to (3 - 2) * a - a. But when the two simplifiers work together, they simplify the expression to 0.0.

At first, the natural idea that comes to mind is to simply combine the above simplification methods, either as constfold `andThen` algebraic or as algebraic `andThen` constfold.

Does it always work?
On paper, come up with an expression that doesn’t get fully simplified with either one of the compositions above.

Based on what we just described, naive composition does not always produce the correct result. Using pen and paper, try coming up with another solution.

Implement a new simplifier, covering all simplifications performed by both previous simplifiers.

def simplify(e: FullExpr): FullExpr =
  e // TODO: modify this

To interact with the simplifier:

• In terminal, switch to the simp mode.
• On the webpage, choose Full expressions, and see the tags Fully Simplified and Fully Simplified (AST).

Your implementation should pass all tests prefixed by FullSimplifier:.

Bonus: Refactor simplify 🔥

This part is optional and not graded.

The version of simplify you came up with is probably verbose and repetitive. Can you extract common patterns between constfold and algebraic to eliminate the duplication?

© 2023, 2024 EPFL. All rights reserved.