dif/2, an illustration
Chip Eastham
in 1981. His later work in constraint logic programming is well-
known, and prompted by Markus Triska's enthusiasm for using this as
introductory element of Prolog, I formulate the follow example both to
illustrate the benefits of dif/2 and to elevate discussion of whether
it should be taught as such or in the alternative as an introductory
element of constraint logic programming.
Consider a predicate permute/2 which is true of two (finite) lists
when one is a permutation of the other. A permutation in which no
item is left in its original location is called a _derangement_ (and
counting them is subject of a well-known recreational math problem
involving the hats/coats of drunken programmers/mathematicians leaving
a darkened cloak room):
["Let's get deranged!" by John C. Baez (Dec. 2003)]
http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf
There is a nice shortcut answer to counting these things, namely that
the number of derangements of N items is very nearly N! divided by the
base e of natural logarithms. Indeed the exact answer is rounding N!/
e to the nearest integer.
A Prolog program to find derangements might use a generate-and-test
approach, so for example taking N=5:
permute([1,2,3,4,5],[A,B,C,D,E]),
A \= 1,
B \= 2,
C \= 3,
D \= 4,
E \= 5.
This approach works, and for smallish N we might not be worried about
improvement, since the code clearly represents the meaning of
"derangement".
However for the sake of discussion suppose we are concerned that we
are generating all possible permutations and only finding after the
fact that a fraction of roughly 1/e of them satisfy the criteria for
derangments.
One possibility would be to open up the "gray box" of permute/2 and
modify its coding so that the restrictions on item locations are
imposed as they are bound. That should provide some "trimming of the
search tree" but at the expense of thinking about the code
modifications and retesting.
For those Prolog implementations which provide it, dif/2 allows the
"black box" of permute/2 to remain closed while getting the effect of
imposing location restrictions a priori like this:
dif(A,1),
dif(B,2),
dif(C,3),
dif(D,4),
dif(E,5),
permute([1,2,3,4,5],[A,B,C,D,E]).
The semantic equivalence with our first code fragment is clear, but
one expects an advantage in roaming the search tree because (for
example) we quickly avoid those permutations in which A = 1. Failure
of those branches is immediate, rather than being deferred as in the
original setup to a point after all the variables are bound.
But how can Prolog do this? This is beyond the ability of the pure
resolution algorithm or of resolution + negation-as-failure.
Admittedly this is something of an under-the-cover view of whether
something is "really Prolog" or not. As Markus points out, the syntax
of dif/2 (or diff/2 in some implementations) is quite comparable with
other elementary relations like =/2 (or \=/2).
I've somewhat telegraphed my own view above, but I invite others to
discuss...
regards, chip
Jan Burse
> But how can Prolog do this? This is beyond the ability of the pure
> resolution algorithm or of resolution + negation-as-failure.
Constraints can be very much be viewed as already part of resolution
algorithms. I think Alain Colmerauer should have shown this already
since when I remember well his Prolog II had a meta predicate
"geler", which translates to "freeze".
Such a meta predicate is able to instruct the interpreter to divert
from the usual greedy left to right SLD resolution algorithm, in that
goals are suspended. But suspended goals are nevertheless a valid
approach in a more general resolution framework. Its just the controlA
that is changed, but logic remains the same, to invoke an other
prominent figure and slogan at those times, namely Robert Kowalski
and his "algorithm = logic + control".
Pretty much can be done with suspended goals, and much of the usual
puzzle examples where the generate and test is inverted, work exactly
in this way. The test is put before the generate, and the test will
result in a set of suspended goals which are woken up during the
generate. Diff/2 is not exception, it can be dealt with in exactly
the same way than any other test.
But what can be done and is currently done, might not be the thing
than should be done and will be done in the future...
Best Regards
bart demoen
[...]
> I've somewhat telegraphed my own view above, but I invite others to
> discuss...
A discussion in three parts - first about the example at hand (I am sure
Chip realises what I am about to write, but I am also sure that most
people don't).
1. For this particular example, since the amount of filtered out
permutations is a constant fraction of the total amount (e-1/e) one
should not expect too much from any early filtering in terms of
efficiency. I have tried it (with freeze - in hProlog, SWI and
B-Prolog [the relative results are the relatively same]) and I get a
slowdown using freeze of about a factor 2, depending ... on the
version of permute used ! [dif/2 is not going to be essentially
faster than freeze/2: they use the same basic mechanism]
2. A version of permute ... euh ?
There are two reasonable versions of permute
perm1([],[]).
perm1([X|R],L) :-
perm1(R,RP),
ins(RP,X,L).
ins(L,X,[X|L]).
ins([Y|R],X,[Y|L]) :- ins(R,X,L).
and
perm2([],[]).
perm2(In,[X|R]) :-
In = [_|_], % you can leave this line out if you want
ins(In1,X,In),
perm2(In1,R).
perm2 is tail-recusive and perm1 is not.
But perm1 is about twice as fast [double excercise here: why and
when]. This might be counter-intuitive but so is life.
Now, if you start of with
perm1([1,2,3,4,5],[A,B,C,D,E]),
A \= 1, B \= 2, C \= 3, D \= 4, E \= 5.
and turn it into
dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
perm1([1,2,3,4,5],[A,B,C,D,E]).
it is about a factor 2 slower !
If you started off with the slower version
perm2([1,2,3,4,5],[A,B,C,D,E]),
A \= 1, B \= 2, C \= 3, D \= 4, E \= 5.
and turned it into
dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
perm2([1,2,3,4,5],[A,B,C,D,E]),
you will gain a factor of about 4.
It would be good if you can explain that for yourself :-)
And finally,
dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
perm2([1,2,3,4,5],[A,B,C,D,E]),
is about the same speed as
perm1([1,2,3,4,5],[A,B,C,D,E]),
A \= 1, B \= 2, C \= 3, D \= 4, E \= 5.
So, what is to be learned here: when combining constraints (like dif)
with regular predicates, be happy if you get a speedup (but you won't
know why most probably), and if you don't get a speedup, don't give up
on constraints to quickly, but you might have a good time thinking
what is happening :-)
> One possibility would be to open up the "gray box" of permute/2 and
In this particular case, that gains you a factor about 1.6 in SWI (and
a little less in hProlog/B-Prolog) - compared to the naive version.
3. [this is not directed at Chip]
If someone wants to learn Prolog, explain Prolog: Prolog is full of
things worth being understood.
Do not say "use dif/2 instead of \= /2'.
If OTOH you say "there is a nicer language than Prolog: it is named
CLP, and maybe some of its aspects will be part of Prolog some day; it
has dif/2 and that makes your life often easier and your programs more
declarative", that's absolutely fine ... but you have also to explain
the pitfalls (like the one above with permute) otherwise you are just
like a salesperson trying to make money.
Cheers
Bart Demoen
Jan Wielemaker
> On Wed, 30 Dec 2009 08:35:34 -0800, Chip Eastham wrote:
>
>> permute([1,2,3,4,5],[A,B,C,D,E]),
>> A \= 1,
>> B \= 2,
>> C \= 3,
>> D \= 4,
>> E \= 5.
<snip>
> 3. [this is not directed at Chip]
>
> If someone wants to learn Prolog, explain Prolog: Prolog is full of
> things worth being understood.
> Do not say "use dif/2 instead of \= /2'.
> If OTOH you say "there is a nicer language than Prolog: it is named
> CLP, and maybe some of its aspects will be part of Prolog some day; it
> has dif/2 and that makes your life often easier and your programs more
> declarative", that's absolutely fine ... but you have also to explain
> the pitfalls (like the one above with permute) otherwise you are just
> like a salesperson trying to make money.
Nice story. Only, this is a bit too long story to explain to beginners :-( I
guess there are two lines of thought that are -as far as I'm concerned-
equally defendable. One is to teach Prolog as a simple depth-first solver and
explain the pitfalls this creates and how to work around them. The other is
to introduce Prolog with a (small) number of simple constraints, just enough
to write meaningful programs without worrying about the plain-Prolog pitfalls.
This seems to be the line taken by Ulrich and Markus. I guess the best
approach depends a bit on your students and your goals.
Cheers --- Jan
bart demoen
> Nice story. Only, this is a bit too long story to explain to beginners
> :-( I guess there are two lines of thought that are -as far as I'm
> concerned- equally defendable. One is to teach Prolog as a simple
> depth-first solver and explain the pitfalls this creates and how to work
> around them. The other is to introduce Prolog with a (small) number of
> simple constraints, just enough to write meaningful programs without
> worrying about the plain-Prolog pitfalls. This seems to be the line
> taken by Ulrich and Markus. I guess the best approach depends a bit on
> your students and your goals.
The main thing I am arguing for is 'please do sell CLP as Prolog':
if someone's goal is to learn Prolog (asking Bratko details) respect
that.
Promoting CLP is fine, but can those people also please explain to beginners
explicitly things like
dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
perm2([1,2,3,4,5],[A,B,C,D,E]),
is fine, but
perm2([1,2,3,4,5],[A,B,C,D,E]),
dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
is not - at least not in the spirit of CLProgramming.
CLP is sold as more declarative, but if you don't order your goals properly,
you forfeit one of its two benefits.
Happy New Year to All,
Bart Demoen
Jan Wielemaker
> On Thu, 31 Dec 2009 10:50:09 +0000, Jan Wielemaker wrote:
>
>
>> Nice story. Only, this is a bit too long story to explain to beginners
>> :-( I guess there are two lines of thought that are -as far as I'm
>> concerned- equally defendable. One is to teach Prolog as a simple
>> depth-first solver and explain the pitfalls this creates and how to work
>> around them. The other is to introduce Prolog with a (small) number of
>> simple constraints, just enough to write meaningful programs without
>> worrying about the plain-Prolog pitfalls. This seems to be the line
>> taken by Ulrich and Markus. I guess the best approach depends a bit on
>> your students and your goals.
>
> The main thing I am arguing for is 'please do sell CLP as Prolog':
> if someone's goal is to learn Prolog (asking Bratko details) respect
> that.
But, who's goal is it `to learn Prolog'? I think more common goals are `to
learn (the) logic programming (paradigm)' or `how do I write/extend/... my app
X in Prolog Y'. Here, we must recognise that (almost?) all actively developed
and used Prolog implementations provide at least some constraints.
The name `Prolog' is simply very misleading. Does it refer to the ISO
standard? Does it refer to shared properties of a collection of
implementations (sort of `Dow Jones index' :-). To me, the latter makes more
sense, which implies that freeze/2 and dif/2 can be considered `Prolog'.
> Promoting CLP is fine, but can those people also please explain to beginners
> explicitly things like
>
> dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
> perm2([1,2,3,4,5],[A,B,C,D,E]),
>
> is fine, but
>
> perm2([1,2,3,4,5],[A,B,C,D,E]),
> dif(A,1), dif(B,2), dif(C,3), dif(D,4), dif(E,5),
>
> is not - at least not in the spirit of CLProgramming.
Well, it works. So, for a real beginner there is nothing to worry about.
Better, optimization can make them equally good, either by reordering or by
deciding that the arguments to diff are always ground and therefore dif/2 ==
(\=)/2 == (\==)/2 (and thus use the last one).
> CLP is sold as more declarative, but if you don't order your goals properly,
> you forfeit one of its two benefits.
That's only 50% :-)
Note that I'm not really a CLP-fan as you probably know. Recently I used
dif/2 to do exactly what Chip was arguing: I had a nicely defined
non-determinisitc API, but testing at the end was pretty inefficient and
breaking up the API in smaller chunks was not elegant. Putting a dif/2 before
it was efficient and clean. I've tried using coroutining for making joins of
rdf/3 statements efficient by delaying highly non-deterministic calls, waiting
for better times. This worked to some extend, but proper join-optimization
over a conjunction of rdf/3 statements and conditions showed much larger
speedups. One of the reasons is that some joins are optimal if you run a goal
with many solutions first because the rest becomes so simple due to the
bindings created by this goal.
Cheers --- Jan
Ulrich Neumerkel
>The predicate dif/2 was proposed in A. Colmerauer's Prolog II language
dif/2 was already part of the very first Prolog implementation
in Algol W - sometimes called Prolog 0. That is 1971.
The big fall of Prolog was the next implementation in Fortran, which
did not include dif/2 - but which was then taken to Edimburg and
effectively became the basis for the standard. This reduced Prolog
allowed implementers to produce efficient implementations rapidly,
which certainly helped to increase Prolog's acceptance - but at the
price of incorrect programs.
The reintroduction of dif/2 into Prolog started about 1980 with Prolog
II and independently with MU-Prolog and others. In the meantime
almost all Prologs have it.
You can approximate it safely within strict ISO Prolog:
dif(X, Y) :-
( X == Y -> fail
; X \= Y -> true
; throw(error(instantiation_error, _))
).
What is still missing are efficient implementations of the related
indexing mechanisms. So far, I have not seen any system that does
indexing for dif/2. But then, this is an implementation issue.
> .... His later work in constraint logic programming is well-
>known, and prompted by Markus Triska's enthusiasm for using this as
>introductory element of Prolog, I formulate the follow example both to
>illustrate the benefits of dif/2 and to elevate discussion of whether
>it should be taught as such or in the alternative as an introductory
>element of constraint logic programming.
Using (==)/2 or (\=)/2 in an introductory course makes it very
difficult for students to see through all those procedural details the
beauty behind.
Even with dif/2 procedural aspects like termination must be
understood. But at least no correctness issues come up. With tools
like cTI, understanding termination can be somewhat supported.
http://www.complang.tuwien.ac.at/cti
Happy newyear!