Subject: Re: Locating Singleton Variables

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 28 Nov 2000 16:18:14 +1300 (NZDT)

It really is a pity that people don't look at the DEC-10 Prolog library,
and even more of a pity that the Quintus Prolog library has not been
either made available at low cost or widely imitated.

This is a *long* solved problem.

First of all, there is no need to use numbervars in any of its incarnations,
and no real point in doing so.

Just do a perfectly standard term traversal.
(Written up as a DAI report about 20 years ago.)

Perhaps I should illustrate that first.

term(Term) :-
    (	var(Term) -> true
    ;   functor(Term, _, N),
        term(1, N, Term)
    ).
    
term(I, N, Term) :-
    (   I > N -> true
    ;   arg(I, Term, Arg),
	term(Arg),
	J is I + 1,
	term(J, N, Term)
    ).

Now let's modify that to pick up all the variables.

vars(Term, Vars) :-
    vars(Term, VarList, []),
    sort(VarList, Vars).

vars(Term, V0, V) -->
    (	var(Term) -> V0 = [Term|V]
    ;   functor(Term, _, N),
        vars(1, N, Term, V0, V)
    ).
    
vars(I, N, Term, V0, V) :-
    (   I > N -> true
    ;   arg(I, Term, Arg),
	vars(Arg, V0, V1),
	J is I + 1,
	vars(J, N, Term, V1, V)
    ).

And now let's modify _that_ so that we can use keysort to group identical
variables together, and split them into singletons and multiples.

vars(Term, Vars, Singletons, Multiples) :-
    vars(Term, VarList, []),
    keysort(VarList, KeyList),
    split_key_list(KeyList, Vars, Singletons, Multiples).

split_key_list([], [], [], []).
split_key_list([V=_,W=_|Vs], Vars, Singletons, Multiples) :- W == V, !,
    Vars = [V|Vars1],
    Multiples = [V|Multiples1],
    split_key_list(Vs, V, Vs1),
    split_key_list(Vs1, Vars1, Singletons, Multiples1).
split_key_list([V=_|Vs], [V|Vars], [V|Singletons], Multiples) :-
    split_key_list(Vs, Vars, Singletons, Multiples).

split_key_list([W=_|Vs], V, Vs1) :- W == V, !,
    split_key_list(Vs, V, Vs1).
split_key_list(Vs1, _, Vs1).

vars(Term, V0, V) -->
    (	var(Term) -> V0 = [Term=x|V]	% Note this change.
    ;   functor(Term, _, N),
        vars(1, N, Term, V0, V)
    ).
    
vars(I, N, Term, V0, V) :-
    (   I > N -> true
    ;   arg(I, Term, Arg),
	vars(Arg, V0, V1),
	J is I + 1,
	vars(J, N, Term, V1, V)
    ).

All done by kindness.
With this predicate, you put in a Term, and you get out
 - a list of all the Vars in the term, in canonical order
 - a list of all the Singleton variables, in canonical order
 - a list of all the multiple occurrence variables, in canonical order.
NO variables in the term are ever bound,
NO copying is done,
and the cost is O(|Term| + |Vars|*lg|Vars|).

(This kind of code is why it is important that functor(T, F, N) work
for *any* non-variable T, which the BSI and ISO Prolog committees did
not at first understand.  You'd think they'd never used the language
under fire.)