Re: transpiling to low level C

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

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.

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.