Symbolic artificial intelligence at Pipedrive
Logic programming — the quintessential element of symbolic artificial intelligence, a subfield of AI that has been almost completely eclipsed by machine learning — is one of the most alien forms of programming out there. In fact, most developers — excluding those who are into the esoteric subjects of programming language and database theory — have probably never heard of it. And yet, recently, it’s been experiencing a sort of renaissance.
While in machine learning the goal is to discover or model rules, in symbolic AI it’s all about using them for decision making.
Developers often describe their profession as highly logical. That is, much of programming is writing rules as code and evaluating them, according to some situations. In the most popular programming languages, rules are not a first-class concept. There isn’t a built-in keyword that attaches semantics to rules, nor are they even explicitly stated. Instead, their evaluation is specified. Logic programming languages, on the other hand, allow you to declaratively write rules and forget about their evaluation, possibly the single greatest source of bugs.
In this blog post, we will explore a use case of logic programming using the Datalog [1] family of logic programming languages and compare it with our previous solution.
We will also introduce you to the theory of the evaluation of Datalog Programs, something I am very sure you would love to learn about, with the goal being to show that by using Datalog, you can ensure all you have to worry about is whether the logic of your rule means what you actually want it to mean.
Problem statement
Pipedrive is a large enterprise of almost 1,000 employees, out of which roughly half are engineers. On average, we deploy up to 350 times per day, which includes about 50 deployments to production environments located in three different regions. Our developers modify up to a third of our features every week [2]. We’ve developed many conventions to guarantee that software quality is consistent across all company software, including specific values or ranges for configuration files, folder structures, templates, version restrictions, etc.
There are two ways to go about enforcing conventions:
* Create a document with all conventions and nag people to review it t̶h̶e̶n̶ ̶s̶h̶a̶m̶e̶ ̶t̶h̶e̶m̶ ̶i̶f̶ ̶g̶o̶d̶ ̶f̶o̶r̶b̶i̶d̶ ̶t̶h̶e̶y̶ ̶e̶n̶d̶ ̶u̶p̶ ̶f̶o̶r̶g̶e̶t̶t̶i̶n̶g̶ ̶s̶o̶m̶e̶
* Write software to ensure conventions are being followed
From the get-go we went with the second route.
Our solutions
A few questions one should consider when writing software for this specific purpose:
1. How to describe conventions in code?
2. How to evaluate conventions with respect to arbitrary configuration data?
3. How to ensure that the convention evaluation is correct?
4. How to test the convention evaluation code?
The answer to the first question is the most crucial one since it determines whether the other three criteria would have to be implemented from scratch or come for free.
Dora
The first solution we experimented with at Pipedrive was called Dora (Deployment Or Repository Analyzer), written entirely from scratch in Javascript. Conventions were only made explicit in the documentation, with their code implementation being a potpourri of parsing logic, evaluation and reporting.
In the code snippet below, taken directly from Dora, we needed to use 30 lines to implement a rule that reads two docker files and checks whether their base image is equivalent. The code has multiple parts:
1. Finding both dockerfiles
2. Loading them in memory
3. Comparing their “FROM” node
4. Reporting what’s been found, if successful, or the exception that was raised
None of these parts, save for 3, relates to the rule itself. In fact, the majority of the code is about evaluation, which has to be tailored to each rule, with line 19 being the only one that implements the logic. That’s over 97% of the code being boilerplate!
Luckily, there are languages specifically designed for evaluating rules, which allow to virtually eliminate all code that does not relate to specifying the rule.
Neodora
Open Policy Agent [3] is a rule engine for enforcing conventions, also known as policies. Its primary focus is the cloud-native sphere, often used to establish fine-grained control over authentication. The next generation of Dora, Neodora, was built on top of this.
Rules are written in a language called Rego [4], a member of the Datalog family whose main purpose is to efficiently reason over JSON data.
This snippet showcases the same rule implemented with Javascript, in Rego. “imageDefinition[result] { … }” is the explicit specification of the rule. All values within it, such as “data.neodora.files[“go.mod”|” are the literal components of the logic of the rule.
As you can see, there isn’t any boilerplate code, and it is quite self-explanatory. Simply by describing a convention, we get the evaluation guaranteed by the Open Policy Agent to be correct and ready for straightforward testing.
In this snippet, we can see a unit test for the rule. A test is simply a rule that is evaluated with “overridden” variables using the “with” keyword. Meanwhile, in Javascript, the test would require testing the logic and all other aspects, including the dreaded evaluation.
Neodora vs Dora: In sum, here are the advantages of writing conventions that are evaluated with Open Policy Agent in Rego over cowboy-coding our rule implementations in Javascript:
1. A declarative syntax for specifying rules
2. No need to implement the evaluation of rules
3. Rule evaluation is always correct
4. Easy unit-testing that only tests the logic of the rule
Datalog
In this section, I’ll show you –informally and vaguely– the simplest Datalog language, its evaluation semantics and how it differs from Rego. This will shed some light on how a correct evaluation can be guaranteed, irrespectively of the rule, as long as it’s written in a legal way.
The central element of programming languages is their respective programs. The difference between them and formal logics — such as first-order logic — is that programming languages have program evaluation semantics, meaning there is a clear definition of a correct evaluation. Writing an algorithm that satisfies the definition implies being able to evaluate any program.
Datalog programs are sets of rules with the following structure:
in which m₀, …, mₙ₋₁, and h are called facts, which together form the body with h being the head.
DockerFile(X), DockerFile(Y), BaseImage(X,Z), BaseImage(Y,Z) → PassesImageDefinition(X, Y) is the recurring rule, written both in Rego and Javascript, in its primordial datalog rule shape, and is read as follows: “If for some X, Y and Z, X and Y are dockerfiles and both of them have the same base image Z, then it follows that PassesImageDefinition is true for X and Y”. X, Y and Z are variables in this example. Rules can have both variables and constants in facts, and a rule will only be true, if there are constants that could be fit to the variables. In formal lingo this is called grounding.
But then, a question arises: Where are these facts stored? Formally, we can assume that there are two fact stores. The Extensional Database — EDB — and the Intensional Database — IDB. EDB is where the actual data is — in the case of Open Policy Agent, the configuration files the rules are executed against. IDB is the result of rule application over the EDB. Applying the example rule over the union of two dockerfiles yields a new fact: PassesImageDefinition. Facts could be seen as lookups. Checking if PassesImageDefinition is true for some arbitrary X and Y is merely a question of looking up whether that fact exists, with X and Y being constants, in the IDB after evaluating the program.
Now that we’ve more or less defined what a program is, it’s time to establish its correct evaluation. The evaluation is built up from the Herbrand Universe — HU — of some datalog program, the set of constant terms.
Let’s create an example with a program consisting only of the Dockerfile rule alongside the following EDB:
Following the definition, the Herbrand Universe is: HU = {dockerfile, dockerfile.CI, dockerfile.TEST, php:16-alpine, php:16-debug}
From the universe, we can generate the Herbrand Base — HB — the set of all possible facts whose terms are only constant. This is the central element to the correctness of evaluation. For the sake of conciseness, we will only show the derivable facts — a subset of the usually huge Herbrand Base:
The correct evaluation of a datalog program is the smallest subset of the Herbrand Base that all facts actually hold. From this example, we can see that it is
alongside the already-existing base facts. This means that any algorithm that derives such subset can evaluate any set of datalog rules.
Datalog in itself is a mathematical formalism, with its most attractive features being that it is not turing-complete, its programs are guaranteed to terminate, and rules can be declaratively specified. However, there isn’t a canonical standardized datalog implementation, as many general programming languages have. Not to mention, since it’s simple and powerful, it’s often bent, twisted and stretched to accommodate a particular use case.
Rego vs. Datalog: The main difference between Rego and Datalog is that Rego considers the EDB to be a big JSON-esque store and doesn’t explicitly allow recursive rules, those that refer to the head fact somewhere in the body. When it comes to recursion, this restriction makes Rego considerably less powerful than Datalog, which is a strong testament to the usefulness of Datalog in itself, given that despite this, Rego is widely used in scenarios by practitioners, far beyond what you might deem such formalism capable of.
References
[1] — https://www2.cs.sfu.ca/CourseCentral/721/jim/DatalogPaper.pdf
[2] — https://medium.com/pipedrive-engineering/fueling-the-rocket-for-500-deploys-a-week-2f31bb84d26a
[3] — https://www.openpolicyagent.org
[4] — https://www.openpolicyagent.org/docs/latest/policy-language/
Interested in working in Pipedrive?
We’re currently hiring for several different positions in several different countries/cities.
Take a look and see if something suits you
Positions include:
- Software Engineer in DevOps Tooling
- Junior Software Engineer in DevOps Tooling
- Junior Site Reliability Engineer
- Automation Engineer
- And several more…
