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

Groups > comp.lang.c > #163802

Re: Does this program have the specified behavior?

Show all headers | View raw

antispam@math.uni.wroc.pl writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Mark Bluemel <mark.bluemel@gmail.com> writes:
>>
>>> On Wednesday, 17 November 2021 at 05:13:08 UTC, Chris M. Thomasson wrote:
>>>
>>>> On 11/16/2021 8:46 PM, olcott wrote:
>>>>
>>>>> #include <stdint.h>
>>>>> #include <stdio.h>
>>>>> typedef int (*ptr)();
>>>>>
>>>>> int H(ptr x, ptr y)
>>>>> {
>>>>>   x(y); // direct execution of P(P)
>>>>>   return 1;
>>>>> }
>>>>>
>>>>> int P(ptr x)
>>>>> {
>>>>>   H(x, x);
>>>>>   return 1;
>>>>> }
>>>>>
>>>>> int main(void)
>>>>> {
>>>>>   H(P, P);
>>>>> }
>>>>
>>>> Stack overflow...
>>>
>>> Surely a compiler can optimise this to remove the recursion, and
>>> for that matter, remove any functionality at all, as the code has
>>> no observable behaviour, as far as I can see (I'd be happy to be
>>> corrected on this!).
>>
>> A program that simply does a 'return 0;' from main() does have
>> observable behavior:  it modifies no files (and doesn't perform
>> any volatile accesses or do any I/O to interactive devices).  The
>> empty set is still a set.
>>
>> By contrast, a program that sits and does nothing and simply runs
>> forever does /not/ have observable behavior.  The reason is
>> simple:  the predicate condition for what happens with files is
>> evaluated only at program termination.  No termination means no
>> way to assess observable behavior.
>>
>> The question of whether the C standard allows (or intends to
>> allow) the program transformation you describe is a thorny
>> problem, and not one I'm planning on researching further.  But
>> considering just "observable behavior" in the two cases, ISTM
>> that the two programs clearly are not identical, because one
>> does have observable behavior and the other one does not.
>
> AFAICS currently there is accepted view among theorists that
> changing non-terminating behavior into terminating behaviour
> is valid program transformation.

The question here concerns only what the C standard does or does
not allow.

> Concerning C standard
> relevant part in N1570 seem to be 5.1.2.3 point 6.  IIUC
> if program does not terminate on abstract machine clause
> about files at program termination is empty:  it places no
> obligation on implementation.

Changing a program that does not have observable behavior into
one that does have observable behavior is obviously a significant
change.

> It seems that also clause
> about interactive streams places no obligation on
> implementation when program performs no I/O.  So it seems
> that according to N1570 changing non-terminating program
> into terminating one is allowed.

A follow-up from Keith Thompson points out N1570 6.8.5p6, which
explicitly allows turning kinds of non-terminating programs into
terminating programs.  Since the C standard identifies specific
cases where such a tranformation /is/ allowed, it is reasonable
to infer that they are /not/ allowed in other cases.  "The
exception proves the rule, in cases not excepted."

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Do this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-16 21:33 -0600
  Does this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-16 22:46 -0600
    Re: Does this program have the specified behavior? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-11-16 21:12 -0800
      Re: Does this program have the specified behavior? Mark Bluemel <mark.bluemel@gmail.com> - 2021-11-17 00:28 -0800
        Re: Does this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-17 08:33 -0600
        Re: Does this program have the specified behavior? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-10 01:40 -0800
          Re: Does this program have the specified behavior? Richard Damon <Richard@Damon-Family.org> - 2021-12-10 07:56 -0500
            Re: Does this program have the specified behavior? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-11 09:40 -0800
              Re: Does this program have the specified behavior? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-12-11 16:37 -0800
                Re: Does this program have the specified behavior? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-12 09:29 -0800
          Re: Does this program have the specified behavior? antispam@math.uni.wroc.pl - 2021-12-11 19:38 +0000
            Re: Does this program have the specified behavior? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-12-11 16:45 -0800
            Re: Does this program have the specified behavior? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-12 08:53 -0800
    Re: Does this program have the specified behavior? Richard Damon <Richard@Damon-Family.org> - 2021-11-17 06:53 -0500
      Re: Does this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-17 08:49 -0600
        Re: Does this program have the specified behavior? Juha Nieminen <nospam@thanks.invalid> - 2021-11-18 06:32 +0000
          Re: Does this program have the specified behavior? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-11-18 11:15 +0000
            Re: Does this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-18 08:59 -0600
          Re: Does this program have the specified behavior? olcott <NoOne@NoWhere.com> - 2021-11-18 08:58 -0600
    Re: Does this program have the specified behavior? Anurag Ranjan <anuragranjan630@gmail.com> - 2021-11-17 22:00 +0000

csiph-web