Free Boolean Algebras: Boolean Logic for Free!

Adam Rosien @arosien
Inner Product LLC inner-product.com

2 Apr 2019

Motivation

My favorite test output

true is not false

(╯°□°）╯︵ ┻━┻

Boolean expressions are everywhere

How do you encode them?

How do you reuse them?

How do you document them?

It’s a mess

What can we do?

Let’s do some refactoring!

Boolean Functions

val atLeast13    = (_: Int) >= 13
val nonEmptyName = (_: String).nonEmpty

val atLeast13AndNonEmptyName = (i: Int, s: String) =>
  atLeast13(i) && nonEmptyName(s)

atLeast13AndNonEmptyName(13, "martin")
// res0: Boolean = true
atLeast13AndNonEmptyName(5, "martin")
// res1: Boolean = false
atLeast13AndNonEmptyName(13, "")
// res2: Boolean = false

Reification

sealed trait Predicate

object Predicate {
  case class AtLeast13(i: Int) extends Predicate
  case class NonEmptyName(s: String) extends Predicate
}

Interpreter

sealed trait Predicate {
  def run: Boolean =
    this match {
      case Predicate.AtLeast13(i)    => i >= 13
      case Predicate.NonEmptyName(s) => s.nonEmpty
    }
}

object Predicate {
  case class AtLeast13(i: Int) extends Predicate
  case class NonEmptyName(s: String) extends Predicate
}

But we’re missing &&:

val AtLeast13AndNonEmptyName =
  Predicate.AtLeast13(13) && Predicate.NonEmptyName("martin")
// error: value && is not a member of repl.Session.App1.Predicate.AtLeast13
//   case Predicate.AtLeast13(i)    => i >= 13
//        ^^^^^^^^

Add && method + Reification

sealed trait Predicate {
  def &&(that: Predicate): Predicate =
    Predicate.And(this, that)
  // TODO: ||, !
}

object Predicate {
  case class AtLeast13(i: Int) extends Predicate
  case class NonEmptyName(s: String) extends Predicate
  case class And(l: Predicate, r: Predicate) extends Predicate
  // TODO: Or, Not
}

Interpreter

sealed trait Predicate {
  def run: Boolean =
    this match {
      case Predicate.AtLeast13(i)    => i >= 13
      case Predicate.NonEmptyName(s) => s.nonEmpty
      case Predicate.And(l, r)       => l.run && r.run
      // TODO: Or, Not
    }

  def &&(that: Predicate): Predicate = Predicate.And(this, that)
  // TODO: ||, !
}

object Predicate {
  case class AtLeast13(i: Int) extends Predicate
  case class NonEmptyName(s: String) extends Predicate
  case class And(l: Predicate, r: Predicate) extends Predicate
  // TODO: Or, Not
}

(Predicate.AtLeast13(13) &&
  Predicate.NonEmptyName("martin"))
  .run
// res8: Boolean = true

(Predicate.AtLeast13(5) &&
  Predicate.NonEmptyName("martin"))
  .run
// res9: Boolean = false

(Predicate.AtLeast13(13) &&
  Predicate.NonEmptyName(""))
  .run
// res10: Boolean = false

Factor Out the Boolean Algebra

sealed trait FreeB[A] {
  def run: Boolean = ???

  def &&(that: FreeB[A]): FreeB[A] = FreeB.And(this, that)
  def ||(that: FreeB[A]): FreeB[A] = FreeB.Or(this, that)
  def unary_!(): FreeB[A] = FreeB.Not(this)
}

object FreeB {
  case class Pure[A](a: A) extends FreeB[A]
  case class True[A]() extends FreeB[A]
  case class False[A]() extends FreeB[A]
  case class And[A](l: FreeB[A], r: FreeB[A]) extends FreeB[A]
  case class Or[A](l: FreeB[A], r: FreeB[A]) extends FreeB[A]
  case class Not[A](fa: FreeB[A]) extends FreeB[A]
}

(FreeB.Pure(Predicate.AtLeast13(13): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName("martin"): Predicate))
  .run
// scala.NotImplementedError: an implementation is missing
//  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:288)
//  at repl.Session$App7$FreeB.run(free-boolean-algebras.md:143)
//  at repl.Session$App7$FreeB.run$(free-boolean-algebras.md:143)
//  at repl.Session$App7$FreeB$And.run(free-boolean-algebras.md:155)
//  at repl.Session$App7$$anonfun$18.apply$mcZ$sp(free-boolean-algebras.md:166)
//  at repl.Session$App7$$anonfun$18.apply(free-boolean-algebras.md:167)
//  at repl.Session$App7$$anonfun$18.apply(free-boolean-algebras.md:167)

How to interpret this algebra?

Structual Recursion

sealed trait FreeB[A] {
  def run: Boolean =
    this match {
      case FreeB.Pure(a)   => ???
      case FreeB.True()    => true
      case FreeB.False()   => false
      case FreeB.And(l, r) => l.run && r.run
      case FreeB.Or(l, r)  => l.run || r.run
      case FreeB.Not(fa)   => !fa.run
    }

  def &&(that: FreeB[A]): FreeB[A] = FreeB.And(this, that)
  def ||(that: FreeB[A]): FreeB[A] = FreeB.Or(this, that)
  def unary_!(): FreeB[A] = FreeB.Not(this)
}

How do we interpret `Pure`?

Make it the caller’s problem

sealed trait FreeB[A] {
  def run(f: A => Boolean): Boolean =
    this match {
      case FreeB.Pure(a)   => f(a)
      case FreeB.True()    => true
      case FreeB.False()   => false
      case FreeB.And(l, r) => l.run(f) && r.run(f)
      case FreeB.Or(l, r)  => l.run(f) || r.run(f)
      case FreeB.Not(fa)   => !fa.run(f)
    }

  def &&(that: FreeB[A]): FreeB[A] = FreeB.And(this, that)
  def ||(that: FreeB[A]): FreeB[A] = FreeB.Or(this, that)
  def unary_!(): FreeB[A] = FreeB.Not(this)
}

sealed trait Predicate

object Predicate {
  case class AtLeast13(i: Int) extends Predicate
  case class NonEmptyName(s: String) extends Predicate
}

val eval: Predicate => Boolean = {
  case Predicate.AtLeast13(i)    => i >= 13
  case Predicate.NonEmptyName(s) => s.nonEmpty
}

(FreeB.Pure(Predicate.AtLeast13(13): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName("martin"): Predicate))
  .run(eval)
// res13: Boolean = true

(FreeB.Pure(Predicate.AtLeast13(5): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName("martin"): Predicate))
  .run(eval)
// res14: Boolean = false

(FreeB.Pure(Predicate.AtLeast13(13): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName(""): Predicate))
  .run(eval)
// res15: Boolean = false

What did we do?

Reify boolean functions into an algebraic data type. Write an interpreter.
Add boolean operators: AND, OR, NOT.
Separate boolean algebra from domain-specific logic: pure: A => FreeB[A]
Augment the boolean algebra with a domain-specific evaluator: run: FreeB[A] => (A => Boolean) => Boolean

FreeB[A] is a boolean algebra for all A!

This is why it is called the Free Boolean Algebra.

Abstracting to Other Boolean Algebras

Can we evaluate an expression to something other than Boolean?

sealed trait FreeB[A] {
  def run(f: A => Boolean): Boolean
}

☟

sealed trait FreeB[A] {
  def run[B : Bool](f: A => B): B
}

Type Classes

Typelevel algebra provides algebra.lattice.Bool:

trait Bool[A] {
  def zero: A
  def one: A
  def and(a: A, b: A): A
  def or(a: A, b: A): A
  def complement(a: A): A
}

import algebra.lattice.Bool

sealed trait FreeB[A] {
  def run[B](f: A => B)(implicit bool: Bool[B]): B =
    this match {
      case FreeB.Pure(a)   => f(a)
      case FreeB.True()    => bool.one
      case FreeB.False()   => bool.zero
      case FreeB.And(l, r) => bool.and(l.run(f), r.run(f))
      case FreeB.Or(l, r)  => bool.or(l.run(f), r.run(f))
      case FreeB.Not(fa)   => bool.complement(fa.run(f))
    }

  def &&(that: FreeB[A]): FreeB[A] = FreeB.And(this, that)
  def ||(that: FreeB[A]): FreeB[A] = FreeB.Or(this, that)
  def unary_!(): FreeB[A] = FreeB.Not(this)
}

import algebra.instances.boolean._

(FreeB.Pure(Predicate.AtLeast13(13): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName("martin"): Predicate))
  .run(eval)
// res17: Boolean = true

(FreeB.Pure(Predicate.AtLeast13(5): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName("martin"): Predicate))
  .run(eval)
// res18: Boolean = false

(FreeB.Pure(Predicate.AtLeast13(13): Predicate) &&
  FreeB.Pure(Predicate.NonEmptyName(""): Predicate))
  .run(eval)
// res19: Boolean = false

FreeB itself has a Bool instance:

implicit def freeBBool[A]: Bool[FreeB[A]] =
  new Bool[FreeB[A]] {
    def and(a: FreeB[A], b: FreeB[A]): FreeB[A] = FreeB.And(a, b)
    def complement(a: FreeB[A]): FreeB[A] = FreeB.Not(a)
    def one: FreeB[A] = FreeB.True()
    def or(a: FreeB[A], b: FreeB[A]): FreeB[A] = FreeB.Or(a, b)
    def zero: FreeB[A] = FreeB.False()
  }

We can evaluate FreeB[A] => FreeB[A]!

Other Interpreters

Pretty Printer

implicit class Pretty[A](p: FreeB[A]) {
  def pretty(f: A => String): String =
    p match {
      case FreeB.Pure(a)   => f(a)
      case FreeB.True()    => "false"
      case FreeB.False()   => "true"
      case FreeB.And(l, r) => s"(${l.pretty(f)} && ${r.pretty(f)})"
      case FreeB.Or(l, r)  => s"(${l.pretty(f)} || ${r.pretty(f)})"
      case FreeB.Not(fa)   => s"!$fa"
    }
}

both.pretty {
  case Predicate.AtLeast13(i)    => s"($i >= 13)"
  case Predicate.NonEmptyName(s) => s"""('$s' != '')"""
}
// res20: String = "((13 >= 13) && ('martin' != ''))"

Normalization

implicit class Normalization[A](p: FreeB[A]) {
  def normalize(): FreeB[A] =
    p match {
      case FreeB.And(FreeB.True(), r)  => r.normalize
      case FreeB.And(r, FreeB.True())  => r.normalize
      case FreeB.And(FreeB.False(), _) => FreeB.`false`
      case FreeB.And(_, FreeB.False()) => FreeB.`false`
      case FreeB.Or(FreeB.True(), _)   => FreeB.`true`
      case FreeB.Or(_, FreeB.True())   => FreeB.`true`
      case FreeB.Or(FreeB.False(), r)  => r.normalize
      case FreeB.Or(r, FreeB.False())  => r.normalize
      case _ => p
    }
}

import FreeB._

(`true`  && `true`).normalize
// res21: FreeB[Nothing] = True()
(`true`  && `false`).normalize
// res22: FreeB[Nothing] = False()
(`false` && `true`).normalize
// res23: FreeB[Nothing] = False()
(`false` && `false`).normalize
// res24: FreeB[Nothing] = False()

(`true`  || `true`).normalize
// res25: FreeB[Nothing] = True()
(`true`  || `false`).normalize
// res26: FreeB[Nothing] = True()
(`false` || `true`).normalize
// res27: FreeB[Nothing] = True()
(`false` || `false`).normalize
// res28: FreeB[Nothing] = False()

Partial Evaluation

implicit class PartialEvaluation[A](p: FreeB[A]) {
  def runPartial(pf: PartialFunction[A, Boolean]): FreeB[A] =
    p.run { a =>
      pf.lift(a).fold(FreeB.pure(a)) { x =>
        if (x) FreeB.`true` else FreeB.`false`
      }
    }
}

val onlyCheckAtLeast13: PartialFunction[Predicate, Boolean] = {
  case Predicate.AtLeast13(i) => i >= 13
}

both
// res29: FreeB[Predicate] = And(
//   Pure(AtLeast13(13)),
//   Pure(NonEmptyName("martin"))
// )
both.runPartial(onlyCheckAtLeast13).normalize
// res30: FreeB[Predicate] = Pure(NonEmptyName("martin"))

not13
// res31: FreeB[Predicate] = And(
//   Pure(AtLeast13(5)),
//   Pure(NonEmptyName("martin"))
// )
not13.runPartial(onlyCheckAtLeast13).normalize
// res32: FreeB[Predicate] = False()

emptyName
// res33: FreeB[Predicate] = And(Pure(AtLeast13(13)), Pure(NonEmptyName("")))
emptyName.runPartial(onlyCheckAtLeast13).normalize
// res34: FreeB[Predicate] = Pure(NonEmptyName(""))

And more!

We can evaluate FreeB[A] expressions to:

cats.data.Validated
documentation
matchers for tests
etc.

Take Aways

We can separate boolean expressions from their evaluation with the Free Boolean Algebra.

This a mechanical process. It works for generating other “free” structures: Applicative, Monad, etc.

Once “free”, we can reuse expressions in many different ways.

Thank You!

Adam Rosien @arosien

Inner Product LLC inner-product.com

Hire us to teach your team! ☝︎

Free Boolean Algebra (Wikipedia)
Free objects - a generalized interpreter pattern (Chris Stucchio, Wingify)
typelevel/algebra