# 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 `Option`

s,
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

🍕