Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Does this program have the specified behavior? Date: Sun, 12 Dec 2021 08:53:11 -0800 Organization: A noiseless patient Spider Lines: 85 Message-ID: <86wnk969zc.fsf@linuxsc.com> References: <2ce7a201-45d4-49aa-a512-2ca01a4fbd36n@googlegroups.com> <3e59b2b4-88f9-4bd1-8cf7-eb7baee8c214n@googlegroups.com> <86y24s7q7i.fsf@linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="52dee2417da2788e9c7fc8c78c748ef1"; logging-data="30669"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/feDsid5F8QMp6DU63VY/8ZpvH/9axlgc=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:vqfw2RMyElUkvwb7eq2AJk/j0AU= sha1:X6fYjElY33B05re5JAFLmQM3QUE= Xref: csiph.com comp.lang.c:163802 antispam@math.uni.wroc.pl writes: > Tim Rentsch wrote: > >> Mark Bluemel 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 >>>>> #include >>>>> 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."