Understanding regexes (Was: Re: DMD 0.147 release)

[Lionello Lunesu]

"Oskar Linde" <oskar.lindeREM at OVEgmail.com> wrote in message 
news:dthe8b$1jg1$1 at digitaldaemon.com...
> 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.

Good point. Completely forgot about that.

> b) The result has to be deterministic and only depend on the arguments.

Yeah, imagine de compiler calling rand(), taking a void (very constant), 
returning 123 or so.. assuming it's constant! :-)

> 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).

Let's see. If the function only uses the inputs, without even unreferencing 
them, then it's pretty clear I suppose. But you're right, it's complex.

> b) The compiler needs a way to evaluate the function at compile time.

That's easy, by just calling it.

> c) The compiler has no way of knowing the function space and time 
> complexity.

How is this different from a) ?

> 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.

Indeed. Something like C++ "const", but then for real, and not removable by 
a cast. A "pure" function would simply have a number of restrictions, I 
suppose something like: not allowed to reference any data outside the 
function (globals, class members, etc).

Lio.