# Re: Mathematics of if-else statements

## "Joachim Durchholz" <joachim_d@gmx.de>11 Sep 2001 00:06:53 -0400

From comp.compilers

Related articles
Mathematics of if-else statements bora@nope.com (Bora Eryilmaz) (2001-09-05)
Re: Mathematics of if-else statements avbidder@vis.ethz.ch (Adrian 'Dagurashibanipal' von Bidder) (2001-09-10)
Re: Mathematics of if-else statements old_dnepr@yahoo.com (2001-09-10)
Re: Mathematics of if-else statements joachim_d@gmx.de (Joachim Durchholz) (2001-09-11)
Re:Mathematics of if-else statements dsha@tepkom.ru (Dmitry Shaporenkov) (2001-09-11)
| List of all articles for this month |

 From: "Joachim Durchholz" Newsgroups: comp.compilers Date: 11 Sep 2001 00:06:53 -0400 Organization: Compilers Central References: 01-09-020 Keywords: optimize Posted-Date: 11 Sep 2001 00:06:52 EDT

Bora Eryilmaz <bora@nope.com> 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
do_something
if foo or bar then
...
end
end
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
...
else
...
end
...
end
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
...
end
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.

Regards,
Joachim

Post a followup to this message