Re: [boost] Formal Review for Interval Library beginning

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-09-06 12:30:49

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, September 06, 2002 1:36 PM
Subject: Re: [boost] Formal Review for Interval Library beginning

> On Friday 06 September 2002 11:49 am, Fernando Cacciola wrote:
> > Could you elaborate specifically which uses could have tribool which
cannot
> > be covered with a comparison policy returning bool?
>
> That would be me :) Static analysis is one domain where we need a full
tribool
> result from interval comparisons. We might have the code:
>
> 1:  int x, y;
> 2:  // x and y get their values here
> 3:  if (x < y)
> 4:    foo();
> 5:  else
> 6:    bar();
>
> Now "execute" this program fragment symbolically, to cover _all_
executions in
> one run. At line 3, we need to compute the result of the conditional 'x <
y'.
> Three things might happen:
>   1) We might know that x < y will always be true (because the interval in
> which x's value lies is below the value in which y's value lies). Here, we
> can just take the 'if' branch and ignore the 'else' (on-the-fly dead code
> elimination, if you will).
>   2) We might know that x < y will always be false. Here, we ignore the
'if'
> branch and just take the 'else' branch.
>   3) We might not be able to determine what the value of 'x < y' will be,
so
> we end up taking both the 'if' and 'else' branches simultaneously.
>
> In this kind of static analysis (abstract interpretation), a 'bool'
variable
> in the program code will actually be represented by a tribool, because we
> might not know the actual value of the boolean variable when we analyze at
> compile-time.
>
OK, let me see if I understood correctly...

If the expression (x<y) is of type bool, then the static analysis of a
program containing it can 'trace' either of two execution branches.
If the expression (x<y) if of type tribool, then the static analysis of a
program containing it can 'trace' both branches simultaneously. I understand
that such an analysis is very useful, for instance, for optimizers (is this
what you are actually doing?)

But, is then tribool useful *only* for the static analysis of the program?
I mean, how is it useful for the program itself? How does it improve the
machine actual execution of it, the readability of the code? Or the ability
for the programmer to rearrange it differently to take advantage of the
intermediate tri-state?

Correct me if I'm wrong, but isn't this usage of tribool just the same as if
I put a comment after the "if" saying that the expression might be
indeterminate with a recognizable format so that the external analyzer can
parse it? (that is, it brings nothing to the program itself).

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