Problem with radixTree in Visual Prolog 7.4

Discussions related to Visual Prolog
Elena Efimova
Posts: 7
Joined: 1 Sep 2006 13:02

Problem with radixTree in Visual Prolog 7.4

Unread post by Elena Efimova » 11 Jan 2013 9:56

Hello!

This program works in Visual Prolog 7.3 but does not work in Visual Prolog 7.4:

Code: Select all

class facts tr : dictionary{dictionary{unsigned}} := empty.   class predicates tryGet : (unsigned, unsigned) -> unsigned determ. setVal : (unsigned, unsigned, unsigned). clauses tryGet(X, Y) = lookup(lookup(tr, X), Y).   setVal(X, Y, V):-     Tree = lookup(tr, X),     !,     tr := insert({(A, _) = A}, tr, X, insert({(A, _) = A}, Tree, Y, V));     tr := insert({(A, _) = A}, tr, X, insert({(A, _) = A}, empty, Y, V)).   class predicates f : (unsigned X, unsigned Y) -> unsigned Val. clauses f(0, Y) = Y + 1:- !. f(X, Y) = V:-      V = tryGet(X, Y),      !. f(X, Y) = V:-     (Y = 0, !, V = f(X - 1, 1);     V = f(X - 1, f(X, Y - 1))),     setVal(X, Y, V).   domains tuple4 = tuple{unsigned X, unsigned Y, unsigned V, unsigned}.     class predicates g : (unsigned, unsigned) -> unsigned. g : (unsigned, unsigned, tuple4) -> unsigned. nextVal : (tuple4) -> tuple4. clauses g(X, Y) = g(X, Y, tuple(0, 0, 1, 1)):-     tr := empty,     setVal(0, 1, 0).   g(X, Y, tuple(X, Y, Z, _)) = Z:- !. g(X, Y, T) = g(X, Y, T1):-     T1 = nextVal(T),     T1 = tuple(A, B, C, _),     setVal(A, C, B).   nextVal(tuple(X, 1, V, N)) = tuple(X + 1, 0, V, N):- !. nextVal(tuple(X, Z, V, N)) = tuple(X + 1, Y + 1, V, N):-     Y = tryGet(X + 1, Z),     !. nextVal(tuple(_, _, _, N)) = tuple(0, N, N + 1, N + 1).   run():-     write(f(3, 13)), nl,     write(g(3, 14)),     _ = readLine().

User avatar
Thomas Linder Puls
VIP Member
Posts: 1622
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 11 Jan 2013 11:33

Hi, Elena. This problem is actually because there was an error in Vip7.3.

The problem is in the merge operation you supply in the insert operations:

Code: Select all

{(A, _) = A}
This merge operation keeps the element from the left tree (but in Vip7.3 it unfortunately in some situations swapped the arguments).

Your algorithm should if it was "correct" ;-) use the right element, because that is the one you have updated.

Code: Select all

setVal(X, Y, V):-     Tree = lookup(tr, X),     !,     tr := insert({(_, B) = B}, tr, X, insert({(_, B) = B}, Tree, Y, V));     tr := insert({(_, B) = B}, tr, X, insert({(_, B) = B}, empty, Y, V)).
The correct algorithm will however only work in Vip7.4 but malfunction in 7.3.

A little extra tip: instead of ending your program with readline:

Code: Select all

run():-     write(f(3, 13)), nl,     write(g(3, 14)),     _ = readLine().
You should try running them from the IDE with Build -> Run in Window Alt+F5.

This gives the desired effect that you can see the result, at the same time the program will behave more normal if you run it ina command prompt (where you don't expect to press enter to terminate a program).
Regards Thomas Linder Puls
PDC

Elena Efimova
Posts: 7
Joined: 1 Sep 2006 13:02

Unread post by Elena Efimova » 11 Jan 2013 12:34

Thank you, Thomas. It works.
The algorithm is correct. :-)
About Build -> Run in Window. I offen use it, but the console window is not "clean" in this case. There are extra lines in it. Sometimes it would be better without them.

Post Reply