Improving the Prolog VM with a choice point mindset

Discussion
#1

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
#3

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

#4

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.

#5

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

#6

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?

#7

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

#8

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.]

#9

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.

#10

“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).