FAQFAQ   SearchSearch   MemberlistMemberlist   RegisterRegister   ProfileProfile   Log inLog in 


Confluence

Post new topic   Reply to topic    discuss.visual-prolog.com Forum Index -> Visual Prolog
View previous topic :: View next topic  
Author Message
Martin Meyer



Frankfurt a.M., Germany
Joined: 14 Nov 2002
Posts: 223

PostPosted: 22 Jun 2017 23:21    Post subject: Confluence Reply with quote

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?

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
Back to top
View user's profile Send private message
Thomas Linder Puls



Copenhagen, Denmark
Joined: 28 Feb 2000
Posts: 3124

PostPosted: 23 Jun 2017 8:29    Post subject: Reply with quote

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:

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:


clauses
    run() :-
        Input = node(empty, empty),
        Output1 = test1(node(empty, empty)),
        test2(node(empty, empty), Output2),
        stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output1)), '\n'),
        stdIO::write(toBoolean(uncheckedConvert(pointer, Input) = uncheckedConvert(pointer, Output2)), '\n').

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
Prolog Development Center
Back to top
View user's profile Send private message
Martin Meyer



Frankfurt a.M., Germany
Joined: 14 Nov 2002
Posts: 223

PostPosted: 23 Jun 2017 20:00    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
Thomas Linder Puls



Copenhagen, Denmark
Joined: 28 Feb 2000
Posts: 3124

PostPosted: 25 Jun 2017 21:03    Post subject: Reply with quote

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
Prolog Development Center
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    discuss.visual-prolog.com Forum Index -> Visual Prolog All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum