Re: [eclipse-clp-users] compiler leaves spurious choice points

On 19/01/2011 15:10, Ulrich Scholz wrote:
> t2(T1, _T2) :-
>      free(T1),
>      !,
>      writeln(a).
>
> t2(_T1, T2) :-
>      T2 \== [],
>      writeln(b).
>
> t2(_T1, []) :-
>      writeln(c).

Hi Ulrich,

The general question you seem to be asking is:

"Is it possible to ensure that, if only one clause of a predicate
will lead to success for a given call, we will always commit to that 
clause without creating a choice-point?"

The short answer is: no, because it is impossible for the system to 
anticipate all possibilities of failures in the other clauses.

The selection of clauses to try to reduce the number of choicescan be 
done by indexing, and in general indexing is done by a combination
of the Prolog engine (the abstract machine in systems such as ECLiPSe)
providing the needed infra-structure, and the compiler recognising and 
generating code that will take advantage of the infra-structure.

How to do indexing have been an active research area in Prolog, and 
there are many issues to consider. There is a lot of trade-off in doing 
indexing: the more indexing you do, the more complicated your support 
machinery and compiler analysis need to be, and you also need to 
consider that at some point the execution can be spending more resources 
doing the indexing that what the indexing will buy you.
[also, the more complex the code for the compiler/abstract machine, the 
more time is required for the development of the system, and the harder 
it is to maintain].

For ECLiPSe, indexing is done for one argument, and the indexing itself 
is relatively simple (e.g. type testing, plus other simple tests). In 
your specific example with two arguments, there is a choice of indexing 
on the first or second argument, and indexing is done for the first 
argument in the generated code, so that's why you see the choice-point.

You can't do any indexing on the second argument on its own. To avoid 
allocating the choice-point with your code, the compiler need to support 
indexing on multiple arguments, so that an additional type testing is 
done for the second argument. The ECLiPSe compiler does not do this. 
Doing this will make the compiler more complex: for just some indication 
of the additional issues this will involve: do you do the indexing for 
the first or second argument first, or do you design some additional 
machinery that will somehow do the indexing for both arguments together? 
[and in that case, how many arguments do you combine in this way]

[For the record: "standard" indexing in Prolog (as defined in the 
original WAM) is for the first argument only; ECLiPSe extends this to 
other arguments (but not together). There are some Prolog systems which 
do multiple argument indexing, and there have been research into doing 
more sophisticated compile-time analysis, but I don't know how much of 
this work have made it into the popular Prolog systems]

 > Is there any way to prevent this?  It is somewhat distracting during 
 > tracing and bug fixing.

The standard way to avoid such choice-points is to add additional cuts. 
For your code:

t2(_T1, T2) :-
     T2 \== [], !,
     writeln(b).
t2(_T1, T2) :-
     T2 == [],
     writeln(c).


[I have changed your code to make the cut "safe", I am assuming this is
the intention of your original code, i.e. that clauses 2 and 3 are truly 
mutually exclusive (previously, the clauses were not mutually exclusive 
if T2 is called as a variable)]

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.