Understanding regexes (Was: Re: DMD 0.147 release)

[Oskar Linde]

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

The function has to halt also. An infinite loop can be impossible for 
the compiler to detect. One would not want the compilation to hang.

>> c) The compiler has no way of knowing the function space and time 
>> complexity.
> 
> How is this different from a) ?

This is similar to a), but since a) is provable undecidable, probably 
not harder. :)

If the function call takes five hours to complete, the compilation would 
take five hours times the number of times the function got called with 
different arguments. Also, if the function uses 2 gb of stack space, the 
compiler might run out of memory...
The compiler would have to execute the function for a certain amount of 
time, and break it if it doesn't return.

/ Oskar