The arity of equality

The symbol “=” is the fulcrum of a balance. It declares that the things on either side of it, whatever they may be, are equivalent, identical, alike, indistinguishable, the same. [*]

The metaphor of the balance implies that exactly two things are being weighed, one against the other; thus equality is usually taken as a pairwise, or binary, relation. The other relational operators, ≠, <, >, ≤ and ≥, get a similar interpretation as comparisons of just two entities. The pairwise constraint is reinforced by the infix notation of mathematics and of many programming languages. When you write x=y or u>v, there’s no convenient place for more than two operands.

The restriction to two arguments no longer seems quite so natural and necessary when you begin thinking in a language with either prefix notation (Lisp) or postfix notation (Forth or Postscript). In Lisp an equality predicate is written (= x y), and there’s nothing to stop you from going on to write (= w x y) or (= w x y z). Furthermore, it seems easy to assign a meaning to such an expression: (= x y z) is true if and only if x, y and z are all equal. Similarly, (< x y z) is true if and only if x, y and z form a strictly increasing sequence.

If we can cope with comparisons of more than two arguments, what about fewer than two? What should we make of an expression such as (= x) or (< y)? How about relational functions with zero arguments, which would be written in Lisp as (=) or (<)? This question arose recently on a mailing list concerned with standards for the Scheme programming language (a dialect of Lisp). The message that initiated the thread was posted last Saturday evening; three days later, the discussion has spawned a couple of satellite threads and there are more than 75 responses.

It’s been a lively exchange, with quite a wide spectrum of views expressed. I can’t do full justice to the dialogue; if you’re at all interested in the issue, please read the original messages. Here I’ll just lay out some of the positions argued:

• The concept of comparison is intrinsically binary; a comparison should have exactly two arguments and otherwise constitutes an error.
• Comparisons with more than two arguments make sense, but not those with fewer than two.
• Comparisons with one argument are okay, and likewise those with two or more arguments, but there’s no need or reason to allow zero arguments.
• Comparison operators should be able to handle any number of arguments. Those invoked with zero arguments or one argument should return false.
• Comparison operators should be able to handle any number of arguments. Those invoked with zero arguments or one argument should return true.

What’s the right answer? At the outset, I was leaning toward the ultraliberal, “anything goes” view, but now I’m not so sure.

On first thought, the extension from exactly two arguments to at least two arguments seems like a harmless convenience. After all, even infix notations allow expressions such as x=y=z or 1<2<3. In a straightforward way we could define the more-than-two-argument versions of the relational operators in terms of a strictly binary operator:

(= x y z) → (and (= x y) (= y z))

Here we rely on the transitivity of equality to dispense with the third comparison, (= x z). If for some reason you don’t believe in transitivity, life is going to be hard for you. But even for those of us who make the leap of faith about x=z, there are some subtle traps here. For strictly binary comparison operators, we can always rely on a few logical identities:

(≠ x y) = (not (= x y))

(≤ x y) = (not (> x y))

(≥ x y) = (not (< x y))

With more than two arguments, these identities no longer hold. Consider (≤ 1 2 1) and (> 1 2 1), which are both false. In the case of = and ≠, it’s not even entirely clear what the semantics ought to be. Is (≠ 1 2 1) true or false? In other words, should the symbol ≠, when applied to more than two arguments, be read as “not all the same” or as “all different”? If we choose the latter interpretation, then we can no longer trust transitivity. The expansion of (≠ x y z) becomes (and (≠ x y) (≠ y z) (≠ x z)). (Note that the number of pairs to be checked grows quadratically with the number of arguments.)

Looking in the other direction—at comparisons of fewer than two arguments—a first question is why anyone would ever want to try such a thing. What’s the point of comparing just one number? Or no numbers? But the counterargument asks why we should forbid such operations. If an expression such as (< 3) or (=) can be assigned a meaning consistent with the semantics of the rest of the language, why impose an arbitrary limitation?

One way of approaching this issue is by analogy with other procedures or operators. Consider addition. In this case too, infix notation gives the impression that “+” ought to be a binary operator, but in a prefix language there’s no reason to enforce that restriction. An expression such as (+ 3 4 5) has an obvious meaning; it returns the value 12. Moreover, there’s no mathematical offense in declaring that (+ 3) evaluates to 3 or that the zero-argument form, (+), yields 0. This last result is justified by noting that 0 is the identity element of the integers under addition.

This reasoning leads to an admirably simple and spare definition of summation. Suppose we are given a binary addition operator, binary+, and we want to build a generic summation operator, list+, which can be applied to any number of arguments from zero on up. To avoid introducing extraneous details, I’m going to assume that the arguments come already wrapped up in a list, numlist, and that all the elements of this list are guaranteed to be numbers. The definition of list+ looks like this:

(define (list+ numlist)
  (if (null? numlist)
      0
      (binary+ (car numlist)
               (list+ (cdr numlist)))))

The definition says that the sum of a list of numbers is 0 if the list is empty and otherwise is equal to the first element of the list plus the sum of the remaining elements. The simple recursive structure of this procedure depends crucially on applying the same rules to a list of any length, including a length of zero. Trying to impose restrictions on the number of arguments would just clutter up the code with needless tests and exceptions.

It’s easy to see that we can deal with multiplication in exactly the same way, except that the identity element is 1 rather than 0. Greatest-common-divisor and least-common-multiple allow a very similar treatment, with the zero-argument (gcd) yielding 0 and (lcm) returning 1.

The logical connectives and and or also lend themselves to this kind of implementation. Given the primitive operation binary-and, we can define an n-ary version as follows:

(define (list-and booleanlist)
  (if (null? booleanlist)
      #t
      (binary-and (car booleanlist)
                  (list-and (cdr booleanlist)))))

Here the argument is a list of booleans. In the base case, applying and to an empty list returns #t (the Scheme token for true) as an identity element; otherwise we invoke list-and recursively on the tail of the list. For the corresponding or procedure, the base case is #f, or false.

It seems we have a pattern—a general method for converting a binary operator into an n-ary one. But does it always work?

Think about max and min, which select the largest and the smallest of their arguments. It looks as if we could fit them into the framework constructed above for “+” and for and—but there’s a problem. What is the base case for the recursion? There’s no doubt that (max 1 2) is 2, and no one would object to saying that (max 1) is 1, but what numerical value is appropriate for the zero-argument form (max)? Mathematically, I suppose the best answer is negative infinity. Some versions of Scheme include a representation of this number, but they don’t return it as the value of (max), and as a matter of practical programming, I don’t think it would be a good idea for them to do so. In fact, both Scheme and Common Lisp require max and min to have at least one argument. (They apply the same rule to subtraction and division.)

Getting back to the relational operators, it’s interesting to note that Common Lisp treats them the same as max and min: They work for one or more arguments but raise an error if invoked on zero arguments. No rationale for this choice is given in the standards documents. The Scheme standard specifies two or more arguments for the relationals, but apparently some implementations of the language also allow zero arguments or one argument, returning true in those cases.

The two dialects also differ in how they deal with the ambiguity of (≠ x y z). Common Lisp declares that “≠” means “all different,” accepting the oddity that “≠” is not the same as “not =”. Scheme has a slyer way of resolving the conflict: The language simply doesn’t offer a “≠” predicate.

I suppose this whole issue is one that can safely be left to the language lawyers. The arity of equality is not likely to become a major issue in software engineering, and I’d be wary of any program whose behavior depends critically on whether (=) is true or false. What intrigues me is simply that issues like these can remain unresolved and the subject of lively debate in spite of the best efforts of very smart people to find right answers. Lisp is celebrating its 50th birthday, and Scheme has been around for roughly 30 years. The standards that define the languages are not slapdash documents; in particular, their treatment of numbers and arithmetic is unsurpassed in the world of programming languages. But it seems we still have to sweat the details.