Re: [boost] Formal Review for Interval Library beginning

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-09-04 14:47:01

Hello,

I haven't looked at the library yet, but I've been following closely the
review discussions.
Before I give my formal review, there is one particular thing that worries
me and which I'd like to discuss right now before the issue is resolved:
comparison semantics.

{note: I'm sending this just about the time I received Joel's "interval
comparison operators"...  which initially seems fine to me. Maybe my post
here have become obsolete already :-) But here it goes anyway.}

It is clear to me that there is more than one way to interpret the semantics
of relational expressions between intervals, so it is clear -to me at least-
that some mechanism to allow the user to choose one interpretation is
needed.
However, I'm not entirely satisfied with the comparison-policy approach, but
I agree with the library authors that a fixed semantic is unlikely to cover
most usage cases, so I can't tell right now if the policy scheme is the only
viable option; it could be, but I'd like to explore the issue at least a bit
further.

Let's start by noticing that the value of a relational expression between
intervals, say (x<y), is not really required to be intrinsically boolean.
That is, we could define relational operations as Profil/BIAS does. Herve
pointed out that there exist a mathematically-sound and consistent
definition for this relational expressions.

If we follow this path: that is, we define that relational expressions are
not boolean, then what we need is a mapping between such expressions and a
boolean value.
In C++ terms, this decoupling would be expressed by an interface like this:

relproxy<interval> operator < ( interval const& x, interval const& y ) ;

bool certainly ( relproxy<interval> const& expr ) ;
bool possibly  ( relproxy<interval> const& expr ) ;

which would yield this idiom:

my_interval x,y;
if ( certainly(x<y) )
 ....

A clear advantage of this interface is that the relational functions
(cerle,posle,etc...) don't need the 'operation postfix' le,e,ge,etc..
anymore.
Another advantage is that this idiom can be used in generic code.

A potential disadvantage is that performance can be compromised; but I'd
favor this interface anyway since the C++ language has enough tools to make
this idiom efficient, thus it is really an issue of compiler technology and
not an intrinsic penalty of the interface.

Another disadvantage is that is doesn't necessarily solves the current
problem :-)

How is:  if ( x < y ) defined?

If the interval relational expression is required to have an implicit
conversion to bool, then we need a mechanism to let the user select the
mapping for the implicit conversion, and so we end up with an interval
policy again.
In this case, the proxy approach only changes the syntax of the
function-based relational expressions: from 'certainly_lower_equal(x,y)' to
'certainly(x<y)'.

OTOH, it would also be possible to simply not support implicit boolean
conversions from a relational expression. That is, the following would fail
to compile:

if (x<y) ...

and it would require an explicit mapping as in:

if (possibly(x<y)) ...

This would permit us to remove the comparison policy giving the interval
type a consistent relational semantic, but it would be only for those users
willing to write code with the explicit consideration that the relational
expression does not have a uniquely defined boolean value.

I for one, use relational operators directly, as in "if (x<y)", ONLY when
there is just one well-known and uniquely defined boolean meaning for (x<y)
AND the relational identities (such as "<=" implies "< || ==", or ">" is
equivalent to "!(<=)") are exactly those defined for totally ordered types.
In cases like this, when even if there is a fixed semantic for, say,
operator <, the usual identities (as defined by STL) don't hold, I always
choose to leave relational operators completely out and use clearly named
functions instead (or as I've proposed here, make them proxies that require
explicit boolean mappings).

Anyway, I admit that most users will find this annoying.

A note about comparison policies and tribool:

What I've just suggested is just a generalization of the tribool approach
presented by Douglas Gregor. Unfortunately, IMHO, the particular way in
which his idea was adopted is even worst that the current design.
AFAICT, his idea was to remove entirely the comparison policy and
consistently use tribool as the type of the relational expressions. If
tribool were to be used, comparison policies are not only unnecessary but
also incongruent with the role of tribool.
IMHO, both strategies cannot coexist because they have overlapping purposes.
This implies that tribool couldn't even be an additional pre-canned policy.

But the idea that was took instead was to allow the user to specify the type
of the relational expression (as a return type in the comparison policy).
IMHO, adding even a new level of undefinition by extending the policy
interface to allow the user to freely specify the type of the relational
expression is not an appropriate design; let me explain:

There are what I call 'totally-specified policies'. These are policies which
allow the user to choose one out of a small set of *precisely* defined
options. The resulting class has indeed a totally specified semantic, even
if such a semantic is 'hidden' in a typedef.
But there are also what I call 'meta-specified policies'. These are policies
which are used to PUSH DESIGN DECISIONS ONTO THE USER. (Let's convey that
the base number type is not a policy). I call these policies meta-specified
because the semantics they represent are not precisely specified but mostly
bounded by behavioral constraints or given by pseudo-definitions.
Meta-specified policies are very useful for allowing the user to choose
internal class behaviors, or in generative systems were the imprecise
semantics of the result is well expected.
However, IMO, using a meta-specified policy to give semantic to a type which
is expected to have consistent and totally-specified semantics is plain
wrong.

Therefore, I strongly recommend that if comparison policies are retained,
their return type shall not be left user-specified and tribool shall not be
supported as an option.

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com