Deutsch   English   Français   Italiano  
<vkb81n$14frj$1@dont-email.me>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c
Subject: Re: transpiling to low level C
Date: Mon, 23 Dec 2024 09:46:46 +0100
Organization: A noiseless patient Spider
Lines: 100
Message-ID: <vkb81n$14frj$1@dont-email.me>
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> <vk8a0e$l8sq$1@paganini.bofh.team>
 <vk9q1p$oucu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 23 Dec 2024 09:46:55 +0100 (CET)
Injection-Info: dont-email.me; posting-host="4541fb8706e33f0d382046069d49cfc8";
	logging-data="1195891"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19h/VnKEDpNEYLXF6/DfokEJDHZotR+z/M="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:dAXZRmsTGkkJNrBC+Q7eysV4Z1c=
In-Reply-To: <vk9q1p$oucu$1@dont-email.me>
Content-Language: en-GB
Bytes: 5275

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.


int fact(int n);

int fact_zero(int n) {
         return 1;
}

int n_fact_n1(int n) {
         return n * fact(n - 1);
}

int fact(int n) {
         return (int (*[])(int)){ fact_zero, n_fact_n1 }[(bool) n](n);
}


There are additional fun things that can be done using different 
operators.  For an unsigned integer "n" that is not big enough to wrap, 
"(n + 2) / (n + 1) - 1"  evaluates "(n == 0)".

And Tim did not rule out using the standard library, which would surely 
open up new possibilities.