57

How to write in a standard conforming manner avs_term_rearranged(AVs, T, AVsR) with given AVs and T such that AVsR is a permutation of AVs with the elements arranged in same order as their variables occur in left-to-right order in T.

AVs is a list of elements of the form A = V where A is an atom designating a variable name like 'X' and V is a corresponding variable. Such lists are produced by read_term/2,3 with the read-option variable_names/1 (7.10.3). Additionally, the precise order of elements is not defined.

| ?- read_term(T,[variable_names(AVs)]).
A+B+A+_+C.

AVs = ['A'=A,'B'=B,'C'=C]
T = A+B+A+_+C

T is a term that contains all variables of AVs plus some more.

Note that in a standard conforming program one cannot rely on the term order for variables (7.2.1):

7.2.1 Variable

If X and Y are variables which are not identical then X term_precedes Y shall be implementation dependent except that during the creation of a sorted list (7.1.6.5, 8.10.3.1 j) the ordering shall remain constant.

NOTE — If X and Y are both anonymous variables then they are not identical terms (see 6.1.2 a).

Consider as an example from 8.4.3.4:

sort([f(U),U,U,f(V),f(U),V],L).
   Succeeds, unifying L with [U,V,f(U),f(V)] or
   [V,U,f(V),f(U)].
   [The solution is implementation dependent.]

So there are two possible ways how sort/2 will work, and one cannot even rely on the success of:

sort([f(U),U,U,f(V),f(U),V],L), sort(L, K), L == K.

As an example:

?- avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, AVsR).
   AVsR = ['A'=A,'C'=C,'B'=B].
false
  • 10,264
  • 13
  • 101
  • 209
  • is `T` an arbitrary term or is it of the same form? is it, e.g., also obtained from `read_term`? – Christian Fritz Jan 25 '14 at 00:00
  • btw, you are using `T` twice in your question with different meanings. Might help to rename one of them to avoid confusion. – Christian Fritz Jan 25 '14 at 00:02
  • @ChristianFritz: I cannot see a difference. Once, `T` is used as an argument for the sought predicate, and once it is used with `read_term` which in this case produces `T` and `AVs` such that they fit to the predicate. – false Jan 25 '14 at 13:58
  • Could you then give an example input and expeted output? Is this what you have in mind `avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, ['A'=A,'C'=C,'B'=B])` ? – Christian Fritz Jan 25 '14 at 17:11
  • seems that if you can figure out how to use `ream_term/3` to read from a stream that you write to using `write_term/3` then you can get a representation of the variables in `T` that conform with that of `AVs`, and at that point it's a simple matter of discarding from the `T`-variables all those that do not appear in the `AVs` variables. – Christian Fritz Jan 25 '14 at 17:51
  • @ChristianFritz: Not sure what you mean. But in fact `read_term/3` and `write_term/3` do use the same format. And determining the void variables is here: http://stackoverflow.com/questions/7947910/converting-terms-to-atoms-preserving-variable-names-in-yap-prolog/7948525#7948525 – false Jan 25 '14 at 17:59
  • and just to clarify: we are in agreement that if `T` was not a term but an atom, e.g., `'A+C+F+B'`, then this would be really easy, right? So really want you are looking for is a way to get at the symbols used for the unbound variables in `T`. Correct? – Christian Fritz Jan 26 '14 at 22:41
  • If `T` is an atom (which is a term, too), then its `AVs` would have to be `[]`. I am not sure about the terminology you use. – false Jan 27 '14 at 01:36
  • Joachim's answer already voids my thought. But just to explain my "terminology", if you had the term you want as an atom (with the variable names preserved), you could have printed that atom into a stream and then used read_term/3 on that stream to recover the variable names. Didn't know term_variables preserves them, too. That's of course easier. – Christian Fritz Jan 27 '14 at 01:49
  • @ChristianFritz: Again, I have difficulties with your terminology: What did you think that `term_variables/2` does? Its functionality is independent of variable names. – false Jan 27 '14 at 01:57
  • I am considering creating a tag called `prolog-variable-names` related to topics about renaming variables using predicates such as numbervars/3. Seeking your feedback. – Guy Coder Feb 01 '20 at 13:37
  • numbervars/3 is a different thing. I don't like it as it is the source of many errors. – false Feb 01 '20 at 15:45

4 Answers4

44
avs_term_rearranged(AVs, T, AVsR) :-
    term_variables(T, Vs),
    copy_term(Vs+AVs, Vs1+AVs1),
    bind_names(AVs1),
    build_vn_list(Vs, Vs1, AVsR).

bind_names([]).
bind_names([N=V|AVs]) :-
    N = V,
    bind_names(AVs).

build_vn_list([], [], []).
build_vn_list([V|Vs],[N|Ns],NVs) :-
    ( atom(N) ->
      NVs = [N=V|NVs1]
    ; var(N) ->
      NVs = NVs1
    ),
    build_vn_list(Vs, Ns, NVs1).
Per Mildner
  • 10,469
  • 23
  • 30
  • 1
    Blows my mind. I could have sworn that one needs either something along @JSchimpf's version (limited by `max_arity` and `max_integer`) or that `sort/2` would be needed to associate the variables and their order. In any case, I'm happy I asked, I would have never found that solution. Maybe the mental block was that I hoped to rearrange the existing `(=)/2`, whereas you are "reconstructing" them, procedurally speaking. – false Jan 30 '14 at 22:46
  • 1
    Going through it step-by-step: After `copy_term/2`: `AVs` can be reclaimed. After `bind_names/2`: `AVs1` can be reclaimed. Prior to `build_vn_list`: Only two lists are present: No pairs at all!! – false Jan 30 '14 at 23:13
  • 1
    Brilliant! I was wondering whether we have a name for this technique of using a bipartite data structure with pairs of corresponding variables as a "mapper". – jschimpf Feb 01 '14 at 15:59
15

Use term_variables/2 on T to obtain a list Xs with variables in the desired order. Then build a list with the elements of AVs, but in that order.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    pick_in_order(AVs, Xs, AVRs).

pick_in_order([], [], []).
pick_in_order(AVs, [X|Xs], AVRs) :-
    ( pick(AVs, X, AV, AVs1) ->
        AVRs = [AV|AVRs1],
        pick_in_order(AVs1, Xs, AVRs1)
    ;
        pick_in_order(AVs, Xs, AVRs)
    ).

pick([AV|AVs], X, AX, DAVs) :-
    (_=V) = AV,
    ( V==X ->
        AX = AV,
        DAVs = AVs
    ;
        DAVs = [AV|DAVs1],
        pick(AVs, X, AX, DAVs1)
    ).

Notes:

  • this is quadratic because pick/4 is linear
  • term_variables/2 is not strictly necessary, you could traverse T directly
jschimpf
  • 4,904
  • 11
  • 24
13

My previous answer had quadratic runtime complexity. If that's a problem, here is a linear alternative. The reason this is a bit tricky is that unbound variables cannot be used as keys for hashing etc.

As before, we basically rearrange the list AVs such that its elements have the same order as the variables in the list Xs (obtained from term_variables/2). The new idea here is to first compute a (ground) description of the required permutation (APs), and then construct the permutation of AV using this description.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    copy_term(AVs-Xs, APs-Ps),
    ints(Ps, 0, N),
    functor(Array, a, N),
    distribute(AVs, APs, Array),
    gather(1, N, Array, AVRs).

ints([], N, N).
ints([I|Is], I0, N) :- I is I0+1, ints(Is, I, N).

distribute([], [], _).
distribute([AV|AVs], [_=P|APs], Array) :-
    nonvar(P),
    arg(P, Array, AV),
    distribute(AVs, APs, Array).

gather(I, N, Array, AVRs) :-
    ( I > N ->
        AVRs = []
    ;
        arg(I, Array, AV),
        I1 is I+1,
        ( var(AV) -> AVRs=AVRs1 ; AVRs = [AV|AVRs1] ),
        gather(I1, N, Array, AVRs1)
    ).
jschimpf
  • 4,904
  • 11
  • 24
  • 2
    Nice but not portable since it requires Array to be a compound term with unbounded arity. A lesser problem is that it requires arbitrary size integers. – Per Mildner Jan 28 '14 at 16:31
  • 2
    @Per, I honestly think after 30 years it is time to lay arity limits on compound terms to rest. – jschimpf Feb 01 '14 at 16:18
  • 1
    @Per, I do not understand your comment about "arbitrary size integers". This code has no more requirement for large integers than any code using length/2. In fact, this is one of the few types of program where integers *are* strictly bounded (to something like 2^30 on 32-bit, or 2^61 on 64-bit machines). – jschimpf Feb 01 '14 at 16:28
  • 3
    The question was specifically about a standard conforming solution. There is nothing in the standard that requires arbitrary arities of compound terms, or integers large enough to represent the length of a representable list. In practice, the integer size is unlikely to be a problem, this is why I wrote that its size is less of a problem. – Per Mildner Feb 02 '14 at 17:04
  • 2
    Let me just summarize and clarify: (1) this is a fully standard-conforming program; (2) it does not require arbitrary sized integers; (3) ISO-Prolog implementations vary in the size of problem instances they support; (4) Per's solution is less likely to run into such implementation limits, and generally more elegant, that's why I upvoted and applauded it. – jschimpf Feb 03 '14 at 16:12
11

This version is very short, using member/2 (from the Prolog prologue) for the search. It has very low auxiliary memory consumption. Only the list AVsR is created. No temporary heap-terms are created (on current implementations). It has quadratic overhead in the length of AVs, though.

avs_term_rearranged(AVs, T, AVsR) :-
   term_variables(T, Vs),
   rearrange(Vs, AVs, AVsR).

rearrange([], _, []).
rearrange([V|Vs], AVs, AVsR0) :-
   ( member(AV, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR
   ),
   rearrange(Vs, AVs, AVsR).

Another aspect is that the member(AV, AVs) goal is inherently non-deterministic, even if only relatively shallow non-determinism is involved, whereas @jschimpf's (first) version does create a choice point only for the (;)/2 of the if-then-else-implementation. Both versions do not leave any choice points behind.

Here is a version more faithfully simulating @jschimpf's idea. This, however, now creates auxiliary terms that are left on the heap.

rearrange_js([], _, []).
rearrange_js([V|Vs], AVs0, AVsR0) :-
   ( select(AV, AVs0, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR,
      AVs0 = AVs
   ),
   rearrange_js(Vs, AVs, AVsR).
false
  • 10,264
  • 13
  • 101
  • 209