Possreps and numeric types

From: Marshall <marshall.spight_at_gmail.com>
Date: 25 Mar 2007 10:30:45 -0700
Message-ID: <1174843845.282590.70570_at_d57g2000hsg.googlegroups.com>

This is more of me trying to sort out my confusion about possreps.

Lately I have been thinking about numeric types. I find the situation tremendously annoying. On the one hand, one sorely wants to faithfully model as many of the algebraic properties of numbers as possible. On the other hand, the real numbers are only available as an approximation, floating point numbers, and operations on these approximations do *not* possess the vast majority of these algebraic properties. Harumph.

I read a paper recently that was an analysis of the situation in the Scheme programming language. Scheme made some ambitious forays into the so called "Numeric Tower" or the hierarchy of natural, integer, rational, etc.


The paper had some recommendations as to how to do it better still. I found the paper quite convincing.

In the past I've been quite unhappy with the canonical example of possreps, which seems to be the pair
(cartesian, polar) for some type, sometimes Point, or
Bob has suggested Complex. It disturbs me that a cartesian (1,1) is not a value that can be represented in polar coordinates in a computer, because the radius is sqrt(1^2+1^2) = sqrt(2) = a transcendental number. Since transcendentals have an infinite number of nonrepeating digits (think pi) they are not representable as a digit sequence in base 2, base 10, or otherwise.
(There are other ways of representing numbers,
as the solutions to equations, but these are quite complicated and have their own problems.)

Anyway, a vague idea I have is something related to representation of numbers. Let us consider just the case of the rationals and the integers. Every integer is a rational. The rationals have all the popular and attractive algebraic properties we are so used to seeing featured in Us magazine and Entertainment Weekly. Therefore all those same properties apply to the integers. (Note I am not speaking of 32 bit integers.)

So what if we had an internal representation for integer similar to java.math.BigInteger, and an internal representation for rational that was a pair of integers. We can define *exact* operators for these types for basic arithmetic functions. (But not for trigonometric functions, logs, and roots.) The implementation of these operators for integer is likely to be significantly faster than the ones for rational. This starts to sound like possreps to me. (Although I don't think of possreps as being used with subsets.)

This differs from the cartesian/polar case, in that every integer values is *exactly* representable as a rational.

It also occurs to me that an integer is a rational where the denominator = 1. This starts to sound like specialization by constraint.

Crazier still, the fact that some rationals are integers and some aren't starts to remind me of parsing a string as a number. A possrep for an integer could be a sequence of ascii digit characters. Then constructing (selecting) an integer from a string
(succeeding only if the string represents an integer)
is isomorphic to parsing the string into a number, a la parseInt or atoi or whatever. Integer isn't a subset of String, but the Integer possrep sequence- -digit-chars *is* a subset of the String possrep sequence-of-chars.

Wacky wacky.

Anyway, this post is long and confusing enough for now. I think I'll go reread the relevant sections of TTM now. Again. I really must buy the 3rd ed.

Marshall Received on Sun Mar 25 2007 - 19:30:45 CEST

Original text of this message