Re: Executing code at compilation time

> [I expect he means things like sum i=1 to infinity of 2^(-i) which we
> know analytically is 1. -John]


This depends on the semantics of the compiler:


(1) If the compiler promises semantic *equivalence* then any infinite
loop in the program must compile to code which implements an infinite
loop. For example:


double addend = 0.5;
double sum = 0.0;
while (1){
      sum += addend;
      addend *= 0.5;
}
print(sum)


The infinite loop must be generated, but there need not be any code inside it.
The print(sum) does not need to be compiled: since it is unreachable.


(2) On the other hand, if the compiler only promises to generate a
*refinement* of the source program, then an infinite loop can be
compiled to any code whatsoever. A refinement of a program is any
program which is defined, i.e. terminating, everywhere the original
program is; and is at least as deterministic as the original program.
One might think that most ordinary programming languages are
deterministic already: but if the language specification declares the
behaviour of a certain program to be "undefined" or "implementation
dependent" then there is an explicit nondeterminacy which the compiler
is allowed to refine to a deterministic executable. One could argue,
therefore, that a compiler is allowed to *refine* the source code into
an executable: and therefore allowed to generate an executable which
terminates in cases where the source program does not.


To see why this might be useful consider the following loop:


while (condition on y) {
    ... code which computes x and y ...
}
print(x)


The compiler "knows" that the value of y is not needed.
Suppose it can compute the value of x separately:


while (condition on y) {
    ... code which computes x and y ...
}
... code which computes x ...
print(x)


Suppose the compiler cannot determine whether or not the while loop
terminates. Should it be allowed to delete the loop? If so, then it
*may* be compiling a nonterminating program into a terminating
executable. If not, then it has to generate a lot of extra code, just
on the off-chance that it might not terminate!


If the compiler is allowed to refine the source code into an
executable, then the original example could be compiled to:


print(1)


But it could *also* be compiled to:


print(42)


or, indeed, any other code whatsoever!


People familiar with the concept of "program slicing" will recognise
this situation, which is discussed in my recent paper:


"Properties of Slicing Definitions", Martin Ward Ninth IEEE
International Working Conference on Source Code Analysis and
Manipulation 20th-21st September 2009, Edmonton, Canada. pp 23-34
http://www.cse.dmu.ac.uk/~mward/martin/papers/properties-final.pdf


--
Martin


STRL Reader in Software Engineering and Royal Society Industry Fellow
martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
[Depends on what the rules for your language are. In Fortran, the rule has
been that anything that's mathematically equivalent, even if not computationally
equivalent, is OK. -John]

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