Meta-Predicates in SWI-Prolog

The meta_predicate directive in Prolog can cause confusion when first encountered for two reasons: 1, it is a horrible, horrible hack; 2, documentation for it is badly-written by people who know what they mean but not how to express it. There is the further problem that each dialect does it differently (this being Pro-"what's a standard?"-log). Here's my attempt to make things a bit less confusing for SWI-Prolog (and probably YAP) users.

Meta-predicates are an unfortunate side effect of two problems in Prolog:

  1. The language is very old and designed at a time when modular programming was in its infancy (and not widely adopted).
  2. Higher order programming was also an afterthought in the language design.

Before the ISO attempted to standardize on something sane, all sorts of dialects did all sorts of weird things to support both higher order programming and modular programming.  Needless to say, none of these were compatible.  The ISO committee really had its work cut out for it and it rose to the task like… well, any standards committee in computing ever: it came up with a horror.  Factor into this that the kind of person usually attracted to working on Prolog isn't exactly the kind of person who relates well to other human beings and you have the proverbial perfect storm of incomprehensible gibberish.

The code

The following code block will be used to illustrate how meta-predicates are used in SWI-Prolog.  Given how closely the YAP project works to ensure maximal compatibility with SWI-Prolog, the explanation will likely apply to that compiler as well (with, perhaps, minor differences here and there).  Other Prolog dialects will have the meta_predicate (possibly metapredicate) directive, but will likely have differences ranging from minor to major in how the directive is used.

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
:- module(maplist, [maplist/3]).
:- meta_predicate maplist(2, ?, ?).

%% maplist(:Goal, +List1, ?List2)
%
% True if Goal can successfully be applied to all
% successive pairs of elements from List1 and List2.

maplist(Goal, L1, L2) :-
    maplist_(L1, L2, Goal).

maplist_([], [], _).
maplist_([H0|T0], [H|T], Goal) :-
    call(Goal, H0, H),
    maplist_(T0, T, Goal).

What the code does

The above code, taken from the SWI-Prolog manual, is an implementation of the maplist/3 predicate.  (Indeed if you fire up swipl and get a listing for each of maplist/3 and maplist_/3, you'll see that the implementation is identical; only the module name is different.)

 

Now how maplist/3 works is straightforward: it applies a passed-in goal (usually a predicate) to each item in two passed-in lists and ensures they unify.  It's typically used for things like this:

 

?- maplist(plus(2), [1,2,3,4,5], L).
L = [3, 4, 5, 6, 7].

 

It could also be used, this being Prolog and all, for weird stuff like this:

 

?- maplist(plus(2), [1,2,3,4,5], [3,4,5,6,6]).
false.

The problem

But ... now let's look at that first parameter: the goal.  The goal is something we supply to the predicate.  maplist/3 applies that goal on our behalf (using the hackish call/* suite of system meta-predicates).  In this example we've passed in a system-known predicate (plus/3), but what happens if we pass in something else?

 

1
2
3
4
5
6
7
:- module(my_module, my_exposed_predicate/4).

% … do some stuff

    maplist(my_private_predicate, [1,2,3,4,5], L),

% … do some more stuff

 

When we call maplist/3, my_private_predicate is unknown to maplist/3 because it's not in the right module.  First, my_private_predicate isn't exposed in the module, so even if we could somehow trick the maplist module to use_module(my_module) (which we can't) it still wouldn't work.  No, we have to find some other way to let maplist/3 know.  Now one possibility is that we could always call it like maplist(my_module:my_private_predicate, [1,2,3,4,5], L), but that would get very old, very quickly.

The solution

The solution is to use some hackery.  The hackery is simple: tell the compiler that anywhere maplist/3 is called that it has to take the provided goal and rewrite it (Prolog is homoiconic, so this is very easy to do) so that the my_module: part gets added.  And, as you've already probably guessed, the meta_predicate directive is how we tell the compiler to do this.  That mysterious line 2 above (:- meta_predicate maplist(2, ?, ?).) is the hackery that informs the compiler of what it has to do.

:- meta_predicate ….

The documentation for meta_predicate in SWI-Prolog is not exactly what I'd call the best-written prose in history.  It's typical reference documentation: if you know what you want to use and why, it'll remind you of how.  Without knowing what and why, however (which hopefully should be clearer now) the documentation is pretty opaque.  So let's pick apart the directive for our maplist module and see what it does.

 

First, as a directive, it begins with :-.  This means, in effect, that it's executed at compile time before any other code that's not preceeded by such.  It is then followed by a comma-separated list of metapredicate heads and terminated by a period.  In this case there's only one head: maplist(2, ?, ?).

maplist(2, ?, ?)

So what does that head mean?  Well first it tells the compiler that maplist has an arity of 3.  Then the weirdness begins.  That 2 at the beginning tells the compiler two things:

  1. The parameter in this position is module-sensitive.
  2. The parameter in this position is a predicate that will require two more parameters beyond those provided in the goal.

The first point is obvious—the maplist/3 predicate will be rewritten at the calling point to put in the module context—but let's look back at maplist(plus(2), [1,2,3,4,5], L) to understand that second one.  The plus/3 predicate has an arity of three.  We're "partially" calling it by passing in a plus/1.  The 2 here is telling the compiler that we expect two more parameters (one from each passed-in list) for this predicate and that it thus must be plus/3 that's actually called in the end.  (Why can't it figure this out for itself?  It turns out it can; the SICStus Prolog environment doesn't use this kind of anal retentive numbering.  It accepts the numbers but treats them all the same, along with the : thing we'll be talking about later.)

 

The ? parameters passed in for the other two arguments to maplist/3's header are mode declarations which in SWI-Prolog are merely documentation.  They are ignored by the compiler except in that they tell the compiler not to rewrite the terms with a module specifier.

0..9, :, ?, +, -, ^ and //: Oh my!

So now we know what the integers do: they tell the compiler how many parameters the provided goal is expecting.  : is simpler.  It tells the compiler that the provided goal is module-sensitive, but that it is not a predicate that's getting called.

 

+, -, and ?, on the other hand, are mode declarations (bound, unbound, and unspecified respectively) whose sole use in the meta_predicate directive is to tell the compiler that they're not module-sensitive.

 

^ can be treated as 0 but has special meanings for the setof/*, bagof/* and aggregate/* predicates.  If you know how to use those, you'll know how to use ^ here.

 

Finally // means that the argument at this position is a DCG rule (which requires different processing than does a regular goal).  If you know how to use DCG rules you'll know how to use this as well.

TL;DR

meta_predicate is a directive used to get around syntactic limitations built into Prolog when a module system was grafted onto it.  It's an ugly hack that causes confusion both because it's an ugly hack and because it's usually very badly explained.  In brief, SWI-Prolog's implementation of this hack specifies for each predicate that has to execute code on behalf of another module which of its parameters are module-sensitive and which are not.  The details are fussy, but once you understand the motivation they're easy enough to learn.