Re: div0 and mod0

[William D Clinger <will@xxxxxxxxxxx>]

I apologize for overlooking Brad's message of 25 July
on the subject of "div0 and mod0".

Brad Lucier wrote:

> div0 and mod0
> 
>     3. are useful in no algorithms of which I am aware;

The current revision of the reference implementation for
SRFI 77 contains the following uses of div0 and mod0.
(I have edited this to remove some debugging code that
would be removed in the next major version anyway.)

Similar uses of div0 and mod0 are found in the definition
of fixnum*/carry, and similar uses will be found in a more
efficient version of the bignum code if I ever get around
to writing it.

; The challenge of fixnum*/2 is to avoid overflow when
; computing the intermediate results.  That is done here
; by computing modulo 1/2 the usual modulus, which this
; code assumes to be an even power of two.
;
; (a * m + b) * (c * m + d)
; = (a * c) * m^2 + (a * d + b * c) * m + b * d

(define (fixnum*/2 x y)
  (call-with-values
   (lambda () (fixnum-div0+mod0 x *half-modulus*))
   (lambda (a b)
     (call-with-values
      (lambda () (fixnum-div0+mod0 y *half-modulus*))
      (lambda (c d)
        (let* ((a*d (r5rs:* a d))
               (b*c (r5rs:* b c))
               (b*d (r5rs:* b d))
               (a*d+b*c (fixnum+/2 a*d b*c))
               (hibits (fixnum-mod a*d+b*c *half-modulus*))
               (hibits (if (fixnum>? hibits *half-high*)
                           (fixnum- hibits *half-modulus*)
                           hibits))
               (hi (r5rs:* hibits *half-modulus*))
               (lo b*d))
        (fixnum+/2 hi lo)))))))

> Yet quotient and remainder have been removed by this
> SRFI, with the only rationale being:
> 
> Well, no rationale is given, only the bald statement
> 
> 
> The quotient, remainder, and modulo procedures were removed.
> 
> 
> This behavior might be characterized as "program
> language design by assertion".

Part of the rationale for removing remainder runs
something like this:

For any modulus n2, we would like to project arbitrary
integers onto a set of n2 distinguished representatives
of Z/n2.  The R5RS remainder procedure does not do this:
it projects onto a set of 2*n2-1 representatives.  The
mod, mod0, and R5RS modulo procedures all project onto
a set of n2-1 representatives, but the sets are different:

    mod:    { 0, 1, ..., |n2| - 1 }
    mod0:   { - |n2|/2, ..., |n2|/2 - 1 }      if n2 is even
            { - (|n2|-1)/2 , ..., (|n2|-1)/2 } if n2 is odd
    modulo: { - n2 + 1, ..., 0 }               if n2 is negative
            { 0, ..., n2 - 1 }                 if n2 is positive

With mod, the representatives are non-negative, which is
advantageous when projecting to an index into Scheme's
0-origin structures (vectors, strings).

With mod0, the representatives are centered (or nearly so)
about zero, which is advantageous when working with two's
complement, which shows up in R6RS fixnum arithmetic and
in R6RS bytes objects.

With modulo, the representatives have the sign of the
divisor.  Although a lot of hardware works this way, and
many programming languages work this way, I don't know of
use cases where this is really what you want.  Since the
modulo procedure was an orphan in the R5RS, without any
matching division operator, the choice was between adding
a division operator that plays well with modulo, or to
remove modulo.  Not knowing of any use cases for modulo
that are as compelling as those for mod and mod0, we left
it out.

> I think these two decisions should be reversed and a
> division operator associated with the existing modulo in
> RNRS be added.

I expect the quotient, remainder, and modulo procedures to
be provided by an R5RS-compatibility library.  I believe
that to be the right place for them if the primary argument
for keeping them is backward compatibility with R5RS and
earlier.

Bear, Marcin Kowalczyk (citing Knuth, but Knuth's argument
as cited doesn't hold for negative divisors, so Knuth seems
to be neutral between mod and modulo), and Brad Lucier have
all argued for modulo and a matching division operator
(absent from R5RS), but none have yet cited applications
for which modulo works better than mod.  I'd like to see
examples.

Bear and Kowalczyk, citing Knuth, have argued against
quotient/remainder on the grounds I gave above, while
Egner et al gave another argument against remainder.
Kowalczyk and Lucier have cited the hardware-friendliness
of quotient/remainder, but I don't regard that by itself
as an advantage; I'd like to see examples for which the
quotient/remainder behavior is what you'd actually want,
as opposed to the div/mod or div0/mod0 behavior.

Will