Implementing Logic Programming

I just think it's neat!

Most of my readers are probably familiar with procedural programming, object-oriented programming (OOP), and functional programming (FP). The majority of top programming languages on all of the language popularity charts (like TIOBE) support all three to some extent.

Even if a programmer avoided one or more of those three paradigms like the plague, they’re likely at least aware of them and what they’re about. Or they’re applying one of the paradigms while denying that they’re doing so, like Haskell programmers using the IO or State Monads (procedural programming), or C programmers writing structs of function pointers (object-oriented programming), or Java programmers using streams (functional programming).

The same is sadly not true of logic programming¹. While some programmers are aware of its existence, and might have experienced a little bit of it in university, it’s not even close to the popularity of the other paradigms. I’d go so far as to say that the majority of programmers have no idea what it’s about, and that’s a shame because logic programming is really good at tackling certain kinds of problems.

OOP and FP are easy to explain in terms of procedural programming concepts, and it’s also pretty easy to explain how to implement them. That’s not really the case for logic programming, but when has that ever stopped me?

What better way to learn something than to implement it?

Why Logic Programming?

If you’ve ever lost your marbles trying to model complex relationships between various concepts as objects with bi-directional pointers to each other and derived properties that need to be cached and all that jazz, then that’s a great example of a problem where you should have used logic programming instead (looking at you OMG and your fancy SysML v2 standard²).

For a rather big list of examples of what you can do with logic programming, check out this blog post from Phillip Zucker.

In logic programming we don’t program with functions as we do in the other paradigms (procedures and methods are also functions). Functions have a set of inputs and a set of outputs, and mutable inputs can be viewed as just another kind of output.

Rather, in logic programming we program with relations. They’re also called predicates in logic programming, but they’re the same thing really (much like procedures and methods are kinds of functions).

The difference between a relation and a function is that a relation doesn’t have a clear distinction between what is an input and what is an output.

I’ll use what is probably the most well known logic programming language, Prolog, to illustrate. Let’s start with a simple example:

male(dicky).
male(randy).
male(mike).
male(don).
male(elmer).

female(anne).
female(rosie).
female(esther).
female(mildred).
female(blair).

In the example above, male and female are what are known as predicates in Prolog. Predicates are defined in terms of clauses, and a clause can be either a rule or a fact. A fact is just a rule that is always true. Every “statement” in the example above is a fact.

By writing male(randy) on its own as above, we’re saying that “it is a fact that randy is a male”. This being an is-a relationship is just our own interpretation of what male(_) means. All Prolog cares about is that there’s a fact for predicate male that states male(randy). A predicate/relation means whatever we want it to mean.

The various names of people above are atoms in Prolog. They’re basically interned strings (same as symbols in Lisp, Ruby, Julia, Smalltalk, etc.), but atoms can also be integers and even complex structures. Prolog is dynamically typed so we don’t need to declare any types, but that’s not the case for logic programming in general³.

All we’ve done so far is state that a bunch of people are either male or female. Not very interesting, but we’ll make use of this information soon. Let’s move on to a more interesting set of facts:

parent(don, randy).
parent(don, mike).
parent(don, anne).

parent(rosie, randy).
parent(rosie, mike).
parent(rosie, anne).

parent(elmer, don).
parent(mildred, don).

parent(esther, rosie).
parent(esther, dicky).

In the example above we’ve added a new predicate (parent) and some associated facts, this time relating two people. When we write parent(don, randy), we’re saying that Don is one of Randy’s parents. Relations don’t really have an ordering, this is just how we’ve chosen to interpret each of the two arguments.

The Power of Rules

So far, nothing special, but now we can write our first rule:

father(X, Y) :- male(X), parent(X, Y).

The rule above says that for any given X and Y (uppercase letters are variables), if X is a male, and X is a parent of Y, then X is the father of Y⁴. The weird :- symbol is a reverse implication, while the comma means “and”. In Prolog “or” would be a semicolon, or just another rule for the same predicate. You can read the example as:

father(X, Y) if male(X) and parent(X, Y)

Anyway, we can now start doing some queries (?- is the query operator)⁵, for example:

?- father(X, randy).

This will return X=don. If instead we query:

?- father(don, X).

We get X=randy, X=mike, and X=anne.

As I mentioned previously, rules don’t have any clear distinction between inputs and outputs. What constitutes an output depends on the query. I can write the query:

?- father(X, Y).

And get every possible pair of father and child in the Prolog interpreter’s “database of facts” (so to speak). The word database is quite relevant actually, since as the name relation implies, logic programming is closer to relational programming (e.g., SQL) than it is to the other paradigms.

But logic programming can be a lot more powerful (and succinct) than crappy SQL. For example, we can keep adding more interesting rules:

son(X, Y) :- male(X), parent(Y, X).
daughter(X, Y) :- female(X), parent(Y, X).

sister(X, Y) :- daughter(X, P), parent(P, Y), X \= Y.
brother(X, Y) :- son(X, P), parent(P, Y), X \= Y.

aunt(X, Y) :- sister(X, P), parent(P, Y).
uncle(X, Y) :- brother(X, P), parent(P, Y).

These should hopefully be pretty obvious. Notice how we can introduce new variables in the body of the rules, like P above. Prolog uses unification to link variables together, the same process used by type inference.

The real power comes from recursion:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

The above is similar to how you do pattern matching in Haskell, in case you’re familiar with that. We can also, for example, add some special cases inspired by the creation myth of Abrahamic religions:

ancestor(adam, X) :- male(X); female(X).
ancestor(eve, X) :- male(X); female(X).

If we declare adam as male, then we end up with adam as being an ancestor of adam, which is pretty funny (but also pretty easy to fix).

Neat, how do I implement it?

Well, I could go over how to implement a Prolog interpreter, but honestly I don’t think you should. Prolog is honestly kind of jank, and I’m not talking about good vintage jank like C.

The main issue is that Prolog is not truly declarative; how you write the rules has a major impact on how the interpreter behaves. You might end up with repeated answers for a query or it might enter an infinite loop. Prolog also allows IO, so the order in which things get executed is critical. It’s Turing-complete, for better or worse.

If you really want to implement Prolog specifically, you have to follow its execution semantics, which are based on SLD resolution using depth-first search and backtracking. Prolog programs depend on the specific order in which rules get executed, so you have to perform the search the same way as all the other Prolog implementations do. Check out Warren’s Abstract Machine on how to do it efficiently (also a good source for implementing unification).

But we don’t need Turing-complete Prolog. We already have whatever Turing-complete, multi-paradigm programming language we’re using on a daily basis, we just need to power it up with logic programming.

Most people would do this by implementing miniKanren, another logic programming language that is specifically designed to be embedded into a host language, originally Scheme. A later developed simplified core, microKanren, is so small it can be implemented in 39 lines of Scheme code without any macros.

But I am not a big fan of the miniKanren family. Its design is very functional, which has its advantages, but to me the “database” aspect is important. Unlike Prolog, where facts can be added and removed while the program is running, in miniKanren you set up the universe of facts you care about each time you make a query.

This results in a very clean implementation⁶, but it leaves a lot of performance on the table. To me, maintaining a stateful database of facts is a core part of the job. That’s what we’re really doing: implementing a fancy database. You can of course bolt on a stateful fact database to a miniKanren implementation, but it’s not how miniKanren is meant to work.

Instead, we’ll turn our attention to Datalog, a subset of prolog that is not Turing-complete. You can’t use Datalog to develop complete applications, but it sure is great at modeling relationships. In fact, I wish it would replace SQL as the language of choice for databases⁷. SQL isn’t even a good relational language, and logic programming is just on another level entirely⁸.

Since Datalog is a subset of Prolog, we could just implement the same algorithm we’d use for a Prolog interpreter and it would work, but the lack of Turing-completeness gives us a lot of room for maneuver.

For one, techniques from databases are applicable: B-trees, query optimization, index selection, etc. Datalog is also very amenable to partial evaluation, as employed by the highly optimized Soufflé dialect.

Here we’ll keep it simple and implement what I think is the most basic algorithm for interpreting Datalog: Naïve Evaluation. It’s a simple bottom-up fixpoint algorithm that repeatedly applies each rule until no new facts can be derived. We’ll also abuse operator overloading to make the code look sort of like Datalog.

Modeling Datalog

We’ll use Python to keep things as simple as possible. The first thing we need is some way to represent variables, values and usages of a predicate (that we’ll call atoms):

class Variable:
    def __init__(self, name: str):
        self.name = name
    
    def __repr__(self) -> str:
        return self.name

Value = bool | int | float | str
Term = Variable | Value

class Atom:
    def __init__(self, predicate: str, terms: Tuple[Term, ...]) -> None:
        self.predicate = predicate
        self.terms = terms

This Atom class is just used to model a predicate usage like father(X, bill) and such, either with a variable or a value in each argument. Not sure what else to call it. Note that this is different from the meaning of an atom in Prolog.

Also notice that we cannot pass predicates as arguments to other predicates. This is allowed in Prolog but not in Datalog. Datalog has some restrictions to ensure it always terminates (they can be loosened, but we’ll stick to the basics):

• negation is not allowed.

• complex terms as arguments of predicates, e.g., p(f(x), y), are not allowed.

• every variable that appears in the head of a clause must also appear in an atom within the body of the clause.

For values we only allow a few builtin Python types to keep things simple. With variables, values and atoms in place, we move on to predicates:

Fact = Tuple[Value, ...]

class Rule:
    def __init__(self, head: Atom, body: Tuple[Atom, ...]):
        assert len(body) >= 1
        self.head = head
        self.body = body

class Predicate:
    def __init__(self, name: str, arity: int):
        self.name = name
        self.arity = arity
        self.facts: Set[Fact] = set()
        self.rules: List[Rule] = []

We split clauses directly into separate facts and rules. A fact is just a row of values belonging to a predicate. A rule has a head (left side of the :- operator), which is just a single atom, and a body with one or more atoms (right side of the :- operator). Arity is the expected number of arguments.

To manage our “database” we’ll create a class simply called Datalog:

class Datalog:
    def __init__(self) -> None:
        self.variables: Dict[str, Variable] = {}
        self.predicates: Dict[str, Predicate] = {}

    def variable(self, name: str) -> Variable:
        assert name not in self.variables
        v = Variable(name)
        self.variables[name] = v
        return v

    def predicate(self, name: str, arity: int) -> Predicate:
        assert name not in self.predicates
        c = Predicate(name, arity)
        self.predicates[name] = c
        return c

We also store the variables here to make the API a bit nicer and to allow us to safely use reference equality later on for better performance. We could do the same with string values (turning them into symbols) but I leave that as an exercise for the reader.

Next, we need a way to create atoms and to add facts and rules to a predicate. We’ll add a bit of nasty operator overloading to the Predicate class to achieve this:

def __getitem__(self, terms: Term | Tuple[Term, ...]) -> Atom:
    # make sure we always work with a tuple
    terms = terms if isinstance(terms, tuple) else (terms,)
    if len(terms) != self.arity:
        raise ValueError()
    return Atom(self.name, terms)

def __setitem__(self, 
    terms: Term | Tuple[Term, ...], 
    rhs: Atom | Tuple[Atom, ...]) -> None:
    # make sure we always work with a tuple
    terms = terms if isinstance(terms, tuple) else (terms,)
    # if the rhs is the empty tuple, we're adding a fact
    if rhs == ():
        # NOTE: facts cannot contain variables, add a check!
        self.facts.add(cast(Tuple[Value, ...], terms))
    elif isinstance(rhs, tuple):
        self.rules.append(Rule(Atom(self.name, terms), rhs))
    else:
        self.rules.append(Rule(Atom(self.name, terms), (rhs,)))

What we’ve done above allows us to write the following:

dl = Datalog()

parent = dl.predicate('parent', 2)
ancestor = dl.predicate('ancestor', 2)

X, Y, Z = dl.variable('X'), dl.variable('Y'), dl.variable('Z')

parent['alice', 'bob'] = ()
parent['bob', 'carol'] = ()
ancestor[X, Y] = parent[X, Y]
ancestor[X, Y] = parent[X, Z], ancestor[Z, Y]

We have square brackets instead of round, = instead of :-, and need to write = () to declare a fact, but it sure looks a lot like Datalog. Even the = () is actually correct because pred(foo, bar). in Prolog and Datalog is just syntax sugar for:

pred(foo, bar) :- .

So all we’re missing is that little bit of syntax sugar.

Interpreting Datalog

We can model Datalog programs now, but we cannot perform any queries nor infer any new information. First thing we’ll need is an extra datastructure:

Substitution = dict[Variable, Value]

Pretty simple, just a mapping of variables to values. We’ll make heavy use of this datastructure soon, but first, the most important method — infer:

def infer(self) -> None:
    while True:
        newly_added_facts: List[Tuple[Predicate, Fact]] = []
        for predicate in self.clauses.values():
            for rule in predicate.rules:
                for sub in self.evaluate(rule.body):
                    fact = tuple(
                        sub[t] if isinstance(t, Variable) 
                        else t for t in rule.head.terms)
                    if fact not in predicate.facts:
                        newly_added_facts.append((predicate, fact))
        if not newly_added_facts:
            break
        for p, f in newly_added_facts:
            p.facts.add(f)

Method infer is the core of our Datalog engine. It implements the fixpoint algorithm that expands rules into new facts. You should call this method each time you manually add a new set of facts and/or rules.

Every loop iteration, for each rule, we call another method called evaluate, which lazily outputs all possible substitutions given the body of the rule. Each substitution is then used to create a new fact by replacing every variable with the associated value in the head of the rule (keeping any values already in the head).

If that fact was not already in the list of known facts, then we’ve derived a new fact. Once we’ve gone over every rule, if we found any new facts, we update our fact database and iterate again. If no new facts were derived, we’re done.

Method evaluate is just a wrapper around another method called search:

def evaluate(self, atoms: Sequence[Atom]) -> Iterable[Substitution]:
    return self._search(0, atoms, {})

def search(self, i: int, atoms: Sequence[Atom], 
            sub: Substitution) -> Iterable[Substitution]:
    if i == len(atoms):
        yield sub
        return
    atom = atoms[i]
    for fact in self.clauses[atom.predicate].facts:
        new_sub = sub.copy()
        if unify(atom, fact, new_sub):
           yield from self._search(i + 1, atoms, new_sub)

Method search implements a lazy depth-first search. Its goal is to successfully unify every atom in the body of a rule. To do this, it picks the atom at index ‘i’, and for every fact associated with the corresponding predicate, it tries to unify the atom with the fact. If unification succeeds (meaning we’ve obtained a substitution for every variable in the atom), we recursively call search again, only this time starting at the next index and enforcing the current substitution.

As an example of how it works, consider this rule:

ancestor[X, Y] = parent[X, Z], ancestor[Z, Y]

The first atom is parent[X, Z]. These are the known facts of parent:

parent['bob', 'carol']
parent['alice', 'bob']

We start with the first fact. We unify X=’bob’ and Z=’carol’. We then call search recursively, moving to the next atom, ancestor[Z, Y], with that substitution in hand.

From the other rule of ancestor:

ancestor[X, Y] = parent[X, Y]

We probably already derived that every parent is an ancestor, so the current facts of ancestor are also:

ancestor['bob', 'carol']
ancestor['alice', 'bob']

We try to unify with the first fact and fail, because the substitution enforces Z=’carol’ which cannot unify with ‘bob’. The second fact also fails to unify, so this is a dead end.

That branch of the recursion dies and we’re back trying to unify the first atom. Now we unify with the second fact, obtaining the substitution X=’alice’ and Z=’bob’. We recurse again with that substitution.

We try to unify ancestor[Z, Y] with its first fact, and we succeed, because we can set Z=’bob’ and Y=’carol’. We managed to do a complete substitution, so we yield it.

The function unify, used within search, is pretty simple:

def unify(atom: Atom, fact: Fact, substitution: Substitution) -> bool:
    for t, v in zip(atom.terms, fact):
        if isinstance(t, Variable):
            if t in substitution and substitution[t] != v:
                return False
            substitution[t] = v
        elif t != v:
            return False
    return True

It takes in an atom, a fact, and a substitution, and pairs up each term in the atom with the corresponding value in the fact at the same position. If the term is a variable, we do the following:

• If the variable is in the substitution, then we check if the value associated with it and the value in the fact match. If they don’t, unification fails.

• If the variable isn’t in the substitution, then we update the substitution by mapping the variable to the value in the fact.

If instead of a variable we see a value, then we just compare that value with the value in the fact directly.

To finish up our little interpreter, we only need one more method, and it’s a trivial one:

def query(self, *atoms: Atom) -> Iterable[Substitution]:
    return self.evaluate(atoms)

Yup, query is just evaluate, but variadic to make the API a bit nicer. With that, we can finally write our tiny Datalog program:

dl = Datalog()

parent = dl.predicate('parent', 2)
ancestor = dl.predicate('ancestor', 2)

X, Y, Z = dl.variable('X'), dl.variable('Y'), dl.variable('Z')

parent['alice', 'bob'] = ()
parent['bob', 'carol'] = ()
ancestor[X, Y] = parent[X, Y]
ancestor[X, Y] = parent[X, Z], ancestor[Z, Y]

dl.infer()

for result in dl.query(ancestor[X, 'carol']):
    print(result)

Which outputs (in any order):

{X: 'alice'}
{X: 'bob'}

Conclusion

Well that ended up a lot longer than I expected, but the actual implementation is pretty small all things considered. It’s not efficient, but some small optimizations go a long way, for example switching to semi-naïve evaluation.

The main difference is that instead of always going over every fact in each iteration of the loop, we only apply each rule to facts we derived in the previous iteration.

Another optimization is dynamically sorting the atoms in the body of a rule based on the number of values each atom contains and the number of associated facts, to try and cause search branches to fail as soon as possible.

We could also add support for arithmetic and composite atoms (like lists), which introduce some challenges if we wish to stay “Turing-incomplete”.

Either way, you now have a new tool in your arsenal. No more horrible object graphs desperately trying and failing to model relations, you can now simply use the best paradigm for the job.

Update: This article was discussed on hackernews.

1. Logic programming just hasn’t had much of an impact. Many reasons have been postulated as to why, but to me the real culprit was trying to make it a general purpose programming paradigm like the other big 3. It’s simply ill-suited for application development. It works much better as a purely declarative auxiliary paradigm, like the relational model (e.g. SQL).

2. Disclaimer: my opinions are my own and do not reflect those of my employer.

3. The hybrid functional-logic programming language Mercury is statically typed. The same is true of the Soufflé dialect of Datalog. More on Datalog later.

4. Reminder this is how we chose to interpret the order of the arguments, the relations themselves don’t have an ordering!

5. Technically we could already do queries, they just wouldn’t be interesting.

6. That is, if you can stand to read (lisp-style (code)) with horribly named functions passing around unnamed closures all over the place. But that’s a syntax issue, not semantics.

7. Datomic uses Datalog, so there’s at least one database using it, but they use a non-standard lisp-style syntax that I really don’t like (it’s Clojure based).

8. For one, database normalization isn’t really something that has to be kept in mind when doing logic programming. The style of relations one writes in logic programming just naturally cover most normal forms by nature.