Tagless Final Scala

tfs.scala

// expression problem:
// evaluating expressions mantaining type safety and returning
// the right value of the right type
// In functional programming all is an expression

object ExpressionProblem {
  trait Expr
  case class B(boolean: Boolean) extends Expr
  case class Or(left: Expr, right: Expr) extends Expr
  case class And(left: Expr, right: Expr) extends Expr
  case class Not(expr: Expr) extends Expr

  val aGiantBoolean: Expr = Or(And(B(true), B(false)), B(false))

  def eval(expr: Expr): Boolean = expr match {
    case B(b)     => b
    case Or(a, b) => eval(a) || eval(b)
    case Not(e)   => !eval(e)
  }

  // include ints
  case class I(int: Int) extends Expr
  case class Sum(left: Expr, right: Expr) extends Expr

  def eval_v2(expr: Expr): Boolean | Int = expr match {
    case B(b)     => b
    case Or(a, b) => eval(a).isInstanceOf[Boolean] || eval(b).isInstanceOf[Boolean]
    case Not(e)   => !eval(e)
    // casts everywhere, and some expr could be integers => runtime crash
  }
}

object Tagging {
  trait Expr(val tag: String)

  case class B(boolean: Boolean) extends Expr("bool")
  case class Or(left: Expr, right: Expr) extends Expr("bool")
  case class And(left: Expr, right: Expr) extends Expr("bool") {
    assert(left.tag == "bool" || right.tag == "bool")
  }
  case class Not(expr: Expr) extends Expr("bool")
  case class I(int: Int) extends Expr("int")
  case class Sum(left: Expr, right: Expr) extends Expr("int")

  def eval(expr: Expr): Boolean | Int = expr match {
    case B(b) => b
    case Or(left, right) =>
      if(left.tag != "bool" || right.tag != "bool") then throw new IllegalArgumentException("improper argument type")
      else eval(left).isInstanceOf[Boolean] || eval(right).isInstanceOf[Boolean]

    // we haven't solved so much: both checks happen at runtime
  }
}

object TaglessInitial {
  // there are intermediate data structures

  trait Expr[A]

  case class B(boolean: Boolean) extends Expr[Boolean]
  case class Or(left: Expr[Boolean], right: Expr[Boolean]) extends Expr[Boolean]
  case class And(left: Expr[Boolean], right: Expr[Boolean]) extends Expr[Boolean]
  case class Not(expr: Expr[Boolean]) extends Expr[Boolean]
  case class I(int: Int) extends Expr[Int]
  case class Sum(left: Expr[Int], right: Expr[Int]) extends Expr[Int]


  def eval[A](expr: Expr[A]): A = expr match {
    case B(b) => b
    case I(i) => i
    case Or(left, right) => eval(left) || eval(right)
    case And(left, right) => eval(left) && eval(right)
    case Sum(left, right) => eval(left) + eval(right)
  }

  // checks moved at compile time
}

object TaglessFinal {
  // the evaluation happens instantly

  trait Expr[A] {
    // the final value we care about after the evaluation
    val value: A
  }

  def b(boolean: Boolean): Expr[Boolean] = new Expr[Boolean] {
    val value = boolean
  }

  def i(int: Int): Expr[Int] = new Expr[Int] {
    val value = int
  }

  def or(left: Expr[Boolean], right: Expr[Boolean]) = new Expr[Boolean] {
    val value = left.value || right.value
  }

  def and(left: Expr[Boolean], right: Expr[Boolean]) = new Expr[Boolean] {
    val value = left.value && right.value
  }

  def sum(left: Expr[Int], right: Expr[Int]) = new Expr[Int] {
    val value = left.value + right.value
  }


  def eval[A](expr: Expr[A]): A = expr.value

  // checks still at compile time
}

//
// How is F[_] : ATypeClass related to "tagless final"?
/**
 * tagless final solves the expression problem, we program with respect to the Expr[A] interface
 * TypeClasses are a set of functionality we want to offer for some types and not for others
 * With tagless final we want to return the right type for the right expressions and not for others
 * We can combine them
 */

  object TaglessFinalV2 {
    trait Algebra[E[_]] {
      // the functionality are grouped together under a common TypeClass
      def b(boolean: Boolean): E[Boolean]
      def i(int: Int): E[Int]
      def or(left: E[Boolean], right: E[Boolean]): E[Boolean]
      def and(left: E[Boolean], right: E[Boolean]): E[Boolean]
      def sum(left: E[Int], right: E[Int]): E[Int]
    }

    case class SimpleExpr[A](value: A)
    given simpleExprAlgebra: Algebra[SimpleExpr] with {
      def b(boolean: Boolean) = SimpleExpr(boolean)
      def i(int: Int) = SimpleExpr(int)
      def or(left: SimpleExpr[Boolean], right: SimpleExpr[Boolean]) = SimpleExpr(left.value || right.value)
      def and(left: SimpleExpr[Boolean], right: SimpleExpr[Boolean]) = SimpleExpr(left.value && right.value)
      def sum(left: SimpleExpr[Int], right: SimpleExpr[Int]) = SimpleExpr(left.value + right.value)
      // oss: evaluation happens at construction time
    }

    def program1[E[_]](using alg: Algebra[E]) : E[Boolean] = {
      import alg._
      or(b(true), and(b(true), b(false)))
    }

    def program2[E[_]](using alg: Algebra[E]) : E[Int] = {
      import alg._
      sum(i(24), i(-3))
    }
  }

def demoTaglessInitial =
  import TaglessInitial._
  println(eval(Or(B(true), And(B(true), B(false)))))
  println(eval(Sum(I(24), I(-3))))

def demoTaglessFinal =
  import TaglessFinal._
  println(eval(or(b(true), and(b(true), b(false)))))
  println(eval(sum(i(24), i(-3))))

def demoFinalTaglessV2 =
  import TaglessFinalV2._
  println(program1[SimpleExpr].value)
  println(program2[SimpleExpr].value)

@main def main = {
  demoTaglessInitial

  demoTaglessFinal

  demoFinalTaglessV2
}