Week 2 Code Snippets (SP26)

Author: Stefan Mitsch

Week 2 Overview

This summary follows the code snippets developed in class: classes and objects, algebraic data types, and pattern matching in Scala.

We start with how class bodies execute, then move to operator methods and companion objects, and finally compare object-oriented and functional encodings of expressions before ending with focused pattern matching examples.

1) Class Body Execution and Initialization Order

The first example shows that Scala class bodies contain executable constructor code. Field initializers run in order, and lazy val defers work until first access.

class Simple:
  println("Line 1 of the constructor")

  val x =
    println("Field x initialized")
    5

  lazy val y =
    println("Memoized def field y initialized")
    7

  println("Line 2 of the constructor")

  def getX =
    println("getX called")
    x

  println("Line 3 of the constructor")
end Simple

After seeing class construction behavior, we can define a more useful class with state-derived fields and an operator method.

2) A Matrix Class With an Operator Method

This example defines a matrix shape from nested lists and overloads + for element-wise addition.

class Matrix(data: List[List[Int]]):
  val rows = data.length
  val cols = if rows > 0 then data.head.length else 0

  def +(other: Matrix): Matrix =
    if this.rows != other.rows || this.cols != other.cols then
      throw new IllegalArgumentException("Matrices must have the same dimensions for addition")

    val newData =
      for i <- 0 until rows yield
        for j <- 0 until cols yield
          this.data(i)(j) + other.data(i)(j)

    new Matrix(newData.map(_.toList).toList)
  end +
end Matrix

Once a class exists, a companion object gives cleaner construction APIs.

3) Companion Object and apply

A companion object can provide factory methods. With apply, users can instantiate without explicitly writing new.

object Matrix:
  def empty(): Matrix = new Matrix(List.empty)
  def apply(): Matrix = empty()
end Matrix

val m1 = new Matrix(List.empty)
val m2 = Matrix.empty()
val m3 = Matrix() // calls Matrix.apply()

Now we broaden from one concrete class to a family of expression nodes.

4) Object-Oriented Expression Evaluator

In the OO style, each node class implements behavior through dynamic dispatch (discussed later in the course). We use a trait (similar to a Java interface) to specify operations common to all expressions. Concrete implementations NumberOO, PlusOO, and TimesOO of the expression trait each implement a fragment of the full eval and toText functionality.

trait ExprOO:
  def eval: Int
  def toText: String
end ExprOO

class NumberOO(x: Int) extends ExprOO:
  def eval = x
  def toText = x.toString
end NumberOO

class PlusOO(l: ExprOO, r: ExprOO) extends ExprOO:
  def eval = l.eval + r.eval
  def toText = l.toText + " + " + r.toText
end PlusOO

class TimesOO(l: ExprOO, r: ExprOO) extends ExprOO:
  def eval = l.eval * r.eval
  def toText = l.toText + " * " + r.toText
end TimesOO

val e: ExprOO = new PlusOO(new NumberOO(3), new NumberOO(5))
val value = e.eval

In object-oriented languages, adding new classes is easy; it is harder to understand the full functionality of eval and toText, because their implementation is spread over many classes. Adding new functionality may require changing many existing classes (as opposed to a single function in functional programming).

The functional style keeps data definitions together and puts operations into separate pattern-matching functions.

5) Functional Expression Evaluator With an ADT

Here we encode expression syntax as an algebraic data type (enum) and process it with functions.

enum Expr:
  case Number(x: Int)
  case Plus(l: Expr, r: Expr)
  case Times(l: Expr, r: Expr)
end Expr

import Expr.*

def eval(e: Expr): Int = e match
  case Number(x)   => x
  case Plus(l, r)  => eval(l) + eval(r)
  case Times(l, r) => eval(l) * eval(r)
end eval

def toText(e: Expr): String = e match
  case Number(x)   => x.toString
  case Plus(l, r)  => toText(l) + " + " + toText(r)
  case Times(l, r) => toText(l) + " * " + toText(r)
end toText

In functional programming languages, adding new functions is easy; it is harder to understand the full functionality of a certain class, like Plus, because it is spread over many functions. Extending the algebraic datatype may require changing many different functions (not just adding a single class as in object-oriented programming).

6) Pattern Matching on a Custom List ADT

This section shows how to model lists directly as ADTs and deconstruct them with exhaustive matches.

enum MyList:
  case Empty
  case Cons(x: Int, rest: MyList)
end MyList

The ADT MyList creates a namespace, so we import the elements of the ADT with an import expression (alternatively, we can use fully qualified names MyList.Empty and MyList.Cons).

import MyList.*

We instantiate lists as follows:

val l = Cons(1, Cons(2, Cons(3, Empty)))

Next, we implement simple functions to operate on the MyList ADT.

def isEmpty(xs: MyList): Boolean = xs match
  case Empty      => true
  case Cons(_, _) => false
end isEmpty

def head(xs: MyList): Int = xs match
  case Empty      => throw new NoSuchElementException()
  case Cons(a, _) => a
end head

def second(xs: MyList): Int = xs match
  case Cons(_, Cons(s, _)) => s
  case _                   => throw new NoSuchElementException()
end second

As an alternative to modeling ADTs using enum, trait and case class/case object with explicit inheritance achieve the same effect.

// explicit classes
trait MyList2
case object Empty2 extends MyList2
case class Cons2(x: Int, rest: MyList2) extends MyList2

val list = new Cons2(1, new Cons2(2, Empty2))

Scala also supports the same pattern-matching ideas over very small enums, which is useful for finite domains.

7) Small Enum Example: Colors

enum Color:
  case White
  case Blue
end Color

import Color.*

def asText(x: Color): String = x match
  case White => "White"
  case Blue  => "Blue"
end asText

Week 2 Alternative Implementations in Java, Python, and C

Calculator in Java

Java was originally designed as an object-oriented language, but more and more features of functional languages become available in modern Java.

Object-Oriented Implementation

public interface Expr {
  public int eval();
  public String print();
}

public class Number implements Expr {
  private final int x;

  public Number(int x) {
    this.x = x;
  }

  @Override
  public int eval() {
    return x;
  }

  @Override
  public String print() {
    return Integer.toString(x);
  }
}

public class Plus implements Expr {
  private final Expr left;
  private final Expr right;

  public Plus(Expr left, Expr right) {
    this.left = left;
    this.right = right;
  }

  @Override
  public int eval() {
    return left.eval() + right.eval();
  }

  @Override
  public String print() {
    return "(" + left.print() + " + " + right.print() + ")";
  }
}

public class Times implements Expr {
  private final Expr left;
  private final Expr right;

  public Times(Expr left, Expr right) {
    this.left = left;
    this.right = right;
  }

  @Override
  public int eval() {
    return left.eval() * right.eval();
  }

  @Override
  public String print() {
    return "(" + left.print() + " * " + right.print() + ")";
  }
}

Functional Implementation

Java 21 provides record patterns and pattern matching switch. These can be used to implement our calculator in a functional style in Java. The base interface is sealed so that the compiler can check that the switch lists all records exhaustively (without sealed, additional implementations of Expr could be added elsewhere in the program). The Java code uses var to declare a variable without annotated type (i.e., use type inference). Like var in Scala, var in Java does also mean mutability and we can use final to make a variable immutable (final var).

public class FunctionalCalculator {

  sealed interface Expr {}

  record Number(int x) implements Expr {}

  record Plus(Expr left, Expr right) implements Expr {}

  record Times(Expr left, Expr right) implements Expr {}

  public static int eval(Expr expr) {
    return switch (expr) {
      case Number(var x)              -> x;
      case Plus(var left, var right)  -> eval(left) + eval(right);
      case Times(var left, var right) -> eval(left) * eval(right);
    };
  }

  public static String print(Expr e) {
    return switch (e) {
      case Number(var x)              -> Integer.toString(x);
      case Plus(var left, var right)  -> "(" + print(left) + " + " + print(right) + ")";
      case Times(var left, var right) -> "(" + print(left) + " * " + print(right) + ")";
    };
  }

  public static void main(String[] args) {
    Expr expr = new Plus(new Number(1), new Times(new Number(2), new Number(3)));
    System.out.println("Expression: " + print(expr));
    System.out.println("Evaluated Result: " + eval(expr));
  }
}

Implementation in Python

Python has object-oriented features and, with @dataclass we can emulate algebraic datatypes. Pattern matching is an enhancement proposal PEP 634; we use conditionals based on type tests instead.

Object-Oriented Implementation

class Expr:
  def eval(self):
    raise NotImplementedError

  def print(self):
    raise NotImplementedError

class Number(Expr):
  def __init__(self, x):
    self.x = x

  def eval(self):
    return self.x

  def print(self):
    return str(self.x)

class Plus(Expr):
  def __init__(self, left, right):
    self.left = left
    self.right = right

  def eval(self):
    return self.left.eval() + self.right.eval()

  def print(self):
    return f"({self.left.print()} + {self.right.print()})"

class Times(Expr):
  def __init__(self, left, right):
    self.left = left
    self.right = right

  def eval(self):
    return self.left.eval() * self.right.eval()

  def print(self):
    return f"({self.left.print()} * {self.right.print()})"

if __name__ == "__main__":
    expr1 = Plus(Number(3), Number(4))
    expr2 = Times(Number(5), Plus(Number(2), Number(3)))

    print(f"Expression 1: {expr1.print()} = {expr1.eval()}")
    print(f"Expression 2: {expr2.print()} = {expr2.eval()}")

Emulating Functional Implementation

from dataclasses import dataclass

@dataclass
class Number:
  x: int

@dataclass
class Plus:
  left: 'Expr'
  right: 'Expr'

@dataclass
class Times:
  left: 'Expr'
  right: 'Expr'

Expr = Number | Plus | Times

def eval(expr: Expr) -> int:
  if isinstance(expr, Number):
    return expr.x
  elif isinstance(expr, Plus):
    return eval(expr.left) + eval(expr.right)
  elif isinstance(expr, Times):
    return eval(expr.left) * eval(expr.right)
  else:
    raise ValueError("Unknown expression type")

def print_expr(e: Expr) -> str:
  if isinstance(e, Number):
    return str(e.x)
  elif isinstance(e, Plus):
    return f"({print_expr(e.left)} + {print_expr(e.right)})"
  elif isinstance(e, Times):
    return f"({print_expr(e.left)} * {print_expr(e.right)})"
  else:
    raise ValueError("Unknown expression type")

if __name__ == "__main__":
    expr1 = Plus(Number(3), Number(4))
    expr2 = Times(Number(5), Plus(Number(2), Number(3)))

    print(f"Expression 1: {print_expr(expr1)} = {eval(expr1)}")
    print(f"Expression 2: {print_expr(expr2)} = {eval(expr2)}")

Implementation in C

In C, we do not have access to runtime type information. As a consequence, we must create type tags ourselves (ExprType). The type Expr uses a type tag type to identify the alternative of the union type int | struct. We use the type tag in switch statements to determine which implementation to choose. Due to manual memory management, the print function is especially verbose.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {
  NUMBER,
  PLUS,
  TIMES
} ExprType;

typedef struct Expr Expr;

struct Expr {
  ExprType type;
  union {
      int number;
      struct {
          Expr* left;
          Expr* right;
      } binary;
  } data;
};

Expr* make_number(int x) {
  Expr* e = malloc(sizeof(Expr));
  e->type = NUMBER;
  e->data.number = x;
  return e;
}

Expr* make_binary(Expr* left, Expr* right, ExprType type) {
  Expr* e = malloc(sizeof(Expr));
  e->type = type;
  e->data.binary.left = left;
  e->data.binary.right = right;
  return e;
}

Expr* make_plus(Expr* left, Expr* right) {
  return make_binary(left, right, PLUS);
}

Expr* make_times(Expr* left, Expr* right) {
  return make_binary(left, right, TIMES);
}

int eval(Expr* expr) {
  switch (expr->type) {
    case NUMBER:
      return expr->data.number;
    case PLUS:
      return eval(expr->data.binary.left) + eval(expr->data.binary.right);
    case TIMES:
      return eval(expr->data.binary.left) * eval(expr->data.binary.right);
    default:
      return 0; // error
  }
}

char* print_expr(Expr* e) {
  char* left_str;
  char* right_str;
  char* result;
  switch (e->type) {
    case NUMBER:
      result = malloc(12); // enough for int
      sprintf(result, "%d", e->data.number);
      return result;
    case PLUS:
      left_str = print_expr(e->data.binary.left);
      right_str = print_expr(e->data.binary.right);
      result = malloc(strlen(left_str) + strlen(right_str) + 6); // ( +  )
      sprintf(result, "(%s + %s)", left_str, right_str);
      free(left_str);
      free(right_str);
      return result;
    case TIMES:
      left_str = print_expr(e->data.binary.left);
      right_str = print_expr(e->data.binary.right);
      result = malloc(strlen(left_str) + strlen(right_str) + 6);
      sprintf(result, "(%s * %s)", left_str, right_str);
      free(left_str);
      free(right_str);
      return result;
    default:
      return NULL;
  }
}

void free_expr(Expr* expr) {
  if (expr->type != NUMBER) {
    free_expr(expr->data.binary.left);
    free_expr(expr->data.binary.right);
  }
  free(expr);
}

int main() {
  Expr* expr = make_plus(
    make_number(3),
    make_times(
      make_number(4),
      make_number(5)
    )
  );

  char* expr_str = print_expr(expr);
  int result = eval(expr);

  printf("Expression: %s\n", expr_str);
  printf("Result: %d\n", result);

  free(expr_str);
  free_expr(expr);

  return 0;
}

Recap

Week 2 connects three ideas:

  1. Classes and companion objects structure construction and behavior in an object-oriented style.
  2. Enums model algebraic data types directly.
  3. Pattern matching makes data deconstruction explicit and concise.

These foundations prepare the next lectures where we continue with contracts and formal reasoning about programs.