Section "union"

Binary built-in predicates such as (=)/2, (==)/2, etc.. have been implemented using a variant of union find. Initially union find based algorithms made its way into rational tree syntactic equali-ty, derived for example from Hopcorft & Karp [7]. Later they made its way into rational tree uni-fication as well, derived for example from Jaffar [8].

We implement a frozen terms aware refinement. We store the union find structure as a modifi-cation of the functor of non-frozen Prolog compounds, but frozen Prolog compounds stay read-only. To keep the main algorithms one pass and to undo the modification we allocated a log-ging structure, which is undone for success, failure and error.

The following union host calls are provided:

union_find(T): host language: The function returns the representative of T.
union_add(L, S, T): host language: The function merges the representatives S and T and returns a new log L.
union_undo(L): host language: The routine uses the log L to undo modifications.