Implementing Kleene logic two different ways in Scala

Recently I’ve been writing a graph query engine at Fault Tolerant System Research Group at uni. The frontend is Cypher, a language popularized by Neo Technology shipped OOTB with their graph database Neo4j.

Recently Cypher is getting standardized in an open source and open government initiative under the name openCypher; and other DB vendors, such as the RDBMS giant Oracle are starting to support it.

The language itself is similar to SQL augmented with syntax for graph pattern matching. One of the similarities is the handling of NULL values.

NULLs

Let’s get back to mother of all query languages, the almighty SQL and start with a test. Can you answer by heart what these SQL queries evaluate to?

SELECT NULL IS NULL;
SELECT NULL = NULL;
SELECT NULL <> NULL;
SELECT TRUE OR NULL;
SELECT TRUE AND NULL;
SELECT FALSE AND NULL;
SELECT FALSE OR NULL;

Results: TRUE, NULL, NULL, TRUE, NULL, FALSE, NULL

The results might surprise you, however there’s nothing unconventional here. The rules are according to Kleene logic, where NULL encodes an uncertain value. So in layman’s terms

  • Is an uncertain value uncertain? Of course! (TRUE)
  • Does an uncertain value (equal to / differ from) another uncertain value? Not sure. (NULL)
  • If something is true OR something else is unknown, is the whole thing true? Of course as TRUE OR TRUE and TRUE or FALSE or both TRUE
  • … and so on.

Actually, if you think about it, TRUE OR NULL == TRUE and FALSE AND NULL == FALSE equivalences are the ones making short circuiting feasible in programming languages.

All in all you get this truth table:

NOT OR TRUE OR NULL OR FALSE AND TRUE AND NULL AND FALSE
TRUE FALSE TRUE TRUE TRUE TRUE NULL FALSE
NULL NULL TRUE NULL NULL NULL NULL FALSE
FALSE TRUE TRUE NULL FALSE FALSE FALSE FALSE

Let’s implement this in Scala!

Using Option[Boolean]

It is pretty straightforward to do with Options, because of the mapping

  • TRUE <-> Some(true)
  • NULL <-> None
  • FALSE <-> Some(false)

I am pretty fond of Haskell’s model for polymorphism, and I use the simulacrum library to implement this functionality for Option[Boolean]s concisely

First define the type class:

@typeclass trait KleeneLike[-A] {
  @op("&&") def and(x: A, y: A): Option[Boolean]
  @op("||") def or(x: A, y: A): Option[Boolean]
  @op("unary_!") def not(x: A): Option[Boolean]
}

Then implement it for Option[Boolean]:

object KleeneLike {
  trait KleeneLikeForOptionBoolean {
    override def and(x: Option[Boolean], y: Option[Boolean]): Option[Boolean] = (x, y) match {
      case (Some(true), Some(true)) => Some(true)
      case (Some(false), _) => Some(false)
      case (_, Some(false)) => Some(false)
      case _ => None
    }
    override def or(x: Option[Boolean], y: Option[Boolean]): Option[Boolean] = (x, y) match {
      case (Some(false), Some(false)) => Some(false)
      case (Some(true), _) => Some(true)
      case (_, Some(true)) => Some(true)
      case _ => None
    }
    override def not(x: Option[Boolean]): Option[Boolean] =
      for { _x <- x } yield !_x
  }

  implicit def optionBooleanKleeneLike
    [Opt <: Option[Boolean]]: KleeneLike[Opt]
    = new KleeneLikeForOptionBoolean {}
}

This looks simple however you should look out for not to do e.g. this:

override def or(x: Option[Boolean], y: Option[Boolean]): Option[Boolean] = (x, y) match {
  for { _x <- x; _y <- y } yield _x || _y
}

because it yields None for Some(true) || None which is not what we want!

Here’s a more general solution with additional == and != ops for arbitrary types.

Using Integer

Option[Boolean] is fine but let’s do something more efficient. Scala has a feature called value classes for sparing a runtime representation for wrappers, compiling their operations into function calls on a single underlying type. Let’s create a value class wrapper around Integer and do the heavy-lifting with bitwise operations!

class Kleene(val value: Int) extends AnyVal {
  def &&(rhs: Kleene): Kleene = ???
  def ||(rhs: Kleene): Kleene = ???
  def unary_! : Kleene = ???
  def ==(rhs: Kleene): Kleene = ???
  def !=(rhs: Kleene): Kleene = ???
}

How to represent stuff? We have 3 values so we need at least two bits. It seems that the most straightforward representation is this:

00: false
{01, 10}: null
11: true

Because then wonderfully:

def &&(rhs: Kleene): Kleene = new Kleene(value & rhs.value)
def ||(rhs: Kleene): Kleene = new Kleene(value | rhs.value)
def unary_! : Kleene = new Kleene(value ^ 0x3)

& is bitwise AND, | is bitwise OR, ^ is XOR.

Now == and != are more complex. The key is to parity here.

Operating on the two bits separately: (a1 ^ b1) & (a1 ^ b2)

  • returns 0 for an odd b,
  • returns 0 for the same, 1 for different a1 b1, if b is even

(a2 ^ b2) | (a2 ^ b1):

  • returns 1 for an odd b
  • returns 0 for the same, 1 for different a2 b2, if b is even

if a is odd and b is even then exactly one of them is false.

So this should do the trick for !=.

private def flipped: Int = (value & 0x1) << 1 | (value & 0x2) >> 1
def !=(rhs: Kleene): Kleene = {
  val first = value ^ rhs.value
  val second = value ^ rhs.flipped
  // MSbs are ANDed, LSbs are ORed
  new Kleene((first & second & 0x2) | ((first | second) & 0x1))
}

You can negate this to get ==. Here’s the whole file

Conclusion

🍕