keithc@cs.qmc.ac.uk (Keith Clarke) (04/07/89)
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]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-requestcompilers-sender@ima.ima.isc.com (04/25/89)
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 as in Peyton Jones, "implementation of functional
programming languages", Prentice Hall, 1987. -John]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-request