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

Discussion
1

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;
}
3

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 …

5

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.

8

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

11

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

13

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

15

I guess the full picture is this:

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

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

18

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

20

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

22

I think the point I am trying to make is this;

Prolog is a generalization of the functional paradigm, which includes non-determinism.

Non-determinism and choice points is at the core of Prolog and is deeply ingrained in the Prolog execution engine. And even when no choice point is generated due to careful Prolog encoding of deterministic relations – the Prolog engine will have to check for that during runtime in order to decide to not create a choice point.

Hence, the benefit of non-determinism adds overhead – no matter what.

Currently, it seems that reducing some part of Prolog to a functional and deterministic island (which i thought => does) is not worth the cost of the added complexity in the VM execution engine – hence its not done.

I personally, would want one day to try out fork where I somehow manage to pause choice point creation and testing – for, say, a =!> operator – at least in a shallow or deep way – to see if it does indeed make a difference or not.

Dan

25

Yes, indeed, i am searching / trying to understand within pl_wam.c and pl_vmi.c to identify the code that does what i am hypothesizing.

26

You might want to read Warren’s Abstract Machine: A Tutorial Reconstruction by Hassan Aït-Kaci:

As Jan wrote elsewhere:

Despite the naming, the SWI-Prolog VM is based on a minimal VM described by Pereira [sic] and Byrd which is closely related to the `ZIP’ VM. The main difference is that this VM passes arguments over the stack rather than using registers.

This paper describes the Bowen&Byrd machine: https://www.researchgate.net/publication/273888197_A_portable_Prolog_compiler

This book might also interest you: Concepts, Techniques, and Models of Computer Programming

29

If i may quote Jan – my understanding was that Prolog does create such choice points and kills them quickly, e.g. when doing an once/1 – but, that such overhead is not significant.

I guess, i am taking this one step further – in my hypothesis – that the decision whether to create a choice point or not – takes cycles as well.