I keep thinking that there should exist a “strict” or “pure” mode in swi prolog that limits or augments behavior to avoid such possibilities and flags issues.
For example, in pure mode a sort could be wrapped into a when clause to ensure clearer semantics – like, say, dif.
Dan
There are lots of predicates that don’t do the right thing when arguments aren’t sufficiently instantiated. For example memberchk(X, [1,2,3]), X=2 vs member(X, [1,2,3]), X=2.
A more pure form of Prolog is a Good Thing; but needs a lot of research to get right. And it’s not the only thing that can trip up programmers - left-recursion is another, even with tabling (Datalog handles this with “stratification”, but that’s insufficient for full Prolog).
thanks,
I think the least would be to include warnings in the documentation, that this is the case.
Also, why does memberchk behave this way. And, memberchk(X, [1,2,3]), X=1. Suceeds.
memberchk/2 is defined to test membership in a list; it is “semi-deterministic” which means it either succeeds once or fails.
So, memberchk(X, [1,2,3]) will succeed once, with X=1. If you then try the goal X=2, that will fail (because X=1) and memberchk/2 won’t give another result.
On the other hand, member/2 is non-deterministic, and can succeed multiple times – e.g., on backtracking, it would unify X with each member of the list.
If you look at the definition of member/2 vs memberchk/2, you’ll see that there’s a “cut” in memberchk/2 that’s missing from member/2. These predicates are builtin, but if they weren’t, they’d be defined something like this:
member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).
memberchk(X, [X|_]) :- !. % Prevents more than one solution!
memberchk(X, [_|Xs]) :- memberchk(X, Xs).
What this all means is that memberchk/2 should only be used when its first argument is sufficiently ground. It doesn’t have to be ground; for example, using memberchk to find an option in a list: memberchk(my_opt(X), [opt1(100), opt2(foo), my_opt(a_value), opt3(qqsv)]).
I guess, its the trade-off between performance and purity that plays here.
I guess two books need to be written:
Dan
If a fraction of the effort that’s been put into C++ compilers had been put into Prolog program analysis tools, there wouldn’t be a trade-off between pure Prolog and high-performance Prolog. 
Sometimes I feel like asking “but why?” helps. There are infinitely many lists that would “sort” to the same [1, 2]. They go something like this:
[1, 2]
[2, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
[1, 1, 1, 2]
...
I am sure there are uses for this (generate-and-test comes to mind) but what happens to the good old “here is a list of things, sort them”?
If you wanted a more pure sorting for integers, you could probably do your own merge sort using zcompare/3 from library(clpfd).
H Boris,
I think from a pure Prolog perspective, it is the simplicity and consistency of the language that matters. If the claim is that Prolog predicates are bi-directional, then there shouldn’t be surprises – at least not in the pure subset.
If there are surprises, then those predicates need to be flagged as “unpure” (analog to unsafe, unmanaged, etc. in other languages).
Dan
Sorting (and the underlying comparison to the standard order of terms) is indeed not “truly relational”. The scripture on the topic is very clear on this I guess.
I have some doubts about using such harsh language. “Pure” and “purity” throws my mind to things like “puritans”; “unpure” is I guess just “dirty” and this means something needs to be “cleansed”? and so on and so forth. I don’t want to continue with the things that pop up in my mind, it makes me somewhat uncomfortable.
Isn’t there an established term as “extra-logical”?
Yea, crossed my mind as well – but, then again Pure Prolog is a technical term, as far as i know.
Dan
Yes, it is a techical term and it has been in use for a long time. That doesn’t make it any better.
I strongly recommend the book “Pre-Suation” by Robert Cialdini. It is not about computer science or programming, it is about people (but it does review a lot of experimental research). And computer scientists and programmers are people so I think it has some relevance.
In the story I tell typically, there is a logical subset and a procedural one. The first you may call pure, but it seems I’m not the only one disliking this term. Prolog is based on the, from a logical viewpoint, rather native SLD resolution. SLD gives proper logical resolution for a rather small subset. Constraints and SLG extend this subset. SLD is also a bit limited procedural language. Cuts, ==/2, sort/2, and many many more extend this.
If you want pure declarative (logic) programming, go Datalog or ASP. Datalog handles a subset that is also covered by SLG as we find it in XSB and SWI-Prolog (several other Prolog systems do SLG, but without sound negation). ASP handles a much richer set of logic. Neither is Turing complete though, so if you want to make it do something you typically need to embed it in Lua/Python/Java/… Calling a non-Turing complete language Programming has always sounded a bit weird to me …
In my view, Prolog is an elegant sweet spot combining logical and procedural aspects. It doesn’t suffer from the mismatch you get combining databases, ASP or Datalog to (object oriented) procedural languages. The fact that the boundary is smooth but also fluid has both an advantage and disadvantage though. It makes the code more uniform, it allows for procedural tweaks while retaining logical correctness (and thus use your own knowledge to work around limitations any fully declarative language has) but it is also easy to cross the logic boundary while this was not intended, getting an incorrect result.
For short, Prolog is a versatile and pragmatic multi-paradigm language. This, in my view, has little to do with purity.
Hi Jan,
Thank you.
I think that having the different subsets made visible, such as via the language and compiler, or, perhaps just how the language is presented in documentation, could help create correct and elegant code.
Dan
Probably yes. It is a bit if a slippery path though. A program using no built-ins is pure. Some built-ins such as =/2 are also really pure. A much larger subset result in logically correct programs as long as you respect certain mode restrictions, which typically means you cannot arbitrary reorder subgoals. Doing so may result in (instantiation) errors as well as incorrect results. This, I guess, is one of the real disadvantages of Prolog: the language requires a fair deal of understanding on how the resolution works and how many built-in predicates interact with that. Some of this can probably be verified by tools or runtime checks. This is not my area of expertise, but I fear a lot cannot be automatically verified.
I think a (swish based) tutorial that illustrates this thinking would be very helpful.
A pure sort requires a pure comparison method, which can be done with compare2:
compare2(C, X, Y) :-
( X == Y
-> C = (=)
; C == (=)
-> X = Y
% Compare when safe
; when((ground(X), ground(Y)), compare(C, X, Y))
).