For your enjoyment: A more complete diagram of the Byrd Box Model

Here it is:

https://raw.githubusercontent.com/dtonhofer/prolog_notes/master/pics/byrd_box_model/Byrd%20Box%20Model.svg

I have added the “Rollback” action and the “Decision Lozenge” on redo. The latter seems really necessary to account for the ability to have deterministic and semi-deterministic predicates. Or is done differently?

SWI-Prolog has a “Unify” port as well. The problem is without
a “Unify” port, you would not see which facts are visited:

foo(bar).
foo(baz).

You would only see the ports of the callee, i.e. “Call”, “Exit”,
“Redo”, “Fail”. But with “Unify” port you also see which fact is used.
By default the “Unify” port is not shown on the command line debugger:

[trace]  ?- foo(X).
   Call: (10) foo(_21146) ? creep
   Exit: (10) foo(bar) ? creep
X = bar 

But you can switch it on:

[trace]  ?- visible(+unify), leash(+unify).

[trace]  ?- foo(X).
   Call: (10) foo(_24504) ? creep
   Unify: (10) foo(bar) ? creep
   Exit: (10) foo(bar) ? creep
X = bar 

If I remember well the “Unify” port is by default switched on in the graphic
debugger? I have a similar port “head” in my system. It is very useful for
the coverage tool in my system.

Determinism and semi-determinism is more complex. You cannot
see it in the ports. You would need to have the debugger list the choice
points between the current head and the current goal.

Some debuggers can list choice points. I think the command “A”
does the job. This command is also available in GNU Prolog and SWI-Prolog.
I used it at the unify port, this is what I get:

[trace]  ?- foo(X).
   Call: (10) foo(_26486) ? creep
   Unify: (10) foo(bar) ? alternatives
 [10] foo(bar)
   Unify: (10) foo(bar) ? creep
   Exit: (10) foo(bar) ? creep
X = bar ;
   Redo: (10) foo(_26486) ? creep
   Unify: (10) foo(baz) ? alternatives
   Unify: (10) foo(baz) ? creep
   Exit: (10) foo(baz) ? creep
X = baz.

The first unify port event still shows the callee foo(bar) goal that it has
alternative, meaning it has a choice point, since there are more fact
candidates. The second unify port event even does not anymore show foo(bar).

I guess the second unify port event does not only have no choice point,
but the callee might have already gone due to Last-Call Optimization (LCO).
It depends when and how the debugger honors LCO.

2 Likes

So basically a Prolog system, an advanced one, is more pro-active. In your diagram you say “Open alternatives? If not, bypass P1!” during redo. But the reality is more that redo fetches from the choice point list, which has already unneccessary alternatives removed.

And a Prolog systems tries to avoid putting an alternative on the choice point list, much earlier. Namely at the “Unify” port. There it decides whether it needs a fresh choice point, during its first call.

Or whether it can drop an already existing choice point, during its next call. Without such a pro-active choice point management the Prolog system might not show the necessary performance and also not deliver enough information for LCO.

But you might be right, the debugger might insert extra choice points, and “Open alternatives? If not, bypass P1!” is what the debugger might need do. But usually it is not exactly what happens during nodebug. So “Decision Lozenge”, yes and no.

You can also see how the cut (!) manipulates the choice point list. Unfortunately the cut (!) is compiled with nodebug, so it wont show ports. But we can use the A command and even don’t need the “Unify” port to illustrate it. Just take this example:

foo(bar).
foo(baz).
test(X) :- foo(X), !.

Now running it in trace mode and using the A command for alternatives here and then, I get the following result:

[trace]  ?- test(A).
   Call: (10) test(_19754) ? creep
   Call: (11) foo(_19754) ? creep
   Exit: (11) foo(bar) ? alternatives
 [11] foo(bar)
   Exit: (11) foo(bar) ? creep
   Exit: (10) test(bar) ? alternatives
   Exit: (10) test(bar) ? 

So the cut (!) in test/1 modifies the choice point list, although there were alternatives. Before the cut (!) there was a choice point because there was a unfication alternative, after the cut (!) even this alternative was removed.

1 Like

SWI-Prolog always creates a choice point for a call when in debug mode. That allows for retry. It also kills LCO. Often that is what you want during debugging. These debug choicepoints are not shown by the A command (and also not by the graphical debugger).

2 Likes

Don’t forget that unification of an attributed variable can “insert” a new goal at various points in the diagram.
:wink:

Also that there are non-backtracking predicates (nb_setval/2 et al) that are unaffected by “rollback” …

2 Likes

In some Prolog systems attribute variable unify hooks are inserted after the “Unify” port and before the next “Call” or “Exit” port. You see this here, without the “Unify” port enabled, you don’t see that X = bar was tried, but interestingly it shows some “Redo”:

SWI-Prolog (threaded, 64 bits, version 8.3.0)

foo(bar).
foo(baz).

[trace]  ?- freeze(X, X = baz), foo(X).
   Call: (11) foo(_22318) ? creep
   Redo: (11) foo(_22318) ? creep
   Exit: (11) foo(baz) ? creep
X = baz.

With “Unify” port it shows more clearly that X = bar was temporarily allowed, and freeze/2 must have been woken up later:

[trace]  ?- visible(+unify), leash(+unify).

[trace]  ?- freeze(X, X = baz), foo(X).
   Call: (11) foo(_25418) ? creep
   Unify: (11) foo(bar) ? creep
   Redo: (11) foo(_25418) ? creep
   Unify: (11) foo(baz) ? creep
   Exit: (11) foo(baz) ? creep
X = baz.

I have tryed to arranged the “Unify” port the same in my system, so that unify hooks are seen after the “Unify” port and before the next “Call” or “Exit” port , but this is currently broken. Have to check whats going wrong in my debugger.

1 Like