Improving the Prolog VM with a choice point mindset

a) Can you make an example of a runtime check of some sort for choice points.

b) Which is a runtime check, that cannot be eliminated by a more clever compilation?

I have an example of such a runtime check, but it can be eliminated by a more clever compilation. Take the elevator example, the second clause of elevator/3:

elevator(N, X, Y) :-
     M is N-1,
     H is X+1,
     elevator(M, H, Y).

And this are the instructions for this clause:

----------------------------------------
clause 2 (<clause>(00000000067BC950)):
----------------------------------------
       0 i_enter
       1 a_add_fc(3,0,-1)
       5 a_add_fc(4,1,1)
       9 l_nolco('L1')
      11 l_var(0,3)
      14 l_var(1,4)
      17 i_tcall
L1:   18 b_var(3)
      20 b_var(4)
      22 b_var2
      23 i_depart(user:elevator/3)
      25 i_exit

The l_nolco instruction, which does poll choice points can be eliminated by the following reasoning. Also what follows after label L1 can be removed. I am assuming that delayed goals are woken up at the call port of a goal:

  • The fresh argument variables N, X, Y will not instantiate an attributed variable,
    therefore no delayed goals will be woken up before M is N-1.

  • The fresh variable M in the evaluation M is N-1 will not instantiate an attributed variable,
    therefore no delayed goals will be woken up before H is X+1.

  • The fresh variable H in the evaluation H is X+1 will not instantiate an attributed variable,
    therefore no delayed goals will be woken up before elevator(M, H, Y).

  • In summary no goals were woken up before elevator(M, H, Y) therefore also
    no new choice points will be found at elevator(M, H, Y).

  • Because there are no new choice points at elevator(M, H, Y) the instruction
    l_nolco('L1') will never jump to L1.

The above reasoning does not need to know whether something is a last clause. It solely works its way around the problem through freshness analysis of variables.

Why do such a thing?

  • It could speed up the Prolog VM execution, if switch is used
    to implement the Prolog VM loop.

  • It could also speed up the Prolog VM execution, if function array is
    used to implement the Prolog VM loop. One less instruction, one
    less function array roundtrip.

1 Like

Pattern matching helps in conducting the above analysis. Take this example which is not pattern matching but unification. Unification is allowed to instantiate an attributed variable, and peng we might have a problem with imported choice points:

foo([X|Y], Z) :- ...

On the other hand take pattern matching. The variables that are matched agains a pattern, are not allowed to bind. So any outside attributed variable is not allowed to bind, and subsquently the head matching will not instantiate any attributed variables from the callee:

foo([X|Y], Z) => ...

This is great!

Edit 27.04.2021:
How does “import of choice points” through delayed goals work. Try this, and
use the variable X somewhere inside deterministic code, like do X=nat(_).

?- freeze(X, (X=nat(1);X=nat(2))).

I am still looking – i am searching for where the function newChoice is called as part of a decision.

Its call is sprinked all over pl_wam and pl_vmi’s and somehow also related to debug not sure why …

But, i expect (assuming my hypothethis) that somewhere Prolog “anticipates” next clauses for a predicate call, and that’s where resolutions such as [], in the head, are made, and that’s where a newChoice is called (or not made) to track a next possible choice, before making a call to a (first?) clause of a predicate.

(is such a resolution made after each backtrack, as a “search” for the next applicable clause to call?)

Dan

In the WAM, you want the instructions “trust_me_else” “retry_me_else”, and “trust_me”, the former can be adjusted by argument indexing. I’m not sure what the equivalent instructions are in SWI-Prolog’s VM.
See also http://wambook.sourceforge.net/wam-slides.pdf pages 66, 116.

So, is this resolution part of the instruction set rather than an “executive” (deciding to) calling VMI’s ?

Do the inclusion of attributed variables in the design of a Prolog implementation incur a compute cost, even when they are not used in a program?

Probably not - they’re just one more case in the unification algorithm for variables.

I don’t understand your question. The trust_me_else etc instructions are used to mark the beginning of each clause. The WAM tutorial goes into more depth on this. (You might also want to look at DHD Warene’s original paper, which is referenced from Warren Abstract Machine - Wikipedia (the wikipedia article also has a short example)

[I once understood all of this deeply - about 35 years ago - but haven’t used that knowledge for over 25 years.]
[BTW, the IBM Prolog/370 compiler could generate machine code - removed the interpreter loop and did some other optimizations. I forget the speed-up, but I’m guessing it was less than 2x. Its interpreter was written in very tight hand-coded assembler.]

Thank you, Peter,

I guess in my mind an interpreter has essentially two parts: an engine executing the instructions and an instruction set – and hence a set of instructions to be executed.

Although, in practice these two functions are blurred because some instructions aid in the execution of instructions, and perhaps even direct what instructions are executed next.

“trust_me_else” etc. are regular interpreted instructions (creating a choicepoint if needed, etc.). There are indexing instructions that can jump past them, as an optimization. Other designs can be envisioned, but I haven’t looked into how closely SWI-Prolog’s VM follows the WAM (with the exception of register vs stack, which is a relatively minor difference).

This is not the issue I am adressing!

My analysis takles the end of a clause not the beginning of a clause. Its not the question whether a choice point needs to be created or not for the present clause. The instruction l_nolco('L1') in SWI-Prolog is used to regulate the way how the last goal in the clause is called.

This depends on whether the clause has still choice points at the last goal. If the clause has still choice points last call optimization is not allowed. There are ways to statically analyse the clause so that a judgement on whether the last call optimization is allowed or not,

can be done at compile time. SWI-Prolog cannot do it, it needs a runtime check:

ECLiPSe can do it, it doesn’t have a runtime check:

The instruction set listing is from the other thread “Can Prolog execute deterministic code as fast as C?”. You can also place the generated instructions for elevator/3 side by side, compare SWI-Prolog and ECLiPSe Prolog side by side, and you will see that the call elevator(M, H, Y) is differently compiled.

In SWI-Prolog the last call of elevator(M, H, Y) needs a runtime check, via l_nolco('L1') . In ECLiPSe Prolog there is no runtime check. Further l_nolco('L1') indeed also checks whether the present clause is a last clause, again in ECLiPSe this check is also eliminated away.

No, they also impact goal execution in the body of clauses. An example being the instruction l_nolco('L1') which is the example of this thread. Unless Jan W. tells me that I am totally misinterpreting the instruction. But the choice points that are checked can also come from delayed goals that were woken up.

Warning! I don’t know whether optimizing this thingy would really have a significant impact. I only wanted to followed the idea from @grossdan that there is fundamentally a problem in Prolog with deterministically code, and highlight that some of unnecessary instructions are known and can statically solved while compiling Prolog code.

But it depends on the Prolog VM. Possibly if native code is not generated, the Prolog VM overhead is anyway that high, that you wont see much if you could optimize away l_nolco('L1'). You might only see a positive impact if you have already reached the limits of your compilation, for example by a native code execution, like in ECLiPSe Prolog.