Deletion of Attribute Variables in Prolog

[Suraj Nair]

Hello,

I am new to prolog and am working on a project involving graphs and I have a list of attribute variables, each representing a node in the graph. Each node has several attributes, such as adjacent nodes, distance to  start node, etc. I want to remove a single node from the list, but when I use delete, I get the following error:

ERROR: uhook/3: Undefined procedure: adjs:attr_unify_hook/2

for example, I get this error if I include delete(OldVertices, Node, NewVertices) in my program.

I also get the exact same error if i am storing my vertices in a binary heap, and try to delete a vertex from the heap using delete_from_heap. 

I was able to successfully use delete and delete_from_heap on the node if I first delete all of it's attributes, but this causes problems for my program because I want to use the attributes later on, I just don't want the node to be contained in the list or binary heap.

Is this a bug, or am I handling attribute variables incorrectly? Any suggestions would be appreciated.

Thanks in advance,

Suraj

[Markus Triska]

Hi Suraj,

first: I think the representation you have chosen (one variable for each node, with attributes attached) is a good choice for doing many important operations on graphs efficiently in Prolog, and moreover it uses features that are at least more affiliated with pure solutions than other destructive operations, so it also stresses features of SWI-Prolog that are getting more and more important in the context of constraint solving.

The key point when using such a representation is to retain the variables as such, and use them only for the sake of providing easy access to their attributes. In particular, you must avoid predicates that unify any of these variables, either amongst themselves or with other terms, because unifications will trigger attr_unify_hook/2 for the attributes that are attached to the variables.

For example, from the definition of delete/3, you see that delete/3 contains in fact a (negated) unification. Unifications that involve attributed variables will in general invoke attr_unify_hook/2 for each of the defined attributes, to give the hook a chance to see whether the unification should succeed or not.

In your case, you are not using the attributes to represent any delayed goals or constraints, so you do not really need such hooks, and, since you justifiably omit the definitions of any such hooks, you get the error message you see upon unification.

To work around such issues, use predicates like (==)/2 and (\==)/2 to detect equality or disequality of two such variables. These predicates do not perform unifications, and therefore do not trigger any attribute hooks. You may have to roll your own versions of some library predicates, using these predicates instead of unification when necessary.

I hope this helps.

All the best!
Markus

[Suraj Nair]

Thanks Markus. Specifically, I have been trying to delete a variable from a binary heap. I have defined a rule as follows:

I was able to get a rule which deletes from a list working : 

list0_var_list(Ls0, V, Ls) :-

    select(V0, Ls0, Ls),

    V0 == V.

However, I am having some issues doing the same for a binary heap.

I defined the following rule:

delheap(Heap, Key, NewHeap) :-

    delete_from_heap(Heap, A1, A0, NewHeap),

    get_attr(Key, dist, A1),

    A0 == Key.

However when I test it I get 

?- TLO = [3-A, 4-B], put_attr(A, dist, 3),put_attr(B, dist, 4), list_to_heap(TLO, H), delheap(H, A, Hq). Correct to: "dijkstra_av:delheap(H,A,Hq)"? yes TLO = [3-A, 4-B], H = heap(t(A, 3, [t(B, 4, [])]), 2), Hq = heap(t(B, 4, []), 1), put_attr(A, dist, 3), put_attr(B, dist, 4).

Which works fine, but when I try with B :

TLO = [3-A, 4-B], put_attr(A, dist, 3), put_attr(B, dist, 4), list_to_heap(TLO, H), delheap(H, B, Hq). Correct to: "dijkstra_av:delheap(H,A,Hq)"? yes TLO = [3-A, 4-B], false.

Any idea on what could be going wrong with this implementation?

Thanks,

Suraj