Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a three-way comparison takes two values A and B belonging to a type with a total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical law of trichotomy.
An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...
s that support such an operation on primitive types.
Some machines have signed integers based on a sign-and-magnitude or one's complement representation (see signed number representations
Signed number representations
In computing, signed number representations are required to encode negative numbers in binary number systems.In mathematics, negative numbers in any base are represented by prefixing them with a − sign. However, in computer hardware, numbers are represented in binary only without extra...
), both of which allow a differentiated positive and negative zero. This does not violate trichotomy as long as we adopt a consistent total order: either -0 = +0 or -0 < +0 is valid. Common floating point
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
types, however, have an exception to trichotomy: there is a special value "NaN" (Not a Number
NaN
In computing, NaN is a value of the numeric data type representing an undefined or unrepresentable value, especially in floating-point calculations...
) such that x < NaN, x > NaN, and x = NaN are all false for all floating-point values x (including NaN itself).
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
The spaceship operator, written , is a binary relational operator that originated in the Perl programming language. Other languages, such as Ruby and Groovy also support the spaceship operator...
In mathematics, the sign function is an odd mathematical function that extracts the sign of a real number. To avoid confusion with the sine function, this function is often called the signum function ....
(a.k.a. signum) values of -1, 0, or 1 depending on whether A < B, A = B, or A > B, respectively. In Python 2.x (since removed in 3.x), the cmp function computes the same thing. In OCaml the compare function computes the same thing. In the Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
standard library the three-way comparison function compare is defined for all types in the Ordclass
Type class
In computer science, a type class is a type system construct that supports ad-hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types...
; it returns type Ordering, whose values are LT (less than), EQ (equal), and GT (greater than).
Many object-oriented languages have a three-way comparison method
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
, which performs a three-way comparison between the object and another given object. For example, in Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, any class that implements the Comparable interface has a compareTo method which returns a negative integer, zero, or a positive integer. Similarly, in the .NET Framework
.NET Framework
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
, any class that implements the IComparable interface has such a CompareTo method.
Since Java version 1.5, the same can be computed using the Math.signum static method if the difference can be known without computational problems such as arithmetic overflow
Arithmetic overflow
The term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
mentioned below. Many computer languages allow the definition of functions so a compare(A,B) could be devised appropriately, but the question is whether or not its internal definition can employ some sort of three-way syntax or else must fall back on repeated tests.
When implementing a three-way comparison where a three-way comparison operator or method is not already available, it is common to combine two comparisons, such as A = B and A < B, or A < B and A > B. A compiler may be able to optimize these two comparisons into a single three-way comparison at a lower level, but this is not a common optimization.
In some cases, three-way comparison can be simulated by subtracting A and B and examining the sign of the result, exploiting special instructions for examining the sign of a number. However, this requires the type of A and B to have a well-defined difference. Fixed-width signed integers may overflow when they are subtracted, floating-point numbers have the value NaN with undefined sign, and character strings have no difference function corresponding to their total order. At the machine level, overflow is typically tracked and can be used to determine order after subtraction, but this information is not usually available to higher-level languages.
In one case of a three-way conditional provided by the programming language, Fortran
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
The arithmetic IF statement has been for several decades a three-way arithmetic conditional statement, starting from the very early version of Fortran, and including FORTRAN IV, FORTRAN 66 and FORTRAN 77...
statement considers the sign of an arithmetic expression and offers three labels to jump to according to the sign of the result:
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and related languages is a three-way lexicographic comparison of strings; however, these languages lack a general three-way comparison of other data types.
Composite data types
Three-way comparisons have the elegant property of being simple to compose to build lexicographic comparisons of non-primitive data types, unlike two-way comparisons.
Here is a composition example in Perl.
sub compare($$) {
my ($a, $b) = @_;
return $a->{unit} cmp $b->{unit}
|| $a->{rank} <=> $b->{rank}
|| $a->{name} cmp $b->{name};
}
Note that cmp is for strings as <=> is for numbers. Two-way equivalents tend to be less compact but not necessarily less legible. The above takes advantage of short-circuit evaluation of the || operator, and the fact that 0 is considered false in Perl. As a result, if the first comparison is equal (thus evaluates to 0), it will "fall through" to the second comparison, and so on., until it finds one that is non-zero, or until it reaches the end.
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, etc., comparison of lists are done lexicographically, which means that it is possible to build a chain of comparisons like the above example by putting the values into lists in the order desired; for example in Ruby: [a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
