Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: transpiling to low level C
Date: Sat, 21 Dec 2024 13:51:27 -0800
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <86ed20g0ww.fsf@linuxsc.com>
References: <vjlh19$8j4k$1@dont-email.me> <vjn9g5$n0vl$1@raubtier-asyl.eternal-september.org> <vjnhsq$oh1f$1@dont-email.me> <vjnq5s$pubt$1@dont-email.me> <vjpn29$17jub$1@dont-email.me> <86ikrdg6yq.fsf@linuxsc.com> <vk78it$77aa$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 21 Dec 2024 22:51:28 +0100 (CET)
Injection-Info: dont-email.me; posting-host="ef945e0dbe248428eadd863336ad9ba7";
	logging-data="257917"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Mkzu1JkWmQbbU6Tq3vJj8pneJSWsIAG0="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:M0N/Xn8fMzpKEM8X2wabeXiwvew=
	sha1:4HrCoh+0mqOARuGyUO9Tincst10=
Bytes: 2800

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> On 21.12.2024 02:28, Tim Rentsch wrote:
>
>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> 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.

Rule out programs with undefined behavior.

The language that is left is still Turing complete.

Proof: exercise for the reader.