Chaining comparisons

Mathematical notation often uses more than one comparison operator in a row:

0 ≤ x < n

Anyone who tries that in C is in for a surprise (and possibly some frustrating debugging, since this sort of bug is easy to not see), but some languages do support it. I know seven ways to do it:

  • N-ary comparison: In most Lisps, comparison operators can take more than two arguments. This doesn't solve the whole problem, since it only covers chains that use two calls to one operator, or that can easily be rewritten to use one operator (e.g. 0 ≤ x < n as 0 ≤ x ≤ n - 1), but it helps, and it doesn't complicate the kernel. It doesn't work well with infix, though.
  • Combinator: Something like chain a f b g c = f a b && g b c enables writing (chain 0 ≤ x < n), if you don't mind the distraction of an explicit combinator call. In an infix language where it's awkward to pass comparison operators as arguments, you may be able to improve on this by making chain a macro.
  • Macros: Comparison operators can be macros which examine their arguments to see if they're calls to other comparison operators, and if so, expand to chain them. This requires a language with macros and infix (and in which booleans aren't possible arguments to comparisons), which explains why I don't know of any language that does it. In such a language, though, it's an easy way to provide fullly general chaining in user code, without kernel support, at the price of turning all the comparison operators into macros. If the language has a feature that rewrites function calls, like a more reliable version of Common Lisp's compiler-macros, then that price can be avoided.
  • Multiple infix: Some languages (e.g. Smalltalk, although it doesn't cover this case) support parsing 0 ≤ x < n as a call to a single ≤< operator with three arguments. In such languages, you can define that operator to be equivalent to (0 ≤ x && x < n). This doesn't scale well to more operators than the basic six, but if you already have multiple infix, it's easy to cover all the common cases of chaining.
  • Associativity option: If you have user-defined infix operators with a choice of left, right, or no associativity, you can add chaining as a fourth associativity option. This is what Perl 6 does.
  • Separate channels: In Icon, comparison operators give their Boolean result by success or failure, leaving the return value available for something else. So they return their right argument, and (0 ≤ x) < n works. This requires unusual language semantics, though.
  • Special case: Python simply has a special case for this, just as it has other special cases to make Boolean expressions look more familiar (e.g. is not).

The language-design pattern behind chaining is to redefine an implausible construct (in this case, comparing the result of a comparison) to express some more useful meaning instead. Usually the implausible construct is an error case — many language features assign meaning to otherwise meaningless operations, and this isn't hard to get right, because there's no question about whether the construct really was implausible.

It's much harder to apply in cases like chaining, where the implausible construct is not actually invalid: it's hard to tell how unlikely it is, and if it appears anyway (as e.g. a == (b < c) occasionally does), the semantic irregularity hurts. Irregularity is a problem even when redefining error cases, because it can produce incoherent semantics, like + overloaded for arithmetic and catenation. So this is not an easy pattern to follow, but it's one that has produced useful results.

No comments:

Post a Comment

It's OK to comment on old posts.