Re: transpiling to low level C

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.