We've spent the last few lessons talking about the theory of pattern matching and algebraic data types, but it's one thing to read about it and another to actually use it to structure a program. To get this to stick, I want us to build a tiny interpreter. We aren't building a full-blown language—just a basic expression evaluator that can handle numbers, addition, multiplication, and variables.

Defining our Expression Language

Whenever I'm building an interpreter, I start by defining the "shape" of the data. In Scala, the gold standard for this is a sealed trait. By marking it sealed, I'm telling the compiler that all possible subtypes are defined in this file. This is huge because if I miss a case in my pattern match later, the compiler will actually yell at me.

sealed trait Expr
case class Num(value: Int) extends Expr
case class Add(left: Expr, right: Expr) extends Expr
case class Mul(left: Expr, right: Expr) extends Expr
case class Var(name: String) extends Expr

I've chosen these four because they cover the basics: a leaf node (Num), recursive nodes (Add and Mul), and a placeholder (Var). This creates a tree structure, which is exactly how most compilers represent code internally.

Writing the Evaluation Logic

Now we need a way to turn these Expr objects into an actual integer result. This is where the pattern matching magic happens. I'll write a function that recursively walks down the tree until it hits a number.

def eval(expr: Expr): Int = expr match {
  case Num(n) => n
  case Add(l, r) => eval(l) + eval(r)
  case Mul(l, r) => eval(l) * eval(r)
  case Var(name) => 0 // Wait, this is wrong.
}

Fixing the "Missing Context" Bug

I just caught myself making a classic mistake. I defined Var in my data model, but in my eval function, I just returned 0 because I didn't have any way to know what the variable was actually worth. A variable isn't a constant; it needs a context (or an environment).

I can't just hardcode values inside the function. I need to pass a map of variable names to values into the eval function. Let's rewrite the signature to fix this.

def eval(expr: Expr, env: Map[String, Int]): Int = expr match {
  case Num(n) => n
  case Add(l, r) => eval(l, env) + eval(r, env)
  case Mul(l, r) => eval(l, env) * eval(r, env)
  case Var(name) => env.getOrElse(name, throw new Exception(s"Variable $name not found!"))
}

Now the logic is sound. If the interpreter hits a Var, it looks it up in the env map. If it's not there, it throws an exception. It's simple, but it's the core loop of almost every interpreted language in existence.

Putting it all together

To see it in action, we just need to construct a tree and provide a context. Let's say we want to calculate (x + 5) * 2 where x is 10.

val expression = Mul(
  Add(Var("x"), Num(5)), 
  Num(2)
)

val context = Map("x" -> 10)
val result = eval(expression, context) 
println(result) // Output: 30

The beauty here is how clean the eval function remains. We don't have if/else chains or type casting. We just describe what the data looks like and what to do with it. If we wanted to add a Subtract or Divide case, we'd just add a case class to the trait and one line to the match block.

📋 Practical Task

Adding Subtraction and Power Operators to the Expression Evaluator

Now it's your turn to extend the interpreter. I've given you the base code, but it's missing a few common mathematical operations.

Your Task:

• Modify the Expr trait to include two new case classes: Sub(left: Expr, right: Expr) and Pow(base: Expr, exponent: Expr).
• Update the eval function to handle these new cases. For Pow, you can use scala.math.pow (remember that it returns a Double, so you'll need to convert it back to an Int).
• Create a test expression that represents (10 - 2) ^ 2 (which should result in 64) and evaluate it.

sealed trait Expr
case class Num(value: Int) extends Expr
case class Add(left: Expr, right: Expr) extends Expr
case class Mul(left: Expr, right: Expr) extends Expr
case class Var(name: String) extends Expr
// Add your new case classes here

def eval(expr: Expr, env: Map[String, Int]): Int = expr match {
  case Num(n) => n
  case Add(l, r) => eval(l, env) + eval(r, env)
  case Mul(l, r) => eval(l, env) * eval(r, env)
  case Var(name) => env.getOrElse(name, throw new Exception(s"Variable $name not found!"))
  // Add your new match cases here
}