Re: transpiling to low level C

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};
     int c1 = a[i] == b;
     (*(t[c1]))();
}
 void l2(void) {
     i++;
     l3();
}
 void l3(void) {
     void (*(t[]))(void) = {l1, l4};
     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'.
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().
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.
It looks like a crude form of threaded code (which, when I use that, never returns, and it doesn't use a stack either).
I've seen enough to know that it would be last kind of IL I would choose (unless it was the last IL left in the world - then maybe).
There is also the oddity that eliminating a simple kind of branching relies on more elaborate branching: call and return mechanisms.
More interesting and more practical would be replacing call/return by 'goto'! (It would need to support label pointers or indirect jumps, unless runtime code modification was allowed.)
(my test)
--------------------------
#include <stdio.h>
int n=6;
int a[]={10,20,30,40,50,60};
int b=30;
int i;
void k2(void);
void k3(void);
void k4(void);
void k0(void) {
     i = 0;
     k3();
}
void k1(void) {
     void (*(t[2]))(void) = {k4, k2};
     printf("%d\n",a[i]);
     int c1 = a[i] == b;
     (*(t[c1]))();
}
void k2(void) {
     i++;
//    k3();
}
void k3(void) {
     void (*(t[]))(void) = {k4, k1};
     int c2 = i < n;
     (*(t[c2]))();
}
void k4(void) {
}
int main(void) {
   k0();
   k1();
   k2();
   k3();
   k4();
}