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: Sun, 22 Dec 2024 23:29:50 -0000 (UTC)
Organization: To protect and to server
Message-ID: <vka7dc$odc7$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> <86ikrdg6yq.fsf@linuxsc.com> <vk78it$77aa$1@dont-email.me> <vk8a0e$l8sq$1@paganini.bofh.team> <vk9q1p$oucu$1@dont-email.me>
Injection-Date: Sun, 22 Dec 2024 23:29:50 -0000 (UTC)
Injection-Info: paganini.bofh.team; logging-data="800135"; 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: 8176
Lines: 158

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> 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.)

Classic definition uses some number of base functions, some
number of base conditions, conditional definitions and
"minimum operator".  "Minimum operator" given a (possibly
partially defined) function f and l  computes smallest n such that
f(k, l) is defined for k=0,1,...,n and f(n, l) = 0 and is undefined
otherwise.  Some texts require minimum to be effective, that
is f should be total and for each l there should be n >= 0 such
that f(n, l) = 0.  Clearly "minimum operator" is equvalent to
'while' loop.  IIRC, if instead of "minimum operator" you only
recursion, then resulting class of functions is strictly smaller.
So assuming that I remember correctly, in framework of recursive
functions claim that conditianals and recursion give Turing
completness is false, one needs some "programming" constructs.

Anyway, using recursion you clearly need some way to stop it.  If you
restrict yourself to eagerly evaluated total integer valued functions
only, then clearly there is no way to stop recursion.  But if
you have different system like lambda calculus or C, then there
are ways to stop recursion that are quite different than 'if'
or tertiary operator.

> 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.

To be clear: I need recursion in general.  I do not need 'if'
to stop 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',

You failed to see that this is on ordinary total function: it
evaluates both arguments and produces a value.  If I take the
following C function:

int lt(int a, int b) {
    return (a < b);
}

and compile it using 'gcc -O -S' I get:

lt:
..LFB0:
        .cfi_startproc
        cmpl    %esi, %edi
        setl    %al
        movzbl  %al, %eax
        ret

As you can see the only control transfer there is 'ret' at the
end of the function.  'if' and C ternary oprators are quite
different, you can not implement them as ordinary functions
(some special case can be optimized to jumpless code, but not
in general).

> 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.

I can, but for something like factorial code would be quite
ugly.  One can implement reasonable Turing machine emulator
using just integer and function pointer arrays, array accesses
and assignments, direct and indirect funcction calls.

By reasonable I mean that as long as Turning machine stays
in part of tape modeled as C array emulator and Turing machine
would move in step.  Stop in Turing machine would exit emulator.
Only when Turing machine exceeds memory of C program, C program
would exhibit undefined behaviour.  If you allow yourself also
C arithmetic operators (crucualy '/' and '%'), then you can
stop execution.

If you assume C implementation with infinite memory such that
'malloc' newer fails, then instead of array you can use
doubly linked list which gets extended when Turing machine
tries to get outside allocated space.

IIUC such infinite C implementation would exhibit undefined
behaviour as C standard requires finite bound on integers and
injective cast from from pointers to some integer type.

> 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.

Wrong, one can use properties of C23 division (actually, 
what is needed division and remainder by a fixed positive
number, say 3).

> I think that is what is to expect by the theory and the essence of
> the point I tried to make.

One point that I wanted to make is that programming languages are
different than theory of integer functions, in particular programming
constructs may be surprisingly powerful.  For example, there was
a theorem about some special concurrecy problem saying that
desired mutial exclusion can not be done by binary semaphores.
David Parnas showed that it in fact can be solved using arrays
of binary semaphores.  The theorem had unstated assumption that
only scalar semaphore variables are in use.  Of course, once you eliminate
all useful constructs from a language, then one can not do anything
is such a language (as a joke David Parnas defined such a language).

Second point was that function calls in tail position are quite similar
to goto, and in case of indirect calls they can do job of 'if' or 'switch'.
So if you consider elimination of 'if' (or 'goto') as a cheat, the
cheat is in using function calls, and not in predicates.

-- 
                              Waldek Hebisch