\index{comparison of terms}
\index{terms!comparison of}
The evaluable predicates described in this section are meta-logical.
They are used to compare and order terms, rather than to evaluate or 
process them.  They treat uninstantiated variables as objects with values
which may be compared, and they never instantiate those variables.
Each of these predicates simply succeeds or fails; there is no 
side-effect, substitution or error condition associated with them.
The predicates described in this section should {\em not} be used when 
what the user really wants is arithmetic comparison predicates
%(see section~\ref{Arithmetic}) 
or unification predicates (see section~\ref{Convenience}).

The predicates described take into account a standard total ordering 
of terms, which has as follows:
	\[		variables 
	   \ {\tt @<} \ floating \ point \ numbers
	   \ {\tt @<} \ integers 
	   \ {\tt @<} \ atoms 
	   \ {\tt @<} \ compound \ terms \]
Within each one of the categories, the ordering is as follows:
\begin{itemize}
\item	variables are put in a standard order (roughly, the oldest first
	--- the order is {\em not\/} related to the names of variables).
	Also, note that two anonymous variables are not identical terms.
	Unfortunately in the current implementation of our system (\version) 
	variables ``tend to move'' rather quickly as a result of unification,
	and thus the ordering may not continue to hold if the variables get
	unified to some other variables.  We intend to ameliorate this bug in
	future releases.
\item	floating point numbers and integers are put in numeric order, 
	from $-\infty$ to $+\infty$.  Note that a floating point number is
	always less than an integer, regardless of their numerical values.
\item	atoms are put in alphabetical (i.e.\ ASCII) order;
\item	compound terms are ordered first by arity, then by the name of their
	principal functor and then by their arguments (in a left-to-right 
	order).
\item	lists are compared as ordinary compound terms having arity 2 and 
	functor {\tt '.'}.
\end{itemize}
For example, here is a list of terms sorted in increasing standard order:
\begin{center}
	{\tt [ X, 3.14, -9, fie, foe, fum(X), [X], X = Y, fie(0,2), fie(1,1) ]}
\end{center}
The basic predicates for comparison of arbitrary terms are:
\begin{description}
\ouritem{T1 == T2}
\index{\texttt{==/2}}
    Tests if the terms currently instantiating {\tt T1} and {\tt T2}
    are literally identical (in particular, variables in equivalent positions
    in the two terms must be identical).
    For example, the question:

% JF
%    \demo{\verb+|+ ?- X == Y.}
    \demo{$|$ ?- X == Y.}

    \noindent
    fails (answers no) because {\tt X} and {\tt Y} are distinct variables.
    However, the question

% JF
%    \demo{\verb+|+ ?- X = Y, X == Y.}
    \demo{$|$ ?- X = Y, X == Y.}

    \noindent
    succeeds because the first goal unifies the two variables 
    (see section~\ref{Convenience}).

\ouritem{T1 {$\backslash$==} T2}
\index{\texttt{$\backslash$==/2}}
    Tests if the terms currently instantiating {\tt T1} and {\tt T2}
    are not literally identical.

% TLS: for some reason these @ comparison operators don't work.
\ouritem{T1 @$<$ T2}
\index{@$</2$}
    Succeeds if term {\tt T1} is before term {\tt T2} in the standard order.

\ouritem{T1 @$>$ T2}
\index{@$>/2$}
    Succeeds if term {\tt T1} is after term {\tt T2} in the standard order.

\ouritem{T1 @$=<$ T2}
\index{@$=</2$}
    Succeeds if term {\tt T1} is not after term {\tt T2} in the standard order.

\ouritem{T1 @$>=$ T2}
\index{@$>=/2$}
    Succeeds if term {\tt T1} is not before term {\tt T2} in the standard order.

\ouritem{T1 @$=$ T2}
\index{@$=/2$}
    Succeeds if {\tt T1} and {\tt T2} are identical variables, or if
    the main strucure symbols of {\tt T1} and {\tt T2} are identical.

\end{description}

Some further predicates involving comparison of terms are:

\begin{description}
\ouritem{compare(?Op, +T1, +T2)}
\index{\texttt{compare/3}}
    Succeeds if the result of comparing terms {\tt T1} and {\tt T2} 
    is {\tt Op}, where the possible values for {\tt Op} are:
    \begin{description}
    \item[`='] if {\tt T1} is identical to {\tt T2},
    \item[`$<$'] if {\tt T1} is before {\tt T2} in the standard order,
    \item[`$>$'] if {\tt T1} is after {\tt T2} in the standard order.
    \end{description}
    Thus {\tt compare(=, T1, T2)} is equivalent to {\tt T1==T2}.
    Predicate {\tt compare/3} has no associated error conditions.

\ouritem{sort(+L1, ?L2)} 
\index{\texttt{sort/2}}
    The elements of the list {\tt L1} are sorted into the standard order,
    and any identical (i.e.\ `==') elements are merged, yielding the 
    list~{\tt L2}.  The time to perform the sorting is $O(n log n)$ where 
    $n$ is the length of list {\tt L1}.  

    Examples:
    {\footnotesize
     \begin{verbatim}
                | ?- sort([3.14,X,a(X),a,2,a,X,a], L).

                L = [X,3.14,2,a,a(X)];

                no
     \end{verbatim}}
    Exceptions:
    \begin{description}
    \item[{\tt instantiation\_error}]
	Argument 1 of {\tt sort/2} is a variable or is not a proper list.
    \end{description}


\ouritem{keysort(+L1, ?L2)}
\index{\texttt{keysort/2}}
    The list {\tt L1} must consist of elements of the form \verb'Key-Value'.
    These elements are sorted into order according to the value of {\tt Key},
    yielding the list~{\tt L2}.  The elements of list {\tt L1} are scanned
    from left to right.  Unlike {\tt sort/2}, in {\tt keysort/2} no
    merging of multiple occurring elements takes place.  The time to perform
    the sorting is $O(n log n)$ where $n$ is the length of list {\tt L1}.  
    Note that the elements of {\tt L1} are sorted only according to the
    value of {\tt Key}, not according to the value of {\tt Value}.  The 
    sorting of elements in {\tt L1} is not guaranteed to be stable.

    Examples:
    {\footnotesize
     \begin{verbatim}
                | ?- keysort([3-a,1-b,2-c,1-a,3-a], L).

                L = [1-b,1-a,2-c,3-a,3-a];

                no
     \end{verbatim}}
    Exceptions:
    \begin{description}
    \item[{\tt instantiation\_error}]
	Argument 1 of {\tt keysort/2} is a variable or is not a proper list.
    \item[{\tt type\_error}]
	The elements of {\tt L1} are not of the form \verb'Key-Value'.
    \end{description}

\ournewitem{parsort(+L1, +SortSpec, +ElimDupl, ?L2)}{machine}
\index{\texttt{parsort/4}}

    {\tt parsort/4} is a very general sorting routine.  The list {\tt
    L1} may consist of elements of any form.  {\tt SortSpec} is the
    atom {\tt asc}, the atom {\tt desc}, or a list of terms of the
    form {\tt asc(I)} or {\tt desc(I)} where {\tt I} is an integer
    indicating a sort argument position.  The elements of list {\tt
    L1} are sorted into order according to the sort specification.
    {\tt asc} indicates ascending order based on the entire term; {\tt
    desc} indicates descending order.  For a sort specification that
    is a list, the individual elements indicate subfields of the
    source terms on which to sort.  For example, a specification of
    {\tt [asc(1)]} sorts the list in ascending order on the first
    subfields of the terms in the list.  {\tt [desc(1),asc(2)]} sorts
    into descending order on the first subfield and within equal first
    subfields into ascending order on the second subfield.  The order
    is determined by the standard predicate {\tt compare}.  If {\tt
    ElimDupl} is nonzero, merging of multiple occurring elements takes
    place (i.e., duplicate (whole) terms are eliminated in the
    output).  If {\tt ElimDupl} is zero, then no merging takes place.
    A {\tt SortSpec} of {\tt []} is equivalent to ``asc''.  The time
    to perform the sorting is $O(n log n)$ where $n$ is the length of
    list {\tt L1}.  The sorting of elements in {\tt L1} is not
    guaranteed to be stable. {\tt parsort/4} must be imported from
    module {\tt machine}.

    Examples:
    {\footnotesize
     \begin{verbatim}
            | ?- parsort([f(3,1),f(3,2),f(2,1),f(2,2),f(1,3),f(1,4),f(3,1)],
                 [asc(1),desc(2)],1,L). 

            L = [f(1,4),f(1,3),f(2,2),f(2,1),f(3,2),f(3,1)];

            no
     \end{verbatim}}
    Exceptions:
    \begin{description}
    \item[{\tt instantiation\_error}]
	Argument 1 of {\tt parsort/4} is not a proper list.
    \item[{\tt type\_error}]
	The elements of {\tt L1} are not terms with at least as many arguments as 
	required by {\tt SortSpec}, or {\tt SortSpec} is not of an allowed form.
    \end{description}
\end{description}

