Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: transpiling to low level C Date: Mon, 13 Jan 2025 08:10:31 -0800 Organization: A noiseless patient Spider Lines: 94 Message-ID: <86tta266fc.fsf@linuxsc.com> References: <86ikrdg6yq.fsf@linuxsc.com> <86ed20g0ww.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Mon, 13 Jan 2025 17:10:35 +0100 (CET) Injection-Info: dont-email.me; posting-host="9eea8443f476a77794ac96904ee9ae64"; logging-data="1961116"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19IJQ2gR/awTYdYthAat6d5zp12DBl9oT4=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:l3EBvWGP1siSupdAsxYaSaFMyx8= sha1:oFE4pVZakzLZgPksnZou1KhjQSE= Xref: csiph.com comp.lang.c:390012 Janis Papanagnou writes: > On 21.12.2024 22:51, Tim Rentsch wrote: > >> Janis Papanagnou writes: >> >>> On 21.12.2024 02:28, Tim Rentsch wrote: >>> >>>> Janis Papanagnou writes: >>>> >>>>> On 16.12.2024 00:53, BGB wrote: >>>>> >>>>>> [...] >>>>>> >>>>>> Pretty much all higher level control flow can be expressed via >>>>>> goto. >>>>> >>>>> A 'goto' may be used but it isn't strictly *necessary*. What >>>>> *is* necessary, though, that is an 'if' (some conditional >>>>> branch), and either 'goto' or recursive functions. >>>> >>>> Conditional branches, including 'if', '?:', etc., are not >>>> strictly necessary either. >>> >>> No? - Can you give an example of your statement? >>> >>> (Unless you just wanted to say that in some HLL abstraction like >>> 'printf("Hello world!\n")' there's no [visible] conditional >>> branch. Likewise in a 'ClearAccumulator' machine instruction, or >>> the like.) >>> >>> The comparisons and predicates are one key function (not any >>> specific branch construct, whether on HLL level, assembler >>> level, or with the (elementary but most powerful) Turing >>> Machine). Comparisons inherently result in predicates which is >>> what controls program execution). >>> >>> So your statement asks for some explanation at least. >> >> Start with C - any of C90, C99, C11. >> >> Take away the short-circuiting operators - &&, ||, ?:. >> >> Take away all statement types that involve intra-function >> transfer of control: goto, break, continue, if, for, while, >> switch, do/while. Might as well take away statement labels too. >> >> Take away setjmp and longjmp. > > And also things like the above mentioned 'printf()' that most > certainly implies an iteration over the format string checking for > it's '\0'-end. The *printf() functions can be implemented in standard C, under the above stated limitations, without needing iteration. > And so on, and so on. - What will be left as "language". I think most C developers would be able to answer that question given the above stated description. Is there some part that isn't clear to you? > Would you be able to formulate functionality of the class of > Recursive Functions (languages class of a Turing Machine with > Chomsky-0 grammar). General rewrite grammars, which is another name IIRC for Chomsky Type 0 languages, are computationally equivalent to Turing Machines (which incidentally takes me back almost five decades to my formal computability education). The answer is yes. >> Rule out programs with undefined behavior. >> >> The language that is left is still Turing complete. > > Is it? Yes, it is. > But wouldn't that be just the argument I mentioned above; that a, > say, 'ClearAccumulator' machine statement wouldn't contain any > jump? No, afaict the two questions have nothing to do with each other. >> Proof: exercise for the reader. > > (Typical sort of your reply.) I expect you will see better results if you put more effort into listening and thinking, and less effort into making ad hominem remarks.