Conflation of Subtraction and Additive Inverse in Lisp.



Conflation of Subtraction and Additive Inverse in Lisp

In mathematics, the symbol - is used as name of two different operations: subtraction and additive inverse. For instance, that symbol has different meaning in the expressions (-3)+7 and (6-3)+7. There is no ambiguity. The edge case of subtraction

c - b1 - b2 - ... - bn

for n = 0, i.e. subtraction with zero subtrahends, is c, which is clearly different than additive inverse of c: - c. However, in prefix notation use of the same symbol for two different operators will cause ambiguity so (- c) can be interpreted as both additive inverse of c and the edge case of subtraction with zero subtrahends. Designers of almost all Lisp dialects have chosen to keep the same symbol and implement both operations. The decision is based on the number of operands: if there is only one operand, operator - behaves as additive inverse; if there is two or more operands - behaves as subtraction.

This decision rarely causes any problems with "hand written" expressions because humans automatically, without much thinking, reduce edge case of subtraction to minuend, so, we'll not see the edge case of subtraction in any mathematical formulas. However, if expressions are processed by programs the reduction of the edge case doesn't happen automatically. For instance, the program that simplifies arithmetic expression could contain the function that deletes zeroes from subtrahends. That function should accept expression as

(- c b1 0 b2 0 0 0)

as argument and return expression

(- c b1 b2).

However, simple implementation like this one in Newlisp
(define (simplify E)
  (let ((operator (first E))
        (minuend (first (rest E)))
        (subtrahends (rest (rest E))))
       (setf new-subtrahends (clean zero? subtrahends))
       (append (list operator)
               (list minuend)
               new-subtrahends)))
will not work correctly, because, for instance, (- 3 0) will be reduced into (- 3) and these two expressions have not the same value. Explicit treatment of the edge case is required:
(define (simplify E)
  (let ((operator (first E))
        (minuend (first (rest E)))
        (subtrahends (rest (rest E))))
       (setf new-subtrahends (clean zero? subtrahends))
       (if (empty? new-subtrahends)
           minuend
           (append (list operator)
                   (list minuend)
                   new-subtrahends))))
The second definition is significantly (~ 15%) larger and less consistent: one can get rid of subtrahends equal to zero only if he removes whole subtraction. On the other hand, edge cases for some other operations like addition are well supported in all Lisp dialects: not only that (+ a 0) can be safely simplified to (+ a), but even (+ 0 0) can be simplified to (+).

Hence, merging of the two operators into one could be design mistake. It would be, arguably, better to
  • define new operator for additive inverse and
  • extend definition of subtraction on special case with zero subtrahends.
Of course, S-expressions would look even less similar to arithmetic expressions, however, clarity and consistency over convenience is, I think, the element of the philosophy of Lisp.

It is even more surprising that this merging is generalized: division operator, / which is not used as divisional inverse in mathematical expressions is used on the way analogous to - in almost all Lisp dialects.

It is hard to expect change in existing Lisp dialects because lot of existing code uses "conflated operator", although I think that such changes should be, gradually, done: the past is finite and future is infinite. However, I think that for future Lisp dialects it would be better to keep the difference between subtraction (division) and additive (multiplicative) inverse.

2 comments:

  1. If (- 5) means something *different* from negation of 5, that would be error-prone because of what humans who write or read it might expect it to mean; hence, for Kernel I require applicative - to have at least two arguments.

    ReplyDelete
  2. 2011-05-20

    hi kaz,

    very interesting post.

    at first, when reading the first paragraph, i don't agree or i didn't find the way you expressed it being correct. Anyhow, i find the main point of your article interesting.

    i think, in some respect, mathematically there's no such thing as substraction, but only addictive inverse. So, if we take this view, then when we write 「a-b」 that “-” operator is really a sugar syntax for 「+(-b)」. If we take this attitude to lisp syntax, then, the expression 「(- a b)」 would be illegal. The function “-” would only allow one argument. This would be alternative way to resolve the syntax problem in your article.

    however, forcing the modern algebra foundation view of treating substractions as addition with inverse elements is really too much. The idea of substraction of taking n things out of m is perfectly fine by itself.

    so, overall, am not sure what to make of this.

    i've put my thought out similarly, here
    〈What's Function, What's Operator?〉
    http://xahlee.org/math/function_and_operators.html
    (in the section “Implicit Operators”.)

    ReplyDelete