Site Map
Download(c) 2005-2025 XLOG Technologies AG
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Example 31</title>
<link rel="stylesheet" href="../style.css" type="text/css">
</head>
<!-- Modern Albufeira Prolog Interpreter -->
<!-- Prolog sandbox -->
<!-- -->
<!-- Warranty & Liability -->
<!-- To the extent permitted by applicable law and unless explicitly -->
<!-- otherwise agreed upon, XLOG Technologies AG makes no warranties -->
<!-- regarding the provided information. XLOG Technologies AG assumes -->
<!-- no liability that any problems might be solved with the information -->
<!-- provided by XLOG Technologies AG. -->
<!-- -->
<!-- Rights & License -->
<!-- All industrial property rights regarding the information - copyright -->
<!-- and patent rights in particular - are the sole property of XLOG -->
<!-- Technologies AG. If the company was not the originator of some -->
<!-- excerpts, XLOG Technologies AG has at least obtained the right to -->
<!-- reproduce, change and translate the information. -->
<!-- -->
<!-- Reproduction is restricted to the whole unaltered document. -->
<!-- Reproduction of the information is only allowed for non-commercial -->
<!-- uses. Selling, giving away or letting of the execution of the -->
<!-- library is prohibited. The library can be distributed as part of -->
<!-- your applications and libraries for execution provided this comment -->
<!-- remains unchanged. -->
<!-- -->
<!-- Restrictions -->
<!-- Only to be distributed with programs that add significant and primary -->
<!-- functionality to the library. Not to be distributed with additional -->
<!-- software intended to replace any components of the library. -->
<!-- -->
<!-- Trademarks -->
<!-- Jekejeke is a registered trademark of XLOG Technologies AG. -->
<body>
<h1>Example 31: Railgun Solver</h1>
<h2>Introduction</h2>
<p>Many existing and evolving constraint logic programming projects
resemble some ancient invention of gunpowder. For example SWI-Prologs 9.3.35
corouting for delayed goals is mainly based on unify hooks. We show
how verify hooks, already used in formerly Jekejeke Prolog, can be
braught to Dogelog Player in a 100% Prolog fashion.</p>
<p>The experimental library(edge/railgun) makes use of cyclic terms
to model delayed goals. One may ask how on earth cyclic terms aka
rational trees enter the picture? We observation the delay of a goal
G(X) on a variable X, creates a circular dependency, if we model
attributed variables as carrying the future value and the delayed goal:</p>
<pre class="code">
:- ensure_loaded(library(edge/railgun)).
?- freeze(X, (deref(X,Y), write(Y), nl)), bind(X, hello).
</pre>
<p>In the above we see the cyclic dependency along the attributed
variable modelled by a compound '$ATTR'/2. To access and modify such
attributed variables we have introduced the utility predicates deref/2 and
bind/2 which are usually not needed in a constraint logic programming
implementation. On the other hand we see a familiar freeze/2.</p>
<pre class="code">
?- dif(X,Y), indomain(X, [1,2,3]), indomain(Y, [1,2,3]),
deref(X,A), deref(Y,B).
</pre>
<p>Rational trees were introduced by Alain Colmerauer in early 80's
with Prolog II. In the above we see the famous dif/2 predicate,
which was also already introduced by Alain Colmerauer at the same
time. Our implentation is a stripped down version for atomic values
that is closer to (#\=)/2 together with a backtracking binder indomain/2.</p>
<p>It should be noted that we do not implement the full constraint
logic programming schema. For example the bind/2 predicate is not able
to alias variables. Corresponding extensions are possible up to the
provision of a unify/2 predicate, which can then be useful for automated
theorem proving, whereas we aim more at combinatorial search.</p>
<h2>Number Permutations</h2>
<p>Constraint solving utilities can be separated into predicates
to setup a constraint model and into predicates to solve a constraint
model. In both cases the constraint model is the same emergent structure
of attributed variables, which does not only define the constraint store
of delayed goals, but also the wakeup dependencies.</p>
<p>Among constraint solving utilities we find in our new
library(edge/railgun) for example the predicate all_different/1
which allows to establish a constraint of differing variables, and
the predicate label/2 which backtracks over a set of variables. In
as far the constraint solving is quite open ended, people regularly
invent and study new such predicates:</p>
<pre class="raw">
/* The predicate delays that all elements of L are different. */
all_different([]).
all_different([X|L]) :-
maplist(dif(X), L),
all_different(L).
/* The predicate binds the elements of L, left to right. */
label([], _).
label([X|L], D) :-
indomain(X, D),
label(L, D).
</pre>
<p>To demonstrate both predicates we generate permutations:</p>
<pre class="code">
test(X) :-
length(L, 3),
all_different(L),
label(L, [1,2,3]),
maplist(deref, L, X).
?- test(X).
</pre>
<h2>Map Coloring</h2>
<p>A popular problem for constraint solving is map coloring. The coloring
appartness between bordering regions is easily represented by a dif/2
constraint. That four colors are enough for a planar problem, was suggested
by Francis Guthrie, while trying to color the map of counties of England:</p>
<pre class="code">
:- ensure_loaded(library(misc/aggregate)).
plane(L) :-
L = [A,B,C,D,E,F],
dif(A, B), dif(A, C), dif(A, D), dif(A, E),
dif(B, C), dif(B, D), dif(B, F),
dif(C, D),
dif(D, E), dif(D, F),
dif(E, F),
label(L, [1,2,3,4]).
?- aggregate_all(count, plane(_), C).
</pre>
<p>We can use exhaustive permutation of [1,2,3,4,5,6,7,8,9] for a first
benchmarking of our new library(edge/railgun) against other contstraint
solving systems, that usually also provide all_different/1 and label/2.
We include in our testing the 10000x times iterating the map coloring and
the Trealla Prolog 2.86.3 system. We leave both Prolog systems behind:</p>
<center><img src="image001.png" width="480" height="289"></center>
<p>It should be mentioned that Dogelog Players 2.1.4 performance is mainly
due to the use of a special built-in '$SEQ'/2, already introduced in version
0.9.0 of Dogelog Player, that allows to put a list of goals on the continuation
in one shot. This is ideal for backtracking problems. But the library could
be also implemented with call/1 and thus ISO core standard Prolog only.</p>
<h2>Conclusions</h2>
<p>t.b.d.</p>
<script type="module">
import {notebook_async
} from "../../../../dogelog/player/canned/dogelog.mjs";
await notebook_async();
</script>
</body>
</html>