Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder8.news.weretis.net!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Does this program have the specified behavior?
Date: Sat, 11 Dec 2021 09:40:00 -0800
Organization: A noiseless patient Spider
Lines: 87
Message-ID: <86czm36nwv.fsf@linuxsc.com>
References: <TeidndjwvpeU5Qn8nZ2dnUU7-QmdnZ2d@giganews.com> <2ce7a201-45d4-49aa-a512-2ca01a4fbd36n@googlegroups.com> <L6KdnUDjcci1FAn8nZ2dnUU7-V_NnZ2d@giganews.com> <sn230n$q4t$1@dont-email.me> <3e59b2b4-88f9-4bd1-8cf7-eb7baee8c214n@googlegroups.com> <86y24s7q7i.fsf@linuxsc.com> <G7IsJ.152140$831.93@fx40.iad>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="601297b613a158a006ae67e40d920115"; logging-data="8919"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19mkWovAZsTjagFKyQC+VQUf1Xo4NLfRKc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:rE2QeSg4IW2Hf8XWU4H0vn24xNk= sha1:Yv3USijU633H2ZMQnbLjuS+/DyA=
Xref: csiph.com comp.lang.c:163789

Richard Damon <Richard@Damon-Family.org> writes:

> On 12/10/21 4:40 AM, Tim Rentsch 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.
>
> I think the key point is that the infinite recursion means the
> program exceeds the environment bounds for defined operation and
> thus the behavior of the program has become officially 'Undefined
> Behavior'.  [...]

This conclusion isn't right.  First, the C standard doesn't
mention any such environmental limit.  Second, even if it did,
exceeding an environmental limit doesn't make defined behavior
turn into undefined behavior.  Consider the following program:

    int
    main( void ){
        int x;
        {{{ .. one billion open braces... {{{
            x = 0;
        }}} .. one billion close braces.. }}}
        return  x;
    }

An implementation is free to reject this program, but if the
program is accepted it has well-defined semantics, which is
to say its behavior is defined, not undefined.  And that is
true regardless of what environmental limits the implementation
may have.

In the context of the C standard, the word "behavior" refers to a
specification, not an action.  In other words the "behavior" of
a program is what the program /should/ do, not necessarily what the
program /will/ do, if and when it is executed.  A program that just
recurses infinitely has "defined behavior" in the sense that the
C standard uses the term.