Re: Questions about srfi-77 Generic Arithmetic William D Clinger 18 Feb 2006 17:22 UTC

Bradley Lucier wrote:
> I'm trying to understand the R5RS-style Generic Arithmetic
> and I have some questions.

Those were excellent questions indeed.  Thank you, Brad.

You have spotted many miskates (!).  I agree with you and
with Mike's reply to you with regard to questions 4, 5, 6,
7, 11, and 15.  I have a little more to say about the others.

> 1.  In the first paragraph it says "The generic operations all
> implement inexact operations."  What does that mean?

I don't know either.  I propose the following change in wording:
Replace

    A number is inexact if it was written as an inexact
    constant, if it was derived using inexact ingredients,
    or if it was derived using inexact operations.  The
    generic operations all implement inexact operations.
    Thus inexactness is a contagious property of a number.

by

    A number is inexact if it was written as an inexact
    constant or was derived from inexact numbers.  Thus
    inexactness is contagious.  The generic operations
    generally return the correct exact result when all
    of their arguments are exact and the result is
    mathematically well-defined, but return an inexact
    result when any argument is inexact.  As indicated
    in the specification of individual operations, some
    exceptions to this rule are allowed (but not required).

    One general exception to the rule above is that an
    implementation may return an exact result despite
    inexact arguments if that exact result would be
    the correct result for all possible substitutions
    of exact arguments for the inexact ones.

While I'm at it, let me propose another correction.  The
current draft of SRFI 77 says "If two implementations produce
exact results for a computation that did not involve inexact
intermediate results or the results of numerical predicates,
the two ultimate results will be mathematically equivalent."

That is both untrue and misleading.  In SRFI 77, the fixnum
operations may return different exact results in different
implementations.  I regard that as a strong argument against
having the fixnum operations in the core language; I would
prefer they be banished to a library, so we can claim
implementation-independence for results of exact computations
that use only the core.  If fixnum? is banished from the core,
then the numerical predicates should return the same results
in every implementation when given exact arguments, so it is
misleading to mention them here.  I therefore propose to revert
the sentence quoted above to its R5RS form:  "If two
implementations produce exact results for a computation that
did not involve inexact intermediate results, the two ultimate
results will be mathematically equivalent."

Although that sentence will not hold for the core augmented
by certain libraries, e.g. the fixnum library, the reason for
that is that the libraries will be implemented differently in
different implementations.  I think people can understand that.

> 2.  In the first paragraph it says "A number is inexact if it is
> infinite, if it was written as an inexact constant, if it was derived
> using inexact ingredients, or if it was derived using inexact
> operations."
>     (a) I prefer some other word to "ingredients".
>     (b) What is an inexact operation?  The in* functions?  Or, do
> you mean every operation in this section?

In my reply to question 1 above, I proposed wording that
would remove the references to "ingredients" and "inexact
operations".  Mike suggested an alternative fix that
would involve some explanation of how "operations" are
distinct from "procedures".  I think Mike's fix would
create more confusion that it would resolve.  I prefer
the wording I proposed above.

>     (c) If 0 denotes exact 0 and 1 denotes exact 1, I prefer
>         (log 1) = (sin 0)=(asin 0)=(atan 0)=(tan 0)=...=0
>         and
>         (cos 0) = (exp 0)=1,
>         in the same way that I prefer (sqrt 4) = 2 (where 4 denotes
> exact 4 and 2 denotes exact 2).  Is this allowed in your proposal?

Not as written, but I regard that as a mistake.  See my
answer to question 3 below.

> 3. Paragraph 6 says "With the exception of inexact->exact,
> the operations described in this section must return inexact
> results when given any inexact arguments."

I think we should just delete that sentence, and rely on
the wording I proposed in my answer to question 1.

> 8.  Integer Divison.
> (a) I think it is a really bad design to have the basic
> operation of div+mod change when the second argument changes sign.

I don't have much problem with that.  These mathematical
operations aren't defined at zero, so they have to compare
against zero anyway.  To quote Egner et al, "the sign of
the modulus y determines which system of representatives
of the residue class ring Z/yZ is being chosen, either
non-negative (y > 0), symmetric around zero (y < 0), or
the integers (y = 0)."  Using the sign of y is ad hoc,
but it's an ad hoc choice anyway.

>    (b) I think it is a really bad design to have
>        (div x1 0) => 0
> It conflicts with the requirement in quotient+remainder,
> quotient, remainder, and modulo that "n2 should be nonzero".
> (Unless I read "should" here in the language lawyer sense,
> i.e., that it is totally nonprescriptive.) The only way I can
> think of making division by exact 0 make sense is by divorcing
> the meaning of "div" from any notion of mathematical division.

I don't have a strong opinion about this.  It is totally
ad hoc, but the alternative is a principled (not ad hoc)
hole in the domain of div.  I'm inclined to think that
passing 0 as the second argument to div is, in practice,
most likely an error for which it would be more useful
to signal an error than to return 0, but I'm willing to
listen to an argument for returning 0.  So far as I can
see, no such argument has been made.  In particular, the
paper by Egner et al contains no such argument.

> (c) This is one place where the Rationale says to refer to
> Egner et al. to see an argument why these procedures "are
> better suited than quotient and remainder to implement
> modular reduction." As a point of procedure, I would really
> prefer to have the arguments included in this document; I
> don't want to have to discuss my opinions of Egner et al.
> just to discuss my opinions of this specific proposal.

If Egner et al actually contained a rationale for this,
it would be completely proper to refer to that paper by
reference instead of including its rationale in the SRFI.
Since Egner et al do not actually offer a rationale for
defining (div x 0) to be 0, however, it is extremely
misleading for this SRFI to refer readers to that paper
for the rationale.  The reference to Egner et al should
certainly be dropped, and some rationale (if anyone can
come up with one) added to this SRFI.

> 9.  I don't agree that +inf.0, -inf.0, and +nan.0 should be in the
> domain of floor, round, ceiling, and truncate; returning these values
> as results implies, to me, that they are integers, and I believe they
> aren't integers, since they aren't rational.

The current draft of SRFI 77 says "These procedures return
inexact integers on inexact arguments that are not infinities
or NaNs, and exact integers on exact rational arguments."
I believe the intent of this was to exclude non-rational
arguments from the domain of floor, round, ceiling, and
truncate.  It would be simpler to replace the x in their
templates by q, thereby implying it is an error to pass
them a non-rational argument.  I believe the last two
examples, for (floor +inf.0) and (ceiling -inf.0), are
just mistakes.

Mike Sperber wrote:
> This is on the issues list---I'm almost convinced, but wonder what
> happens in representations where the argument isn't infinite or NaN,
> and the result still can't be represented as an inexact integer.

That is something to worry about, all right, but that has
to do with the range, not the domain.  I think we should
exclude non-rational arguments from the domain.

Back to Brad Lucier's questions:
> 12. (a) You give the examples:
>        (log +inf.0) => +inf.0
>        (log -1.0+0.0i) => 0.0+pii
>        (log -1.0-0.0i) => 0.0-pii
>        yet
>        (log -inf.0) => unspecified
>        Given the previous examples, shouldn't
>        (log -inf.0) => +inf.0+pii

Yes.  That was a mistake, which we'll fix.

>     (b) You don't say what (log 0) evaluates to; I would prefer it
> to be an error.

Me too.  In general, passing exact arguments for which
the exact result is not mathematically well-defined
should be an error.  We shouldn't require implementations
to return an inexact result (e.g. -inf.0) when given
exact arguments, and we shouldn't allow implementations
to return some random exact result.

> 13.  For sqrt:  Is your intention to no longer have sqrt return exact
> results when possible given exact arguments?

The language I proposed in my answer to question 1 would
*require* sqrt to return exact results when given exact
arguments.  Inasmuch as most implementations cannot
represent the mathematically correct result in most cases,
the description of sqrt should explicitly allow (but not
require) it to return inexact results even when given exact
arguments.

A similar exception to the general rule should be stated
for exp, log, sin, cos, tan, asin, acos, atan, expt,
make-polar, magnitude, and angle.  I'd argue for making
this exception for make-rectangular as well, to avoid
making rectangular coordinates privileged over polar.

Which brings up a larger question:  If neither make-polar
nor make-rectangular are required to return an exact
result when given exact arguments, what requires
implementations to provide non-real exact numbers?
I think the only requirement of that sort follows from
the ability to write things like 3+4i and to compute with
them.  Do we actually need to require implementations to
represent 3+4i exactly and to perform exact arithmetic
on non-real numbers?

> Or will
>      (sqrt 4) => 2
>      be allowed?  Your definition
>      (sqrt z) => (exp (/ (log z) 2.0))
>      seems to preclude it by putting in that inexact 2.  Do you mean
> the right hand side of this formula literally, with exp and log being
> Scheme procedures, or do you mean to represent the mathematical
> formula $e^{\log(z)/2}$ (in TeX notation).

When the meaning is mathematical, as here, we should use
mathematical notation instead of Scheme's syntax.

> 13 bis: Again for sqrt, why is
>         (sqrt -inf.0) => unspecified
>         and not
>         (sqrt -inf.0) => +inf.0i
>         You didn't have any problem with
>         (log 0.0) => -inf.0

That, too, was a mistake.  (sqrt -inf.0) should return
+inf.0i.

> 14. About expt: In contrast to my comments about sqrt, I note
> that your definition of expt uses mathematical notation to
> define it, so
>
>      (expt 5 3)  => 125, not 125.0
>      is not only allowed, but required?  Is
>      (expt 125 1/3) => 5
>      allowed?

As mentioned in my answer to question 13, I think expt
should be explicitly excepted from the general requirement
that operations return exact results when given exact
arguments.  I think, however, that expt should be explicitly
required to return exact results when both arguments are
exact, and the second argument is an integer.

Thus (expt 5 -3) would be required to evaluate to 1/125,
but (expt 125 1/3) would be allowed but not required to
evaluate to 5.

> 16.  About magnitude: Following Kahan, I think it should be required
> that
>      (magnitude z) => +inf.0
>      if either the real or imaginary part of z is infinite (even if
> the other part is a NaN).  Here Kahan is following the argument that,
> if the real or imaginary part is infinite, you would get the same
> answer no matter the (finite) value of the other part, so you should
> give that answer even if the other part is infinite or NaN.

I agree with you and Kahan on this.

Will