Logic programming: the infamous Rete algorithm in Elixir

Elixir is a fantastic and dynamic expressive language that lets you build almost anything. But immutability and functional paradigms come with a price. Implementing stateful algorithms is a bit more complex with them.

Take the Rete algorithm, for example, logic programming.

So imagine you need to check that some value, a representation of the world, could match around 1 million set of if/else statements that generate other values that have to check against 1 million set of conditions. Writing this with a simple if/else (conditional logic) would simply not work. What you need to do is have a smarter way to match things with their logic. What you need is that the speed at which you identify a matching condition is the same independently of the set of conditions you have. This is where Rete and logic programming comes in.

What is logic programming?

Logic programming is a computer programming paradigm in which program statements express facts and rules about problems within a system of formal logic. Rules are written as logical clauses with a head and a body; for instance, “H is true if B1, B2, and B3 are true.” — from computerhope.com

The Rete algorithm is a pattern matching algorithm for implementing rule-based systems. Pattern matching he? Sounds familiar to me.

Fibonacci in Rete:

https://www.semanticscholar.org/

Erlang was inspired by Prolog. Actually, “Mostly from prolog. Erlang started life as a modified prolog”.

But too much history for now, let’s dig deeper into how would it be possible to implement Rete in Elixir.

Rete is stateful

The Rete algorithm is a stateful pattern matching algorithm designed to minimize the evaluation of repetitive tests across many objects/attributes and many rules. … To make the rules executable by a rule engine, it is also necessary to implement the operations and conditions in a programming language. — en.wikipedia.org

And there are many implementations of it out there, mostly in python, ruby and java. There is even something in Rust and Haskell (fancy!) but I wanted to take the challenge of writing a very complex stateful algorithm in an immutable functional language.

But Elixir is immutable, how do we solve this?

State monads! I am not gonna go into that but there is a paper about this.

We need some sort of state that we pass in every function, and we need a proper data structure.

First of all, we need to note that Rete is an acyclic, directed graph data structure and we have a crazy good library implementing that in Elixir, it is https://github.com/bitwalker/libgraph by Bitwalker.

This will give us the opportunity to have a data structure to compile the rules into, the tools to traverse each child, the sharing of nodes and everything else we need to traverse the rules in order to find which nodes can be activated.

So I came up with a basic naive implementation of Rete using those key concepts: state monads, directed graph using libgraph and produced Retex, something that follows the concepts of:

• Retex compiles the rules using libgraph (A graph data structure library for Elixir projects)
• The activation of nodes is done using a Map.reduce over each node and activating them using the Activation protocol. Each type of node implements its own protocol for the activation, passes the tokens to the children
• When a node is activated, a map (the state) is updated adding its ID to the list of activated nodes (the Retex state)
• A list of bindings is passed along each iteration of the reduction on the graph and updated/checked depending on each implementation of the Activation protocol that the current node has
• It works as a boilerplate to create your own implementation of Rete (in Elixir)

What did I learn with this challenge?

- Rete is hard (for me)
- Elixir could work even with things that seem to be far from the paradigms that it follows
- choosing the right data structure is key
- monads are scary for many but they can make you do things that at first seem impossible

One of the key concepts of logic programming is that you need to think ahead and only then implement a solution. This is exactly what I did with Retex.

For sure I won’t be able to apply this algorithm in a lot of cases but exercising our brain into doing something that goes out of the box in which we usually code can be beneficial to what else we do day by day: it could make us better programmers, better at solving problems.

This is the source code if you wanna check it out: https://github.com/lorenzosinisi/retex or the complete solution with a DSL at https://github.com/lorenzosinisi/neural_bridge

Notes

It is really hard to explain all of this in a simple blog post, so bear with me for all the crazy simplifications I made and bear with me if something is not that clear. I will link some resources so that if you want you can read more:

1. A decent explanation of Rete: https://www.sparklinglogic.com/rete-algorithm-demystified-part-2/

2. Another one but on YouTube https://www.youtube.com/watch?v=XG1sxRcdQZY

3. Feel free to add more links in the comments below!