Re: Feasible or not...?
On Aug 4 2011, Dan Zuras Intervals wrote:
In its full generality, including on-the-fly heterogeneous
parallelism, you are no doubt correct that it is infeasible.
But you must admit that there are contexts in which it IS
feasible. Whether or not Arnold would use it in that case.
It's not just the contexts that are the issue, but the constraints
that are placed on the expressions. You don't need parallelism to
expose the problems - they are just more obvious in that.
All I propose is some statement of the form "It shall be
possible to deterministically evaluate an interval
expression" & not much more. How this is made to be
possible we can leave up to the implementers.
That doesn't simplify anything. I am assuming that you intend to
define what the result is when executing deterministically; if not, you
are going to have to define what you mean by 'deterministic'. You seem
to like the relatively simple specification:
Treat the input operands as exact mathematical values, evaluate
the result in mathematical terms (assuming infinite precision and
range) and deliver the closest enclosing interval.
However, while that's easy enough to specify, it is computationally
infeasible as it stands.
In order to make it feasible, you have to place draconian constraints on
what forms of expression are allowed, including forbidding any functions
other than the very restricted list in 754 (and I am not convinced about
some of them, for the entirety of their ranges and precisions).
If you want to specify it in terms of the 'basic operations', you are
BOTH going to have to forbid those functions, AND you are going to have
to persuade the language standards to change their arithmetic model of
50+ years' standing. The history of the Java Grande project is worth
studying in this context.
Together with statements like "It shall be possible to
parallelize the crap out of things" & "It shall be possible
to use (1) algebraic identities, (2) numeric tricks, & (3)
algorithmic improvements to tighten results" we have said
all we need to say to give the users the necessary
capabilities.
It doesn't mean we're done.
We still have to put reasonable limits on how loose a
parallel expression can get & when it is safe to change
what is written to something else.
I wish you the best of luck. Many people have tried to do that, but
none have ever got anywhere useful. It's trivial for trivial expressions,
and gets very rapidly intractable. The point is that you are requiring
compilers to do it automatically, which is the known intractable aspect.
Do you really think I am proposing a failing course of
action?
Yes.
Regards,
Nick Maclaren.