Series of "procedural" predicates -- removing choice points

Help!
1

Hi,

I have predicates, that are basically procedural code, such as when asserting new facts, and all the checks that need to be done before hand, where i don’t want to see choice points. To ensure that I now use once/1 extensively, but I am wondering if there is a better approach,

Any thoughts are much appreciated.

For example,

a1 (Return) :-
once(p1), % precondition p1
once(p2), % precondition p2
once(p3),
…
once(pn),
Return = ok.

a1(Error) :-
not(p1),
Error = “p1 failed”.

a1(Error) :-
not(p2),
Error = “p2 failed”.

is there a better way to avoid all the many once/1

2

http://www.swi-prolog.org/pack/list?p=rdet

but you have to declare each predicate, so there’s a certain amount of extra boilerplate.

Anyway, using this package, your code would become

:- use_module(library(rdet)).
:- rdet(p1/0).
:- rdet(p1/0).
:- rdet(p2/0).
   ...
:- rdet(pn/0).

a1 :-
  p1,
  p2,
     ...
  pn.

and an error will be thrown (which you could catch, of course) if any of p1, p2n, … pn fails – the deterministic goal p1 is expanded to something like

( p1 -> true ; throw(error(goal/failed(p1/0, user:5)))

I use rdet quite a bit and it’s been very useful in catching errors where predicates that should be deterministic aren’t (about 90% of my code is deterministic, and without a tool like rdet, it can be quite tiresome to track down unexpected failures. (I have one weird situation where rdet’s failure handling interacts with backtrace to go into an infinite loop; I haven’t figured out the root cause but there is a work-around.)

If you don’t like this, you can define your own must_once predicate, e.g.:

must_once(Goal) :-
(  call(Goal)
-> true
;  throw(error(must_once_failed(Goal), _))
).

must_once_msg(Goal, Msg, MsgArgs) :-
(  call(Goal)
-> true
;  functor(Goal, Pred, Arity),
   format(string(MsgStr), Msg, MsgArgs),
   throw(error(must_once_failed(Goal), context(Pred/Arity, MsgStr)))
).
3

Great. Thank you.

Too bad that failure raises an exception – to handle this i will need to wrap things – as you mentioned …

Dan

4

As is, rdet seems a non failure check. A determinism check is a little harder, but quite doable. You have the wrap your code like this:

t(G) :-
    (   call_cleanup(G, Det=true),
        (   Det == true
        ->  true
        ;   throw(error(multi(G), _))
        )
    ->  true
    ;   throw(error(failed(G), _))
    ).

See https://swish.swi-prolog.org/p/RLZCwtkJ.swinb

Of course, the overhead will be a lot larger. Typically you see non-determinism while debugging on the terminal. If you encounter it you run the graphical tracer, jump (skip) over the goal and inspect the open choices that are visible in the top-right panel of the tracer.

P.s. There is also a more efficient but non-portable solution to check non-determinism. See the predicate deterministic/1.

P.s. Please indent code blocks or put a line with ``` above and below.

5

This is just my opinion, but using once/1 to wrap code you wrote is somewhat similar to saying “I give up”.

If you don’t want a choice point, write your code so that it doesn’t have choice points. There are endless tricks, depending on the specific case, on how to either a) not create choice points or b) get rid of unnecessary choice points at the right spot. The right spot might be in the client code, or might be in the predicate definition.

Unwanted or unexpected non-determinism, in my limited experience, is the single most annoying weakness of Prolog as a general-purpose programming language. This isn’t surprising: non-determinism is one of the most powerful tools that Prolog has to offer. If you think that your code is or should be deterministic and it isn’t, consider this a bug. You might remember to use once/1 once, but next time you’ll forget, you might backtrack into a non-deterministic predicate, and at that point, you don’t any more understand what your program is really doing. This kind of stuff makes me nervous :slight_smile:

So, to wrap this up, I would recommend the following approach:

  • if you think that code should deterministic, make sure it is;
  • if you expect something to be deterministic but isn’t, fix your code;
  • use -> or once/1 or cuts to get rid of choice points if you are using other people’s (purposefully) non-deterministic code and you have made sure that you are not introducing errors by doing so;
  • during development (at least), use what Jan showed so that you catch your errors.

I hope this makes sense. I am writing it in the hope that you find it helpful.

1 Like
6

Hi Boris,

Thank you for your comments.

I very much value these kind of discussions, since they help improve my programming overall with deeper insights.

Can you provide some examples in Prolog, how you write the code without choice points – or do you mean that such code should not be written in prolog in the first place, but be moved to a client written in a procedural language.

Personally, i prefer to stay within Prolog as much as possible.

any further thoughts are much appreciated,

Dan

7

If you want to learn about good and efficient coding in Prolog, Richard O’Keefs The Craft of Prolog is probably still the best start. It is dated in the sense that it only covers classical Prolog, but it does explain choosing data structures, when (not) to use cuts, etc.

8

Eliminating unexpected/unwanted non-determinism can be key for good performance. Sometimes the code can be easily rewritten to take advantage of first-argument indexing, eliminating the spurious choice-points, without being forced to use non-logical features such as cut and if-then-else constructs. But hard to give concrete advice without actual code being posted.

For actually detecting unexpected non-determinism, the top-level is of limited use. An application may be wasting time doing useless backtracking and a cut later on the computation can hide the problem. Tools, as Jan mentioned, can help expose these problems. Debuggers are useful here when they show that there’s a choice-point at an exit port. Another option, is a ports profiler tool, which allows a postmortem analysis of a query. As an example, with the ports_propfiler Logtalk tool, I can do:

% run a query:

| ?- miss_cann::initial_state(Initial), hill_climbing(16)::solve(miss_cann, Initial, Path, Cost), miss_cann::print_path(Path).
...


% print the collected profiling data:

| ?- ports_profiler::data.

-------------------------------------------------------------------------------------
Entity              Predicate          Fact  Rule  Call  Exit *Exit  Fail  Redo Error
-------------------------------------------------------------------------------------
miss_cann           goal_state/2          1     0    13     1     0    12     0     0
miss_cann           heuristic/2           0    15    15    15     0     0     0     0
miss_cann           initial_state/2       1     0     1     1     0     0     0     0
miss_cann           next_state/3          0    66    18     0    38    18    38     0
miss_cann           print_state/1         0    12    12    12     0     0     0     0
state_space         goal_state/1          0    13    13     1     0    12     0     0
state_space         initial_state/1       0     1     1     1     0     0     0     0
state_space         member_path/2         0   103   118    22     0    96     0     0
state_space         print_path/1          1    12    13    13     0     0     0     0
heuristic_search/1  solve/4               0     1     1     0     1     0     0     0
heuristic_search/1  threshold/1           0     1     1     1     0     0     0     0
hill_climbing/1     hill/7                0    25    13     0    12     1     0     0
hill_climbing/1     search/5              0     1     1     0     1     0     0     0
-------------------------------------------------------------------------------------

In a similar way to command-line debugger, the *Exit column show exists with open choice-points (Fact and Rule are unification ports). But the other columns also provide useful information. From the tool documentation:

  • which predicates are called more often (from the call port)
  • unexpected failures (from the fail port)
  • unwanted non-determinism (from the *exit port)
  • performance issues due to backtracking (from the *exit and redo ports)
  • predicates acting like a generator of possible solutions (from the *exit and redo ports)
  • inefficient indexing of predicate clauses (from the fact, rule, and call ports)

For more information, see https://logtalk.org/tools.html#ports-profiler

Cheers,
Paulo

1 Like
9

Thank you.

Sometimes the code can be easily rewritten to take advantage of first-argument indexing, eliminating the spurious choice-points, without being forced to use non-logical features such as cut and if-then-else constructs.

Could you provide a didactic example for a rewrite … (in Prolog :-))

thanks,

Dan

10

This is a recurrent topic in StackOverflow questions and answers. A couple of recent examples where I explain it:

Try the search https://stackoverflow.com/search?q=prolog+determinism for more related questions.

Cheers,
Paulo

1 Like
11

Repeating what Paulo said:

It is much easier to comment on a specific example. As I said above, there are countless ways to avoid choice points.

Peter already showed how to make your log_file/1 deterministic.

Paulo mentioned first argument indexing.

First argument indexing comes in many forms. You can do it for lists ([] vs. [H|T]), you can do it for DCGs (by consuming a token and using it as the first argument), and so on.

If can replace arithmetic comparison with compare/3 (in some cases…)

and so on, and so on.

12

I second the book recommendation. With one disclaimer, I bought it and “read” it, then used Prolog for about two years, then I read it again and was actually able to understand what on earth the author is talking about.

2 Likes
13

One particular relevant section on the ROK book to this discussion thread describes how to avoid catchall clauses, which usually result lost or weak first-argument indexing and in repeated creation of choice-points just to cut them.

14

if i do systematically wrap predicates with once/1 in the code – would this lead to performance improvements – in case it does avoid un-needed backtracking?

It seems that this would at this stage be the simplest solution for me. Followed by understanding in depth how to rearrange recursive calls to minimize and/or avoid choice points, and make better use of indexing.

thank you,

Dan

15

It would lead to really ugly code. Whether and how much faster it is depends on the level of non-determinism and how quickly that is pruned.

The result are quite simple:

  • If possible, let clause indexing do the job. That means getting an instantiated first argument (good practice is to but instantiated inputs before outputs) and make sure each clause has a different value for that argument.
  • If the above doesn’t do the job, each clause is of the shape
head :-
    <guard>,
    !,
    <deterministic actions>

Where <guard> are goals that select the right clause (may be empty).

16

Hi Jan,

* If possible, let clause indexing do the job. That means getting an instantiated first argument (good practice is to but instantiated inputs before outputs ) and make sure each clause has a different value for that argument.

Could you rephrase that – i can’t parse the sentence …

thank you,

Dan

17

btw, in some of my code i am carrying along assocs – i happen to structure it as follows:

I am not using DCG because i like the oversight i have over the threaded argument …

it looks like this …

action_x(Assoc1, Arg1, Arg2, Assoc2) :-

The Assoc can become quite large – i guess having it as first argument is then a bad idea … better to both Assocs at the end

18

The two links to Stackoverflow answers that Paulo shared above show exactly what Jan is saying, for lists. The first argument in that case are the empty list [] or the non-empty list [_|_]. Read the code.

Another example, this time using compare/3, is in library(ordsets). There, the helper predicate has the “instantiated first argument”.

19

(Apparently, Discourse is clever enough to embed code from github but not clever enough to keep the indentation)

20

ok, great. i see.

So, is it bad practice to have the threaded Assoc argument as a first argument …better to move the threaded arguments to the end of the argument list …

I now notice that in the Assoc library its indeed the key that is in the first argument position:

       **put_assoc** (+Key, +Assoc0, +Value, -Assoc)

Dan