Re: transpiling to low level C

On 21.12.2024 22:51, Tim Rentsch wrote:

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.

And also things like the above mentioned 'printf()' that most certainly
implies an iteration over the format string checking for it's '\0'-end.
And so on, and so on. - What will be left as "language".

Would you be able to formulate functionality of the class of Recursive
Functions (languages class of a Turing Machine with Chomsky-0 grammar).

 
Rule out programs with undefined behavior.
 
The language that is left is still Turing complete.

Is it? - But wouldn't that be just the argument I mentioned above; that
a, say, 'ClearAccumulator' machine statement wouldn't contain any jump?

Proof: exercise for the reader.

(Typical sort of your reply.)

Janis