My comments Marcin 'Qrczak' Kowalczyk (19 Oct 2005 18:37 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 19:17 UTC)
Re: My comments Thomas Bushnell BSG (19 Oct 2005 19:44 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 19:55 UTC)
Re: My comments Thomas Bushnell BSG (19 Oct 2005 20:11 UTC)
Re: My comments John.Cowan (19 Oct 2005 20:10 UTC)
Re: My comments Thomas Bushnell BSG (19 Oct 2005 20:13 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 20:25 UTC)
Re: My comments Marcin 'Qrczak' Kowalczyk (19 Oct 2005 20:23 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 20:36 UTC)
Re: My comments Marcin 'Qrczak' Kowalczyk (19 Oct 2005 21:36 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 21:42 UTC)
Re: My comments Bradd W. Szonye (19 Oct 2005 22:08 UTC)
Exactness (was Re: My comments) bear (20 Oct 2005 01:50 UTC)
Re: Exactness Thomas Bushnell BSG (20 Oct 2005 03:45 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (20 Oct 2005 09:13 UTC)
Re: Exactness Bradd W. Szonye (20 Oct 2005 20:15 UTC)
Re: Exactness bear (20 Oct 2005 22:09 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 02:08 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 03:05 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 08:15 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 18:38 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 20:12 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 20:29 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 20:38 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 20:44 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 21:20 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 21:44 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (21 Oct 2005 22:18 UTC)
Re: Exactness Thomas Bushnell BSG (21 Oct 2005 22:48 UTC)
Re: Exactness Marcin 'Qrczak' Kowalczyk (22 Oct 2005 00:34 UTC)
Re: Exactness Thomas Bushnell BSG (22 Oct 2005 01:02 UTC)
Re: Exactness Per Bothner (22 Oct 2005 00:59 UTC)

Re: Exactness Marcin 'Qrczak' Kowalczyk 20 Oct 2005 09:13 UTC

bear <xxxxxx@sonic.net> writes:

> The problem with exactness and inexactness, it appears, is that
> many implementors don't feel that it's worth implementing fully.

I disagree. The problem is that R5RS tries to describe it as one of
two fields of a number, the other being its value - while in reality
it's a predicate about the representation of the value, not
independently settable.

> And they have a point, I guess, in that a full implementation of
> it (fully orthogonal to type information) adds overhead to each
> and every fundamental mathematical function.

Suppose we have two flonums tagged as exact. You divide them, and the
result is not a finite binary fraction, so the implementation can't
use the same representation for the result. What should it do?

a) Represent it in a flonum tagged as inexact.
b) Represent it as an exact ratio of two integers.

In case a) exactness of flonums would be almost useless, because most
fp data except initial inputs would be inexact - most fp operations
must round data. Not only division; mere multiplication quickly runs
out of space for representing all digits. Since exactness doesn't
influence how computation proceeds, you could use it only to check the
confidence of the implementation that the answer is correct, which is
not strictly true anyway because of predicates returning exact
booleans.

In case b) using flonums to represent exact numbers would be almost
useless, because most exact data except initial inputs would be
converted to ratios - most fp operations must use some other type for
the result to represent it fully accurately. The implementation could
as well use ratios for all exact rational numbers and results will be
the same, so exact doubles are redundant.

R5RS doesn't specify what happens. For the first sight it seems to
suggest a), but actually it encourages to implement b). It mandates it
even for operations that integers are closed under, as long as the
given exact integer is representable at all.

I claim that the practical utility of numbers represented as fixnums,
bignums or ratios but tagged as inexact is close to zero, and similarly
for flonums tagged as exact.

> So they usually make the dodges and hacks that the standard fails to
> forbid, specifically making exactness correspond to representation
> type information rather than being orthogonal to type.

And that's good, it's not orthogonal. If it was, using different
representations for numbers of the same value and the same precision
would be redundant. R5RS even specifies that such numbers would be
indistinguishable (even more: the precision is not compared but the
exactness only, which is wrong if there are several possible amounts
of inexact precision, and SRFI-77 fixes that).

> Furthermore, treating exactness as type information actively
> messes up people who are trying to use it as exactness; having
> different numeric ranges and precisions for example, for exact
> and inexact numbers leads to all kinds of inconsistencies and
> problems.

I presume then that since (factorial 100) preserves all 158 digits,
you want (factorial 100.0) to produce a result with 158 digits but
tagged as inexact, right? But this would make impossible to reason
about complexity of numerical algorithms. Fixed-size flonums have a
constant cost of primitive operations; this would no longer be true.

People can be taught about this problem for rationals (or learn about
it in the painful way), which is a necessary evil. But taking away
the remaining tool for approximate computation with constant cost of
primitive operations would be impractical.

> And the question comes down to this; in view of the widespread
> rebellion against fully implementing exactness among scheme system
> authors, and the harm caused by conflating exactness with type,
> should exactness remain part of the standard?

It should be described as a property which can be inferred from the
representation, not as an independently settable field.

> Or maybe we should make the whole concept optional, and explictly
> forbid any exact/inexact distinctions at all except in implementations
> where it really *is* information orthogonal to representation type.

Are there any implementations where it is?

> I'd like to see more full implementations of exactness, but I'm not
> going to recommend that the standard actually require it; this
> appears to be a situation where making a demand that very few would
> bother to implement would just undermine the authority of the
> standard.

Indeed. If everybody ignores something in the standard, it's should
raise suspections that the standard has made an unfortunate decision.

--
   __("<         Marcin Kowalczyk
   \__/       xxxxxx@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/