Discussions related to Visual Prolog
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Confluence

Unread post by Martin Meyer »

Hello Thomas,

say tree is some algebraic tree type. When comparing two variables of type tree, it makes sense to first check whether the variables point to the same address in memory. Because in case they do, we know that they are equal and we can spare the much more costly comparison of the variables' values.

To make address-equality checks work out most often, we should write our programs as confluent as possible. I.e., when we known that a predicate's output equals one of its inputs, it is a good idea to let the output variable point to the same memory address as the input variable (instead of returning a duplicate of the input variable's value residing at a different address in memory).

However VIP (7.5.0.2) does not support the 'confluence dogma' very well. Please have a look at this example. It has two predicates test1 and test2 which are just handing the input over to the output. After calling these predicates the example checks whether in- and output variables point to same memory address. Surprisingly (at least for me) the result is that in- and output do not point to same address. Why is that, could it be improved in future?

Code: Select all

domains     tree =         empty;         node(tree LeftChild, tree RightChild).   class predicates     test1 : (tree) -> tree. clauses     test1(Tree) = Tree.   class predicates     test2 : (tree, tree [out]). clauses     test2(Tree, Tree).   clauses     run() :-         Input = node(empty, empty),         Output1 = test1(Input),         test2(Input, Output2),         stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output1)), '\n'),         stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output2)), '\n').
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

There is clearly a problem here, that we have to solve. But the problem is not what you think.

The predicates test1 and test2 behaves in the way you expect. Which you can validate if you change the test like this:

Code: Select all

constants     t : tree = node(empty, empty).   clauses     run() :-         Input = t,         Output1 = test1(Input),         test2(Input, Output2),         stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output1)), '\n'),         stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output2)), '\n').
The problem is in the handling of the constant tree in the run predicate, where the first two occurrences of Input has been inline expanded:

Code: Select all

 
I don't know exactly why this has happened, but given the complexity of the term it should not have been duplicated.
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer »

Ah ok, thanks for the info Thomas!

So the problem arises only in cases where a free tree variable is unified with a tree literal, so that the compiler can expand the variable to the value represented by the literal. Naturally tree literals represent trees of (only) constant height and reasonably the height will be very small. Consequently the issue has no relevant impact.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

Yes.

More over it is quite natural to define non-trivial literal trees as constants. And when defined as constants the problem also disappears.

You should also notice that the empty tree is always the same pointer value (=0x00000001).
Regards Thomas Linder Puls
PDC
Post Reply