Kleene Algebra (was: Mathematics of if-else statements)

"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

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