Week 2 Code Snippets (FA26)

Author: Stefan Mitsch

Week 2 Overview

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

1) A Matrix Class With an Operator Method

The following Matrix uses a one-dimensional array to store two-dimnensional matrix data. It is AI-generated, review it for correctness and clarity.

class Matrix private (private val data: Array[Double], rows: Int, cols: Int):
  require(rows > 0, "Rows must be positive")
  require(cols > 0, "Cols must be positive")
  require(data.length == rows * cols, s"Data length ${data.length} must equal rows*cols=${rows * cols}")

  // auxiliary constructor
  def this(rows: Int, cols: Int, init: Double = 0.0) = this(
    new Array[Double](rows * cols),
    rows,
    cols
  )

  def apply(row: Int, col: Int): Double =
    require(row >= 0 && row < rows, s"Row $row out of range [0,${rows})")
    require(col >= 0 && col < cols, s"Col $col out of range [0,${cols})")
    data(row * cols + col)

  def update(row: Int, col: Int, value: Double): Unit =
    require(row >= 0 && row < rows, s"Row $row out of range [0,${rows})")
    require(col >= 0 && col < cols, s"Col $col out of range [0,${cols})")
    data(row * cols + col) = value

  def rows: Int = rows
  def cols: Int = cols
  def size: Int = rows * cols

  def +(that: Matrix): Matrix =
    require(this.rows == that.rows && this.cols == that.cols, "Matrix dimensions must match")
    val result = new Matrix(rows, cols)
    var i = 0
    while i < data.length do
      result.data(i) = data(i) + that.data(i)
      i += 1
    result

  def *(that: Matrix): Matrix =
    require(this.cols == that.rows, s"Columns of first (${this.cols}) must equal rows of second (${that.rows})")
    val result = new Matrix(rows, that.cols)
    for i <- 0 until rows do
      for j <- 0 until that.cols do
        var sum = 0.0
        for k <- 0 until this.cols do
          sum = sum + this(i, k) * that(k, j)
        result.update(i, j, sum)
    result

  def transpose: Matrix = new Matrix(cols, rows, { var i = 0; while i < data.length do { val r = i / cols; val c = i % cols; result.update(c, r, data(i)); i += 1 }; result })

  def map(f: Double => Double): Matrix = new Matrix(rows, cols) { var i = 0; while i < data.length do { result.data(i) = f(data(i)); i += 1 }; result }

  def map2(that: Matrix)(f: (Double, Double) => Double): Matrix =
    require(this.rows == that.rows && this.cols == that.cols, "Matrix dimensions must match")
    val result = new Matrix(rows, cols)
    var i = 0
    while i < data.length do
      result.data(i) = f(data(i), that.data(i))
      i += 1
    end while
    result
  end map2

  override def toString: String =
    val sb = new StringBuilder
    for i <- 0 until rows do
      for j <- 0 until cols do
        sb.append(f"${apply(i, j)}%8.2f")
      if i < rows - 1 then sb.append("\n")
    sb.toString()

end Matrix

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

3) Companion Object

The following companion object (also auto-generated) provides factory methods to create Matrix objects:

// Factory object with convenient creation methods
object Matrix:
  def apply(rows: Int, cols: Int, init: Double = 0.0): Matrix = new Matrix(rows, cols, init)

  def fill(rows: Int, cols: Int)(f: (Int, Int) => Double): Matrix =
    val m = new Matrix(rows, cols)
    for i <- 0 until rows do
      for j <- 0 until cols do
        m.update(i, j, f(i, j))
    m

  def identity(n: Int): Matrix = Matrix.fill(n, n) { (i, j) => if i == j then 1.0 else 0.0 }

  def zeros(rows: Int, cols: Int): Matrix = Matrix(rows, cols, 0.0)
  def ones(rows: Int, cols: Int): Matrix = Matrix(rows, cols, 1.0)

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

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.