Make in Prolog

Kovacsics Robert

This turned out to be a long post, so here is an outline.

Make in Prolog code at https://git.kovirobi.uk/kovirobi/prolog-make.

I have maintained for a long time that Prolog and Makefiles are very similar, recently I spent some time showing this is so. Let’s explore this. The similarity comes from the way they both operate, looking at a database of facts, trying to prove what the user asked.

Make is logic programming

But Make isn’t proving anything, I hear you say. It actually is, let me demonstrate, by proving to you that three is odd, and four is even. I think you can agree that zero is even, and adding one flips the odd/even property – we can tell Make this by using Peano arithmetic (as Make only does very simple pattern matching).

Makefile

even_0:
	@echo 0 is even
even_%+1:
	$(MAKE) odd_$*
odd_%+1:
	$(MAKE) even_$*

Note: I started with odd_%+1: even_% and vice versa but turns out GNU Make limits recursion this way, so I had to switch to recursive Make. But for comparison with Prolog, here is the original implementation.

Original Makefile

even_0:
even_%+1: odd_%
odd_%+1: even_%

Now let’s prove that three is odd:

❯ make -n --no-print-directory \
     "odd_0$(yes +1 | head -n3 | tr -d "$IFS")"
make even_0+1+1
make odd_0+1
make even_0
echo 0 is even

But four is not:

❯ make -n --no-print-directory \
    "odd_0$(yes +1 | head -n4 | tr -d "$IFS")"
make even_0+1+1+1
make odd_0+1+1
make even_0+1
make odd_0
make[4]: *** No rule to make target 'odd_0'.  Stop.
make[3]: *** [Makefile:4: even_0+1] Error 2
make[2]: *** [Makefile:6: odd_0+1+1] Error 2
make[1]: *** [Makefile:4: even_0+1+1+1] Error 2
make: *** [Makefile:6: odd_0+1+1+1+1] Error 2

What an easy way to fork bomb proving that one million is even! (Though having tried it, we run into filename limits first.)

Prolog is (the original) logic programming

Now let’s go the other way, to get a taste of Prolog syntax, let’s implement the even/odd example above in Prolog.

even-odd.pl

even(0).
even(N+1) :- odd(N).
odd(N+1) :- even(N).

Note how full-stops are the end of the clause definition in Prolog (a bit like the closing brace of a C function). The clause even(0) doesn’t even have a body. The turnstile-ish :- separates the head of the clause definition from the clause body. Semantically it means if the body is true then the head is true.

Also, identifiers starting with an upper case letter denote variables, identifiers starting with a lower case letter are atoms (interned strings, i.e. only one address for each unique string for fast comparison).

Compare with the original Makefile, it looks quite similar, just with more powerful pattern-matching.

Original Makefile

even_0:
even_%+1: odd_%
odd_%+1: even_%

And to query it, we open the script in SWI-Prolog:

❯ swipl -q even-odd.pl
1 ?- even(0+1+1).
true.

2 ?- even(0+1+1+1).
false.

3 ?- even(0+1+1+1+1).
true.

We can even trace the query, for example

4 ?- trace(even).
%     user:even/1: [all]
true.

5 ?- even(0+1+1).
 T [12] Call: even(0+1+1)
 T [20] Call: even(0)
 T [20 +0.1ms] Exit: even(0)
 T [12 +0.6ms] Exit: even(0+1+1)
true.

Though this is not an overly interesting example. Let’s implement list length, then use it to generate lists.

mylen.pl

mylen([], 0).
mylen([_ | T], N+1) :- mylen(T, N).

Pretty simple, the magic here is that either argument can be the input, indeed both can be outputs too.

Another way to load a file is via consult/1, which has the shorthand list form. Then when Prolog knows it can backtrack, e.g. in the third input, you can use semicolon to get more results, and the period to stop. You can press ? to list actions.

1 ?- [mylen].
true.

2 ?- mylen(L, 0+1+1).
L = [_, _].

3 ?- mylen(L, N+1+1).
L = [_, _],
N = 0 ;
L = [_, _, _],
N = 0+1 ;
L = [_, _, _, _],
N = 0+1+1 ;
L = [_, _, _, _, _],
N = 0+1+1+1 ;
L = [_, _, _, _, _, _],
N = 0+1+1+1+1 .

Let’s trace it, then we see it backtracking.

4 ?- trace(mylen).
%     user:mylen/2: [all]
true.

5 ?- mylen(L, N+1+1).
 T [12] Call: mylen(_42002, _41990+1+1)
 T [19] Call: mylen(_43486, _41990+1)
 T [26] Call: mylen(_44528, _41990)
 T [26 +0.1ms] Exit: mylen([], 0)
 T [19 +0.5ms] Exit: mylen([_44526], 0+1)
 T [12 +0.9ms] Exit: mylen([_43484, _44526], 0+1+1)
L = [_, _],
N = 0 ;
 T [12 +2301.2ms] Redo: mylen([_43484, _44526], 0+1+1)
 T [19 +2301.1ms] Redo: mylen([_44526], 0+1)
 T [26 +2301.0ms] Redo: mylen([], 0)
 T [33] Call: mylen(_52844, _52848)
 T [33 +0.1ms] Exit: mylen([], 0)
 T [26 +2301.4ms] Exit: mylen([_52842], 0+1)
 T [19 +2301.7ms] Exit: mylen([_44526, _52842], 0+1+1)
 T [12 +2302.1ms] Exit: mylen([_43484, _44526, _52842], 0+1+1+1)
L = [_, _, _],
N = 0+1 .

Logic programming is Make

The code for this is available at https://git.kovirobi.uk/kovirobi/prolog-make but here I walk through the core of the make.pl implementation. It is the make and maybe_build predicates:

make.pl

% Core of make, first split an atom so we can pattern match on the
% file extension easily. Get dependencies, make them first, then build
% if necessary.
make(Atom) :-
    path_to_atom(Path, Atom),
    % If no explicit deps, treat as no deps
    (user:deps(Path, Deps) *-> true; Deps=[]),
    maplist(make, Deps),
    maybe_build(Path, Deps).

% Phony, only used for deps
maybe_build(Target, _Deps) :- phony(Target), !.
% Up to date, don't build
maybe_build(Target, Deps) :-
    up_to_date(Target, Deps), !,
    path_to_atom(Target, Atom),
    format(user_output, "~w up to date\n", [Atom]).
% Try building
maybe_build(Target, Deps) :- user:build(Target, Deps), !.
% If it exists and no dependencies or build steps, then no need to build
maybe_build(Target, []) :- path(Atom, Target), exists_file(Atom).

Let’s go line-by-line, the first line starts the definition of make(Atom) – remember identifiers starting with an upper case letter denote variables, identifiers starting with a lower case letter are atoms (interned strings, i.e. only one address for each unique string for fast comparison).

make.pl

make(Atom) :-

We convert the given argument (an atom, i.e. interned string) to a pattern we can match on the file extension, if possible. The path_to_atom is written in a way that if it is not possible, it succeeds and unifies the two arguments. Unification is how arguments are returned in Prolog, and in this case you can use path_to_atom(Path, Atom) with either the first argument as the input, or the second argument as the input. For example:

1 ?- path_to_atom(foo/bar:c, Out).
Out = 'foo/bar.c'.

2 ?- path_to_atom(Out, 'foo/bar.c').
Out = foo/bar:c.

3 ?- write_canonical(foo/bar:c).
:(/(foo,bar),c)
true.

Note: we use the operator : instead of . for extensions because . is automatically converted in swipl for functions operating on dictionaries.

make.pl

    path_to_atom(Path, Atom),

Then we have a soft-cut, which is a bit complicated to start off with, but gets us explaining the semantics of Prolog. The way Prolog works is by trying each clause in turn, if that clause is true then all good, if not then it tries the next clause (backtracking). In the process of a clause, it may make some assignments (unifications), any which were made during a clause which turned out to be false are forgotten.

The cut operator ! tells Prolog to not backtrack in this clause, the soft-cut operator A *-> B; C tells Prolog to try A, if it is true then ignore C for backtracking, else ignore A and B for backtracking.

So what we have here is if Path has any stated dependencies, then use those, and never use the empty list as dependencies. On the other hand, if Path never got explicitly defined as having any dependencies, then treat it as having no dependencies. This is purely for user convenience.

make.pl

    % If no explicit deps, treat as no deps
    (user:deps(Path, Deps) *-> true; Deps=[]),

Then we call make on each dependency first, before we check if our Path needs to be built, and if so then building it. This is the end of the make clause.

make.pl

    maplist(make, Deps),
    maybe_build(Path, Deps).

The maybe_build first checks if the target is phony, if so then it doesn’t try to build it. To ensure it doesn’t backtrack to other clauses of maybe_build, we use the cut ! operator.

make.pl

% Phony, only used for deps
maybe_build(Target, _Deps) :- phony(Target), !.

Then check if it is not already up to date, if so we can skip building it. Also using cut to prevent backtracking.

make.pl

% Up to date, don't build
maybe_build(Target, Deps) :-
    up_to_date(Target, Deps), !,
    path_to_atom(Target, Atom),
    format(user_output, "~w up to date\n", [Atom]).

Almost finally, we can see if the user has any build rules. Note the cut again.

make.pl

% Try building
maybe_build(Target, Deps) :- user:build(Target, Deps), !.

We also need a rule to return true if the Target cannot be built because it has no rules, but also no dependencies and is an existing file. No need for cut as it is the last clause.

make.pl

% If it exists and no dependencies or build steps, then no need to build
maybe_build(Target, []) :- path(Atom, Target), exists_file(Atom).

This wraps up the core of the make.pl, the rest

Let’s see it in use with a simple makefile.pl that builds and links C or C++ using GCC.

makefile.pl

default_target(all).

phony(all).

deps(all, ['.'/main:elf]).
deps(Dir/Base:elf, [Dir/Base:obj]).
deps(Dir/Base:obj, [Dir/Base:c]).
deps(Dir/Base:obj, [Dir/Base:cpp]).

build(Path:elf, Deps) :- system(gcc, ['-o', Path:elf | Deps]).
build(Path:obj, [Path:c | Rest]) :-
    system(gcc, ['-c', '-o', Path:obj, Path:c | Rest]).
build(Path:obj, [Path:cpp | Rest]) :-
    system('g++', ['-c', '-o', Path:obj, Path:cpp | Rest]).

The only thing to note here is the linked list destructuring syntax [Head | Tail] can be used to match on zero or more items, or append those items back to the list we give to the system/2 clause.

Grab the full Prolog code from https://git.kovirobi.uk/kovirobi/prolog-make and have a play. Perhaps next I will implement using hashes for dependency tracking instead of modification times.