History dependent semi_lex_compare/3

General
36

Using my fuzzer I found a ground term transitivity violation:

?- T1 = s(_S1, 1), % where
    _S1 = s(_S1, s(s(_S1, 1), s(1, 0))),
T2 = s(T2, 1),
T3 = _S3, % where
    _S2 = s(_S2, 1),
    _S3 = s(_S2, _S3),
compare_with_stack(C1,T1,T2,[],F1), compare_with_stack(C2,T2,T3,F1,F2), 
compare_with_stack(C3,T1,T3,F2,_).
% answer
C1 = C2, C2 = (<),
C3 = (>).

So your new predicate cannot be used for sort/2.