|Mathematics of if-else statements firstname.lastname@example.org (Bora Eryilmaz) (2001-09-05)|
|Re: Mathematics of if-else statements email@example.com (Adrian 'Dagurashibanipal' von Bidder) (2001-09-10)|
|Re: Mathematics of if-else statements firstname.lastname@example.org (2001-09-10)|
|Re: Mathematics of if-else statements email@example.com (Joachim Durchholz) (2001-09-11)|
|Re:Mathematics of if-else statements firstname.lastname@example.org (Dmitry Shaporenkov) (2001-09-11)|
|From:||"Joachim Durchholz" <email@example.com>|
|Date:||11 Sep 2001 00:06:53 -0400|
|Posted-Date:||11 Sep 2001 00:06:52 EDT|
Bora Eryilmaz <firstname.lastname@example.org> wrote:
> Are there any mathematical/logical approaches to analyze nested
> if-else statements in order to simplify or optimize them, or to
> understand the flow of successive tests.
Yes there is. However, optimizing it fully is exponential in the number
of variables (checking that two boolean expressions are the same is
exponential in the number of boolean variables involved; if you find a
better algorithm, we have P=NP, which would give you the Nobel prize for
mathematics if one existed).
In practice, the problem isn't too pressing since most programmers don't
write the type of nested ifs that you display. Analyzing legacy code
would be harder, but you can't still optimize code like
if foo then
if foo or bar then
One could still analyze it, for later improvement by a human.
There's another problem: Your example problem were of the form
if a > 0 then
if a < 20 then
An analysis that just replaces "a > 0" and "a < 20" with boolean
variables ("logical parameters") will entirely miss the fact that some
code is specific to the case 0 <= a <= 20. IOW the tool will entirely
miss transformation possibilities like
if a < 0 then
elseif a < 20 then
else -- a >= 20
If the code does a lot of arithmetic interval comparisons, this is
important... and at that point, we enter the endless world of
application-specific adaptations of the basic algorithm. You'll end up
writing an inference engine if you aren't careful ;)
Just to give you an idea what the theoretical limits of such a tool
would be; I don't know whether one exists.
Return to the
Search the comp.compilers archives again.