Path: ...!weretis.net!feeder8.news.weretis.net!newsfeed.bofh.team!paganini.bofh.team!not-for-mail
From: antispam@fricas.org (Waldek Hebisch)
Newsgroups: comp.lang.c
Subject: Re: transpiling to low level C
Date: Wed, 18 Dec 2024 03:51:17 -0000 (UTC)
Organization: To protect and to server
Message-ID: <vjtgrj$396sg$1@paganini.bofh.team>
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> <vjps0l$18hon$1@dont-email.me> <vjq36r$19sis$1@dont-email.me> <vjqcut$1bld5$1@dont-email.me> <877c7z85t2.fsf@nosuchdomain.example.com> <vjs871$1q22j$1@dont-email.me> <vjsgt6$32kfa$1@paganini.bofh.team> <vjsutq$1u93o$1@dont-email.me> <vjt4le$38j95$1@paganini.bofh.team> <vjt88q$20478$1@dont-email.me>
Injection-Date: Wed, 18 Dec 2024 03:51:17 -0000 (UTC)
Injection-Info: paganini.bofh.team; logging-data="3447696"; posting-host="WwiNTD3IIceGeoS5hCc4+A.user.paganini.bofh.team"; mail-complaints-to="usenet@bofh.team"; posting-account="9dIQLXBM7WM9KzA+yjdR4A";
User-Agent: tin/2.6.2-20221225 ("Pittyvaich") (Linux/6.1.0-9-amd64 (x86_64))
X-Notice: Filtered by postfilter v. 0.9.3
Bytes: 9744
Lines: 244

bart <bc@freeuk.com> wrote:
> On 18/12/2024 00:23, Waldek Hebisch wrote:
>> bart <bc@freeuk.com> wrote:
>>> On 17/12/2024 18:46, Waldek Hebisch wrote:
>>>> bart <bc@freeuk.com> wrote:
>>>>>
>>>>> If you try to extract any meaning, it is that any control flow can be
>>>>> expressed either with 'goto' or with 'recursive functions'.
>>>>>
>>>>> This is what I picked up on. Who on earth would eschew 'goto' and use
>>>>> such a disproportionately more complex and inefficient method like
>>>>> recursive functions?
>>>>
>>>> Due to silly conding standard?  Or in language that does not have
>>>> 'goto'.
>>>
>>> It was suggested that 'theoretically', 'goto' could be replaced by
>>> recursive function calls.
>>>
>>> Whether still within the context of a language with no other control
>>> flow instructions, is not known. The suggester also chose not to share
>>> examples of how it would work.
>> 
>> The example I gave (and you snipped) was supposed to explain how
>> the technique works, but it seems that it is not enough.
> 
> It showed how to do conditional code without explicit branching. It 
> didn't seem to me to cover arbitrary gotos, or where recursion comes 
> into it.
> 
> (Actually I implemented it in my two languages to compare performance to 
> 'straight' versions, however my test called silly() lots of times so it 
> wasn't a good test.)
> 
>>  So
>> let us look at another example.  Start from ordinary C code that
>> only uses global variables (this is not strictly necessary, but
>> let as make such assumption for simplicity):
>> 
>> int n;
>> int * a;
>> int b;
>> int i;
>> 
>> ...
>>      /* Simple search loop */
>>      for(i = 0; i < n; i++) {
>>          if (a[i] == b) {
>>              break;
>>          }
>>      }
>> 
>> First, express flow control using only conditional and unconditional
>> jump:
>> 
>>    l0:
>>      i = 0;
>>      goto l3;
>>    l1:
>>      int c1 = a[i] == b;
>>      if (c1) {
>>        goto l4;
>>      } else {
>>        goto l2;
>>      }
>>    l2:
>>      i++;
>>    l3:
>>      int c2 = i < n;
>>      if (c2) {
>>          goto l1;
>>      } else {
>>          goto l4;
>>      }
>>    l4:
>>      ;
>> 
>> Note, I introduced more jumps than strictly necessary, so that
>> hunks between labels end either in conditional or unconditional
>> jump.
>> 
>> Next, replace each hunk staring in a label, up to (but not
>> including) next label, by a new function.  Replace final jumps
>> by function calls, for conditional jumps using the same trick
>> as in previous 'silly' example:
>> 
>> int n;
>> int * a;
>> int b;
>> int i;
>> 
>> void l2(void);
>> void l3(void);
>> void l4(void);
>> 
>> void l0(void) {
>>      i = 0;
>>      l3();
>> }
>> 
>> void l1(void) {
>>      void (*(t[2]))(void) = {l4, l2};
                                ^^^^^^^
Should be
                                l2, l4
>>      int c1 = a[i] == b;
>>      (*(t[c1]))();
>> }
>> 
>> void l2(void) {
>>      i++;
>>      l3();
>> }
>> 
>> void l3(void) {
>>      void (*(t[]))(void) = {l1, l4};
                               ^^^^^^
                               l4, l2
>>      int c2 = i < n;
>>      (*(t[c2]))();
>> }
>> 
>> void l4(void) {
>> }
>> 
>> Note: 'l4' is different than other functions, intead of calling
>> something it returns, ensuring that the sequence of calls
>> eventually terminate.
> 
> OK thanks for this. I tried to duplicate it based on this starting point:
> 
>  #include <stdio.h>
> 
>  int n=6;
>  int a[]={10,20,30,40,50,60};
>  int b=30;
>  int i;
> 
>  int main(void) {
>     for(i = 0; i < n; i++) {
>          printf("%d\n",a[i]);
>          if (a[i] == b) {
>              break;
>          }
>      }
>  }
> 
> This prints 10 20 30 as it is. But the version with the function calls 
> showed only '10'. If I swapped '{l1, l4}' in l3(), then I got '10 10 20'.

Sorry, there was a thinko: 1 is true and this is the second element
of the array, while I was thinking that the first one is true branch
and second is false branch.
 
> I didn't spend too long to debug it further. I will take your word that 
> this works. (I tried 3 compilers all with the same results, including TCC.)
> 
> I don't fully understand it; what I got was that you first produce 
> linear code with labels. Each span between labels is turned into a 
> function. To 'step into' label L, or jump to L, I have to do L().

Yes.

> There would still be lots of questions (even ignoring the problems of 
> accessing locals), like what the return path is, or how an early return 
> would work (also returning a value). Or what kind of pressure the stack 
> would be under.

OK, you take a function F, it has some arguments and local variables.
And some retrun type.  You create "entry function" to take the
same arguments as F and has the same return type as F.  You tranform
body as above, but now each new function has the same return type
as F and arguments are arguments of original function + extra arguments,
one for each local variable of F.  In "entry function" you call
function corresponding to first label passing it arguments and
initial values of local variables of F.  In each subseqent call
you pass argument and values around so that they are available
in each new function.  And the call is an argument to return
statement.  When you want to return you simply return value,
without performing a call.

Stack use depend on optimizations in your compiler.  With small
effort compiler can recognize that it will return value (possibly
void) from a call and replace such call by stack+register
shuffling + jump.  Actually when there is return value, you
========== REMAINDER OF ARTICLE TRUNCATED ==========