Fri, 7 Apr 89 11:22:07 GMT

Related articles |
---|

short circuit evaluation of boolean expressions harvard!NSS.Cs.Ucl.AC.UK!cs.qmc.ac.uk!keithc (1989-04-07) |

short circuit evaluation of boolean expressions keithc@cs.qmc.ac.uk (Keith Clarke) (1989-04-07) |

Date: | Fri, 7 Apr 89 11:22:07 GMT |

From: | Keith Clarke <keithc@cs.qmc.ac.uk> |

I'm trying to establish who has priority for the following code

generation algorithm, for the short-circuit evaluation of

boolean expressions. I hope the algorithm will be of interest,

as it's really short, neat & gives excellent results.

I *don't think* it is very widely known.

It was invented by R.Bornat & P.Gardner at the University of

Essex in the '70s, and described in Bornat's book

"Understanding and writing compilers", Macmillan, London, 1979.

I really want to know if anyone else can cite an earlier

publication of the same idea. I know of many strategies that

are similar - it is the *boolean constant* parameter (see below) that is

crucial, as this ensures that the generated code contains no

redundant jumps, jumps over jumps or jumps to jumps.

The version I give here is much simplified. It is easy to

include 'relational expressions' (comparisons) in the same

framework.

The code generator works on a tree representation of the

source expression; it has three other parameters. The code

generated may jump to the first label, but only of the

expression evaluates to true; it may jump to the second label,

but only if the expression evaluates to false; it may

fall-through, but only if the expression evaluates to the same

boolean value as is given as the third parameter.

I've rewritten the algorithm in the style of semantic

equations, to which it is well suited; the information flow is

'top down'.

B: SourceExpr*label*label*bool -> CodeSequence

B[v] t f false = TEST v; JUMPTRUE t {translate a variable}

B[v] t f true = TEST v; JUMPFALSE f

B[p and q] t f n = (B[p] N f true); N: (B[q] t f n) {a conjunction}

B[p or q] t f n = (B[p] t N false); N: (B[q] t f n) {a disjunction}

B[not p] t f n = (B[p] f t (not n))

You use the translator for conditional formula in statements,

like this:

S[if p then i else j] = (B[p] T E true); T: S[i]; jump F; E: S[j]; F:

The code produced is really good. It is exactly the same as

that produced by Logothetis & Mishra's algorithm (Software P&E,

1981), which works bottom-up and left-right and so can be used during

parsing, but their algorithm is a bit harder to understand.

--

Keith Clarke

UUCP: keithc@qmc-cs.uucp or ...seismo!mcvax!ukc!qmc-cs!keithc

JANET: keithc@uk.ac.qmc.cs

[This notation is described in Peyton Jones, "Implementation of functional

programming languages", Prentice Hall, 1987. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.