That is correct
Yes, this is good advice.
Actually, in section 3.7 of the craft of prolog there is a âflowâ chart of this. Perhaps, after such an exercise, i will start to understand (portions of) it.
Dan
Hi Jan,
But doesnât that little bit add up âŚ
A choice point is created and removed for every call in the program â and prolog program are to the most extent calls. Choice points are short lived â but its there.
The rationale, say, for inlining (say, in C or C++) is to reduce call overhead in critical areas; perhaps some âinliningâ capabilities makes sense here as well
Dan
A choice point is created within the called predicate, and only if needed.
See page 51 in
http://wambook.sourceforge.net/wam-slides.pdf
(I might be wrong. Itâs been over 30 years since Iâve worked on Prolog internals.)
There are two costs to creating a choice point:
- The actual cost of creating (and deleting) it, which is minimal.
- A choice point can force new allocations onto the heap rather than the regular stack, so memory use increases and more work is needed when returning from a call.
1 Like
Thank you.
That is very helpful.
So, if i have something like this:
g1(X) :-
g2(X) :-
gn(X) :-
ground(X),
g1(X),
g2(X).
Then for g1(X) and g2(X) there is creation of choice point â it would compile and execute quite like calls to functions in procedural languages (say, C).
The bottom line isnât that hard. If a goal is started it will first use its clause indexing logic (which is implementation defined) to find applicable clauses. If there is only one, just start this clause. If there are more than one, create a choice point and start the first. As also pointed out by Peter, if you kill this quickly, notably before starting the last call of the selected clause, the price is low. If you donât and you do deep non-deterministic recursion the price gets high because last-call optimization does not apply and a lot of data remains accessible. The latter seriously degrades GC performance.
1 Like
Thanks.
I think what is important to me here, is that in language such as C there doesnât exist a âsecondâ clause with the same functor, that would be called, upon failure of a first clause.
Hence, no choice points.
While this is obvious, it sort of remained implicit knowledge for me 
What i am now wondering about is code like this:
is_known(a).
is_known(b).
goal(X, Y) :-
var(X),
is_known(X),
do_something(X, Y).
vs.
goal(X, Y) :-
ground(X),
is_known(X),
do_something(X, Y).
Would the ground(X) cause (or make clear) the subsequent call is_known(X) to not generate a choice point?
I.e. is the generation of choice points something that occurs during compile time, or during runtime?
Dan
This might help you
Prolog - Explain trace steps in English
See my accepted answer which explains the creation of choice points in the trace output.
Hi Eric,
Thank you.
What i am wondering about is whether the determination of whether choice points need to be generated is a compile time or a runtime mechanism â or a bit of both.
If there is no second clause, then its clear during compile time that no choice point is needed, so none needs to be created.
If there is a second clause, yet the call is using a bound, ground, variable; then this can only be determined during runtime â unless there is ground(X) guard.
Dan
I am not an expert on this so if I make a mistake here hopefully someone here will correct me.
They are created at run time and live on the stack, See Limits on memory areas which notes the local stack (also called environment stack) stores the environment frames used to call predicates as well as choice points. When a search for a matching clause is done, if more than one matching clause is found then a choice-point is created for next clause (or maybe all the choices, not sure) and the first clause is executed.
If a choice point is executed and fails and there is another choice point then that choice point is executed. This continues until there are no more choice points.
If a choice point is executed and succeeds and there are other choice-points created at that time then those choice-points remain on the stack. (This is disregarding the use of cuts (!) (link) and conditionals (->) (link) an other such syntax that modifies choice-points.
As each choice-point is executed, it is removed from the stack.
Thatâs basically it.
Like I noted before the best way I found to learn how they work was to write a basic Prolog interpreter. See earlier post in this topic.
Another more specific, harder and costly way is to read the ISO specification.
Each line is a separate query. so preceding lines do not effect the creation of choice-points on another line (This is excluding the use of assert or retract and such that dynamically adds or removes clauses). If a preceding lines fails then the next line is not executed and backtracking takes place, if the preceding line succeeds then the next line is executed. (This is ignoring conditionals like â ; and such).
If you look at the Warren Abstract Machine description, youâll see that there are three kinds of instructions that deal with choice points:
- try, try_me_else
- retry, retry_me_else
- trust, trust_me_else_fail
plus switch_on_{term, constant, structure}.
Each clause is preceded by a
try_me_else,retry_me_else, ortrust_me_else, depending on whether it is the first, an intermediate, or the last clause in the procedure [sic]. These instructions are executed only in the case thatA1dereferences to a variable and all clauses have to be tried for a match.
SWI-Prolog uses something a bit different (and has more ways of being deterministic), but the basic principles apply. Essentially, there are separate generated byte-code paths for the case where the register has a variable and requires a choice point, or where the register has something that is sufficiently instantiated to allow determinism and requires no choice point.
See also pp 40 et seq of http://wambook.sourceforge.net/wambook.pdf
Thank you â that is helpful.
Its great if swi-prolog could continue to be optimized when it comes to determinism â and enable compiler hints that can optimize in this direction â such as analyze branches that must be bound due to guards, and hence can be âtrustedâ to not need backtracking â as i have mentioned.
In addition, it would be great if there were data structure libraries that are âlookupâ efficient, such as real linked lists and enable structures that have memory locality.
I feel that even indexed lookup is for some usages still a significant overhead.
I am dreaming of a swi-prolog for system programming
I think that is where Mercury is heading â but, currently, swi-prolog is so much more developed in terms of ecosystem that Mercury is, at least for me, not a choice for production code.
Dan
For deterministic code such as C I would agree that optimizing early is not a good rule of thumb, but for Prolog with non-determinism a few missing cuts can turn something that should run in minutes in to several hours or more. Just spending a few minutes to find those places that can benefit from a cut, a guard or conditional and shave minutes off the run time is worth the time to seek them out.
Some may see that as good Prolog coding and not an optimization, but it should be made clear what is an optimization and what is good Prolog coding. 
Getting determinism right isnât an optimization ⌠itâs a way of making sure my code is correct. If code that should be deterministic backtracks, it can generate wrong results or go into an infinite loop. Itâs a nice bonus that correct code runs faster.
1 Like
SWI-Prolog splits VM code into two parts: code for the clauses and code for what is called the supervisor, which is the code associated with the predicate. The latter is generated on the fly on the first call and analyses the predicate to realize clause indexing and other stuff such as thread-local, foreign, meta-predicates and -last version- wrapping the predicate.
At the moment, SWI-Prologâs indexing is good at a few specialized cases (no clause, one clause, two clauses with [] and [_|_] and a couple of clauses with unique first arguments. It is also pretty good in the other extreme: many many clauses that can be indexed using hashes on one argument, two combined arguments or using deep indexing to look into compound terms.
It isnât much good at all other cases, notably say up to 20 clauses where a smart choice strategy can quickly find the one and only clause that applies. The design should make it quite easy to add this though.
1 Like
With regards to deterministic code and in particular implementing something like a switch statement in other languages, here is one of the best examples in the SWI-Prolog code I have seen that simply and clearly demonstrates such.
From: iostream.pl
open_any(Spec, Mode, Stream, Close, Options) :-
\+ ( ground(Spec), % argument sanity check
var(Stream),
var(Close),
is_list(Options) ),
!,
open_error(Spec, Mode, Stream, Close, Options).
open_any(Spec, _Mode, Stream, Close, Options) :-
is_stream(Spec),
!,
Stream = Spec,
input_options(Spec, Stream, true, Close, Options).
:- if(current_predicate(uri_file_name/2)).
open_any(Spec, Mode, Stream, Close, Options0) :-
atomic(Spec),
uri_file_name(Spec, File),
!,
open_any_builtin(file(File), Mode, Stream0, Close0, Options0, Options),
input_options(Stream0, Stream, Close0, Close, Options).
:- endif.
open_any(Spec, Mode, Stream, Close, Options0) :-
open_any_builtin(Spec, Mode, Stream0, Close0, Options0, Options),
!,
input_options(Stream0, Stream, Close0, Close, Options).
open_any(Spec, Mode, Stream, Close, Options0) :-
open_hook(Spec, Mode, Stream0, Close0, Options0, Options),
!,
input_options(Stream0, Stream, Close0, Close, Options).
open_any(Spec, Mode, Stream, Close, Options0) :-
open_any_builtin(file(Spec), Mode, Stream0, Close0, Options0, Options),
input_options(Stream0, Stream, Close0, Close, Options).
open_error(Spec, _Mode, _Stream, _Close, _Options) :-
var(Spec), !, instantiation_error(Spec).
open_error(_Spec, _Mode, Stream, _Close, _Options) :-
nonvar(Stream),
!,
uninstantiation_error(Stream).
open_error(_Spec, _Mode, _Stream, Close, _Options) :-
nonvar(Close),
!,
uninstantiation_error(Close).
open_error(_Spec, _Mode, _Stream, _Close, Options) :-
\+ is_list(Options),
!,
must_be(list, Options).
The part that I find the most interesting is that the first clause is designed to sanity check the arguments up front versus letting all the errors fall through to the last clause and is implemented using
predicate(<arguments>) :-
\+ (<guard statements on arguments>),
!,
<handle erroneous arguments>.
I know much of my older code would redo some of the same argument sanity checks in each clause, but this is clearly better.
You can also have as first clause something like:
open_any(Spec, Mode, Stream, Close, Options) :-
% argument sanity check
must_be(ground, Spec),
must_be(var, Stream),
must_be(var, Close),
must_be(list, Options),
fail.
In this case, you no longer need the open_error/5 predicate. The downside is that calling open_any/5 will create a choice-point. But the choice-point will also be discarded without requiring any action from the caller.