Re: transpiling to low level C

On 22/12/2024 20:41, Janis Papanagnou wrote:

On 22.12.2024 07:01, Waldek Hebisch wrote:

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

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?

>
Look at example that I posted (apparently neither you nor Tim
looked at my posts where I explained in detail how to translate
goto program (with conditional jumps) into program that contains
no goto and no conditional jumps).

>
I'm not sure but may have just skimmed over your "C" example if it
wasn't of interest to the point I tried to make (at that stage).
>

Or try to figure out how to do this knowing that C has function
pointers.

>
I will retry to explain what I tried to say... - very simply put...
>
There's "Recursive Functions" and the Turing Machines "equivalent".
The "Recursive Functions" is the most powerful class of algorithms.
Formal Recursive Functions are formally defined in terms of abstract
mathematical formulated properties; one of these [three properties]
are the "Test Sets". (Here I can already stop.)
>
But since we're not in a theoretical CS newsgroup I'd just wanted
to see an example of some common, say, mathematical function and
see it implemented without 'if' and 'goto' or recursion. - Take a
simple one, say, fac(n) = n! , the factorial function. I know how
I can implement that with 'if' and recursion, and I know how I can
implement that with 'while' (or 'goto').
>
If I re-inspect your example upthread - I hope it was the one you
wanted to refer to - I see that you have removed the 'if' symbol
but not the conditional, the test function; there's still the
predicate (the "Test Set") present in form of 'int c2 = i < n',
and it's there in the original code, in the goto transformed code,
and in the function-pointer code. And you cannot get rid of that.
>
Whether you have the test in an 'if', or in a ternary '?:', or
use it through a bool-int coercion as integer index to an indexed
function[-pointer] table; it's a conditional branch based on the
("Test Set") predicate i<n. You showed in your example how to get
rid of the 'if' symbol, but you could - as expected - not get rid
of the actual test that is the substance of a conditional branch.
>
I think that is what is to expect by the theory and the essence of
the point I tried to make.
>

 You are adding more restrictions than Tim had given.
 We all know that for most non-trivial algorithms you need some kind of repetition (loops, recursion, etc.) and some way to end that repetition.   No one is claiming otherwise.
 Tim ruled out &&, ||, ?:, goto, break, continue, if, for, while, switch, do, labels, setjmp and longjmp.
 He didn't rule out recursion, or the relational operators, or any other part of C.