HaloO,

Darren Duncan wrote:
Michael G Schwern wrote:
TSa (Thomas Sandlaß) wrote:
I want to stress this last point. We have the three types Int,
Rat and Num. What exactly is the purpose of Num? The IEEE formats
will be handled by num64 and the like. Is it just there for
holding properties? Or does it do some more advanced numeric
stuff?


"Int", "Rat" [1] and "Num" are all human types. They work like
humans were taught numbers work in math class. They have no size
limits. They shouldn't lose accuracy. [2]

As soon as you imply that numbers have a size limit or lose
accuracy you are thinking like a computer. That's why "num64" is
not a replacement for "Num", conceptually nor is "int64" a
replacement for "Int". They have limits and lose accuracy.

All agreed.

I also agree. But I want to work out a bit more of the semantics
of Num. Int and Rat are easy insofar as there are arbitrary precision
implementations. This is not the case for irrational numbers. One
route here is to go into symbolic math. But this is at best the task
of add-on modules.

The concept I have in mind is the subtype chain Int <: Rat <: Num
with automatic upgrades and non-automatic downgrades. That is

    my Int $i = 2/3;
    my Rat $r = sqrt(2);

are conceptually failures and result in exceptions which can of course
be converted to warnings or automatic conversions by pragmas. I see
the Complex type as a parametric type that replicates the above subtype
chain as Complex[Int] <: Complex[Rat] <: Complex[Num]. This should be
the general scheme for other types that implement numeric operations.

The Num type is basically an arbitrary precision float as Duncan has
proposed together with an .irrational flag that marks it as non-Rat.
E.g. the Num implementation of sqrt might even flag sqrt(4) as non-Rat
and actually not even achieve 2 numerically. This can be remedied as
follows

   subset SqrInt of Int where { $_ == any(1..* »**» 2) }

   multi sub sqrt (SqrInt $i --> Int)
   {
      # calculate approximate result that will be almost an Int
      # cast is needed to avoid endless dispatch
      return round( sqrt( Num $i ) );
   }

   subset SqrRat of Rat where { .numerator ~~ SqrInt &&
                                .denominator ~~ SqrInt }

   multi sub sqrt (SqrRat $r --> Rat)
   {
      # dispatches to sqrt:(SqrInt --> Int)
      return round( sqrt( $r.numerator ) ) /
             round( sqrt( $r.denominator ) );
   }

The latter implementation has the drawback that it needs to produce
two possibly large Ints as intermediate results. So we could instead
call the approximate sqrt with $r directly with appropriately set
precision demands.

The specced behavior of / for two Ints falls out naturally because it
returns a Num that simply doesn't happen to have the non-Rat flag set
and as such is assignable to a variable with a Rat constraint. It's
also easy to get typesafe assignments of Rats with .denominator == 1
to Int variables. That is we have the conceptual subsets

  subset Rat of Num where { !.irrational }

  subset Int of Rat where { .denominator == 1 }

Functions like sin are not required to flag sin(pi/6) == 1/2
as rational. They might not even achieve the numeric equality
unless some additional definitions are made for the equality
of Nums with some epsilon.


[2] "Num" should have an optional limit on the number of decimal places
    it remembers, like NUMERIC in SQL, but that's a simple truncation.

I disagree.

I disagree as well. But Num should provide an interface to access the
underlying approximations made by functions that operate on Nums. The
default will be a relative error i.e. a ratio between the difference
to the exact value and the exact value---note that this error itself is
approximate. This means that the absolute error can be quite large for
large numbers. This estimation strategy allows an implementation of Num
on top of Rat.

For starters, any "limit" built into a type definition should be defined not as stated above but rather with a simple subtype declaration, eg "subtype of Rat where ..." that tests for example that the Rat is an exact multiple of 1/1000.

The interesting thing that occurred to me is that constraints on
variables are known at compile time. If we define that the point
in a computation where the rounding takes place is the moment when
it comes to storing a value in a variable then the parser can
propagate the accuracy of the constraint to all functions called
in the expression tree. This means we need a definition language
how the Num type performs its approximations. This is then used
in the where clause of subset declarations of Num.

This means that we have an extensible set of operators and functions
that do numerics. All these functions have an approximation interface
that the compiler generates input for. If the programmer wishes she
can also use that interface directly, of course.

Second, any truncation should be done at the operator level not at the type level; for example, the rational division operator could have an optional extra argument that says the result must be rounded to be an exact multiple of 1/1000; without the extra argument, the division doesn't truncate anything.

These extra arguments are quite annoying to use. My proposal above
automates this on a per expression basis. If a long computation
shall be split into several expressions then intermediate variables
can still be defined to have high precision.


Regards, TSa.
--

"The unavoidable price of reliability is simplicity" -- C.A.R. Hoare
"Simplicity does not precede complexity, but follows it." -- A.J. Perlis
1 + 2 + 3 + 4 + ... = -1/12  -- Srinivasa Ramanujan

Reply via email to