11 Sep 2001 00:06:53 -0400

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) |

From: | "Joachim Durchholz" <joachim_d@gmx.de> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.