11 Sep 2001 23:13:49 -0400

Related articles |
---|

Mathematics of if-else statements bora@nope.com (Bora Eryilmaz) (2001-09-05) |

Kleene Algebra (was: Mathematics of if-else statements) whopkins@csd.uwm.edu (2001-09-11) |

From: | whopkins@csd.uwm.edu (Alfred Einstead) |

Newsgroups: | comp.compilers |

Date: | 11 Sep 2001 23:13:49 -0400 |

Organization: | http://groups.google.com/ |

References: | 01-09-020 |

Keywords: | optimize |

Posted-Date: | 11 Sep 2001 23:13:49 EDT |

"Bora Eryilmaz" <bora@nope.com> wrote in message news:01-09-020...

*> 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.*

Control flow structures are Kleene algebraic. Dexter Kozen has

numerous papers on Kleene algebra (including, particularly, Kleene

algebra with tests) at www.cs.cornell.edu/kozen

*> For example, if I have*

*> if (a > 10) {*

*> if (a < 20) {*

*> statement1;*

*> } else {*

*> statement2;*

*> }*

*> } else {*

*> statement3;*

*> }*

Defining the operator (A?B:C) as (A B) + (!A C), you'd probably write

this as

(a>10)? ((a<20)? S1: S2): S3

The statements (a>10), (a<20) reside in a boolean subalgebra of

the Kleene algebra. Substituting a value in for a and reducing

the statements (a>10), (a<20) to 1 or 0 will yield

If a is < 10 --- 1? (1? S1: S2): S3 = 1 (1 S1 + 0 S2) + 0 S3 = S1

If a is >= 20 -- 0? (0? S1: S2): S3 = 0 (0 S1 + 1 S2) + 1 S3 = S3

Otherwise ------ 1? (0? S1: S2): S3 = 1 (0 S1 + 1 S2) + 0 S3 = S2

What's interesting to notice is that a proper account of control flow

structure necessarily involves consideration of the more general type

of branching represented by "+". This is actually the fundamental

concept, not the if-then-else.

Algebraically, you'd write:

(a>10) ((a<20) S1 + (a>=20) S2) + (a<=10) S3

= (a>10)(a<20) S1 + (a>10)(a>=20) S2 + (a<=10)S3

A Boolean algebra is a partially ordered algebra in which the

ordering relation B >= A means (A implies B). This is

equivalently rendered as:

B >= A <--> AB = A

since AB = greatest lower bound of {A,B}. Therefore,

(a>10)(a>=20) = (a>=20).

So, the original statement reduces to:

(a>10)(a<20) S1 + (a>=20) S2 + (a<=10) S3

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.