I’ve been working my way through The Art of Prolog. The book is a fantastic eye-opener. The first five chapters are very science-heavy as they cover all Prolog principles. What follows are the twenty or so delightful, short, but on-subject chapters explaining the Prolog language in detail. I have a couple of chapters left to go through. I am looking forward to the compiler example from chapter 24.
However, I do have a couple of research problems to look at.
table of contents
Before I jump into that, though, some thoughts on Prolog.
What strikes me when writing Prolog code: what, not how. Solving a Problem in Prolog puts the focus on data flow. A continuous data transformation. The Zen of the thought process is minted in composable predicates, which the Prolog VM uses to solve the problem at hand.
I had such an aha moment six years ago when I was learning Erlang. Bugs appear when the logic applied to the problem isn’t correct.
There are no loops, no syntactical conditionals, no return statements, and no state mutation. There is so little noise in the code. Individual predicates replacing traditional conditional branches from imperative languages make the reasoning about each branch easy to follow and test. The code is much more composable and ready to test in isolation. Now I remember why I enjoyed Erlang so much. There is one more language family with such utility—everything Lisp, everything S-expressions.
Prolog is not your grandma’s programming language. Definitely not SWI-Prolog, a Prolog implementation actively developed since 1985. It’s a very modern platform for any task one can imagine having today.
On top of my head:
- TCP, UDP, sockets.
- HTTP servers.
- TLS support.
- Paxos library.
- Protocol buffers.
- Coherent testing story.
- Official Docker image in the Docker Hub, running programs in containers.
- C and Java interoperability.
That, and more, is what SWI-Prolog offers. I haven’t had a chance yet to try Scryer Prolog or Ichiban Prolog, but I expect that having a combination of Prolog and a powerful, expressive, imperative language available within a single program can be a huge productivity boost.
§last week’s problems
In the Zanzibar-style ACLs in Prolog article, I experienced a couple of problems prohibiting general applicability to many children, single parent permission inheritance. My original implementation used hard-coded document and directory fact predicates inside of the
inherits/3 and API code. I outlined a couple of possible improvements:
- Find a way to provide the type of fact to query for.
- Or create a general fact container.
Both are equally easy to implement, but there are significant differences in the user experience.
§general fact container
The inheritance resolution program requires something to resolve the parent of an object with a given ID to traverse the inheritance tree. Given an ID, fetch the parent reference and use it further to seek a solution. Given:
- A needle name in form of an atom
- A compound container term.
Find the compound member named like the atom inside of the container term. For example:
directory(...) term, the
Out value should be
parent(objectid('851a7566-b83d-4993-bd04-9b8244091d45')). Frankly, anything that contains
parent(...) should be handled the same way. This problem can be solved by using a couple of built-ins:
arg/3. Here’s my solution:
This code, given any valid compound, will figure out its arity and recursively try to find an argument with the name under an atom. This solution works pretty well, except for two issues:
- An argument cannot be of zero arity because the
functor/3predicate raises an exception in that case. For example:
But this will be fine:
- The second problem is that the, in this case,
directory(...)term has to be available at the call site. As in, it has to come from some other call site. Ergo, it must be fully typed by someone into the program. A usual case would be to have a bunch of facts in a global database, as I had in my previous article, and I would like to reference those. Hence, I would like to avoid having to type them in. But, it’s not trivial to take a reference to a term of possibly variable arity and pass it as an argument. Prolog provides meta-programming facilities allowing a term to be reconstructed at run time, but it’s not trivial.
I’m happy with the code, but for the reasons above, I don’t like this solution.
§providing a type of the fact to the query
In imperative language, I would consider solving this problem by passing a closure that, given an ID of an object, returns the parent reference. Prolog does not offer closures, but it has something that can be compared to a closure, if you squint hard enough… Consider the following code:
What happens here, Proc is given the predicate
hello('a') as a value, the standalone Proc. calls that value as a predicate. We can make it better using the built-in
=.. (univ) predicate to construct a call site from arguments. Here’s a rudimentary example:
This is much more promising than the previous solution. Using the construct above, I have arrived at the following example:
And the call:
Yes, this is much better. The
find_parent/3 predicate would be called by existing
inherits/3. The user would be required to provide their
parent_resolver/2, which makes sense as the user knows the structure of the compound they work with.
The immediate next step is to integrate this into the actual program so that I have a general inheritance API. The next problem is more interesting: the distribution of the individual facts close to the compute so that a small Prolog program can use a minimum necessary number of facts required to make a decision. The simplest way of doing it is to provide something similar to the Open Policy Agent bundles.
The second step is a little bit more mundane task to provide a trace facility to the user so that the user knows why permission is granted or denied. Similar to the Open Policy Agent playground trace feature, or the explanation API in Keto. A pure Prolog recipe exists in chapter 17 of The Art of Prolog.
§scratching the itch
Having solved this problem in OPA and Prolog, I’m pretty confident the permissions API does not need a database to work. Neither does one want a database for this because:
- A single-node RDBMS will be a single point of failure, always.
- Building and operating a leader/follower RDBMS setup reliably is not easy.
- A distributed RDBMS is a massive cost and operational factor.
OPA is the best example of how to do this best. Rego is very lightweight. The OPA VM is embeddable and available in many programming languages as a library.
That makes it easy to move the compute very close to where the problem is, even into the actual application. Inside of the application, that’s where this journey started for me two years ago. I was trying to scratch my itch, which was to provide permissions API to Firebuild. Today, I know I could have used OPA. But I now understand why that would have been the best choice back then.
The problem is not in querying for permissions, the problem is in bringing the facts to where the decision has to be made. The key to solving this in Prolog is sticking to standard Prolog and leveraging whatever implementation there exists for a programming language a developer is using for their application.
Time to refocus and bring two years’ worth of learnings together.