Re: about emp (was: Motion 42: NO)
Le dimanche 17 février 2013 à 14:32 +0000, John Pryce a écrit :
> > Either the implementation knows that the point function being computed
> > is not defined and it returns empty_emp or empty_ill, or it does not and
> > it returns [0,0]_trv or any superset. Any other behavior is meaningless.
>
>
> Guillaume's point (maybe written tongue in cheek) seems equally unsatisfactory that x*x might actually be x*y:
Actually, I was serious. See below for four different use cases where
the product of two intervals at the same memory location actually means
x * y. When I said that breaking "referential transparency" was
unconceivable, I meant it.
> On 13 Feb 2013, at 10:05, Guillaume Melquiond wrote:
> > Le lundi 11 février 2013 à 03:07 +0100, Vincent Lefevre a écrit :
> >> Because when considering decorations (and only in this case), reasoning
> >> is based on the *point functions*, not their interval version. The point
> >> function is here f(x) = sqrt(-x*x-1).
> >
> > You do not know that! Who said that the point function was f(x) =
> > sqrt(-x*x-1)? Is there anything in the motion that prevents the point
> > function from being f(x,y) = sqrt(-x*y-1)? In that case, the domain is
> > definitely not empty.
> >
> > Do not forget about this fundamental principle of modern programming
> > languages, "referential transparency"...
>
> P1788 does not formally define the meaning of "expression", but in the
> forthcoming Draft 7.x, part of Ch 1 says semi-formally some things
> that an expression is, and is not, as guidance. I propose that it
> should also include this:
> (*)
> +---------------------------------------------+
> |An implementation SHOULD treat an arithmetic |
> |expression as meaning exactly what it says. |
> +---------------------------------------------+
> This would imply, for us, that
> (**)
> +---------------------------------------------+
> |The standard's design decisions shall assume,|
> |where relevant, that this is the case. |
> +---------------------------------------------+
>
> That is, any section of code (possibly part of a larger expression)
> that defines an arithmetic expression f(x_1,...,x_n) in distinct code
> variables x_1,...,x_n, SHOULD be regarded as defining the real
> function of those variables in the naive way.
First, what is a "code variable"? Just for fun, I asked Google about it.
The answer is rather edifying: the twenty first results did not have
much to do with programming languages, at least not the common ones. So
you will have to come with a definition of it that compiler and library
people can relate to.
For instance, what about object-oriented languages that use data
members? Are they code variables? What about functional and/or
data-oriented languages that use binders instead of variables? Are they
code variables? What about languages that do not have anything related
to variables? (This last question is rhetorical; while possibly the most
pervasive languages, it is doubtful people would ever perform interval
computations with them, though people in aerospace might disagree.) What
about function arguments? What about formal parameters? And so on.
Now let us move to more practical considerations. Let us assume that the
text of the standard ends up giving a clear way to infer an expression
from the user program. How, as a library implementer, should I implement
it in practice? For instance, in C++, I could go the following way for
multiplication:
interval operator*(interval const &x, interval const &y) {
if (&x == &y) return square_of(x);
else return product_of(x, y);
}
I test whether the two arguments point to the same memory location, and
if they do, I compute the square instead of the product. Seems clever
and foolproof, right? Wrong. If any of the following happens, the answer
will be incorrect:
1. the user performs memoization (some systems also do it, e.g. Maple);
2. the user performs hash-consing;
3. the environment performs maximal sharing (e.g. garbage collection or
serialization);
4. the compiler performs optimization (e.g. common subexpression
eliminations).
So, let me state it clearly: I am convinced it is impossible to write a
library that follows your meaning of expressions, whatever the
programming language. Now, it would be possible to achieve it by
modifying compilers, but you have to wonder whether a feature (from a
non-language standard) that requires modifying compilers is actually
useful.
Just to be complete, I want to point out that it is impossible to write
a library, but only if you expect expressions to be inferred implicitly
from the user code. Now, if you relax your expectations and depend on
the user to explicitly provide expressions, this becomes a whole
different matter. You can then rely on quotation, reflection,
reification, or whatever related technique your programming language
support (all of them do, with more or less syntactic sugar). For
instance, I can write a C++ library that supports the following syntax:
evaluate(sqrt(- _1 * _1 - 1), interval(-1, 1))
But notice how different it is from what you suggest. In particular, the
user explicitly wrote the syntax tree of the expression; it was not
inferred from the program.
Note that this issue also occurs with constant constructors. For
instance, nobody on this mailing-list expects interval(0.1) to return an
enclosure of one tenth for languages that do not support decimal
arithmetic. We all know that the compiler will have replaced it by the
binary floating-point number the closest to one tenth beforehand. As a
consequence, we would all suggest to write it interval("0.1") instead.
That process perfectly matches what a quotation is.
Best regards,
Guillaume