gruchalski.com

Zanzibar with Prolog, week 2

 1558  8 mins
thumbnail

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.

§on (SWI-)Prolog

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.
  • Multi-threading.
  • RocksDB.
  • 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[1] 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:

1
2
3
4
5

search_compound(parent, directory(
    dirname('documents'),
    objectid('b94c1f40-818b-47be-882b-ce1a8fbee254'),
    parent(
        objectid('851a7566-b83d-4993-bd04-9b8244091d45'))), Out).

Given the 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: functor/3 and arg/3. Here’s my solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

search_compound(Atom, Term, Out) :-
    compound(Term),
    functor(Term, _, Y),
    search_compound(Atom, Term, Out, 1, Y).

search_compound(Atom, Term, Value, N, _) :-
    atom(Atom),
    arg(N, Term, Value),
    compound(Value),
    % To support compounds with arity 0,
    % change the functor/3 below to
    % compound_name_arity/3.
    % **Warning**: This is SWI-Prolog specific, it may not work in other Prolog implementations.
    functor(Value, Atom, _).

search_compound(Atom, Term, Out, N, T) :-
    N < T,
    M is N + 1,
    search_compound(Atom, Term, Out, M, T).

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/3 predicate raises an exception in that case. For example:
1
2
3
4
5
6
7
8

search_compound(parent, directory(
    whatever(),
    dirname('documents'),
    objectid('b94c1f40-818b-47be-882b-ce1a8fbee254'),
    parent(
        objectid('851a7566-b83d-4993-bd04-9b8244091d45'))), Out).

% ERROR: Domain error: `compound_non_zero_arity' expected, found `whatever()'

But this will be fine:

1
2
3
4
5
6
7
8

search_compound(whatever, directory(
    whatever(nil),
    dirname('documents'),
    objectid('b94c1f40-818b-47be-882b-ce1a8fbee254'),
    parent(
        objectid('851a7566-b83d-4993-bd04-9b8244091d45'))), Out).
 
% Out = whatever(nil).
  • 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:

1
2
3
4
5
6
7
8
9

?- assertz(hello(Arg) :- format('Hello, world, you said: ~q!~n', [Arg])).
true.

?- Proc = hello('a').
Proc = hello(a).

?- Proc = hello('a'), Proc.
Hello, world, you said: a!
Proc = hello(a).

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:

1
2
3
4
5
6

?- assertz((call_it(Atom, Arg) :- Proc =.. [Atom, Arg], Proc)).
true.

?- call_it(hello, 'a').
Hello, world, you said: a!
true.

This is much more promising than the previous solution. Using the construct above, I have arrived at the following example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

entity(
    objectid('851a7566-b83d-4993-bd04-9b8244091d45'),
    parent(objectid()),
    metadata([type, directory, name, 'data'])).

find_parent(Id, Out) :-
    ProcCall =.. [parent_resolver, Id, Out],
    ProcCall. % I could use call(ProcCall) but this does the job.

% The user of the API need to provide this predicate:
parent_resolver(Id, Out) :-
    entity(objectid(Id), Out, _).

And the call:

1
2

?- find_parent('851a7566-b83d-4993-bd04-9b8244091d45', Out).
Out = parent(objectid()).

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.

§next steps

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.

  1. Zanzibar-style ACLs in Prolog 

See Also: