The Vapors!

Building Fact Filter Expressions

Vapors is an open-source Scala library that allows for building and evaluating logic rules over a table of facts.

​

Evaluation := (Expr[In, Out], FactTable, In) => F[Out]

​

The F wrapper can contain metadata about the facts used to compute the result, the source code information, etc.

1. Define Your Fact Types

First we define our FactType over some Scala type. This provides the ability to create facts of this type and gives us access to NamedLens objects which allow us to select fields.

3

import com.rallyhealth.vapors.factfilter.data.FactType

val DateOfBirth = FactType[LocalDate]

2. Create An Expression Using the DSL

Then we define our expression using the Fact Filter Domain-Specific Language (DSL)

import java.time.ChronoUnit.YEARS

import com.rallyhealth.vapors.v1.dsl.uncached._

val isOver18: Any ~:> Boolean = {

valuesOfType(DateOfBirth).exists { dob =>

dateDiff(today, dob, YEARS) >= 18L.const

}

}

3. Evaluate the Expression

The DSL will produce a I ~:> O that you can evaluate with an input of I and a FactTable to get an O. When I is Any, you can call .run() without any input instead of .runWith().

import com.rallyhealth.vapors.v1.dsl.uncached._

val facts = FactTable(

DateOfBirth(LocalDate.of(1980, 1, 1)),

)

assert(isOver18.run(facts) == true)

Building Expressions

An Expr is a tree of expression nodes that can be interpreted with a recursive Expr.Visitor. Every subclass of Expr provides the typeclass instances required to implement the evaluation of that node. These same type classes can be used to interpret the expression with different visitors. Additionally, you can provide a custom OP[_] type constructor, which will grab implicit instances for the custom output type where each node is constructed and can be used inside the Expr.Visitor.

Expression Algebra

Expr is a sealed class with subclasses like:

​

​

• And
• ForAll
• Select
• IsEqualTo

• Or
• Exists
• Combine
• WithinWindow

Operation Typeclasses

Every operation, like +, -, /, etc will have a type class for defining the operation over a type (i.e. a set of possible values).

​

​

Fact-Flavored Expressions

We can define a DSL over our generic algebra by lifting each operation into the applicative with the appropriate constraints on the types, so that we can define the operations required by the algebra.

​

TerminalFactsExp = Exp[Facts, ResultSet] =

FreeApplicative[ExpAlg[Facts, *], ResultSet]

Generic Expressions

For example, in order to define the AND operator, we need to support Exp[Facts, Boolean] and Exp[Facts, ResultSet].

​

We can pass any Exp[T, A] to and() / or() so long as there is a way to go from List[A] => A. When we are operating over a ResultSet, we just union the results and treat empty sets as falsy and non-empty sets as truthy. For Boolean, we just use the standard definitions && and ||. But you can write your own.

What is a�“Free Applicative”?

Free Applicatives: “It’s FREE Real Estate”

It is called “Free” because the parameter A is never constrained to any specific class of types. This allows us to recurse over the free parameter, passing things like functions, values, other Exp[T, A] nodes, etc.

​

This Applicative can then foldMap over the nodes to interpret the same structure in different ways...

Fact Expression Evaluator

In order to evaluate a TerminalFactsExp, we write an interpreter that transforms the operations of our ADT into a function from T => A.

​

Evaluator = (ExpAlg[T, *] ~> (T => *))

FreeApplicative[ExpAlg[Facts, *], ResultSet]

exp.foldMap(eval) = Facts => ResultSet

13

Evaluating Fact Expressions

14

case ExpAlg.Exists(toIterable, condition, whenTrue, whenFalse) =>

val results = toIterable(data).iterator.map(evalLoop(condition))

val success = results.exists(identity[Boolean])

if (success) whenTrue(data)

else whenFalse(data)

case ExpAlg.ForAll(toIterable, condition, whenTrue, whenFalse) =>

val results = toIterable(data).iterator.map(evalLoop(condition))

val success = results.forall(identity[Boolean])

if (success) whenTrue(data)

else whenFalse(data)

case ExpAlg.Within(window, whenTrue, whenFalse) =>

if (window.contains(data)) whenTrue(data) else whenFalse(data)

...

​

Interpreting Free Applicatives

Because we never given the value of A directly -- as we would in a FreeMonad[F[_], A] with flatMap(A => F[A]) -- we are restricted in only being able to describe all behavior inside the algebraic data type. This restriction in behavior inside the data structure grants us the freedom to interpret the it from outside. So long as we can define a “Natural Transformation”:�

new (F ~> G) { def apply[A](fa: F[A]): G[A] }

Coming Soon!

Can we optimize the queries before evaluating them?

Query Optimizing Interpreter

Since we can map the expression with .foldMap, we can convert an expression into one that is cheaper to evaluate. We would just need to define the following natural transformation*:

​

(ExpAlg[T, *] ~> ExpAlg[T, *])

​

* We might need intermediate data structures, but you get the idea

Query Optimizing Interpreter

In this interpreter, we could follow standard rules of logic to simplify the expressions:

• Combine Ands with consecutive Ands
• Combine Ors with consecutive Ors
• Combine ForAlls with consecutive ForAlls
• Combine Exists with consecutive Exists
• Estimate costs for branches of a logical operation and order the traversal for the most valuable branches first (depending on the quality threshold)

Can We Generate PlantUML Activity Diagrams?

Generate PlantUML for an Expression

For every node in the expression, we can draw logical flows of underlying nodes. While the specifics of how this would look need to be worked out, the essence of the transformation would be:

​

(ExpAlg[T, *] ~> ActivityChart)

ActivityChart[A] = List[PlantUml.ActivityNode]

21

PlantUML: isOver18

@startuml

start

:Collect[Facts, FactsOfType[LocalDate], ResultSet];

if (__.withFactsOfType(DateOfBirth)) then (empty)

:NoFactsMatch;

stop

else (non-empty)

:Exists[FactsOfType[LocalDate], TypedFact[LocalDate], ResultSet];

:Select[TypedFact[LocalDate], LocalDate];

:WithinWindow[LocalDate, Boolean];

...

​

if (__ < LocalDate.now().minusYears(18)) then (empty)

:NoFactsMatch;

stop

else (non-empty)

:FactsMatch;

stop

endif

endif

@enduml��LINK TO DIAGRAM

​

22

Next Steps: Performance Testing

Compare performance of Vapors with:

• Large inputs and complex expressions with similar logic written directly in Scala (measure the overhead of abstracting over the rules with expressions)
• Alternative libraries (OPA / Oso Policy Manager)
• Optimized queries

23

Next Steps: Embedding Expressions

Support embedding TerminalFactsExp as conditional expressions.

• Makes it easier to build queries that nest logical expressions after selecting facts of a specific type
• Pass the original input of facts through all nodes in the expression, and define an expression node that swaps the current state with the initial state for computing the embedded expression.

24

Next Steps: Negation

Implement negation (i.e. ExpAlg.Not)

• Negation is an add-on to DataLog, so probably not a trivial operator
• Maybe define a negation operation on every node or a function that can negate any given node using a foldMap.
• For example, we can consider negation of an expression as swapping the ifTrue and ifFalse functions on all conditional expressions within it

25

Next Steps: Lazy data Iteration

Support lazily retrieved input sources

• We will likely be pulling the data from a database, which can support lazy iteration.
• Depending on our ability to terminate early, we may be able to stop the calculation when we sufficiently prove a query.
• Maybe we can avoid pulling everything into memory or constructing too many intermediate collections.

26

Thanks!

Questions?

Learn more at https://github.com/jeffmay/vapors