Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #382072 > unrolled thread

Is C ready to become a safer language?

Back to article view | Back to comp.lang.c

Contents

  Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 01:01 -0300
    Re: Is C ready to become a safer language? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-02-08 04:40 +0000
      Re: Is C ready to become a safer language? Kaz Kylheku <433-929-6894@kylheku.com> - 2024-02-08 05:00 +0000
      Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 09:20 -0300
        Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-08 17:02 +0000
          Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 14:17 -0300
            Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 14:19 -0300
            Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-08 09:57 -0800
        Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-08 09:45 -0800
          Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 14:56 -0300
    Re: Is C ready to become a safer language? Kaz Kylheku <433-929-6894@kylheku.com> - 2024-02-08 04:58 +0000
      Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-07 21:33 -0800
    Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-07 20:59 -0800
      Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-08 09:17 +0100
        Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 09:48 -0300
          Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-08 14:42 +0000
          Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-08 16:25 +0100
            Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 13:15 -0300
              Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-08 21:42 +0100
        Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-08 08:04 -0800
          Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-08 16:14 +0000
            Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-08 08:32 -0800
            Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 08:19 +0100
              Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-09 07:46 +0000
                Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 09:33 +0100
                  Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-09 10:03 +0000
                    Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 11:17 +0100
                  Re: Is C ready to become a safer language? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-02-09 10:24 +0000
                    Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-09 11:24 +0000
                      Re: Is C ready to become a safer language? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-02-09 13:28 +0000
                        Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-09 14:04 +0000
                      Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 15:03 +0100
                        ustent on that. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-09 16:01 +0000
                          Re: ustent on that. David Brown <david.brown@hesbynett.no> - 2024-02-09 18:00 +0100
                            Re: ustent on that. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-10 01:20 +0000
                    Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-09 12:45 +0000
                      Re: Is C ready to become a safer language? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-02-09 13:01 +0000
                        Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 15:08 +0100
                Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-09 08:48 -0800
          Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 08:14 +0100
            Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-09 08:28 -0800
              Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-09 20:15 +0100
      Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-10 02:28 -0800
        Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-10 16:15 -0800
          Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-10 23:22 -0800
            Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-11 00:12 -0800
              Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-11 23:48 -0800
                Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-18 15:28 -0800
                  Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-23 10:35 -0700
    Re: Is C ready to become a safer language? Richard Kettlewell <invalid@invalid.invalid> - 2024-02-08 15:37 +0000
      Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-08 13:25 -0300
    Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-08 16:30 +0000
      Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-09 17:59 -0800
        Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-10 20:22 +0000
          Re: Is C ready to become a safer language? Richard Harnden <richard.nospam@gmail.invalid> - 2024-02-10 21:30 +0000
          Re: Is C ready to become a safer language? Kaz Kylheku <433-929-6894@kylheku.com> - 2024-02-10 21:49 +0000
            Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-10 20:44 -0300
              Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-11 13:06 +0100
                Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-11 15:43 -0300
                  Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-11 13:33 -0800
                  Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-12 11:32 +0100
            Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-11 00:02 +0000
              Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-10 17:39 -0800
              Re: Is C ready to become a safer language? Kaz Kylheku <433-929-6894@kylheku.com> - 2024-02-11 02:46 +0000
                Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-11 12:24 +0000
                  Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-11 15:06 +0100
                  Re: Is C ready to become a safer language? Kaz Kylheku <433-929-6894@kylheku.com> - 2024-02-11 18:32 +0000
              Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-11 13:15 +0100
          Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-10 16:31 -0800
            Re: Is C ready to become a safer language? Thiago Adams <thiago.adams@gmail.com> - 2024-02-11 15:57 -0300
              Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-11 13:47 -0800
          Re: Is C ready to become a safer language? vallor <vallor@cultnix.org> - 2024-02-11 00:40 +0000
            Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-11 01:06 +0000
            Re: Is C ready to become a safer language? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-02-10 17:51 -0800
              Re: Is C ready to become a safer language? David Brown <david.brown@hesbynett.no> - 2024-02-11 13:27 +0100
            Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-10 19:54 -0800
              Re: Is C ready to become a safer language? vallor <vallor@cultnix.org> - 2024-02-13 06:22 +0000
            Re: Is C ready to become a safer language? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-02-11 11:01 +0000
              Re: Is C ready to become a safer language? Richard Harnden <richard.nospam@gmail.invalid> - 2024-02-11 11:31 +0000
                Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-11 12:38 +0000
                  Re: Is C ready to become a safer language? Richard Harnden <richard.nospam@gmail.invalid> - 2024-02-11 13:23 +0000
                    Re: Is C ready to become a safer language? bart <bc@freeuk.com> - 2024-02-11 14:17 +0000
          Re: Is C ready to become a safer language? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-10 22:21 -0800

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#382112

On 08/02/2024 16:04, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 08/02/2024 05:59, Keith Thompson wrote:
>>> Thiago Adams <thiago.adams@gmail.com> writes:
>>>> Let's say C compilers can detect all sorts of bugs at compile time.
>>>>
>>>> How would C compilers report that? As an error or a warning?
>>>>
>>>> Let's use this sample:
>>>>
>>>> int main() {
>>>>       int a = 1;
>>>>       a = a / 0;
>>>> }
>>>>
>>>> GCC says:
>>>>
>>>> warning: division by zero is undefined [-Wdivision-by-zero]
>>>>       5 |  a = a / 0;
>>>>         |        ^ ~
>>>>
>>>> In case GCC or any other compiler reports this as an error, then C
>>>> programmers would likely complain. Am I right?
>>> Someone will always complain, but a conforming compiler can report
>>> this as a fatal error.
>>
>> I'm not /entirely/ convinced.  Such code is only undefined behaviour
>> at run-time, I believe.  A compiler could reject the code (give a
>> fatal error) if it is sure that this will be reached when the code is
>> run. But can it be sure of that, even if it is in "main()" ?
>> Freestanding implementations don't need to run "main()" (not all my
>> programs have had a "main()" function), and the freestanding/hosted
>> implementation choice is a matter of the implementation, not just the
>> compiler.
> 
> In a freestanding implementation, main() *might* be just another
> function.  In that case a compiler can't prove that the code will be
> invoked.
> 
Well sometimes it can. The boot routine or program entry point is by 
defintion always invoked, and you can generally prove that at least some 
code is always reached from that. However it is the halting problem, and 
you can never prove for all cases, even if the code must be reached or 
not reached regardless of runtime inputs.

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382118

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On 08/02/2024 16:04, Keith Thompson wrote:
[...]
>> In a freestanding implementation, main() *might* be just another
>> function.  In that case a compiler can't prove that the code will be
>> invoked.
>> 
> Well sometimes it can. The boot routine or program entry point is by
> defintion always invoked, and you can generally prove that at least
> some code is always reached from that.

That's not the case in the example being discussed, which was an
unconditional division by zero in main().

>                                        However it is the halting
> problem, and you can never prove for all cases, even if the code must
> be reached or not reached regardless of runtime inputs.

The halting problem is hardly relevant.  A compiler *may* reject a
program if it can prove that undefined behavior will always occur.
It's under no obligation to do so, or even to diagnose it.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#382162

On 08/02/2024 17:14, Malcolm McLean wrote:
> On 08/02/2024 16:04, Keith Thompson wrote:

>> In a freestanding implementation, main() *might* be just another
>> function.  In that case a compiler can't prove that the code will be
>> invoked.
>>
> Well sometimes it can. The boot routine or program entry point is by 
> defintion always invoked, and you can generally prove that at least some 
> code is always reached from that. However it is the halting problem, and 
> you can never prove for all cases, even if the code must be reached or 
> not reached regardless of runtime inputs.
> 

It is not "the halting problem".  What you are trying to say, is that it 
is undecidable or not a computable problem in the general case.

Compilers and linkers can - and do - map potential reachability, erring 
on the side of false positives.  It is very common, at least in embedded 
systems where you try to avoid wasting space, to trace reachability and 
discard code and data that is known to never be reachable.  But this is 
done by treating any symbol referenced by each function (after dead-code 
elimination) as being reachable by that function, which may include 
false positives.

[toc] | [prev] | [next] | [standalone]

#382163

On 09/02/2024 07:19, David Brown wrote:
> On 08/02/2024 17:14, Malcolm McLean wrote:
>> On 08/02/2024 16:04, Keith Thompson wrote:
> 
>>> In a freestanding implementation, main() *might* be just another
>>> function.  In that case a compiler can't prove that the code will be
>>> invoked.
>>>
>> Well sometimes it can. The boot routine or program entry point is by 
>> defintion always invoked, and you can generally prove that at least 
>> some code is always reached from that. However it is the halting 
>> problem, and you can never prove for all cases, even if the code must 
>> be reached or not reached regardless of runtime inputs.
>>
> 
> It is not "the halting problem".  What you are trying to say, is that it 
> is undecidable or not a computable problem in the general case.
> 
The "is this code reached?" problem is the halting problem with the 
trivial and unimportant difference that the code in question does not 
have to be "exit()".

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382171

On 09/02/2024 08:46, Malcolm McLean wrote:
> On 09/02/2024 07:19, David Brown wrote:
>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>
>>>> In a freestanding implementation, main() *might* be just another
>>>> function.  In that case a compiler can't prove that the code will be
>>>> invoked.
>>>>
>>> Well sometimes it can. The boot routine or program entry point is by 
>>> defintion always invoked, and you can generally prove that at least 
>>> some code is always reached from that. However it is the halting 
>>> problem, and you can never prove for all cases, even if the code must 
>>> be reached or not reached regardless of runtime inputs.
>>>
>>
>> It is not "the halting problem".  What you are trying to say, is that 
>> it is undecidable or not a computable problem in the general case.
>>
> The "is this code reached?" problem is the halting problem with the 
> trivial and unimportant difference that the code in question does not 
> have to be "exit()".
> 

No, it is not.

The two problems can be shown to be equivalently "hard" - that is, if 
you could find a solution to one, it would let you solve the other.  But 
that does not make them the same problem.

And even if they /were/ the same thing, writing "this is undecidable" or 
"this is infeasible to compute" is clear and to the point.  Writing 
"this is the halting problem" is name-dropping a computer science theory 
in order to look smart - and like most such attempts, is more smart-arse 
than smart.

[toc] | [prev] | [next] | [standalone]

#382172

On 09/02/2024 08:33, David Brown wrote:
> On 09/02/2024 08:46, Malcolm McLean wrote:
>> On 09/02/2024 07:19, David Brown wrote:
>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>
>>>>> In a freestanding implementation, main() *might* be just another
>>>>> function.  In that case a compiler can't prove that the code will be
>>>>> invoked.
>>>>>
>>>> Well sometimes it can. The boot routine or program entry point is by 
>>>> defintion always invoked, and you can generally prove that at least 
>>>> some code is always reached from that. However it is the halting 
>>>> problem, and you can never prove for all cases, even if the code 
>>>> must be reached or not reached regardless of runtime inputs.
>>>>
>>>
>>> It is not "the halting problem".  What you are trying to say, is that 
>>> it is undecidable or not a computable problem in the general case.
>>>
>> The "is this code reached?" problem is the halting problem with the 
>> trivial and unimportant difference that the code in question does not 
>> have to be "exit()".
>>
> 
> No, it is not.
> 
> The two problems can be shown to be equivalently "hard" - that is, if 
> you could find a solution to one, it would let you solve the other.  But 
> that does not make them the same problem.
> 
> And even if they /were/ the same thing, writing "this is undecidable" or 
> "this is infeasible to compute" is clear and to the point.  Writing 
> "this is the halting problem" is name-dropping a computer science theory 
> in order to look smart - and like most such attempts, is more smart-arse 
> than smart.
> 
Well I've been accused of wasting my English degree, and so now I'm 
going to accuse you of wasting your mathematics-related degree.
-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382174

On 09/02/2024 11:03, Malcolm McLean wrote:
> On 09/02/2024 08:33, David Brown wrote:
>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>> On 09/02/2024 07:19, David Brown wrote:
>>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>>
>>>>>> In a freestanding implementation, main() *might* be just another
>>>>>> function.  In that case a compiler can't prove that the code will be
>>>>>> invoked.
>>>>>>
>>>>> Well sometimes it can. The boot routine or program entry point is 
>>>>> by defintion always invoked, and you can generally prove that at 
>>>>> least some code is always reached from that. However it is the 
>>>>> halting problem, and you can never prove for all cases, even if the 
>>>>> code must be reached or not reached regardless of runtime inputs.
>>>>>
>>>>
>>>> It is not "the halting problem".  What you are trying to say, is 
>>>> that it is undecidable or not a computable problem in the general case.
>>>>
>>> The "is this code reached?" problem is the halting problem with the 
>>> trivial and unimportant difference that the code in question does not 
>>> have to be "exit()".
>>>
>>
>> No, it is not.
>>
>> The two problems can be shown to be equivalently "hard" - that is, if 
>> you could find a solution to one, it would let you solve the other.  
>> But that does not make them the same problem.
>>
>> And even if they /were/ the same thing, writing "this is undecidable" 
>> or "this is infeasible to compute" is clear and to the point.  Writing 
>> "this is the halting problem" is name-dropping a computer science 
>> theory in order to look smart - and like most such attempts, is more 
>> smart-arse than smart.
>>
> Well I've been accused of wasting my English degree, and so now I'm 
> going to accuse you of wasting your mathematics-related degree.

I haven't seen anyone here accusing you of wasting your English 
literature degree.  I think you have a lot of trouble communicating with 
others here, and I think you have a strong tendency to invent what you 
think others might have written, rather than reading what they actually 
wrote.  It is not helped by your "slapdash" style.  I would have 
expected someone with a university level degree in English to have a 
greater emphasis on reading and understanding, and communicating.

But that does not mean I could or did accuse you of wasting your degree. 
  I don't know nearly enough about your life to comment on that.  If you 
are where you are now, and if your career, hobbies, interests, 
education, or anything else in your life has benefited from the degree, 
then it was not wasted.

I studied mathematics and computation.  Both have been very useful in my 
work.  I can't claim that much of the high-level mathematics is directly 
applicable to my job, but the training in logical thinking, problem 
solving, and an emphasis on proof is vital.  In addition, I was lucky 
enough to have a tutor that put a lot of weight on communication and 
accurate technical writing, which is an essential part of my job.

[toc] | [prev] | [next] | [standalone]

#382175

David Brown <david.brown@hesbynett.no> writes:

> On 09/02/2024 08:46, Malcolm McLean wrote:
>> On 09/02/2024 07:19, David Brown wrote:
>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>
>>>>> In a freestanding implementation, main() *might* be just another
>>>>> function.  In that case a compiler can't prove that the code will be
>>>>> invoked.
>>>>>
>>>> Well sometimes it can. The boot routine or program entry point is by
>>>> defintion always invoked, and you can generally prove that at least
>>>> some code is always reached from that. However it is the halting
>>>> problem, and you can never prove for all cases, even if the code must
>>>> be reached or not reached regardless of runtime inputs.
>>>>
>>>
>>> It is not "the halting problem".  What you are trying to say, is that it
>>> is undecidable or not a computable problem in the general case.
>>>
>> The "is this code reached?" problem is the halting problem with the
>> trivial and unimportant difference that the code in question does not
>> have to be "exit()".
>
> No, it is not.
>
> The two problems can be shown to be equivalently "hard" - that is, if you
> could find a solution to one, it would let you solve the other.  But that
> does not make them the same problem.

Sure.  But it's not the halting problem for another reason as well.

In the formal models (that have halting problems and so on), it's "the
computation" that is the problem instance.  That is, the code and all
the data are presented for an answer.  A C compiler has to decide on
reachability without knowing the input.

For example, is this code "undefined":

  int c, freq[128];
  while ((c = getchar()) != EOF) freq[c]++;

?  Maybe it was knocked up as a quick way to collect stats on base64
encoded data streams.  If so, it's fine (at least in terms of UB).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#382178

On 09/02/2024 10:24, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>> On 09/02/2024 07:19, David Brown wrote:
>>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>>
>>>>>> In a freestanding implementation, main() *might* be just another
>>>>>> function.  In that case a compiler can't prove that the code will be
>>>>>> invoked.
>>>>>>
>>>>> Well sometimes it can. The boot routine or program entry point is by
>>>>> defintion always invoked, and you can generally prove that at least
>>>>> some code is always reached from that. However it is the halting
>>>>> problem, and you can never prove for all cases, even if the code must
>>>>> be reached or not reached regardless of runtime inputs.
>>>>>
>>>>
>>>> It is not "the halting problem".  What you are trying to say, is that it
>>>> is undecidable or not a computable problem in the general case.
>>>>
>>> The "is this code reached?" problem is the halting problem with the
>>> trivial and unimportant difference that the code in question does not
>>> have to be "exit()".
>>
>> No, it is not.
>>
>> The two problems can be shown to be equivalently "hard" - that is, if you
>> could find a solution to one, it would let you solve the other.  But that
>> does not make them the same problem.
> 
> Sure.  But it's not the halting problem for another reason as well.
> 
> In the formal models (that have halting problems and so on), it's "the
> computation" that is the problem instance.  That is, the code and all
> the data are presented for an answer.  A C compiler has to decide on
> reachability without knowing the input.
> 
> For example, is this code "undefined":
> 
>    int c, freq[128];
>    while ((c = getchar()) != EOF) freq[c]++;
> 
> ?  Maybe it was knocked up as a quick way to collect stats on base64
> encoded data streams.  If so, it's fine (at least in terms of UB).
> 
Yes, but I specified "regardless of runtime inputs". A bit downthread, 
you can be forgiven for having missed that. But DB less so, especially 
when I'm accused of being the one who doesn't read things properly. And 
even when I agree there might be some truth in that, and explain why, I 
am then accused of misrepresenting what an Oxford English degree is like.
If you change the halting problem such that some of the symbols on the 
tape are allowed to have unknown values then I don't think you are 
changing it in any mathematically very interesting way so it is still 
"trival", but if you attempt a halt decider it will substantially change 
your programming approach, and so it is no longer "unimportant".

If a signed integer overflows the behaviour is undefined, so you also 
have to prove that the input stream is short. And of course you also 
forgot to intialise to zero.
-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382186

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On 09/02/2024 10:24, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>>> On 09/02/2024 07:19, David Brown wrote:
>>>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>>>
>>>>>>> In a freestanding implementation, main() *might* be just another
>>>>>>> function.  In that case a compiler can't prove that the code will be
>>>>>>> invoked.
>>>>>>>
>>>>>> Well sometimes it can. The boot routine or program entry point is by
>>>>>> defintion always invoked, and you can generally prove that at least
>>>>>> some code is always reached from that. However it is the halting
>>>>>> problem, and you can never prove for all cases, even if the code must
>>>>>> be reached or not reached regardless of runtime inputs.
>>>>>>
>>>>>
>>>>> It is not "the halting problem".  What you are trying to say, is that it
>>>>> is undecidable or not a computable problem in the general case.
>>>>>
>>>> The "is this code reached?" problem is the halting problem with the
>>>> trivial and unimportant difference that the code in question does not
>>>> have to be "exit()".
>>>
>>> No, it is not.
>>>
>>> The two problems can be shown to be equivalently "hard" - that is, if you
>>> could find a solution to one, it would let you solve the other.  But that
>>> does not make them the same problem.
>> Sure.  But it's not the halting problem for another reason as well.
>> In the formal models (that have halting problems and so on), it's "the
>> computation" that is the problem instance.  That is, the code and all
>> the data are presented for an answer.  A C compiler has to decide on
>> reachability without knowing the input.
>> For example, is this code "undefined":
>>    int c, freq[128];
>>    while ((c = getchar()) != EOF) freq[c]++;
>> ?  Maybe it was knocked up as a quick way to collect stats on base64
>> encoded data streams.  If so, it's fine (at least in terms of UB).
>> 
> Yes, but I specified "regardless of runtime inputs".

How can it be the halting problem "regardless of runtime inputs"
considering my point that the HP instances include the input?  You may
be thinking of the universal halting problem, but that does not really
fit what you said.

A better way to put it would be just to state that almost all
interesting run-time properties of programs are undecidable.  And Rice's
theorem gives any one who is curious the exact definition of
"interesting".

> If a signed integer overflows the behaviour is undefined, so you also have
> to prove that the input stream is short. And of course you also forgot to
> intialise to zero.

I did indeed.  Thanks.  Overflow is just another example of the point I
was making, but not zeroing wasn't!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#382190

On 09/02/2024 13:28, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
>> On 09/02/2024 10:24, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>>>> On 09/02/2024 07:19, David Brown wrote:
>>>>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>>>>
>>>>>>>> In a freestanding implementation, main() *might* be just another
>>>>>>>> function.  In that case a compiler can't prove that the code will be
>>>>>>>> invoked.
>>>>>>>>
>>>>>>> Well sometimes it can. The boot routine or program entry point is by
>>>>>>> defintion always invoked, and you can generally prove that at least
>>>>>>> some code is always reached from that. However it is the halting
>>>>>>> problem, and you can never prove for all cases, even if the code must
>>>>>>> be reached or not reached regardless of runtime inputs.
>>>>>>>
>>>>>>
>>>>>> It is not "the halting problem".  What you are trying to say, is that it
>>>>>> is undecidable or not a computable problem in the general case.
>>>>>>
>>>>> The "is this code reached?" problem is the halting problem with the
>>>>> trivial and unimportant difference that the code in question does not
>>>>> have to be "exit()".
>>>>
>>>> No, it is not.
>>>>
>>>> The two problems can be shown to be equivalently "hard" - that is, if you
>>>> could find a solution to one, it would let you solve the other.  But that
>>>> does not make them the same problem.
>>> Sure.  But it's not the halting problem for another reason as well.
>>> In the formal models (that have halting problems and so on), it's "the
>>> computation" that is the problem instance.  That is, the code and all
>>> the data are presented for an answer.  A C compiler has to decide on
>>> reachability without knowing the input.
>>> For example, is this code "undefined":
>>>     int c, freq[128];
>>>     while ((c = getchar()) != EOF) freq[c]++;
>>> ?  Maybe it was knocked up as a quick way to collect stats on base64
>>> encoded data streams.  If so, it's fine (at least in terms of UB).
>>>
>> Yes, but I specified "regardless of runtime inputs".
> 
> How can it be the halting problem "regardless of runtime inputs"
> considering my point that the HP instances include the input?  You may
> be thinking of the universal halting problem, but that does not really
> fit what you said.
> 
Most real programs have some runtime data and it is rare to have a 
program which is designed to calculate a hardcoded value. But often it 
doesn't feed into any branches and so it's quite straightforwards to 
show that it won't affect flow control. However this won't help you to 
write a "statement reached decider" which works for all cases.
> A better way to put it would be just to state that almost all
> interesting run-time properties of programs are undecidable.  And Rice's
> theorem gives any one who is curious the exact definition of
> "interesting".
> 
Unlike you I'm not a trained computer scientist and I just pick up bits 
as I go along. I'm familiar with Turing's proof that a halt decider is 
impossible (how could I not be?), but not so comfortable with Rice's 
theorem. So whilst I'm sure your explanation is more general and better, 
I could not have made it myself. I do qualify as "curious" however.

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382189

On 09/02/2024 12:24, Malcolm McLean wrote:
> On 09/02/2024 10:24, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>>> On 09/02/2024 07:19, David Brown wrote:
>>>>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>>>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>>>
>>>>>>> In a freestanding implementation, main() *might* be just another
>>>>>>> function.  In that case a compiler can't prove that the code will be
>>>>>>> invoked.
>>>>>>>
>>>>>> Well sometimes it can. The boot routine or program entry point is by
>>>>>> defintion always invoked, and you can generally prove that at least
>>>>>> some code is always reached from that. However it is the halting
>>>>>> problem, and you can never prove for all cases, even if the code must
>>>>>> be reached or not reached regardless of runtime inputs.
>>>>>>
>>>>>
>>>>> It is not "the halting problem".  What you are trying to say, is 
>>>>> that it
>>>>> is undecidable or not a computable problem in the general case.
>>>>>
>>>> The "is this code reached?" problem is the halting problem with the
>>>> trivial and unimportant difference that the code in question does not
>>>> have to be "exit()".
>>>
>>> No, it is not.
>>>
>>> The two problems can be shown to be equivalently "hard" - that is, if 
>>> you
>>> could find a solution to one, it would let you solve the other.  But 
>>> that
>>> does not make them the same problem.
>>
>> Sure.  But it's not the halting problem for another reason as well.
>>
>> In the formal models (that have halting problems and so on), it's "the
>> computation" that is the problem instance.  That is, the code and all
>> the data are presented for an answer.  A C compiler has to decide on
>> reachability without knowing the input.
>>
>> For example, is this code "undefined":
>>
>>    int c, freq[128];
>>    while ((c = getchar()) != EOF) freq[c]++;
>>
>> ?  Maybe it was knocked up as a quick way to collect stats on base64
>> encoded data streams.  If so, it's fine (at least in terms of UB).
>>
> Yes, but I specified "regardless of runtime inputs". A bit downthread, 
> you can be forgiven for having missed that. But DB less so, especially 
> when I'm accused of being the one who doesn't read things properly.

Why should I be "forgiven" for missing that, when I did not miss it and 
when it is not at all relevant to what I wrote?  I saw it, but responded 
only to the clear bit of your claim "it is the halting problem", and 
ignored the jumbled part about "runtime inputs".  My point stands 
whatever you meant to say about runtime inputs, and however what you 
meant relates to what you tried to write.

So again, you did not read my post, or you are bizarrely blaming /me/ 
for something you think Ben did.


> And 
> even when I agree there might be some truth in that, and explain why, I 
> am then accused of misrepresenting what an Oxford English degree is like.

Again, read my posts.  I said your description of your degree does not 
match my experience with my own degree at Oxford, nor what I heard from 
others at the time who studied English literature.  You may have given 
an accurate description of your personal experiences - I have no way to 
either prove or disprove that, and no reason to suspect you of being 
intentionally deceptive.  But I believe it to have been unusual, and due 
to a bad tutor.

> If you change the halting problem such that some of the symbols on the 
> tape are allowed to have unknown values then I don't think you are 
> changing it in any mathematically very interesting way so it is still 
> "trival", but if you attempt a halt decider it will substantially change 
> your programming approach, and so it is no longer "unimportant".
> 

I would prefer to think a bit about how a volatile input tape would 
relate to the halting problem as it is normally stated, before offering 
an opinion on how it may or may not change the result.  I suspect you 
are correct that it will not change the problem or the results, but I 
would want to be a bit more rigorous about what is meant before jumping 
to conclusions.

However, I have no idea what you mean by "if you attempt a halt decider 
it will substantially change your programming approach".

[toc] | [prev] | [next] | [standalone]

#382200 — ustent on that.

On 09/02/2024 14:03, David Brown wrote:
> On 09/02/2024 12:24, Malcolm McLean wrote:
>>
>> And even when I agree there might be some truth in that, and explain 
>> why, I am then accused of misrepresenting what an Oxford English 
>> degree is like.
> 
> Again, read my posts.  I said your description of your degree does not 
> match my experience with my own degree at Oxford, nor what I heard from 
> others at the time who studied English literature.  You may have given 
> an accurate description of your personal experiences - I have no way to 
> either prove or disprove that, and no reason to suspect you of being 
> intentionally deceptive.  But I believe it to have been unusual, and due 
> to a bad tutor.
> 

OK. So you also attended Oxford. And now I'm surprised. That's what 
Oxford English is like. Very much an emphasis on geting things done, 
quickly and to deadlines, because most Oxford English graduates will 
work in careers where that is important. Only a small minority become 
computer programmers like me where a program often has t be perfect ot 
it doesn't work at all. Now whislt of course I don;t have direct 
experience of other colleges, I'm pretty sure my own college was fairly 
normal about this. One tutor was maybe a bit keener than normal.
  We got essays for next week on an author most of us had never read on 
the very first day, and I dn;t think you;f]=d get that at every college. 
But not far off.

I'm really not mischaracterising. Of course you also have to defend the 
essay and it is marked. But that's less important. It's very unusual to 
receive a mark for an essay which is so low that it means that if you 
write a similar essay in finals you will fail. Oxford is extremely 
generous with the lower marks and in ensuring that they are not a fail. 
Unless of course the candidate submits nothing. In which case it can 
only be a fail. So you must submit something which constitutes an essay 
for the tutorial, and my tutors were very insistent on that.

I fell out with my tutor catastrophically over moral issues and because 
of the type of subject English Literature is, that had profound 
implications for my work. He allowed that to happen, he was in the wrong 
about our dispute  and everything I predicted that would happen in 
English Studies has in fact come to pass, and he was therefore a bad 
tutor. But to be fair I was an extremely difficult student.

>> If you change the halting problem such that some of the symbols on the 
>> tape are allowed to have unknown values then I don't think you are 
>> changing it in any mathematically very interesting way so it is still 
>> "trival", but if you attempt a halt decider it will substantially 
>> change your programming approach, and so it is no longer "unimportant".
>>
> 
> I would prefer to think a bit about how a volatile input tape would 
> relate to the halting problem as it is normally stated, before offering 
> an opinion on how it may or may not change the result.  I suspect you 
> are correct that it will not change the problem or the results, but I 
> would want to be a bit more rigorous about what is meant before jumping 
> to conclusions.
>
Well this is it isn't it. Employ a computer scientist as a mathematician 
and you'll get a rigorous proof. Employ an English graduate (and I have 
actually held the job title "mathematician" though I am in no way 
qualified to describe myself as such) and he quickly guesses. But are 
you so surprised that you think I am thereby misrepresenting Oxford 
English? And the English graduate does at least produce something 
constructive quickly.

 >
> However, I have no idea what you mean by "if you attempt a halt decider 
> it will substantially change your programming approach".
> 
We're changing the model slightly so that instead of all the input tape 
being available to the decider, some values are unknown. It still has to 
determine whether the program will halt or not, and whilst sometimes 
this will now be inherently impossible because the answer depends on the 
input, often it will not be so. As I said, I don't think anything much 
has actually changed. But it does mean that we now have to write our 
halt decider in a different way. It's no longer as simple as replacing 
the code we want to know is reached by exit() and declaring that it is 
now the halting problem.

The halt decider will fail to work as specified on some inputs, so I say 
"attempt a halt decider". You can have a go. But it won't actually work.



-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382207 — Re: ustent on that.

On 09/02/2024 17:01, Malcolm McLean wrote:
> On 09/02/2024 14:03, David Brown wrote:
>> On 09/02/2024 12:24, Malcolm McLean wrote:
>>>
>>> And even when I agree there might be some truth in that, and explain 
>>> why, I am then accused of misrepresenting what an Oxford English 
>>> degree is like.
>>
>> Again, read my posts.  I said your description of your degree does not 
>> match my experience with my own degree at Oxford, nor what I heard 
>> from others at the time who studied English literature.  You may have 
>> given an accurate description of your personal experiences - I have no 
>> way to either prove or disprove that, and no reason to suspect you of 
>> being intentionally deceptive.  But I believe it to have been unusual, 
>> and due to a bad tutor.
>>
> 
> OK. So you also attended Oxford. And now I'm surprised. 

Why is that surprising?

> That's what 
> Oxford English is like. Very much an emphasis on geting things done, 
> quickly and to deadlines, because most Oxford English graduates will 
> work in careers where that is important. Only a small minority become 
> computer programmers like me where a program often has t be perfect ot 
> it doesn't work at all. Now whislt of course I don;t have direct 
> experience of other colleges, I'm pretty sure my own college was fairly 
> normal about this. One tutor was maybe a bit keener than normal.
>   We got essays for next week on an author most of us had never read on 
> the very first day, and I dn;t think you;f]=d get that at every college. 
> But not far off.
> 

Perhaps you should discourage your cat from walking across your keyboard 
while trying to type.  Surely accurate typing is a skill you need for 
programming?

I know literature students (of any language) were expected to work hard, 
reading a lot of texts - /all/ students at Oxford had intense workloads. 
  In computer science, practicals were done in whatever language the 
lecturer liked - so you might easily find you have to learn a new 
programming language in a couple of weeks, outside of any courses or 
tutorials, for answering the practical.

I know literature students were expected to write a lot, quickly - as 
were students of most subjects.  But IME they were also expected to 
write accurately and sensibly.  There is no point in doing something 
fast, if it is not correct (to the extent that a literature essay can be 
"correct").


> I'm really not mischaracterising. Of course you also have to defend the 
> essay and it is marked. But that's less important. It's very unusual to 
> receive a mark for an essay which is so low that it means that if you 
> write a similar essay in finals you will fail. Oxford is extremely 
> generous with the lower marks and in ensuring that they are not a fail. 

I have seen students at Oxford fail.  Not many, but a few.

> Unless of course the candidate submits nothing. In which case it can 
> only be a fail. So you must submit something which constitutes an essay 
> for the tutorial, and my tutors were very insistent on that.
> 

You sound like you were trying to get away the absolute minimum possible 
without failing.

> I fell out with my tutor catastrophically over moral issues and because 
> of the type of subject English Literature is, that had profound 
> implications for my work. He allowed that to happen, he was in the wrong 
> about our dispute  and everything I predicted that would happen in 
> English Studies has in fact come to pass, and he was therefore a bad 
> tutor. But to be fair I was an extremely difficult student.

Such bad chemistry between a student and a tutor happens sometimes, 
unfortunately.

But what you are describing is a situation where you scraped through, 
learning little from the tutor.  That is not normal university experience.

> 
>>> If you change the halting problem such that some of the symbols on 
>>> the tape are allowed to have unknown values then I don't think you 
>>> are changing it in any mathematically very interesting way so it is 
>>> still "trival", but if you attempt a halt decider it will 
>>> substantially change your programming approach, and so it is no 
>>> longer "unimportant".
>>>
>>
>> I would prefer to think a bit about how a volatile input tape would 
>> relate to the halting problem as it is normally stated, before 
>> offering an opinion on how it may or may not change the result.  I 
>> suspect you are correct that it will not change the problem or the 
>> results, but I would want to be a bit more rigorous about what is 
>> meant before jumping to conclusions.
>>
> Well this is it isn't it. Employ a computer scientist as a mathematician 
> and you'll get a rigorous proof. Employ an English graduate (and I have 
> actually held the job title "mathematician" though I am in no way 
> qualified to describe myself as such) and he quickly guesses. But are 
> you so surprised that you think I am thereby misrepresenting Oxford 
> English? And the English graduate does at least produce something 
> constructive quickly.
> 

I think your situation at university was unusual, as you describe it - 
though not impossible.

And I would expect someone who has a degree in English to be more 
accurate in the language they write.  Perhaps my expectations are 
unreasonable, but in comparison to other regulars here, your rate of 
typos, spelling mistakes, grammatical errors, and - more importantly - 
confusing and unclear wording, is significantly higher.  We all make 
mistakes at times, but to reach your level shows a lack of care and a 
lack of attention to detail.  It is not a matter of producing things 
quickly - it is laziness.

Put it this way.  If you were to apply to my department for a job as a 
programmer, and you wrote your CV and cover letter in the style you 
write in this newsgroup, I would reject you on that basis alone.


>  >
>> However, I have no idea what you mean by "if you attempt a halt 
>> decider it will substantially change your programming approach".
>>
> We're changing the model slightly so that instead of all the input tape 
> being available to the decider, some values are unknown. It still has to 
> determine whether the program will halt or not, and whilst sometimes 
> this will now be inherently impossible because the answer depends on the 
> input, often it will not be so. As I said, I don't think anything much 
> has actually changed. But it does mean that we now have to write our 
> halt decider in a different way. It's no longer as simple as replacing 
> the code we want to know is reached by exit() and declaring that it is 
> now the halting problem.
> 
> The halt decider will fail to work as specified on some inputs, so I say 
> "attempt a halt decider". You can have a go. But it won't actually work.
> 

So when you write "if you attempt a halt decider", you mean something 
like attempting to "write" a halt decider, or "design", or "test", or 
"run" a halt decider?  And doing this will somehow "change your 
programming approach" ?  Are you trying to say that if you allow some 
input values to be unknown, it changes how you design your halt decider? 
  That would make no sense, because you /can't/ design a general halt 
decider (without transfinite computation models and "oracles").  Are you 
trying to say that if someone spends time trying to do this, it will 
change their attitude to programming in general?

Your first attempt at explaining this made no sense.  Your second 
attempt did not help at all.  Perhaps it is best just to leave it alone.

[toc] | [prev] | [next] | [standalone]

#382252 — Re: ustent on that.

On 09/02/2024 17:00, David Brown wrote:
> On 09/02/2024 17:01, Malcolm McLean wrote:
>
>> OK. So you also attended Oxford. And now I'm surprised. 
> 
> Why is that surprising?
> 
You don't seem to have the same understanding as me about what makes 
Oxford tick,

> There is no point in doing something 
> fast, if it is not correct (to the extent that a literature essay can be 
> "correct").
> 
>> I'm really not mischaracterising. Of course you also have to defend 
>> the essay and it is marked. But that's less important. It's very 
>> unusual to receive a mark for an essay which is so low that it means 
>> that if you write a similar essay in finals you will fail. Oxford is 
>> extremely generous with the lower marks and in ensuring that they are 
>> not a fail. 
> 
> I have seen students at Oxford fail.  Not many, but a few.
> 
There is a point in dong something fast but not correct, and I think I 
explained it very clearly. Something fast but not correct may get a low 
mark, but as long as it is not too badly incorrect, it will pass. 
Something slow and accurate but not submitted on time will receive a 
fail. Now maybe less so in computer science.

>> Unless of course the candidate submits nothing. In which case it can 
>> only be a fail. So you must submit something which constitutes an 
>> essay for the tutorial, and my tutors were very insistent on that.
>>
> 
> You sound like you were trying to get away the absolute minimum possible 
> without failing.
> 
My experience is that people at Oxford just don't think lke that. 
Obviously your exoerience must have been different. That's what I mean 
about being surprised.

>
> Such bad chemistry between a student and a tutor happens sometimes, 
> unfortunately.
> 
> But what you are describing is a situation where you scraped through, 
> learning little from the tutor.  That is not normal university experience.
>
I wasn't really bad chemistry. I disgreed with him over some moral 
issues, and ultimately the direction in which he was taking the other 
students, and we fell out. It's not normal to have such a dispute, I 
agree. However whilst he was my personal tutor, he wasn't my only tutor, 
and I remained on good terms with the others. In some ways I was a very 
difficult student.

> I think your situation at university was unusual, as you describe it - 
> though not impossible.
> 
Surely you are not saying that this is all invented? It did actually 
happen, and so, no, it can't have been impossible.

> And I would expect someone who has a degree in English to be more 
> accurate in the language they write.  Perhaps my expectations are 
> unreasonable, but in comparison to other regulars here, your rate of 
> typos, spelling mistakes, grammatical errors, and - more importantly - 
> confusing and unclear wording, is significantly higher.  We all make 
> mistakes at times, but to reach your level shows a lack of care and a 
> lack of attention to detail.  It is not a matter of producing things 
> quickly - it is laziness.
> 
> Put it this way.  If you were to apply to my department for a job as a 
> programmer, and you wrote your CV and cover letter in the style you 
> write in this newsgroup, I would reject you on that basis alone.
> 
Whilst I'd have no hesitation at all in recommedending you for a job as 
a programmer with us.
> 
>>  >
>>> However, I have no idea what you mean by "if you attempt a halt 
>>> decider it will substantially change your programming approach".
>>>
>> We're changing the model slightly so that instead of all the input 
>> tape being available to the decider, some values are unknown. It still 
>> has to determine whether the program will halt or not, and whilst 
>> sometimes this will now be inherently impossible because the answer 
>> depends on the input, often it will not be so. As I said, I don't 
>> think anything much has actually changed. But it does mean that we now 
>> have to write our halt decider in a different way. It's no longer as 
>> simple as replacing the code we want to know is reached by exit() and 
>> declaring that it is now the halting problem.
>>
>> The halt decider will fail to work as specified on some inputs, so I 
>> say "attempt a halt decider". You can have a go. But it won't actually 
>> work.
>>
> 
> So when you write "if you attempt a halt decider", you mean something 
> like attempting to "write" a halt decider, or "design", or "test", or 
> "run" a halt decider?  And doing this will somehow "change your 
> programming approach" ?  Are you trying to say that if you allow some 
> input values to be unknown, it changes how you design your halt decider? 
>   That would make no sense, because you /can't/ design a general halt 
> decider (without transfinite computation models and "oracles").  Are you 
> trying to say that if someone spends time trying to do this, it will 
> change their attitude to programming in general?
> 
> Your first attempt at explaining this made no sense.  Your second 
> attempt did not help at all.  Perhaps it is best just to leave it alone.
> 
>
Now am I unclear or are you obtuse? Are people so contentious that they 
can't understand, or is it genuinely my fault?

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

[toc] | [prev] | [next] | [standalone]

#382182

On 09/02/2024 10:24, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 09/02/2024 08:46, Malcolm McLean wrote:

>> The two problems can be shown to be equivalently "hard" - that is, if you
>> could find a solution to one, it would let you solve the other.  But that
>> does not make them the same problem.
> 
> Sure.  But it's not the halting problem for another reason as well.
> 
> In the formal models (that have halting problems and so on), it's "the
> computation" that is the problem instance.  That is, the code and all
> the data are presented for an answer.  A C compiler has to decide on
> reachability without knowing the input.
> 
> For example, is this code "undefined":
> 
>    int c, freq[128];
>    while ((c = getchar()) != EOF) freq[c]++;
> 
> ?  Maybe it was knocked up as a quick way to collect stats on base64
> encoded data streams.  If so, it's fine (at least in terms of UB).

Perhaps until you read an input that has 2**31 or more of the same 
character.

[toc] | [prev] | [next] | [standalone]

#382183

bart <bc@freeuk.com> writes:

> On 09/02/2024 10:24, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 09/02/2024 08:46, Malcolm McLean wrote:
>
>>> The two problems can be shown to be equivalently "hard" - that is, if you
>>> could find a solution to one, it would let you solve the other.  But that
>>> does not make them the same problem.
>> Sure.  But it's not the halting problem for another reason as well.
>> In the formal models (that have halting problems and so on), it's "the
>> computation" that is the problem instance.  That is, the code and all
>> the data are presented for an answer.  A C compiler has to decide on
>> reachability without knowing the input.
>> For example, is this code "undefined":
>>    int c, freq[128];
>>    while ((c = getchar()) != EOF) freq[c]++;
>> ?  Maybe it was knocked up as a quick way to collect stats on base64
>> encoded data streams.  If so, it's fine (at least in terms of UB).
>
> Perhaps until you read an input that has 2**31 or more of the same
> character.

Yes, that's the point.  Any UB is dependent on the input.  It's not a
static property of the code.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#382191

On 09/02/2024 14:01, Ben Bacarisse wrote:
> bart <bc@freeuk.com> writes:
> 
>> On 09/02/2024 10:24, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 09/02/2024 08:46, Malcolm McLean wrote:
>>
>>>> The two problems can be shown to be equivalently "hard" - that is, if you
>>>> could find a solution to one, it would let you solve the other.  But that
>>>> does not make them the same problem.
>>> Sure.  But it's not the halting problem for another reason as well.
>>> In the formal models (that have halting problems and so on), it's "the
>>> computation" that is the problem instance.  That is, the code and all
>>> the data are presented for an answer.  A C compiler has to decide on
>>> reachability without knowing the input.
>>> For example, is this code "undefined":
>>>     int c, freq[128];
>>>     while ((c = getchar()) != EOF) freq[c]++;
>>> ?  Maybe it was knocked up as a quick way to collect stats on base64
>>> encoded data streams.  If so, it's fine (at least in terms of UB).
>>
>> Perhaps until you read an input that has 2**31 or more of the same
>> character.
> 
> Yes, that's the point.  Any UB is dependent on the input.  It's not a
> static property of the code.
> 

Well, /some/ UB is determinable at compile time - such as an identifier 
having both internal and external linkage in the same unit, and a few 
other bits and pieces that the language designers probably thought were 
too burdensome to require compiler implementers to handle.

But mostly UB is a runtime issue, and therefore usually it is dependent 
on the input.

[toc] | [prev] | [next] | [standalone]

#382206

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On 09/02/2024 07:19, David Brown wrote:
>> On 08/02/2024 17:14, Malcolm McLean wrote:
>>> On 08/02/2024 16:04, Keith Thompson wrote:
>>>> In a freestanding implementation, main() *might* be just another
>>>> function.  In that case a compiler can't prove that the code will be
>>>> invoked.
>>>>
>>> Well sometimes it can. The boot routine or program entry point is
>>> by defintion always invoked, and you can generally prove that at
>>> least some code is always reached from that. However it is the
>>> halting problem, and you can never prove for all cases, even if the
>>> code must be reached or not reached regardless of runtime inputs.
>>>
>> It is not "the halting problem".  What you are trying to say, is
>> that it is undecidable or not a computable problem in the general
>> case.
>> 
> The "is this code reached?" problem is the halting problem with the
> trivial and unimportant difference that the code in question does not 
> have to be "exit()".

Your earlier statement that "it is the halting problem" is at best
questionable, partly because it's not clear what "it" refers to in that
statement.

The issue is not whether we understand what the halting problem is.
The issue is that it's not relevant in this context.

We were discussing whether a compiler can reject a program that has
undefined behavior.  It clearly can *if* the undefined behavior will
occur in every execution of the program (for all inputs if the program
has inputs).

If a program includes the expression 1/0, evaluation that expression has
undefined behavior, but there is no undefined behavior if that code is
never reached and the expression is not evaluated.

Determining, for all programs containing the expression 1/0, whether
that expression will be evaluated is (probably) more or less equivalent
to the halting problem, which means that no compiler can perfectly
determine whether it's allowed to reject such programs.

But the halting program is irrelevant because *compilers are not
required to do that*.  Most compilers do *some* flow analysis, and can
determine *in some cases* whether a given expression will always,
sometimes, or never be evaluated, but they cannot, do not, and are not
required to do a perfect job.  They are not required to do any such
analysis at all.  A conforming compiler can issue a non-fatal warning
whenever it sees a division by a constant 0, not caring whether it can
be reached -- or it can ignore the issue altogether (except that it must
detect it if it occurs in a context that requires a constant
expression).

The example was one in which it's trivially provable that the expression
1/0 will be evaluated whenever the program is executed (assuming a
hosted implementation).

And if you and David want to argue about Oxford English degrees, I urge
*both of you* to do it elsewhere.  David, you don't have to respond to
everything.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#382161

On 08/02/2024 17:04, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 08/02/2024 05:59, Keith Thompson wrote:
>>> Thiago Adams <thiago.adams@gmail.com> writes:
>>>> Let's say C compilers can detect all sorts of bugs at compile time.
>>>>
>>>> How would C compilers report that? As an error or a warning?
>>>>
>>>> Let's use this sample:
>>>>
>>>> int main() {
>>>>       int a = 1;
>>>>       a = a / 0;
>>>> }
>>>>
>>>> GCC says:
>>>>
>>>> warning: division by zero is undefined [-Wdivision-by-zero]
>>>>       5 |  a = a / 0;
>>>>         |        ^ ~
>>>>
>>>> In case GCC or any other compiler reports this as an error, then C
>>>> programmers would likely complain. Am I right?
>>> Someone will always complain, but a conforming compiler can report
>>> this as a fatal error.
>>
>> I'm not /entirely/ convinced.  Such code is only undefined behaviour
>> at run-time, I believe.  A compiler could reject the code (give a
>> fatal error) if it is sure that this will be reached when the code is
>> run. But can it be sure of that, even if it is in "main()" ?
>> Freestanding implementations don't need to run "main()" (not all my
>> programs have had a "main()" function), and the freestanding/hosted
>> implementation choice is a matter of the implementation, not just the
>> compiler.
> 
> In a freestanding implementation, main() *might* be just another
> function.  In that case a compiler can't prove that the code will be
> invoked.
> 
> I was assuming a hosted implementation -- and the compiler knows whether
> its implementation is hosted or freestanding.
> 

It's reasonable to assume "hosted" unless you have particular reason not to.

But I am not sure that the /compiler/ knows that it is compiling for a 
hosted or freestanding implementation.  The same gcc can be used for 
Linux hosted user code  and a freestanding Linux kernel.  Does the 
compiler always know which when compiling a unit that happens to contain 
"main()" ?  I don't think gcc's "-ffreestanding" or "-fno-hosted" flags 
are much used - after all, virtually every freestanding C implementation 
also implements at least a fair part of the C standard library, and 
implements the same semantics in the functions it provides, so there 
really is no difference for the compiler.

(This is not something I claim to have any kind of clear answer for - 
it's an open question for my part.)

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web