2.28.3 Introduction

This SRFI defines a mechanism for comparing Scheme values with respect to a total order (aka linear order) [1]. The mechanism provides operations for:

1. Comparing objects of the built in types.
2. Using a total order in situations that arise in programs.
3. Facilitating the definition of a new total order.

In the following, these aspects will briefly be illustrated.

Traditionally, a total order is represented in Scheme by an order predicate, like < or char<?. For the purpose of this SRFI, however, a total order is represented by a Scheme–procedure comparing its two arguments and returning either -1, 0, or +1 depending on whether the first argument is considered smaller, equal, or greater than the second argument respectively. Examples of such compare procedures include:

(lambda (x y) (sign (- x y)))

for comparing real numbers, but also:

(lambda (x y) 0)

comparing anything. For most built in types specified in the Revised5 Report on the Algorithmic Language Scheme (R5RS, [3]) compare procedures are specified in Sections of this SRFI. An axiomatic definition of “compare procedure” is given in another section.

The primary reason for using 3-valued compare procedures instead of (2-valued) order predicates is efficiency: When comparison is computationally expensive, it is wasteful if two predicates are evaluated where a single 3-valued comparison would suffice. This point is discussed in greater detail in a section.

But dealing directly with 3-valued comparisons in the application program is inconvenient and obscures intention: For testing x < y one would have to write:

(eqv? (compare x y) -1)

For this reason, an operation <? is supplied which allows to phrase the same test as:

(<?  compare x y)

This is an example of mapping the three possible outcomes of a comparison into the two boolean values {#f, #t}. Since <? takes the total order as an explicit parameter, a comfortably large arsenal of tests can be made available for each and every total order. This deviates from the approach of R5RS, in which there are only five operations (=, <, >, <=, >=)—and for each total order (real/number, char, char-ci, string, string-ci) a complete set of these five operation is provided.

But still, using <? would be inconvenient if the compare procedure would have to be supplied explicitly every time. For this reason, the parameter compare is often made optional in this SRFI—and the procedure default-compare is used whenever no compare procedure is passed explicitly. default-compare defines some resonable total order on the built in types of R5RS.

For the third aspect of this SRFI, defining compare procedures, special control structures (macros) are provided. These control structures can be used in the definition of a (potentially recursive) compare procedure. This is best explained by an extended example.

Example

Assume there is a type length representing physical length. The type has an accessor procedure meters returning the length in meters (a real number). A compare procedure for lengths can then be defined in terms of real-compare as:

(define (length-compare length1 length2)
  (real-compare (meters length1) (meters length2)))

Now,

(<? length-compare x y)

tests if length x is shorter than length y. Also,

(<=/<? length-compare a x b)

tests if length x lies between length a (inclusive) and length b (exclusive). The expression:

(min-compare length-compare x y z)

is a shortest of the lengths x, y, and z. Likewise,

(chain<? length-compare x1 x2 x3 x4)

tests if the lengths x1, x2, x3, x4 are strictly increasing, and so on.

Furthermore, assume there is another type box representing a physical box. The type has procedures width, height, and depth accessing the dimension (each giving a length). A compare procedure for boxes, comparing first by width then by height and then by depth, can be defined using the control structure refine-compare as:

(define (box-compare box1 box2)
  (refine-compare
    (length-compare (width  box1) (width  box2))
    (length-compare (height box1) (height box2))
    (length-compare (depth  box1) (depth  box2))))

This time,

(<? box-compare b1 b2)

tests if box b1 is smaller than box b2—in the sense of the order defined. Of course, all the other tests, minimum, maximum etc. are available, too.

As a final complication, assume that there is also a type bowl with accessors radius (a length) and open? (a boolean). Bowls are to be compared first by whether they are open or closed, and then by radius. However, bowls and boxes also need to be compared to each other, ordered such that a bowl is considered “smaller” than a box. (There are type-test predicates box? and bowl?). Using the control structure select-compare this can be expressed as:

(define (container-compare c1 c2)
  (select-compare c1 c2
    (bowl? (boolean-compare (open?  c1) (open?  c2))
           (length-compare  (radius c1) (radius c2)))
    (box?  (box-compare c1 c2))
    (else "neither bowls nor boxes" c1 c2)))

This is an example of “hierarchical extension” of compare procedures. Also note the implicit use of refine-compare in the bowl? case.

The preceeding example illustrates the main functionality of this SRFI.