Hi,

I was wondering why CTFE is context sensitive, why don't we check
every expressions and run the CTFE if it applies?

PS: I'm sorry for the double post, I just noticed that D.learn wasn't the right place to ask this question. It'd be great if someone could delete this misplaced post. Thanks.

On 1/26/14 3:22 AM, Pierre Talbot wrote:
> Hi,
>
> I was wondering why CTFE is context sensitive, why don't we check
> every expressions and run the CTFE if it applies?
>
> PS: I'm sorry for the double post, I just noticed that D.learn wasn't
> the right place to ask this question. It'd be great if someone could
> delete this misplaced post. Thanks.

Compilation would get awfully slow (and sometimes won't terminate).

Andrei

On Monday, 27 January 2014 at 04:07:04 UTC, Andrei Alexandrescu wrote:
> On 1/26/14 3:22 AM, Pierre Talbot wrote:
>> Hi,
>>
>> I was wondering why CTFE is context sensitive, why don't we check
>> every expressions and run the CTFE if it applies?
>
> Compilation would get awfully slow (and sometimes won't terminate).
>
> Andrei

So it is theoretically possible? I mean if the compilation doesn't terminate, the execution won't either for at least one program input, so we can detect an infinite loop at compile-time. Moreover, isn't the same problem with context-sensitive CTFE?

Pierre

On Monday, 27 January 2014 at 18:30:43 UTC, Pierre Talbot wrote:
> On Monday, 27 January 2014 at 04:07:04 UTC, Andrei Alexandrescu wrote:
>> On 1/26/14 3:22 AM, Pierre Talbot wrote:
>>> Hi,
>>>
>>> I was wondering why CTFE is context sensitive, why don't we check
>>> every expressions and run the CTFE if it applies?
>>
>> Compilation would get awfully slow (and sometimes won't terminate).
>>
>> Andrei
>
> So it is theoretically possible? I mean if the compilation doesn't terminate, the execution won't either for at least one program input, so we can detect an infinite loop at compile-time. Moreover, isn't the same problem with context-sensitive CTFE?
>
> Pierre

Just because code runs for a long time doesn't mean that it will run forever. This is known as the Halting problem [1]. We could have configurable switches to halt CTFE if it runs for more than N seconds or allocates more than N MiB.

However, this still doesn't take away from the point that it would make compilation awfully slow with presumably little benefit. There are further issues in that CTFE isn't exactly stable yet (I've had it produce incorrect results in a few cases), so relying on it to produce correct, optimized code is a bad idea.

I would be in favor of some "lite-CTFE" for the sake of optimization. Simply halting if the interpreter encounters a loop or function recursion should make it pretty snappy. But I think many compilers / optimizers already do this to some extent.

[1] https://en.wikipedia.org/wiki/Halting_problem

On Monday, 27 January 2014 at 18:30:43 UTC, Pierre Talbot wrote:
> On Monday, 27 January 2014 at 04:07:04 UTC, Andrei Alexandrescu wrote:
>> On 1/26/14 3:22 AM, Pierre Talbot wrote:
>>> Hi,
>>>
>>> I was wondering why CTFE is context sensitive, why don't we check
>>> every expressions and run the CTFE if it applies?
>>
>> Compilation would get awfully slow (and sometimes won't terminate).
>>
>> Andrei
>
> So it is theoretically possible? I mean if the compilation doesn't terminate, the execution won't either for at least one program input, so we can detect an infinite loop at compile-time. Moreover, isn't the same problem with context-sensitive CTFE?
>
> Pierre

lolwut ? How do you make the difference between a program that won't terminate ever and one that will terminate eventually (say, in several years) ?

On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
> lolwut ? How do you make the difference between a program that won't terminate ever and one that will terminate eventually (say, in several years) ?

1. The halting problem does not apply to finite resources. The proof is trivial: just record all state. You are in an infinite loop when you revisit a state your program already has been in. The halting problem only applies if you have non-finite storage.

2. You can set a timeout and use heurististics (and profiling) for what computations you want to try to precompute. Perfectly doable.

On 2014-01-27 21:37, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>"@puremagic.com wrote:
> On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
>> lolwut ? How do you make the difference between a program that won't
>> terminate ever and one that will terminate eventually (say, in several
>> years) ?
>
> 1. The halting problem does not apply to finite resources. The proof is
> trivial: just record all state. You are in an infinite loop when you
> revisit a state your program already has been in. The halting problem
> only applies if you have non-finite storage.

My computer has 16GB of RAM. You try keeping track of all the possible states.

Now, I know DMD cannot use 16GB of RAM, so let's limit ourselves to 3GB or so. We then make a bit array for all permutations of 3*2^30 bits. That would take 2^(3*2^30) bits. All the hard drives in the world may be on the order of 10 zettabytes. When I ask Mathematica what multiple of this number we need to keep track of all the possible permutations of 3GB, it gives up and calls me an asshole. Some jotting on a piece of paper indicates 2^3,221,225,399 is fairly close. Even if Kryder's Law[0] continues to hold, it will take 2.5 billion years before the entire world has enough storage capacity to do what you suggest, and even then, searching all that data will *still* be prohibitively expensive.

In simpler terms: Just because something is not theoretically impossible, it may still be so ridiculously computationally expensive it might as well be impossible. Stop making the argument that the halting problem does not apply to regular computers. It's technically true, yes. It also does not matter, for the reason described above.

Lastly, deadalnix didn't even bring up the halting problem, so why even mention it?


[0]: http://en.wikipedia.org/wiki/Mark_Kryder

--
  Simen

On Monday, 27 January 2014 at 21:37:58 UTC, Ola Fosheim Grøstad wrote:
> On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
>> lolwut ? How do you make the difference between a program that won't terminate ever and one that will terminate eventually (say, in several years) ?
>
> 1. The halting problem does not apply to finite resources. The proof is trivial: just record all state. You are in an infinite loop when you revisit a state your program already has been in. The halting problem only applies if you have non-finite storage.
>
> 2. You can set a timeout and use heurististics (and profiling) for what computations you want to try to precompute. Perfectly doable.

I don't think that is quite right, you can have an infinite loop without there being any repeated states. Simple example is

for( i = 1; i>0 ; i++) {...}

This will run forever while still never repeating state, assuming that i never wraps around. After all you said that we don't have finite resources which is the same as saying we have unlimited resources.

On 2014-01-27 23:18, Tofu Ninja wrote:
> On Monday, 27 January 2014 at 21:37:58 UTC, Ola Fosheim Grøstad wrote:
>> On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
>>> lolwut ? How do you make the difference between a program that won't
>>> terminate ever and one that will terminate eventually (say, in
>>> several years) ?
>>
>> 1. The halting problem does not apply to finite resources. The proof
>> is trivial: just record all state. You are in an infinite loop when
>> you revisit a state your program already has been in. The halting
>> problem only applies if you have non-finite storage.
>>
>> 2. You can set a timeout and use heurististics (and profiling) for
>> what computations you want to try to precompute. Perfectly doable.
>
> I don't think that is quite right, you can have an infinite loop without
> there being any repeated states. Simple example is
>
> for( i = 1; i>0 ; i++) {...}
>
> This will run forever while still never repeating state, assuming that i
> never wraps around. After all you said that we don't have finite
> resources which is the same as saying we have unlimited resources.

I assume i is a bigint then, and that you have infinite memory for it. Otherwise, you'll have repeated state when i overflows.

--
  Simen

On 1/27/14 1:37 PM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
> On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
>> lolwut ? How do you make the difference between a program that won't
>> terminate ever and one that will terminate eventually (say, in several
>> years) ?
>
> 1. The halting problem does not apply to finite resources. The proof is
> trivial: just record all state. You are in an infinite loop when you
> revisit a state your program already has been in. The halting problem
> only applies if you have non-finite storage.

Somebody please give him a T-shirt :o).

Andrei