From Newsgroup: comp.lang.prolog
Here is an implementation that doesnrCOt suffer from
the same anomaly. I get these results:
?- test1(X), term_vars(X, [V,W]).
X = f(g(X, W), V).
?- test2(X), term_vars(X, [V,W]).
X = f(_S1, V), % where
_S1 = g(f(_S1, V), W).
Only the algorithm is a little expensive. Whats
annonying that I backtrack over a bisimulation
equals. And can only collect the union find store
during a sucesss. But a failure of the bisimulation
equals does a local union find store rollback, without
keeping any partial union find results that were
from successful sub-equals calls:
term_vars(T, L) :-
term_vars([], T, []-[], L-_).
% term_vars(+List, +Term, +Pair, -Pair)
term_vars(_, V, L-P, L-P) :- var(V),
member(W, L), W == V, !.
term_vars(_, V, L-P, [V|L]-P) :- var(V), !.
term_vars(M, T, L-P, L-Q) :- compound(T),
member(S, M), equals(T, S, P, Q), !.
term_vars(M, T, L, R) :- compound(T), !,
T =..[_|A],
foldl(term_vars([T|M]), A, L, R).
term_vars(_, _, L, L).
The bisimulation equals itself is:
equals(X, Y) :-
equals(X, Y, [], _).
% equals(+Term, +Term, +List, -List)
equals(X, Y, L, R) :- compound(X), compound(Y), !,
union_find(X, L, Z),
union_find(Y, L, T),
equals2(Z, T, L, R).
equals(X, Y, L, L) :- X == Y.
equals2(X, Y, L, L) :-
same_term(X, Y), !.
equals2(X, Y, _, _) :-
functor(X, F, N),
functor(Y, G, M),
F/N \== G/M, !, fail.
equals2(X, Y, L, R) :-
X =.. [_|A],
Y =.. [_|B],
foldl(equals, A, B, [X-Y|L], R).
And the union find trivially:
union_find(X, L, T) :-
member(Y-Z, L),
same_term(X, Y), !,
union_find(Z, L, T).
union_find(X, _, X).
Mild Shock schrieb:
Take this test case:
test1(X) :- X = f(g(X,_B),_A).
test2(X) :- Y = g(f(Y,A),_B), X = f(Y,A).
Now try this (numbervars/3):
/* SWI-Prolog 9.3.26 */
?- test1(X), numbervars(X,0,_).
X = f(g(X, A), B).
?- test2(X), numbervars(X,0,_).
X = f(_S1, A), % where
-a-a-a _S1 = g(f(_S1, A), B).
And try this (nonground/2):
?- test1(X), nonground(X, V).
X = f(g(X, V), _).
?- test2(X), nonground(X, V).
X = f(_S1, V), % where
-a-a-a _S1 = g(f(_S1, V), _).
And try this (term_variables/2):
?- test1(X), term_variables(X, [V,W]).
X = f(g(X, V), W).
?- test2(X), term_variables(X, [V,W]).
X = f(_S1, V), % where
-a-a-a _S1 = g(f(_S1, V), W).
All 3 predicates suffer from an similar anomaly,
namely, in the first query V appears 2nd
argument of g/2, and in the second query V
appears 2nd argument of f/2. Can this be fixed?
Mild Shock schrieb:
Concerning the input (xxx yyy zzz) the OP wrote:
I would expect it to print zzz(xxx(yyy)).
Where did he get this requirement from, he didnrCOt
compare other Prolog systems, right? So it came from
his applicationdomain. But what was his application
domain? Ok, lets proceed to an example with multiple
brakets. Lets make the Pascal rCLbeginrCY rCLendrCY example,
by replacing xxx and zzz by rCLbeginrCY and rCLendrCY.
I get this result:
?- member(X,[begin,end]), current_op(Y,Z,X).
X = (begin), Y = 1100, Z = fy ;
X = (end), Y = 1100, Z = yf.
?- X = (begin
|-a-a-a-a-a-a-a-a-a x = 1;
|-a-a-a-a-a-a-a-a-a y = 2;
|-a-a-a-a-a-a-a-a-a begin
|-a-a-a-a-a-a-a-a-a-a-a-a-a-a z = 3
|-a-a-a-a-a-a-a-a-a end
|-a-a-a-a-a-a end).
X = (begin x=1;y=2;begin z=3 end end).
But is the abstract parse term, the Prolog result useful?
--- Synchronet 3.21a-Linux NewsLink 1.2