Re: Motion 52 -- Time to revive the "Expression" subgroup?
On 2013-11-03 15:57:06 -0500, Michel Hack wrote:
> At the end of Clause 6.1 (c) one of the effects of repeated
> subexpressions is mentioned:
>
> "If the algebraic expression is evaluated naively, such a
> subexpression is evaluated more than once, which affects
> efficiency but not the numerics of what is computed."
>
> Assuming no side-effects, this may be the only worry for *point*
> evaluation.
This is not clear. By "not the numerics of what is computed", does
this mean the exact result (i.e. assuming infinite precision)? But
this would be misleading after "evaluated".
If this means the computed result on a machine, this is obviously
incorrect in practice. See
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
due to extended precision (some reported problems are actually not
bugs: if IEEE 754 is not supported, then the C language does not
guarantee that 1/3. - 1/3. gives 0). There may be similar problems
with languages that allow a FMA to be used for x*y+z.
> To this I wanted to add:
>
> Perhaps more significantly, when evaluated in interval mode,
> multiple instances of the same variable can lead to excessive
> widening of the final result; see Clause 6.x below.
No, this is unrelated: you would have the same problem with the
evaluation using forms (a) and (b) -- as you say in your PS below.
What you need is a rewrite of the structure of the expression to
make a difference.
> I even drafted such a Clause 6.x, to be inserted between current
> 6.3 (The FTIA) and 6.4 (Related Issues):
>
> 6.x. The dependency issue. When the same variable occurs multiple times
> in an expression, and the expression is evaluated in interval mode, there
> are two possible interpretations: (a) the interval variable denotes a
> single uncertain value, or (b) the interval denotes a range of values.
> In case (a) there would be an implied dependency between two instances
> of the same variable that is not present in case (b). The most extreme
> example might be x-x which would be the singleton [0] when viewed as (a),
> but would be an interval twice as wide as x when viewed as (b). Since
> the evaluator (interpreter, compiler) typically does not know the intent,
> it must assume view (b) in order to guarantee containment and the FTIA.
Note that these two possible interpretations are both valid for the
3 forms. Perhaps instead of "variable", you could say "input" so that
it applies to the computational graph.
> It also means that it must be possible to control compiler optimizations
> that turn x-x into 0, x+x into 2*x, or x*x into sqr(x) -- and it explains
> why the standard requires the presence of a Square function sqr().
I wouldn't call that a compiler optimization, as you change the
semantics. IMHO, the semantics could be controlled in the language,
via a pragma (directive) or different types (I prefer the latter).
[...]
> P.S. Initially I thought the common subexpression issue was peculiar
> to the "algebraic expression" view, 6.1 (c), but John reminded
> me that the issue is present already in the "formal expression"
> view, which allows the output v of one formal operation to be
> an input to several others, even though all inputs to a formal
> operation (the u_i) have to be distinct variables. So my 6.x
> is indeed general, and not particular to 6.1 (c).
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)