Understanding regexes (Was: Re: DMD 0.147 release)

[Oskar Linde]

Lionello Lunesu skrev:
> Interesting indeed.
> 
> Is there no way to "fold constants" in this kind of code too? If you know 
> the inputs to a function are all constant, can't you simply replace the 
> inputs + function call with the function's output?

Disclaimer: I don't know much about this. Most is pure speculation.

I guess it is theoretically possible, but the compiler has to know that 
the function is pure. That is:

a) The function can not have any side effects.
b) The result has to be deterministic and only depend on the arguments.

This means that the function can not call any function not fulfilling a 
and b, and that it can not rely on things like floating point rounding 
state etc.

In the general case, the compiler has no way of knowing this. The 
function may be externally defined, and only resolved at link time. For 
stdlib-functions the compiler could of course be given this knowledge 
beforehand (like strlen).

For functions fully known to the compiler, inlining followed by constant 
folding could theoretically have the same effect, but I don't think any 
compilers are smart enough to identify pure blocks of code in a general 
fashion and being able to evaluate them at compile time. Somewhat easier 
would be to identify pure functions and evaluate them at compile time. I 
guess this is going much further than current constant folding. The 
problems I see are:

a) Hard for the compiler to tell if a function is pure. In many cases it 
is not even possible (The halting problem has an example of such an 
undecidable function).
b) The compiler needs a way to evaluate the function at compile time.
c) The compiler has no way of knowing the function space and time 
complexity.

It would be interesting if there was a way to flag functions as being 
pure. The compiler could then try to evaluate the function at compile 
time or reduce the number of calls to the function at run time similar 
to what a common sub-expression removal optimization would do.

/Oskar