Current mood:	amused
Entry tags:	humor, programming, r6rs, scheme

Defining "Less Than"

Sudden changes of opinion are funny.

Everyone knows that more information can change your mind, but when it happens all at once it's like opening a door that doesn't lead where you expected.

Recently, there was a controversy on the r6rs-discuss mailing list about comparisons.¹ So far, everyone I've told about it in person offers the same opinion--then switches when they hear the reasons. The original mailing list discussion seemed to abruptly trail off as the initially obvious position lost its critical mass of supporters.

Comparisons

Scheme has several comparison procedures. For example², if you want to know whether x is strictly less than y, you can write (< x y). That gives you #t (true) if x is indeed strictly less than y and #f (false) if x is greater than or equal to y.

You can also compare more than two numbers at a time. (< 1 2 3) is true, but (< 1 2 0) is false because two is not strictly less than zero.

But what about (< x) and (<)? How should the < operator respond to one or zero arguments?

Options

The discussion focused on two major³ options:

The current standard says that a comparison applied to fewer than two arguments produces an error. Supporters of keeping it that way pointed out that you are not actually making a comparison unless you have two things.

The other option is for comparisons to produce #t, representing true, when given fewer than two arguments.

Why

Why would you want that?

Consider this: We already allow more than two arguments, so the purpose of a "comparison operator" is not to compare two things. It can take up to two comparisons to decide whether (< x y z) is true or false, let alone (< x y z a b). The maximum number of comparisons we are making grows and shrinks with the number of arguments, so why not let them both shrink to zero?

One way to think of the < operator is that it checks whether the sequence of arguments is strictly increasing. You can define that using a rule: A sequence is increasing if it has no non-increasing pairs. Under that definition, sequences of one or zero elements are strictly increasing. (They are also strictly decreasing, and a whole bunch of other things, under analogous definitions.)

Practically speaking, that's what we want.

It's easier to think of the operator as always working on single list of numbers, with the list being allowed to vary in length. There are ways of invoking the operator that make this explicit, by giving it arguments from a list whose contents (and length) are determined after the program is written.

Also, we'll usually already need separate code to detect that the list is out of elements because we generally process it one or a few elements at a time, and we need to detect that we are finished. When we ask whether the list is <, we generally want to know whether we can count on the rule for strictly increasing sequences. Letting (< x) and (<) be true makes it easier, in the more common cases, to separate "nothing needs to be done" from "you can't do it that way."

Moral and Code

So far, everyone I've asked in person has started out favoring error and switched to #t after hearing the reasons. This being the Internet, I'm sure a few die-hards will continue to support error or #f or who-knows-what, but I expect that most people who read this will go through the same switch, unless they start off favoring #t.

If you switched, laugh. It's funny, and you're not the only one who walked into a closet⁴.

If you're using an actual Scheme, here's a procedure that turns a two-argument comparison (whether or not it also takes other numbers of arguments) into a zero-or-more-argument comparison:

(define (generalize two-comp?)
  (define (gen-comp? . args)
    (if (or (null? args) (null? (cdr args)))
      #t
      (and (two-comp? (car args) (cadr args))
           (apply gen-comp? (cdr args)))))
  gen-comp?)