D's treatment of values versus side-effect free nullary functions

[Jim Balter]

"Jim Balter" <Jim at Balter.name> wrote in message 
news:i2fkp7$2if$1 at digitalmars.com...
> "Peter Alexander" <peter.alexander.au at gmail.com> wrote in message 
> news:i2er6d$1jkv$1 at digitalmars.com...
>> On 24/07/10 12:43 PM, Jim Balter wrote:
>>>> I thought that this was exactly the halting problem.
>>>
>>> A common misconception, but not so. The halting problem is to find an
>>> algorithm that will, for every possible function and data as input,
>>> correctly determine whether the function will terminate. Turing proved
>>> that such an algorithm is impossible, but that's irrelevant to any
>>> practical problem. Not only isn't it necessary to guarantee that the
>>> functions you decide not to attempt CTFE on really don't terminate, but
>>> no function in any real program looks anthing like the arcane function
>>> that Turing proved will baffle your algorithm.
>>
>> Walter is right.
>>
>
> No, he's not, and I explained why, and you have failed to rebut anything I 
> wrote.
>
>> Yes, Turing did prove it using an unrealistic example, but the only 
>> reason he did so was to keep the proof simple.
>
> You have no absolutely no idea what you're talking about; Turing's proof 
> is reductio ad absurdum based on a diagonalization argument -- the 
> constructed undeterminable function is dependent on the algorithm 
> purported to be able to decide it. See 
> http://en.wikipedia.org/wiki/Halting_problem
>
>> There are plenty of practical examples of functions which are difficult 
>> (or impossible) to determine whether or not they terminate.
>
> The halting problem proof isn't about "diffiicult", only "impossible", and 
> you have failed to provide a function and a proof that it is *impossible* 
> to determine whether it terminates.
>
>> In particular, any recursion or unconstrained loops make it very 
>> difficult to prove termination, and there's plenty of practical examples 
>> of those e.g. quicksort.
>
> Again, difficulty is not an issue, *impossibility* is -- *that* is what 
> the halting problem is, and if you don't understand that then you don't 
> understand the issue *at all*.
>

P.S.

The point about difficulty goes to why this is not a matter of the halting 
problem. Even if the halting problem were decidable, that would not help us 
in the slightest because we are trying to solve a *practical* problem. Even 
if you could prove, for every given function, whether it would halt on all 
inputs, that wouldn't tell you which ones to perform CTFE on -- we want CTFE 
to terminate before the programmer dies of old age. The halting problem is 
strictly a matter of theory; it's ironic to see someone who has designed a 
programming language based on *pragmatic* rather than theoretical 
considerations to invoke it.