Transformation Tools and simple optimiser

I’ve written a very simple optimiser library with a swipl pack structure.

The current version checks to see if all subsequent calls are disjoint from the current predicate call by checking the arguments. There is also code for a constraint based approach which takes into account types and binding status but this code is still not completed and so not exposed in the interface.

Ultimately I hope to slurp up a guard from the clause body defined as the largest initial segment of predicates that fall into a grammar:

X,Y in any
N,M in number
G,H := G,H | G ; H | \+ G | integer(X) | string(X) | ... | X <= Y | X >= Y | ... | var(X) | ground(X) ...

So far there are some bugs which appear with complicated module loading and pre-existing term transformations. I’d be happy if people tried it out and reported bugs or even better reasons for the bugs.

The advantage of the simple equality based optimiser is that it relies on very little about the host system. It seems to me that the type checking is going to be fairly fragile as one switches prolog systems and would probably have to be specialised for each one. In any event I’ll have a prototype in swipl fairly soon.

In particular the reify_reflect/2 predicate was informed by Markus Triska’s recent lecture on avoiding ‘defaulty’ representations. The initial version of the code had used the prolog term language for program transformation and it was indeed awkward and required explicit cuts and a bit more thinking than the reflected representation required.

Cheers!

3 Likes

Thanks for sharing, interesting work!

Hi Gavin,

Thank you for making your work publicly available.

Could you provide some simple examples that help those who introduce themselves into Prolog understand what exactly you are doing.

Personally, I really only understand once I see representative examples with some short explanation what the problem is that is addressed and how the approach provides a solution.

If you could do that, that would be great …

many thanks,

Dan

Given a source program:

:- module(test_optimiser,[]).

:- use_module(library(transformer)).

:- optimise_all.

p(x,y,z) :- q.
p(x,w,z) :- r.
p(x,y,q) :- s.

p(x,y) :- s.
p(z,w) :- s.

q.
q.

r.
r.

s.
s.

You can load this and obtain the following:

?- [test_optimiser].

Transformer: Performed optimisation on p/2

Transformer: Performed optimisation on p/3

?- listing(p/3).
test_optimiser:p(x, y, z) :-
    !,
    q.
test_optimiser:p(x, w, z) :-
    !,
    r.
test_optimiser:p(x, y, q) :-
    s.

true.

The optimiser has just inserted some cuts where it could reason that the cuts did not alter the semantics as the subsequent clauses were no longer reachable.

In addition there is some infrastructure to make program transformations more convenient.

?- use_module(library(transformer)). 
true.

?- reify_reflect(( p(X) :- X = 1), Reflected), reify_reflect( Term, Reflected).
Reflected = clause(p/1, [X], [X=1]),
Term =  (p(X):-X=1).

The Term structure is transformed to remove the “defaulty” qualities of the prolog code, enabling argument indexing to get us determinacy without the need for cuts. It makes the structure of the optimiser very straightfoward - it’s around 15 lines at core.

Thats a strange optimizer. It changes the logic of the program.

Before optimization:

?- p(x,y,X).
X = z ;
X = q

After optimization:

?- p(x,y,X).
X = z

You sure you are designing an optimizer, and not a new language.

Like in Haskell where you don’t have non-determinism, and such cuts are implicit.

1 Like

Very embarrassing! I’d started the optimiser for a guarded clause language in which each clause would fire deterministically and then mistakenly thought I could get away with just sticking the cuts in! Indeed this is closer to picat. I’ll go back to the guarded clause language :smiley:

I oppened an issue on GitHub #1. But otherwise cuts do not
improve clause indexing for input mode. Especially in
Prolog systems with multi-argument indexing.

You can test yourself. Among these two predicates, except
that they dont represent the same logic, see GitHub #1 for output mode,
there is also no performance difference in input mode:

p(x,y,z).
p(x,w,z).
p(x,y,q).

p2(x,y,z) :- !.
p2(x,w,z) :- !.
p2(x,y,q).

Orginally this has to do with neck cut instruction in WAM,
and functor switch in WAM. If the functor switch anyway leads
to only one clause, neck cut can be ignored by the WAM.

In multi-argument indexing there is just a automatic multi
functor switch, determined from call pattern. Testing also shows
that there is no difference:

?- time((between(1,1000000,_), (p(x,y,z); p(x,w,z); p(x,y,q)), fail; true)).
% 4,999,999 inferences, 0.313 CPU in 0.312 seconds (100% CPU, 15999997 Lips)
true.

?- time((between(1,1000000,_), (p2(x,y,z); p2(x,w,z); p2(x,y,q)), fail; true)).
% 3,999,999 inferences, 0.313 CPU in 0.312 seconds (100% CPU, 12799997 Lips)
true.

That the number of inferences are differently counted might
be SWI-Prolog artefact, how the neck cut optimization
is accounted for. Automatic indexing in SWI-Prolog started

with version 5.11.29 (Oct. 2011).

Disclaimer: I am not sure whether the test tests what
I think it tests. Maybe try something else? Or inspect the
clause index that SWI-Prolog builts.

Another really nice language that is maybe a bit closer to “functional” while it took a lot of good ideas from Prolog is Erlang. In particular, it has a nice interface to “guarded clauses”. I certainly wished that Prolog had a more intuitive / less error prone way to do “guards”.

(of course the usual disclaimer applies: I don’t really know what exactly you are looking for, and I suspect I don’t know what I’m talking about :wink: )

You could utilize your transformation, to turn a Prolog system
into a Delphi machine. See also:

PrologPF: Parallel Logic and Functions - Lewis, 1998
https://www.repository.cam.ac.uk/bitstream/handle/1810/221792/ian_lewis_prologpf_phd.pdf

You would not insert cuts, but transfer points. Quite beautiful
idea, except I wouldn’t call the parallel platform skynet.

Possibly you can do it also with shift/reset?

I am always amazed to learn what else there is out there Prolog land …

thank you for posting

Dan