floor() function and mathematical integers - the Scheme approach

[Tim Peters]

[Dennis E. Hamilton]
> Thanks to the lead from Greg Ewing, I see that Scheme has an approach
> that is along the lines I favor.  It is defined in section 6.2 of the
> Revised**5 Report on the Algorithmic Language Scheme.
>
> 	http://www.schemers.org/Documents/Standards/#ieee1178
>
> I am very interested in how this works out in practice as an aid to
> people working with numbers.

Well, I'm afraid Scheme isn't used much in real life.  You should also check
out the TeachScheme! project:

    http://www.cs.rice.edu/CS/PLT/Teaching/

> I resonate very strongly with the motivation for the Scheme approach
> and the care with which implementation and  representation of
> abstractions (i.e., mathematical entities) are addressed.

Scheme actually says very little about implementation; for example, a
conforming implementation needn't implement any numeric type other than
floating point.  Of course the extreme latitude allowed by the standard is
part of why it doesn't get used much outside academia.  Scheme is a jewel
when it comes to careful definition, though; but part of what it carefully
defines is what it refuses to guarantee.

> For the specific case of floor():  In Scheme if the operand is noted
> as inexact, the result will be also.

Sure, and not unique to floor.

> If the operand is noted to be exact, the result will be so long as it
> can be represented exactly.

"provided ... the mathematically expected result is representable as an exact
integer within the implementation".  But since they put so few constraints on
the implementation, it's a cross-implementation crapshoot whether, e.g., the
exactness of (floor 200000000000) you enjoy on one implementation will carry
over to another.

Note that the treatment of inexact in Scheme has a lot in common with an
extreme form of interval arithmetic, where the intervals are constrained to
be either a single point or unbounded (and that Scheme inexactness "is
contagious" follows from that).  From that view it should be clear where the
utility of "the exact bit" breaks down for serious work.  As a merely
suggestive example, (- x x) for inexact x usually yields an inexact 0 in
Scheme, despite that the true result is exactly 0 regardless of x.  The std
allows either result, but mandates neither, via the "An operation may,
however, return an exact result if it can prove that the value of the result
is unaffected by the inexactness of its arguments." escape clause.

IMO this doesn't act so much as a simplification of floating-point life, as
it adds yet another layer of guesswork about what a particular release of a
particular implementation happens to do.

> My sense is that most Schemes can always represent the exact result.

I think that's true.

> There is also provision for exceptions to be thrown, when the
> implementation isn't comprehensive enough to handle some cases.

"may either report the violation of an implementation restriction or it may
silently coerce its result to an inexact value".  "report" may mean no more
than displaying an error message to stderr; "silent" is self-explanatory
<wink>; there's no guarantee that you can handle it programmatically when it
occurs.

> This strikes me as very valuable for maintaining user confidence and
> also allowing people to work their way into the intricacies of numerical
> computation one toe at a time.

"One toe at a time" is what TeachScheme! is all about.  They define 4
different "language levels", across which the semantics of Scheme expressions
differ (but the std allows so much latitude they're all more than less
conforming interpretations).  In all but the "full Scheme" level, undecorated
(as to exactness) literals like 6.02e23 are treated as exact rationals(*).
The language Guido worked on before Python (ABC) also did that.  It may be
good for teaching (beats me <wink>), but in practice it sucks -- unbounded
rationals have a way of making extreme demands on memory and CPU usage as
computation proceeds unless you're an expert in their application.  So while
it's fine to sidestep some kinds of newbie confusion in brief numeric
examples, in the end you have to become expert in *its* quirks if you want to
get serious work done.

Computer numerics is hard stuff, and all approaches bristle with surprises of
one kind or another.

pick-your-poison-ly y'rs  - tim


(*) The Scheme std clearly says the undecorated literal 6.02e23 denotes an
inexact number, so 3 of TeachScheme!'s 4 language levels are fudging on that.