Re: Mathematics of if-else statements

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

Return to the comp.compilers page.
Search the comp.compilers archives again.