Where in the swi-prolog code is the need for the creation of choice points checked

I am looking to identify in the code where after a call of goal and before the execution of the goal, swi-prolog checks if choice points need to be generated.

It was suggested that it might be within i_enter in vmi.c, but i can’t see this relevaled in the code itself, so it seems that whether to create choice points has already been performed.

Edit:

Seems to be somewhere in pl_wam.c

VMI(I_ENTER, VIF_BREAK, 0, ())
{ ARGP = argFrameP(lTop, 0);

  if ( unlikely(LD->alerted) )
  {
#if O_DEBUGGER
    if ( debugstatus.debugging )
    { int action;

      SAVE_REGISTERS(qid);
      clearUninitialisedVarsFrame(FR, PC);
      action = tracePort(FR, BFR, UNIFY_PORT, PC PASS_LD);
      LOAD_REGISTERS(qid);

      switch( action )
      { case ACTION_RETRY:
	  goto retry;
	case ACTION_FAIL:
	  FRAME_FAILED;
	case ACTION_ABORT:
	  THROW_EXCEPTION;
      }
    }
#endif /*O_DEBUGGER*/

    CHECK_WAKEUP;
  }
  NEXT_INSTRUCTION;
}

($)/0 is not implemented at i_enter. It doesn’t check the choice point that belongs to the current clause. It checks whether goals in the body leave some choice point. This is check in i_exit. Basically ($)/0 sets a flag, so that i_exit performas an additional check.

So, the check whether to create a choice point is entirely within VMI instructions – they (the generated VI instructions) take care of it rather than the VMI execution engine within pl_wam.c?

Edit:

There is some reference back: via the defined TRY_CLAUSE macro – hmm …

Why is ($)/0 does not check the choice point that belongs to the current clause. Well the choice point of the current clause is anyway cut away by the (=>)/2. Just recall that (=>)/2 has a cut:

The (=>)/2 removes choice point from the current clause. Since (=>)/2 has implicitly a cut. But then the Body can still created choice points. ($)/0 prepares the clause so that an additional check is performed when the clause is “Exit”-ed. To see whether Body created some choicepoints.

When I realized that, i was initially quite disappointed – i was thinking that => behaves like Erlang – i.e. no choice points are created in the body.

But, i didn’t truly understand at the time how deep choice points actually reach, when, for example, in the body there are non-determinstic sub-goals.

The main motivation of my pattern matching compilation in my Prolog
system was to utilize the usual choice point elimination. The compilation
is still experimental and there are some pending tickets to help

the Prolog interpreter more to deal with my pattern matching compilation.
But you can check already that it generates more efficient Prolog code,
since it doesn’t need to create a choice point:

Pattern Matching with Cut:

?- [user].
p(X) ?- !, q(X).

Translated to ISO Prolog, nothing needs to be done for a fresh variable:

?- listing(p/1).
p(X) :-
   !,
   q(X).

If the above is a last clause, no choice point is created and the
cut has nothing to do. You can manually code last clauses
write (?-)/2 only and no (!)/0. The translator written in Prolog

itself is open source.

Edit 26.04.2021:
A translator for ($)/0 would not be feasible. Since this would impact
last call optimization (LCO), when its not done low-level like in SWI-Prolog.
So plagiarizing the idea of ($)/0 in the form of a ISO Prolog translator

will possibly not materialize. LoL

From what I gather, it doesn’t behave like Erlang, simply because Erlang does not not have choice points – so any subgoal would not generate choice points either. Whereas, Picat => may be non-deterministic after all, despite the cut after the guard, while Erlang will always be determinstic.

Dan

I recognize that the notion “deterministic code” is extremly challenging. But a professional Prolog programmer needs to know the ABC of “deterministic code” backwards and forwards while sleeping on a burning airplane without a parachute.

(=>)/2 together with if-then-else (like in Erlang) is always deterministic. If in your Prolog code every clause in your program with (=>)/2 and with if-then-else (like in Erlang) nothing will be non-deterministic. You need at least one rule using (:-)/2 or (?=>)/2 or at least one rule using the true (;)/2 disjunction, which is not if-then-else, to get something non-deterministic.

Maybe ask @dtonhofer to create a matrix. In the past @dtonhofer has created quite useful matrixes, about Prolog types, attributed variables, etc… You could make one dimension with the clause operator (=>)/2, (?=>), (:-)/2 and one dimension with what is found in the body. And then in the cells whether the predicate might be deterministic or not. He will possibly confirm my claim.

Edit 26.04.2021:
In as far the ($)/0 would only make sense if the Body has predicates that are coded with (:-)/2 or (?=>)/2 or true (;)/2. If the Body has nothing that is coded this way, you also don’t need ($)/0. There is a further and maybe fifth clause operator, namely (:-)/2 together with cut (!)/0.

Or namely (:-)/2 together with some guards and the cut (!)/2. Also there are a few further ISO core standard predicates that generate choice points, like for example repeat/0. So when I mentioned (;)/2, I mentioned only one representant of non-deterministic control flow.

There are a few more system predicates which might need a ban to create determinsitic code, like repeat/0 etc… This could also go in a matrix.

Here is an attempt:

grafik

The deterministic square is also the Erlang square, where Prolog
and Erlang overlap. Disclaimer: This is a simplification, there might
be still differences between Prolog and Erlang.

Proof:
We can prove the matrix, for example the Erlang square, the
body aspect. Lets prove (’,’)/2 first. Take a goal of the form:

P, Q

If P is semi-determistic or deterministic, then it has 0 or 1 solutions. If Q is semi-determistic or deterministic, then it has 0 or 1 solutions. The upper bound for solutions of the conjunction P, Q is the product, so its either 0=0*0, 0=0*1, 0=1*0 or 1=1*1. So this conjunction is semi-determistic or deterministic.

Now lets prove if-then-else. Take a goal of the form:

(G -> P; Q)

If P is semi-determistic or deterministic, then it has 0 or 1 solutions. If Q is semi-determistic or deterministic, then it has 0 or 1 solutions. If the guard G succeeds, then P is chosen, and the overall number of solutions is 0 or 1. If the guard G fails, then Q is chosen, and the overall number of solutions is 0 or 1. So this if-then-else is semi-determistic or deterministic.

Q.E.D.

Thank you for putting this together.

Could I ask you give examples for each square – or at least in Prolog, how the form would look like in code? I am not fully clear about this.

Where, for example, is if the else placed …

Dan

In the body. Its a control construct.
Isn’t if-then-else covered in Richard O’Keefes book?

Edit 26.04.2021:
The if-then-else is also part of the ISO core standard.
You can look it up there.

I mean how exactly should if the else be used in conjunction with =>, to ensure determinsim of the predicate

Nothing special. Just use it, goal is synonymous to body:

Edit 26.04.2021:
Jan W. used it just a few hours ago:

But the above is tricky, since sub_atom/5 is used with different modes.

I guess the full picture is this:

Head, Guard => (G → P; Q) … is deterministic, whereas:

Heard, Guard => Body is not, necessarily so.

Richard O’Keefe has a chapter 3.16 If-Then-Else on page 108.

Is it a good chapter?

You can’t say that, it depends on Body:

I need to digest this … in particular since the construction of (G → P; Q) stands in for once(G)

Not really. When I mean deterministic I mean all predicates are deterministic. Otherwise you cannot run it in Erlang and my claim of a Erlang square would be wrong.

You don’t need once(P) if P is semi-deterministic or deterministic. If P is semi-deterministic or deterministic, you have:

   once(P) == P

But, now i am confused again.

You are saying that Head, Guard => (G->P;Q) is deterministic if P is semi-deterministic or deterministic.

But, that is exactly the reason why i felt that => is not Erlang equivalent.

Its only equivalent if you arrange the Body in Prolog to be deterministic – with whatever scheme you choose … it can be an if-the-else with deterministic subgoals – or it can be a body with determinstic subgoals – whichever …

Dan

You need to match Erlang completely to get Erlang. What do you expect?

Also Erlang doesn’t have once/1.

And Jan’ Ws example would also not work in Erlang. You would need a function sub_atom , to get a sub_atom index in the guard. Such a function would be semi-deterministic. So in the end, as I said, you would have everything determistic all user defined predicates.

And as a result you would have no non-deterministic guards as well. The guards would be also all deterministic. Which allows for a more efficient implementation of if-then-else. Mercury might perform an according analysis to realize more efficient if-then-else. Not sure whether SWI-Prolog can do it.

Through the new det/1 declaration, SWI-Prolog could maybe enhance its code generation. It could have already hard wired some built-ins that speed up the if-then-else, but whether it also translates to user predicates I don’t know. Languages such as Mercury try to cover all squares,

including optimizations for the Erlang square.

Edit 26.04.2021:
There is a translition guide for Mercury. And the first thing we see a Prolog code translated to if-then-else. I don’t know how much Mercury relies on if-then-else. I am not advocating if-then-else, you can also use (=>)/2 with a guard and flatten things.

The Prolog to Mercury transition guide: Determinism
https://www.mercurylang.org/information/doc-latest/mercury_trans_guide/Determinism.html