On 16/12/2024 20:39, Janis Papanagnou wrote:
I wasn't commenting on any "IL",
The subthread was about ILs.
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive than C. >>>>> You can easily write a C++-statement that would hunddres of lines in >>>>> C (imagines specializing a unordered_map by hand). Making a language >>>>> less expressive makes it even less readable, and that's also true for >>>>> your reduced C.
That's not really the point of it. This reduced C is used as an
intermediate language for a compiler target. It will not usually be
read, or maintained.
An intermediate language needs to at a lower level than the source
language.
And for this project, it needs to be compilable by any C89 compiler.
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser and
AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing statements that map 1:1 with a 3AC IR operation), it may save a bit more...
As for whether or not it makes sense to use a C like syntax here, this
is more up for debate (for practical use within a compiler, I would
assume a binary serialization rather than an ASCII syntax, though ASCII
may be better in terms of inter-operation or human readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the structures
used to implement those operators. Also I would assume that the IR need
not be in SSA form (conversion to full SSA could be done when reading in
the IR operations).
Ny argument is that not using SSA form means fewer issues for both the serialization format and compiler front-end to need to deal with (and is comparably easy to regenerate for the backend, with the backend
operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
Em 12/17/2024 4:03 AM, BGB escreveu:
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive than C. >>>>>> You can easily write a C++-statement that would hunddres of lines in >>>>>> C (imagines specializing a unordered_map by hand). Making a language >>>>>> less expressive makes it even less readable, and that's also true for >>>>>> your reduced C.
That's not really the point of it. This reduced C is used as an
intermediate language for a compiler target. It will not usually be >>>>> read, or maintained.
An intermediate language needs to at a lower level than the source
language.
And for this project, it needs to be compilable by any C89 compiler. >>>>>
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser
and AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing
statements that map 1:1 with a 3AC IR operation), it may save a bit
more...
As for whether or not it makes sense to use a C like syntax here, this
is more up for debate (for practical use within a compiler, I would
assume a binary serialization rather than an ASCII syntax, though
ASCII may be better in terms of inter-operation or human readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the structures
used to implement those operators. Also I would assume that the IR
need not be in SSA form (conversion to full SSA could be done when
reading in the IR operations).
Ny argument is that not using SSA form means fewer issues for both the
serialization format and compiler front-end to need to deal with (and
is comparably easy to regenerate for the backend, with the backend
operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
I also have considered split expressions.
For instance
if (a*b+c) {}
into
register int r1 = a * b;
register int r2 = r1 + c;
if (r2) {}
This would make easier to add overflow checks in runtime (if desired)
and implement things like _complex
Is this what you mean by 3AC or SSA?
This would definitely simplify expressions grammar.
Em 12/17/2024 2:55 PM, Thiago Adams escreveu:
Em 12/17/2024 4:03 AM, BGB escreveu:
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive
than C.
You can easily write a C++-statement that would hunddres of lines in >>>>>>> C (imagines specializing a unordered_map by hand). Making a language >>>>>>> less expressive makes it even less readable, and that's also true >>>>>>> for
your reduced C.
That's not really the point of it. This reduced C is used as an
intermediate language for a compiler target. It will not usually
be read, or maintained.
An intermediate language needs to at a lower level than the source >>>>>> language.
And for this project, it needs to be compilable by any C89 compiler. >>>>>>
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser
and AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing
statements that map 1:1 with a 3AC IR operation), it may save a bit
more...
As for whether or not it makes sense to use a C like syntax here,
this is more up for debate (for practical use within a compiler, I
would assume a binary serialization rather than an ASCII syntax,
though ASCII may be better in terms of inter-operation or human
readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the structures
used to implement those operators. Also I would assume that the IR
need not be in SSA form (conversion to full SSA could be done when
reading in the IR operations).
Ny argument is that not using SSA form means fewer issues for both
the serialization format and compiler front-end to need to deal with
(and is comparably easy to regenerate for the backend, with the
backend operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
I also have considered split expressions.
For instance
if (a*b+c) {}
into
register int r1 = a * b;
register int r2 = r1 + c;
if (r2) {}
This would make easier to add overflow checks in runtime (if desired)
and implement things like _complex
Is this what you mean by 3AC or SSA?
This would definitely simplify expressions grammar.
I also have consider remove local scopes. But I think local scopes may
be useful to better use stack reusing the same addresses when variables
goes out of scope.
For instance
{
int i =1;
{
int a = 2;
}
{
int b = 3;
}
}
I think scope makes easier to use the same stack position of a and b
because it is easier to see a does not exist any more.
also remove structs changing by unsigned char [] and cast parts of it to access members.
I think this the lower level possible in c.
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?
How would you even express an arbitrary goto from random point X in a function to random point Y, which may be inside differently nested
blocks, via a recursive function?
On 16/12/2024 21:23, Lawrence D'Oliveiro wrote:
On Sun, 15 Dec 2024 17:53:30 -0600, BGB wrote:
As an IL, even C is a little overkill, unless turned into a restricted
subset ...
Why not use WASM as your IL?
Have you tried it? I mean, directly generating WASM from a compiler front-end, not just using somebody else's tool to do so.
WASM is a stack-based language, but one that supposedly doesn't even
have branching, although there is a 'br' statement, with some restrictions.
Information about it is quite elusive; it took me 5 minutes to even get examples of what it looks like (and I've seen it before).
C can apparently compile to WASM via Clang, so I tried this program:
void F(void) {
int i=0;
while (i<10000) ++i;
}
which compiled to 128 lines of WASM (technically, some form of 'WAT', as WASM is a binary format). The 60 lines correspondoing to F are shown
below, and below that, is my own stack IL code.
So, what do you with your WASM/WAT program once generated? I've no idea, except that WASM is inextricably typed up with with browsers and with JavaScript, in which I have no interest.
With C, you run a compiler; with ASM, an assembler; these formats are
well understood.
You can appreciate that it can be easier to devise your own format and
your own tools that you understand 100%.
-------------------------------------- F: # @F
.functype F () -> ()
.local i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32,
i32, i32, i32
# %bb.0:
global.get __stack_pointer
local.set 0
i32.const 16
local.set 1
local.get 0
local.get 1
i32.sub
local.set 2
i32.const 0
local.set 3
local.get 2
local.get 3
i32.store 12 .LBB0_1: # =>This Inner Loop Header: Depth=1
block
loop # label1:
local.get 2
i32.load 12
local.set 4
i32.const 10000
local.set 5
local.get 4
local.set 6
local.get 5
local.set 7
local.get 6
local.get 7
i32.lt_s
local.set 8
i32.const 1
local.set 9
local.get 8
local.get 9
i32.and
local.set 10
local.get 10
i32.eqz
br_if 1 # 1: down to label0
# %bb.2: # in Loop: Header=BB0_1 Depth=1
local.get 2
i32.load 12
local.set 11
i32.const 1
local.set 12
local.get 11
local.get 12
i32.add
local.set 13
local.get 2
local.get 13
i32.store 12
br 0 # 0: up to label1
.LBB0_3:
end_loop
end_block # label0:
return
end_function
-----------------------------
proc F::
local i32 i.1
load i32 0
store i32 i.1
jump #2
#4:
load u64 &i.1
incrto i32 /1
#2:
load i32 i.1
load i32 10000
jumplt i32 #4
#3:
#1:
retproc
endproc
On 17/12/2024 18:16, Thiago Adams wrote:
also remove structs changing by unsigned char [] and cast parts of it
to access members.
I think this the lower level possible in c.
This is what I do in my IL, where structs are just fixed blocks of so
many bytes.
Em 12/17/2024 4:03 AM, BGB escreveu:
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive than C. >>>>>> You can easily write a C++-statement that would hunddres of lines in >>>>>> C (imagines specializing a unordered_map by hand). Making a language >>>>>> less expressive makes it even less readable, and that's also true for >>>>>> your reduced C.
That's not really the point of it. This reduced C is used as an
intermediate language for a compiler target. It will not usually be >>>>> read, or maintained.
An intermediate language needs to at a lower level than the source
language.
And for this project, it needs to be compilable by any C89 compiler. >>>>>
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser
and AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing
statements that map 1:1 with a 3AC IR operation), it may save a bit
more...
As for whether or not it makes sense to use a C like syntax here, this
is more up for debate (for practical use within a compiler, I would
assume a binary serialization rather than an ASCII syntax, though
ASCII may be better in terms of inter-operation or human readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the structures
used to implement those operators. Also I would assume that the IR
need not be in SSA form (conversion to full SSA could be done when
reading in the IR operations).
Ny argument is that not using SSA form means fewer issues for both the
serialization format and compiler front-end to need to deal with (and
is comparably easy to regenerate for the backend, with the backend
operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
I also have considered split expressions.
For instance
if (a*b+c) {}
into
register int r1 = a * b;
register int r2 = r1 + c;
if (r2) {}
This would make easier to add overflow checks in runtime (if desired)
and implement things like _complex
Is this what you mean by 3AC or SSA?
This would definitely simplify expressions grammar.
On 12/17/2024 11:55 AM, Thiago Adams wrote:
Em 12/17/2024 4:03 AM, BGB escreveu:
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive
than C.
You can easily write a C++-statement that would hunddres of lines in >>>>>>> C (imagines specializing a unordered_map by hand). Making a language >>>>>>> less expressive makes it even less readable, and that's also true >>>>>>> for
your reduced C.
That's not really the point of it. This reduced C is used as an
intermediate language for a compiler target. It will not usually
be read, or maintained.
An intermediate language needs to at a lower level than the source >>>>>> language.
And for this project, it needs to be compilable by any C89 compiler. >>>>>>
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser
and AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing
statements that map 1:1 with a 3AC IR operation), it may save a bit
more...
As for whether or not it makes sense to use a C like syntax here,
this is more up for debate (for practical use within a compiler, I
would assume a binary serialization rather than an ASCII syntax,
though ASCII may be better in terms of inter-operation or human
readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the structures
used to implement those operators. Also I would assume that the IR
need not be in SSA form (conversion to full SSA could be done when
reading in the IR operations).
Ny argument is that not using SSA form means fewer issues for both
the serialization format and compiler front-end to need to deal with
(and is comparably easy to regenerate for the backend, with the
backend operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
I also have considered split expressions.
For instance
if (a*b+c) {}
into
register int r1 = a * b;
register int r2 = r1 + c;
if (r2) {}
This would make easier to add overflow checks in runtime (if desired)
and implement things like _complex
Is this what you mean by 3AC or SSA?
3AC means that IR expressed 3 (or sometimes more) operands per IR op.
So:
MUL r1, a, b
Rather than, say, stack:
LOAD a
LOAD b
MUL
STORE r1
SSA:
Static Single Assignment
Generally:
Every variable may only be assigned once (more like in a functional programming language);
Generally, variables are "merged" in the control-flow via PHI operators (which variable merges in depending on which path control came from).
IMHO, while SSA is preferable for backend analysis, optimization, and
code generation; it is undesirable pretty much everywhere else as it
adds too much complexity.
Better IMO for the frontend compiler and main IL stage to assume that
local variables are freely mutable.
Typically, global variables are excluded in most variants, and remain
fully mutable; but may be handled as designated LOAD/STORE operations.
In BGBCC though, full SSA only applies to temporaries. Normal local variables are merely flagged by "version", and all versions of the same local variable implicitly merge back together at each branch/label.
This allows some similar advantages (for analysis and optimization)
while limiting some of the complexities. Though, this differs from temporaries which are assumed to essentially fully disappear once they
go outside of the span in which they exist (albeit with an awkward case
to deal with temporaries that cross basic-block boundaries, which need
to actually "exist" in some semi-concrete form, more like local variables).
Note that unless the address is taken of a local variable, it need not
have any backing in memory. Temporaries can never have their address
taken, so generally exist exclusively in CPU registers.
This would definitely simplify expressions grammar.
Information about it is quite elusive ...
Em 12/17/2024 3:37 PM, bart escreveu:
On 17/12/2024 18:16, Thiago Adams wrote:
also remove structs changing by unsigned char [] and cast parts of it
to access members.
I think this the lower level possible in c.
This is what I do in my IL, where structs are just fixed blocks of so
many bytes.
How do you do with struct parameters?
On Tue, 17 Dec 2024 12:04:29 +0000, bart wrote:
Information about it is quite elusive ...
Did you try the usual place for Web-related stuff?
<https://developer.mozilla.org/en-US/docs/WebAssembly>
On 17/12/2024 01:19, Keith Thompson wrote:
bart <bc@freeuk.com> writes:
[SNIP]
In that case I've no idea what you were trying to say.I read Janis's post. I saw a suggestion that certain constructs are
When somebody says that 'goto' can emulate any control structure, then
clearly some of them need to be conditional; that is implied.
Your reply suggested they you can do away with 'goto', and use
recursive functions, in a scenario where no other control structures
need exist.
OK, if this is not for an IL, then it's not a language I would care
for either. Why tie one hand behind your back for no good reason?
*theoretically* unnecessary. I saw no suggestion of any advocacy for
such an approach.
"""
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.
"""
This doesn't actually make much sense. So 'goto' is necessary, but
'goto' *is*?
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?
On 17/12/2024 19:40, Lawrence D'Oliveiro wrote:
On Tue, 17 Dec 2024 12:04:29 +0000, bart wrote:
Information about it is quite elusive ...
Did you try the usual place for Web-related stuff?
<https://developer.mozilla.org/en-US/docs/WebAssembly>
It's not aimed at people /implementing/ such a tool.
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'.
On Tue, 17 Dec 2024 19:45:49 +0000, bart wrote:
On 17/12/2024 19:40, Lawrence D'Oliveiro wrote:
On Tue, 17 Dec 2024 12:04:29 +0000, bart wrote:
Information about it is quite elusive ...
Did you try the usual place for Web-related stuff?
<https://developer.mozilla.org/en-US/docs/WebAssembly>
It's not aimed at people /implementing/ such a tool.
It is aimed at those capable of following the links to relevant specs.
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.
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.
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.
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.)
On 17/12/2024 22:25, Lawrence D'Oliveiro wrote:
On Tue, 17 Dec 2024 19:45:49 +0000, bart wrote:
It's not aimed at people /implementing/ such a tool.
It is aimed at those capable of following the links to relevant specs.
It also a pretty terrible link.
On 12/17/2024 6:04 AM, bart wrote:
C can apparently compile to WASM via Clang, so I tried this program:
void F(void) {
int i=0;
while (i<10000) ++i;
}
which compiled to 128 lines of WASM (technically, some form of 'WAT',
as WASM is a binary format). The 60 lines correspondoing to F are
shown below, and below that, is my own stack IL code.
Hmm... It looks like the WASM example is already trying to follow SSA
rules, then mapped to a stack IL... Not necessarily the best way to do
it IMO.
But, yeah, in BGBCC I am also using a stack-based IL (RIL), which
follows rules more in a similar category to .NET CIL (in that, stack
items carry type, and the stack is generally fully emptied on branch).
In my IL, labels are identified with a LABEL opcode (with an immediate),
and things like branches work by having the branch target and label
having the same immediate (label ID).
bart <bc@freeuk.com> writes:
[...]
[...]
(Janis, please correct me if I'm mistaken.)
bart <bc@freeuk.com> wrote:
[...]
Due to silly conding standard? Or in language that does not have
'goto'.
On 17/12/2024 18:51, BGB wrote:
On 12/17/2024 6:04 AM, bart wrote:
C can apparently compile to WASM via Clang, so I tried this program:
void F(void) {
int i=0;
while (i<10000) ++i;
}
which compiled to 128 lines of WASM (technically, some form of 'WAT',
as WASM is a binary format). The 60 lines correspondoing to F are
shown below, and below that, is my own stack IL code.
I'm not even sure what format that code is in, as WAT is supposed to use S-expressions. The generated code is flat. It differs in other ways from examples of WAT.
Hmm... It looks like the WASM example is already trying to follow SSA
rules, then mapped to a stack IL... Not necessarily the best way to do
it IMO.
I hadn't considered that SSA could be represented in stack form.
But couldn't each push be converted to an assignment to a fresh
variable, and the same with pop?
As for Phi functions, the only similar thing I encounter (but could be mistaken), is when there is a choice of paths to yield a value (such as
(c ? a : b) in C; my language has several such constructs).
With stack code, the result conveniently ends up on top of the stack whichever path is taken, which is a big advantage. Unless you then have
to convert that to register code, and need to ensure the values end up
in the same register when the control paths join up again.
But, yeah, in BGBCC I am also using a stack-based IL (RIL), which
follows rules more in a similar category to .NET CIL (in that, stack
items carry type, and the stack is generally fully emptied on branch).
In my IL, labels are identified with a LABEL opcode (with an
immediate), and things like branches work by having the branch target
and label having the same immediate (label ID).
So, you jump to label L123, and the label looks like:
L123:
I think that is pretty standard! But it sounds like you use a very tight encoding for bytecode, while mine uses a 32-byte descriptor for each IL instruction.
(One quibble with labels is whether a label definition occupies an
actual IL instruction. With my IL used as a backend for static
languages, it does. And there can be clusters of labels at the same spot.
With dynamic bytecode designed for interpretation, it doesn't. It uses a different structure. This means labels don't need to be 'executed' when encountered.)
On 17/12/2024 19:07, Thiago Adams wrote:
Em 12/17/2024 3:37 PM, bart escreveu:
On 17/12/2024 18:16, Thiago Adams wrote:
also remove structs changing by unsigned char [] and cast parts of
it to access members.
I think this the lower level possible in c.
This is what I do in my IL, where structs are just fixed blocks of so
many bytes.
How do you do with struct parameters?
In the IL they are always passed notionally by value. This side of the
IL (that is, the frontend compile that generates IL), knows nothing
about the target, such as ABI details.
(In practice, some things are known, like the word size of the target,
since that can change characteristics of the source language, like the
size of 'int' or of 'void*'. It also needs to assume, or request from
the backend, argument evaluation order, although my IL can reverse order
if necessary.)
It is the backend, on the other size of the IL, that needs to deal with those details.
That can include making copies of structs that the ABI says are passed
by value. But when targeting SYS V ABI (which I haven't attempted yet),
it may need to know the internal layout of a struct.
You can however do experiments with using SYS V on Linux (must be 64 bits):
* Create test structs with, say, int32 or int64 elements
* Write a test function where such a struct is passed by value, and
then return a modified copy
* Rerun the test using a version of the function where a char[] version
of the struct is passed and returned, and which contains the member
access casts you suggested
* See if it gives the same results.
You might need a union of the two structs, or use memcpy to transfer contents, before and after calling the test function.
Em 12/17/2024 4:07 PM, BGB escreveu:
On 12/17/2024 11:55 AM, Thiago Adams wrote:
Em 12/17/2024 4:03 AM, BGB escreveu:
On 12/16/2024 5:21 AM, Thiago Adams wrote:
On 15/12/2024 20:53, BGB wrote:
On 12/15/2024 3:32 PM, bart wrote:
On 15/12/2024 19:08, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive >>>>>>>> than C.
You can easily write a C++-statement that would hunddres of
lines in
C (imagines specializing a unordered_map by hand). Making a
language
less expressive makes it even less readable, and that's also
true for
your reduced C.
That's not really the point of it. This reduced C is used as an >>>>>>> intermediate language for a compiler target. It will not usually >>>>>>> be read, or maintained.
An intermediate language needs to at a lower level than the
source language.
And for this project, it needs to be compilable by any C89 compiler. >>>>>>>
Generating C++ would be quite useless.
As an IL, even C is a little overkill, unless turned into a
restricted subset (say, along similar lines to GCC's GIMPLE).
Say:
Only function-scope variables allowed;
No high-level control structures;
...
Say:
int foo(int x)
{
int i, v;
for(i=x, v=0; i>0; i--)
v=v*i;
return(v);
}
Becoming, say:
int foo(int x)
{
int i;
int v;
i=x;
v=0;
if(i<=0)goto L1;
L0:
v=v*i;
i=i-1;
if(i>0)goto L0;
L1:
return v;
}
...
I have considered to remove loops and keep only goto.
But I think this is not bring too much simplification.
It depends.
If the compiler works like an actual C compiler, with a full parser
and AST stage, yeah, it may not save much.
If the parser is a thin wrapper over 3AC operations (only allowing
statements that map 1:1 with a 3AC IR operation), it may save a bit
more...
As for whether or not it makes sense to use a C like syntax here,
this is more up for debate (for practical use within a compiler, I
would assume a binary serialization rather than an ASCII syntax,
though ASCII may be better in terms of inter-operation or human
readability).
But, as can be noted, I would assume a binary serialization that is
oriented around operators; and *not* about serializing the
structures used to implement those operators. Also I would assume
that the IR need not be in SSA form (conversion to full SSA could be
done when reading in the IR operations).
Ny argument is that not using SSA form means fewer issues for both
the serialization format and compiler front-end to need to deal with
(and is comparably easy to regenerate for the backend, with the
backend operating with its internal IR in SSA form).
Well, contrast to LLVM assuming everything is always in SSA form.
...
I also have considered split expressions.
For instance
if (a*b+c) {}
into
register int r1 = a * b;
register int r2 = r1 + c;
if (r2) {}
This would make easier to add overflow checks in runtime (if desired)
and implement things like _complex
Is this what you mean by 3AC or SSA?
3AC means that IR expressed 3 (or sometimes more) operands per IR op.
So:
MUL r1, a, b
Rather than, say, stack:
LOAD a
LOAD b
MUL
STORE r1
SSA:
Static Single Assignment
Oh sorry .. I knew what SSA is.
Generally:
Every variable may only be assigned once (more like in a functional
programming language);
Generally, variables are "merged" in the control-flow via PHI
operators (which variable merges in depending on which path control
came from).
I do similar merge in my flow analysis but without the concept of SSA.
IMHO, while SSA is preferable for backend analysis, optimization, and
code generation; it is undesirable pretty much everywhere else as it
adds too much complexity.
Better IMO for the frontend compiler and main IL stage to assume that
local variables are freely mutable.
Typically, global variables are excluded in most variants, and remain
fully mutable; but may be handled as designated LOAD/STORE operations.
In BGBCC though, full SSA only applies to temporaries. Normal local
variables are merely flagged by "version", and all versions of the
same local variable implicitly merge back together at each branch/label.
Sorry what is BGBCC ? (C compiler?)
This allows some similar advantages (for analysis and optimization)
while limiting some of the complexities. Though, this differs from
temporaries which are assumed to essentially fully disappear once they
go outside of the span in which they exist (albeit with an awkward
case to deal with temporaries that cross basic-block boundaries, which
need to actually "exist" in some semi-concrete form, more like local
variables).
Note that unless the address is taken of a local variable, it need not
have any backing in memory. Temporaries can never have their address
taken, so generally exist exclusively in CPU registers.
This would definitely simplify expressions grammar.
It can be added in the future.
I took a different approach:
In the backend IR stage, structs are essentially treated as references
to the structure.
A local structure may be "initialized" via an IR operation, in which
point it will be assigned storage in the stack frame, and the reference
will be initialized to the storage area for the structure.
Most operations will pass them by reference.
Assigning a struct will essentially be turned into a struct-copy
operation (using the same mechanism as inline memcpy).
On 12/18/2024 6:08 AM, bart wrote:
With stack code, the result conveniently ends up on top of the stack
whichever path is taken, which is a big advantage. Unless you then
have to convert that to register code, and need to ensure the values
end up in the same register when the control paths join up again.
With JVM, the rule was that all paths landing at the same label need to
have the same stack depth and same types.
With .NET, the rule was that the stack was always empty, any merging
would need to be done using variables.
BGBCC is sorta mixed:
In most cases, it follows the .NET rule;
A special-case exception exists mostly for implementing the ?: operation (which in turn has special stack operations to signal its use).
BEGINU // start a ?: operator
L0:
... //one case
SETU
JMP L2
L1:
... //other case
SETU
JMP L2
ENDU
L2:
This is a bit of wonk,
if I were designing it now, would likely do it
the same as .NET, and use temporary variables.
Em 12/18/2024 3:51 PM, BGB escreveu:
I took a different approach:
In the backend IR stage, structs are essentially treated as references
to the structure.
A local structure may be "initialized" via an IR operation, in which
point it will be assigned storage in the stack frame, and the
reference will be initialized to the storage area for the structure.
Most operations will pass them by reference.
Assigning a struct will essentially be turned into a struct-copy
operation (using the same mechanism as inline memcpy).
But what happens with calling a external C function that has a struct X
as parameter? (not pointer to struct)
On Tue, 17 Dec 2024 22:55:53 +0000, bart wrote:
On 17/12/2024 22:25, Lawrence D'Oliveiro wrote:
On Tue, 17 Dec 2024 19:45:49 +0000, bart wrote:
It's not aimed at people /implementing/ such a tool.
It is aimed at those capable of following the links to relevant specs.
It also a pretty terrible link.
Did you see this link <https://developer.mozilla.org/en-US/docs/WebAssembly/Reference>? Lots of examples from there.
On 12/18/2024 1:43 PM, Thiago Adams wrote:
Em 12/18/2024 3:51 PM, BGB escreveu:
I took a different approach:
In the backend IR stage, structs are essentially treated as
references to the structure.
A local structure may be "initialized" via an IR operation, in which
point it will be assigned storage in the stack frame, and the
reference will be initialized to the storage area for the structure.
Most operations will pass them by reference.
Assigning a struct will essentially be turned into a struct-copy
operation (using the same mechanism as inline memcpy).
But what happens with calling a external C function that has a struct
X as parameter? (not pointer to struct)
In my ABI, if larger than 16 bytes, it is passed by reference (as a
pointer in a register or on the stack), callee is responsible for
copying it somewhere else if needed.
For struct return, a pointer to return the struct into is provided by
the caller, and the callee copies the returned struct into this address.
If the caller ignores the return value, the caller provides a dummy
buffer for the return value.
If no prototype is provided... well, most likely the program crashes or similar.
So, in effect, the by-value semantics are mostly faked by the compiler.
It is roughly similar to the handling of C array types, which in this
case are also seen as a combination of a hidden pointer to the data, and
the backing data (the array's contents). The code-generator mostly
operates in terms of this hidden pointer.
By-Value Structs smaller than 16 bytes are passed as-if they were a 64
or 128 bit integer type (as a single register or as a register pair,
with a layout matching their in-memory representation).
...
But, yeah, at the IL level, one could potentially eliminate structs and arrays as a separate construct, and instead have bare pointers and a
generic "reserve a blob of bytes in the frame and initialize this
pointer to point to it" operator (with the business end of this operator happening in the function prolog).
On 19/12/2024 00:27, BGB wrote:
On 12/18/2024 1:43 PM, Thiago Adams wrote:
Em 12/18/2024 3:51 PM, BGB escreveu:
I took a different approach:
In the backend IR stage, structs are essentially treated as
references to the structure.
A local structure may be "initialized" via an IR operation, in which
point it will be assigned storage in the stack frame, and the
reference will be initialized to the storage area for the structure.
Most operations will pass them by reference.
Assigning a struct will essentially be turned into a struct-copy
operation (using the same mechanism as inline memcpy).
But what happens with calling a external C function that has a struct
X as parameter? (not pointer to struct)
In my ABI, if larger than 16 bytes, it is passed by reference (as a
pointer in a register or on the stack), callee is responsible for
copying it somewhere else if needed.
For struct return, a pointer to return the struct into is provided by
the caller, and the callee copies the returned struct into this address.
If the caller ignores the return value, the caller provides a dummy
buffer for the return value.
If no prototype is provided... well, most likely the program crashes
or similar.
So, in effect, the by-value semantics are mostly faked by the compiler.
It is roughly similar to the handling of C array types, which in this
case are also seen as a combination of a hidden pointer to the data,
and the backing data (the array's contents). The code-generator mostly
operates in terms of this hidden pointer.
By-Value Structs smaller than 16 bytes are passed as-if they were a 64
or 128 bit integer type (as a single register or as a register pair,
with a layout matching their in-memory representation).
...
But, yeah, at the IL level, one could potentially eliminate structs
and arrays as a separate construct, and instead have bare pointers and
a generic "reserve a blob of bytes in the frame and initialize this
pointer to point to it" operator (with the business end of this
operator happening in the function prolog).
The problem with this, that I mentioned elsewhere, is how well it would
work with SYS V ABI, since the rules for structs are complex, and
apparently recursive.
Having just a block of bytes might not be enough.
On 12/18/2024 6:35 PM, bart wrote:
On 19/12/2024 00:27, BGB wrote:
By-Value Structs smaller than 16 bytes are passed as-if they were a
64 or 128 bit integer type (as a single register or as a register
pair, with a layout matching their in-memory representation).
...
But, yeah, at the IL level, one could potentially eliminate structs
and arrays as a separate construct, and instead have bare pointers
and a generic "reserve a blob of bytes in the frame and initialize
this pointer to point to it" operator (with the business end of this
operator happening in the function prolog).
The problem with this, that I mentioned elsewhere, is how well it
would work with SYS V ABI, since the rules for structs are complex,
and apparently recursive.
Having just a block of bytes might not be enough.
In my case, I am not bothering with the SysV style ABI's (well, along
with there not being any x86 or x86-64 target...).
For my ISA, it is a custom ABI, but follows mostly similar rules to some
of the other "Microsoft style" ABIs (where, I have noted that across multiple targets, MS tools have tended to use similar ABI designs).
For my compiler targeting RISC-V, it uses a variation of RV's ABI rules. Argument passing is basically similar, but struct pass/return is
different; and it passes floating-point values in GPRs (and, in my own
ISA, all floating-point values use GPRs, as there are no FPU registers; though FPU registers do exist for RISC-V).
Not likely a huge issue as one is unlikely to use ELF and PE/COFF in the same program.
For the "OS" that runs on my CPU core, it is natively using PE/COFF, but
On 19/12/2024 05:46, BGB wrote:
On 12/18/2024 6:35 PM, bart wrote:
On 19/12/2024 00:27, BGB wrote:
By-Value Structs smaller than 16 bytes are passed as-if they were a
64 or 128 bit integer type (as a single register or as a register
pair, with a layout matching their in-memory representation).
...
But, yeah, at the IL level, one could potentially eliminate structs
and arrays as a separate construct, and instead have bare pointers
and a generic "reserve a blob of bytes in the frame and initialize
this pointer to point to it" operator (with the business end of this
operator happening in the function prolog).
The problem with this, that I mentioned elsewhere, is how well it
would work with SYS V ABI, since the rules for structs are complex,
and apparently recursive.
Having just a block of bytes might not be enough.
In my case, I am not bothering with the SysV style ABI's (well, along
with there not being any x86 or x86-64 target...).
I'd imagine it's worse with ARM targets as there are so many more
registers to try and deconstruct structs into.
For my ISA, it is a custom ABI, but follows mostly similar rules to
some of the other "Microsoft style" ABIs (where, I have noted that
across multiple targets, MS tools have tended to use similar ABI
designs).
When you do your own thing, it's easy.
In the 1980s, I didn't need to worry about call conventions used for
other software, since there /was/ no other software! I had to write everything, save for the odd calls to DOS which used some form of SYSCALL.
Then, arrays and structs were actually passed and returned by value (not
via hidden references), by copying the data to and from the stack.
However, I don't recall ever using the feature, as I considered it efficient. I always used explicit references in my code.
For my compiler targeting RISC-V, it uses a variation of RV's ABI rules.
Argument passing is basically similar, but struct pass/return is
different; and it passes floating-point values in GPRs (and, in my own
ISA, all floating-point values use GPRs, as there are no FPU
registers; though FPU registers do exist for RISC-V).
Supporting C's variadic functions, which is needed for many languages
when calling C across an FFI, usually requires different rules. On Win64
ABI for example, by passing low variadic arguments in both GPRs and FPU registers.
/Implementing/ variadic functions (which only occurs if implementing C)
is another headache if it has to work with the ABI (which can be assumed
for a non-static function).
I barely have a working solution for Win64 ABI, which needs to be done
via stdarg.h, but wouldn't have a clue how to do it for SYS V.
(Even Win64 has problems, as it assumes a downward-growing stack; in my
IL interpreter, the stack grows upwards!)
Not likely a huge issue as one is unlikely to use ELF and PE/COFF in
the same program.
For the "OS" that runs on my CPU core, it is natively using PE/COFF, but
That's interesting: you deliberately used one of the most complex file formats around, when you could have devised your own?
I did exactly that at a period when my generated DLLs were buggy for
some reason (it turned out to be two reasons). I created a simple
dynamic library format of my own. Then I found the same format worked
also for executables.
But I needed a loader program to run them, as Windows obviously didn't understand the format. Such a program can be written in 800 lines of C,
and can dynamically libraries in both my format, and proper DLLs (not
the buggy ones I generated!).
A hello-world program is under 300 bytes compared with 2 or
2.5KB of EXE. And the format is portable to Linux, so no need to
generate ELF (but I haven't tried). Plus the format might be transparent
to AV software (haven't tried that either).
On 12/19/2024 5:27 AM, bart wrote:
On 19/12/2024 05:46, BGB wrote:
On 12/18/2024 6:35 PM, bart wrote:
On 19/12/2024 00:27, BGB wrote:
By-Value Structs smaller than 16 bytes are passed as-if they were a >>>>> 64 or 128 bit integer type (as a single register or as a register
pair, with a layout matching their in-memory representation).
...
But, yeah, at the IL level, one could potentially eliminate structs >>>>> and arrays as a separate construct, and instead have bare pointers
and a generic "reserve a blob of bytes in the frame and initialize
this pointer to point to it" operator (with the business end of
this operator happening in the function prolog).
The problem with this, that I mentioned elsewhere, is how well it
would work with SYS V ABI, since the rules for structs are complex,
and apparently recursive.
Having just a block of bytes might not be enough.
In my case, I am not bothering with the SysV style ABI's (well, along
with there not being any x86 or x86-64 target...).
I'd imagine it's worse with ARM targets as there are so many more
registers to try and deconstruct structs into.
Not messed much with the ARM64 ABI or similar, but I will draw the line
in the sand somewhere.
Struct passing/return is enough of an edge case that one can just sort
of declare it "no go" between compilers with "mostly but not strictly compatible" ABIs.
For my ISA, it is a custom ABI, but follows mostly similar rules to
some of the other "Microsoft style" ABIs (where, I have noted that
across multiple targets, MS tools have tended to use similar ABI
designs).
When you do your own thing, it's easy.
In the 1980s, I didn't need to worry about call conventions used for
other software, since there /was/ no other software! I had to write
everything, save for the odd calls to DOS which used some form of
SYSCALL.
Then, arrays and structs were actually passed and returned by value
(not via hidden references), by copying the data to and from the stack.
However, I don't recall ever using the feature, as I considered it
efficient. I always used explicit references in my code.
Most of the time, one is passing/returning structures as pointers, and
not by value.
By value structures are usually small.
When a structure is not small, it is both simpler to implement, and
usually faster, to internally pass it by reference.
If you pass a large structure to a function by value, via an on-stack
copy, and the function assigns it to another location (say, a global variable):
Pass by reference: Only a single copy operation is needed;
Pass by value on-stack: At least two copy operations are needed.
One also needs to reserve enough space in the function arguments list to hold any structures passed, which could be bad if they are potentially large.
But, on my ISA, ABI is sort of like:
R4 ..R7 : Arg0 ..Arg3
R20..R23: Arg4 ..Arg7
R36..R39: Arg8 ..Arg11 (optional)
R52..R55: Arg12..Arg15 (optional)
Return Value:
R2, R3:R2 (128 bit)
R2 is also used to pass in the return value pointer.
'this':
Generally passed in either R3 or R18, depending on ABI variant.
Where, callee-save:
R8 ..R14, R24..R31,
R40..R47, R56..R63
R15=SP
Non-saved scratch:
R2 ..R7 , R16..R23,
R32..R39, R48..R55
Arguments beyond the first 8/16 register arguments are passed on stack.
In this case, a spill space for the first 8/16 arguments (64 or 128
bytes) is provided on stack before the first non-register argument.
If the function accepts a fixed number of arguments and the number of argument registers is 8 or less, spill space need only be provided for
the first 8 arguments (calling vararg functions will always reserve
space for 16 registers in the 16-register ABI). This spill space
effectively belongs to the callee rather than the caller.
Structures (by value):
1.. 8 bytes: Passed in a single register
9..16 bytes: Passed in a pair, padded to the next even pair
17+: Pass as a reference.
Things like 128-bit types are also passed/returned in register pairs.
Contrast, RV ABI:
X10..X17 are used for arguments;
No spill space is provided;
...
My variant uses similar rules to my own ABI for passing/returning structures, with:
X28, structure return pointer
X29, 'this'
Normal return values go into X10 or X11:X10.
Note that in both ABI's, passing 'this' in a register would mean that
class instances and COM objects are not equivalent (COM object methods always pass 'this' as the first argument).
The 'this' register is implicitly also used by lambdas to pass in the pointer to the captured bindings area (which mostly resembles a
structure containing each variable captured by the lambda).
Can note though that in this case, capturing a binding by reference
means the lambda is limited to automatic lifetime (non-automatic lambdas
may only capture by value). In this case, capture by value is the default.
For my compiler targeting RISC-V, it uses a variation of RV's ABI rules. >>> Argument passing is basically similar, but struct pass/return is
different; and it passes floating-point values in GPRs (and, in my
own ISA, all floating-point values use GPRs, as there are no FPU
registers; though FPU registers do exist for RISC-V).
Supporting C's variadic functions, which is needed for many languages
when calling C across an FFI, usually requires different rules. On
Win64 ABI for example, by passing low variadic arguments in both GPRs
and FPU registers.
I simplified things by assuming only GPRs are used.
/Implementing/ variadic functions (which only occurs if implementing
C) is another headache if it has to work with the ABI (which can be
assumed for a non-static function).
I barely have a working solution for Win64 ABI, which needs to be done
via stdarg.h, but wouldn't have a clue how to do it for SYS V.
(Even Win64 has problems, as it assumes a downward-growing stack; in
my IL interpreter, the stack grows upwards!)
Most targets use a downward growing stack.
Mine is no exception here...
Not likely a huge issue as one is unlikely to use ELF and PE/COFF inThat's interesting: you deliberately used one of the most complex file
the same program.
For the "OS" that runs on my CPU core, it is natively using PE/COFF, but >>
formats around, when you could have devised your own?
For what I wanted, I would have mostly needed to recreate most of the
same functionality as PE/COFF anyways.
When one considers the entire loading process (including DLLs/SOs), then PE/COFF loading is actually simpler than ELF loading (ELF subjects the loader to needing to deal with symbol and relocation tables), similar to
PIE loading.
Things like the MZ stub are optional in my case, and mostly ignored if present (in my LZ compressed PE variants, the MZ stub is omitted entirely).
I had at one point considered doing a custom format resembling LZ
compressed MachO, but ended up not bothering, as it wouldn't have really saved anything over LZ compressed PE/COFF.
Some "unneeded cruft" like the Resource Section was discarded, mostly replaced by an embedded WAD2 image. The header was modified some to
allow for backwards compatibility with the Windows format (mostly
creating a dummy header in the original format that points to the WAD2 directory).
Idea is that icons, bitmaps, and other things, would mostly be held in
WAD lumps. Though, resources which may be accessed via symbols in the EXE/DLL need to be stored uncompressed (where "__rsrc_lumpname" may be
used to access the contents of resource-section lumps as an extern symbol).
Say, for example:
extern byte __rsrc_mybitmap[]; //resolves to a DIB/BMP or similar
For now, resource formats:
Images:
BMP (various settings)
4, 8, and 16 bpp typical
Supports a non-standard 16-bpp alpha-blended mode (*1).
Supports non-standard 16 color and 256 color with transparent.
Supports CRAM BMP as well (2 bpp)
QOI (assumes RGBA32, nominally lossless)
QOI is a semi-simplistic non-entropy-coded format.
Can give PNG-like compression in some cases.
Reasonably fast/cheap to decode.
LCIF, custom lossy format, color-cell compression.
OK Q/bpp but mostly only on the low-end.
Resembles a QOI+CRAM hybrid.
UPIC, lossy or lossless, JPEG-like (*2)
*1:
0rrrrrgggggbbbbb Normal/Opaque
1rrrraggggabbbba With 3 bit alpha (4b/ch RGB).
For 16 and 256 color, a variant is supported with a transparent color. Generally the high intensity magenta is reused as the transparent color. This is encoded in the color palette (if all colors apart from one have
the alpha bits set to FF, and one color has 00, then that color is
assumed to be a transparent color).
CRAM bpp: Uses a limited form of the 8-bit CRAM format:
16 bits, 4x4 pixels, 1 bit per pixel
2x 8 bits: Color Endpoints
The rest of the format being unsupported, so it can simply assume a
fixed 32-bits per 4x4 pixel cell.
*2: The UPIC format is structurally similar to JPEG, but:
Uses TLV packaging (vs FF-escape tagging);
Uses Rice coding (vs Huffman)
Uses Z3.V5 VLC, vs Z4.V4
Uses Block-Haar and RCT
Vs DCT and YCbCr.
Supports an alpha channel.
Y 1 (*2A)
YA 1:1 (*2A)
YUV 4:2:0
YUV 4:4:4 (*2A)
YUVA 4:2:0:4
YUVA 4:4:4:4 (*2A)
*2A: May be used in the lossless modes, depending on image.
VLC coding resembles Deflate's natch distance encoding, with sign-folded values. Runs of zero coefficients have a shorter limit, but similar.
Like with JPEG, an 0x00 symbol encodes an early EOB.
In tests, on my main PC:
Vs JPEG: It is a little faster
Q/bpp is similar, better/worse depends on image.
Slightly worse on photos, but "similar".
Generally somewhat better on artificial images.
Vs PNG:
Faster to decode (with less memory overhead);
Better compression on many images (particularly photo-like).
Note that UPIC was designed to not require any large intermediate
buffers, so will decode directly to an RGB555 or RGBA32 output buffer (decoding happens in terms of individual 16x16 pixel macroblocks).
It was designed to be moderately fast and to try to minimize memory
overhead for decoding (vs either PNG or JPEG, which need a more
significant chunk of working memory to decode).
Block-Haar is a Haar transform made to fit the same 8x8 pixel blocks as
DCT, where Haar maps (A,B)->(C,D):
C=(A+B)/2 (*: X/2 here being defined as (X>>1))
D=A-B
But, can be reversed exactly, IIRC:
B=C-(D/2)
A=B+D
By doing multiple stages of Haar transform, one can build an 8-pixel version, and then use horizontal and vertical transforms for an 8x8
block. It is computationally fairly cheap, and lossless.
The Walsh-Hadamard transform can give similar properties, but generally involves a few extra steps that make it more computationally expensive.
It is possible to use a lifting transform to make a Reversible DCT, but
it is slow...
BGBCC accepts JPEG and PNG for input and can convert them to BMP/QOI/
UPIC as needed.
For audio storage, generally using the RIFF WAV format. For bulk audio,
both A-Law and IMA ADPCM work OK. Granted, IMA ADPCM is not space
efficient for stereo, but mostly OK for mono (most common use-case for
sound effects).
I did exactly that at a period when my generated DLLs were buggy for
some reason (it turned out to be two reasons). I created a simple
dynamic library format of my own. Then I found the same format worked
also for executables.
But I needed a loader program to run them, as Windows obviously didn't
understand the format. Such a program can be written in 800 lines of
C, and can dynamically libraries in both my format, and proper DLLs
(not the buggy ones I generated!).
A hello-world program is under 300 bytes compared with 2 or
2.5KB of EXE. And the format is portable to Linux, so no need to
generate ELF (but I haven't tried). Plus the format might be
transparent to AV software (haven't tried that either).
OK.
By design, my PEL format (PE+LZ) isn't going to get under 2K (1K for headers, 1K for LZ'ed sections).
But, usually this is not a problem.
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.
Every variable may only be assigned once ...
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.
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?
(Unless you just wanted to say that in some HLL abstraction like 'printf("Hello world!\n")' there's no [visible] conditional branch.
Likewise in a 'ClearAccumulator' machine instruction, or the like.)
The comparisons and predicates are one key function (not any specific
branch construct, whether on HLL level, assembler level, or with the (elementary but most powerful) Turing Machine). Comparisons inherently result in predicates which is what controls program execution).
So your statement asks for some explanation at least.
So your statement asks for some explanation at least.
Janis
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens years.
And it shows.
On 21.12.2024 23:20, Michael S wrote:
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens
years. And it shows.
Ranks and titles are, per se, no guarantee. I'm not impressed; I've
seen all sorts/qualities of professors. YMMV.
If that is true (that he was one) I'm wondering why we observe so
often that he posts statements here and doesn't care to explain it.
At least the many _good_ professors I met in my life typically were
keen to explain their theses, statements, or knowledge (instead of
dragging that out of him).
Janis
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
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?
(Unless you just wanted to say that in some HLL abstraction like
'printf("Hello world!\n")' there's no [visible] conditional branch.
Likewise in a 'ClearAccumulator' machine instruction, or the like.)
The comparisons and predicates are one key function (not any specific
branch construct, whether on HLL level, assembler level, or with the
(elementary but most powerful) Turing Machine). Comparisons inherently
result in predicates which is what controls program execution).
So your statement asks for some explanation at least.
Start with C - any of C90, C99, C11.
Take away the short-circuiting operators - &&, ||, ?:.
Take away all statement types that involve intra-function transfer
of control: goto, break, continue, if, for, while, switch, do/while.
Might as well take away statement labels too.
Take away setjmp and longjmp.
Rule out programs with undefined behavior.
The language that is left is still Turing complete.
Proof: exercise for the reader.
On Sun, 22 Dec 2024 01:13:07 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
On 21.12.2024 23:20, Michael S wrote:
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens
years. And it shows.
Ranks and titles are, per se, no guarantee. I'm not impressed; I've
seen all sorts/qualities of professors. YMMV.
If that is true (that he was one) I'm wondering why we observe so
often that he posts statements here and doesn't care to explain it.
At least the many _good_ professors I met in my life typically were
keen to explain their theses, statements, or knowledge (instead of
dragging that out of him).
It seems, you didn't understand me. (Ogh, it is contagious ;-)
On 22.12.2024 01:18, Michael S wrote:
On Sun, 22 Dec 2024 01:13:07 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
On 21.12.2024 23:20, Michael S wrote:
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens
years. And it shows.
Ranks and titles are, per se, no guarantee. I'm not impressed; I've
seen all sorts/qualities of professors. YMMV.
If that is true (that he was one) I'm wondering why we observe so
often that he posts statements here and doesn't care to explain it.
At least the many _good_ professors I met in my life typically were
keen to explain their theses, statements, or knowledge (instead of
dragging that out of him).
It seems, you didn't understand me. (Ogh, it is contagious ;-)
I'm sorry, no. - I certainly took it literally - as I do (at first)
with most people and their statements (until I get to know better).
If it was meant sarcastically or anything, I'd appreciate a smiley
or something like that. (It certainly wasn't obvious to me.)
If it was meant serious and I completely missed the point - which
may also happen occasionally - I'd appreciate a pointer.
Janis
[...]
Part of the answer is in your previous response.
You wrote: "many _good_ professors I met in my life typically were
keen to explain their theses, statements, or knowledge (instead of
dragging that out of him)". You essentially admitted that not all good professors behave like that.
[ "schools of teaching" stuff snipped ]
You make an impression of one that received basics of CS. Probably, 40
or so years ago, but still you have to know basic facts. Unlike me, for example.
So, Tim expects that you will be able to utilizes his hints.
And that
it would lead to much better understanding on your part then if he
feeds you by teaspoon.
That is one part. Another part is that he is annoyed by your tone.
There is more than one school of teaching. One school believes that
students learn from explanations and exercises. Other school believes
that students learn best when provided with bare basics and then asked
to figure out the rest by themselves.
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?
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).
Or try to figure out how to do this knowing that C has function
pointers.
On Sun, 22 Dec 2024 06:01:52 -0000 (UTC)
antispam@fricas.org (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).
Considering that Janis replied to your post I find a possibility that
he did not look at it unlikely. Although not completely impossible.
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?
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
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?
I don't want to speak for Tim, but as far as I am concerned, it all
boils down to what you take to be a model of (effective) computation.
In some purely theoretical sense, models like the pure lambda calculus
and combinator calculus are "complete" and they have no specific
conditional "branches".
Going into detail (such as examples of making a "choice" in pure lambda calculus) are way off topic here.
This is exactly what comp.theory should be used for, so I will cross
post there and set the followup-to header. comp.theory has been trashed
by cranks but maybe a topical post will help it a but.
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 [...]
On 12/21/24 20:04, Michael S wrote:
...
There is more than one school of teaching. One school believes that
students learn from explanations and exercises. Other school believes
that students learn best when provided with bare basics and then asked
to figure out the rest by themselves.
I personally believe that Tim generally thinks there's a justification
for what he says, and that we'd be better off figuring it out ourselves.
I also know, from the rare occasions when he's been convinced to provide
his justification, that I often don't consider his justification valid. However, he says things that seem to be unjustified so often, I can't
help wondering if he doesn't occasionally say things he realizes are unjustified (either at the time, or as the result of subsequent
discussion), and withholds his justifications in order to hide the fact
that he knows he was wrong. Probably not, but I keep wondering.
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).
Or try to figure out how to do this knowing that C has function
pointers.
antispam@fricas.org (Waldek Hebisch) writes:
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>
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 [...]
What makes you think I didn't?
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?
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.
Janis
On 2024-12-21, 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?
In a functional langauge, we can make a decision by, for instance,
putting two lambdas into an array A, and then calling A[0] or A[1],
where the index 0 or 1 is comes from some Boolean result.
The only reason we have a control construct like if(A, X, Y) where X
is only evaluated if A is true, otherwise Y, is that X and Y
have side effects.
If X and Y don't have side effects, then if(A, X, Y) can be an ordinary function whose arguments are strictly evaluated.
Moreover, if we give the functional language lazy evaluation semantics,
then anyway we get the behavior that Y is not evaluated if A is true,
and that lazy evaluation model can be used as the basis for sneaking
effects into the functional language and conctrolling them.
Anyway, Turing calculation by primitive recursion does not require conditional branching. Just perhaps an if function which returns
either its second or third argument based on the truth value of
its first argument.
For instance, in certain C preprocessor tricks, conditional expansion
is achieved by such macros.
When we run the following through the GNU C preprocessor (e.g. by pasting into gcc -E -x c -p -):
#define TRUE_SELECT_TRUE(X) X
#define TRUE_SELECT_FALSE(X)
#define FALSE_SELECT_TRUE(X)
#define FALSE_SELECT_FALSE(X) X
#define SELECT_TRUE(X) X
#define SELECT_FALSE(X)
#define PASTE(X, Y) X ## Y
#define IF(A, B, C) PASTE(TRUE_SELECT_, A)(B) PASTE(FALSE_SELECT_, A)(C)
#define FOO TRUE
#define BAR FALSE
IF(FOO, foo is true, foo is false)
IF(BAR, bar is true, bar is false)
We get these tokens:
foo is true
bar is false
Yet, macro expansion has no conditionals. The preprocessing language has
#if and #ifdef, but we didn't use those. Just expansion of computed names.
This is an example of not strictly needing conditionals to achieve conditional evaluation or expansion: an IF(A, B, C) operator that
yields B or C depending on the truth of A, and so forth.
John MacCarthy (Lisp inventor) wrote himself such an IF function
in Fortran, in a program for calculating chess moves. It evaluated
both the B and C expressions, and so it wasn't a proper imperative conditional, but it didn't matter.
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>
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.
On 22/12/2024 21:45, Kaz Kylheku wrote:
On 2024-12-21, 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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>
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?
In a functional langauge, we can make a decision by, for instance,
putting two lambdas into an array A, and then calling A[0] or A[1],
where the index 0 or 1 is comes from some Boolean result.
The only reason we have a control construct like if(A, X, Y) where X
is only evaluated if A is true, otherwise Y, is that X and Y
have side effects.
If X and Y don't have side effects, then if(A, X, Y) can be an ordinary
function whose arguments are strictly evaluated.
Moreover, if we give the functional language lazy evaluation semantics,
then anyway we get the behavior that Y is not evaluated if A is true,
and that lazy evaluation model can be used as the basis for sneaking
effects into the functional language and conctrolling them.
Anyway, Turing calculation by primitive recursion does not require
conditional branching. Just perhaps an if function which returns
either its second or third argument based on the truth value of
its first argument.
For instance, in certain C preprocessor tricks, conditional expansion
is achieved by such macros.
When we run the following through the GNU C preprocessor (e.g. by pasting
into gcc -E -x c -p -):
#define TRUE_SELECT_TRUE(X) X
#define TRUE_SELECT_FALSE(X)
#define FALSE_SELECT_TRUE(X)
#define FALSE_SELECT_FALSE(X) X
#define SELECT_TRUE(X) X
#define SELECT_FALSE(X)
#define PASTE(X, Y) X ## Y
#define IF(A, B, C) PASTE(TRUE_SELECT_, A)(B) PASTE(FALSE_SELECT_, A)(C) >>
#define FOO TRUE
#define BAR FALSE
IF(FOO, foo is true, foo is false)
IF(BAR, bar is true, bar is false)
We get these tokens:
foo is true
bar is false
So, how long did it take to debug? (I've no idea how it works. If I
change all TRUE/FALSE to BART/LISA respectively, it still gives the same output. I'm not sure how germane such an example is.)
On 2024-12-21, 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?
In a functional langauge, we can make a decision by, for instance,
putting two lambdas into an array A, and then calling A[0] or A[1],
where the index 0 or 1 is comes from some Boolean result.
The only reason we have a control construct like if(A, X, Y) where X
is only evaluated if A is true, otherwise Y, is that X and Y
have side effects.
If X and Y don't have side effects, then if(A, X, Y) can be an ordinary function whose arguments are strictly evaluated.
Moreover, if we give the functional language lazy evaluation
semantics, then anyway we get the behavior that Y is not evaluated
if A is true, and that lazy evaluation model can be used as the
basis for sneaking effects into the functional language and
conctrolling them.
Anyway, Turing calculation by primitive recursion does not require conditional branching. Just perhaps an if function which returns
either its second or third argument based on the truth value of its
first argument.
For instance, in certain C preprocessor tricks, conditional
expansion is achieved by such macros.
When we run the following through the GNU C preprocessor (e.g. by
pasting into gcc -E -x c -p -):
#define TRUE_SELECT_TRUE(X) X
#define TRUE_SELECT_FALSE(X)
#define FALSE_SELECT_TRUE(X)
#define FALSE_SELECT_FALSE(X) X
#define SELECT_TRUE(X) X
#define SELECT_FALSE(X)
#define PASTE(X, Y) X ## Y
#define IF(A, B, C) PASTE(TRUE_SELECT_, A)(B) PASTE(FALSE_SELECT_, A)(C)
#define FOO TRUE
#define BAR FALSE
IF(FOO, foo is true, foo is false)
IF(BAR, bar is true, bar is false)
We get these tokens:
foo is true
bar is false
Yet, macro expansion has no conditionals. The preprocessing
language has #if and #ifdef, but we didn't use those. Just
expansion of computed names.
On 22.12.2024 02:04, Michael S wrote:
[...]
Part of the answer is in your previous response.
You wrote: "many _good_ professors I met in my life typically were
keen to explain their theses, statements, or knowledge (instead of
dragging that out of him)". You essentially admitted that not all good
professors behave like that.
Oh, what I meant to express was different; that good professors
*would* explain it (only bad ones wouldn't).
(At least that was my experience; and not only covering the CS
domain, BTW.)
[ "schools of teaching" stuff snipped ]
You make an impression of one that received basics of CS. Probably, 40
or so years ago, but still you have to know basic facts. Unlike me, for
example.
So, Tim expects that you will be able to utilizes his hints.
The point [repeatedly] stated (also by others here) was that
he more often than not just provides no information but simple
arbitrary statements of opinion.
... (what debug mechanisms I have, effectively lack any symbols
for things inside "ld-linux.so"'s domain).
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are
no more statements of opinion than a statement about whether the
Riemann Hypothesis is true is a statement of opinion. Someone
might wonder whether an assertion "The Riemann Hypothesis is
true" is true or false, but it is still a matter of fact, not a
matter of opinion.
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are opinions _about facts_, or if you prefer, opinion
about truth value of some statements.
They are
no more statements of opinion than a statement about whether the
Riemann Hypothesis is true is a statement of opinion. Someone
might wonder whether an assertion "The Riemann Hypothesis is
true" is true or false, but it is still a matter of fact, not a
matter of opinion.
It is reasobable to assume that you do not know if Riemann Hypothesis
is true or false.
So if you say "Riemann Hypothesis is true",
this is just your opinion.
I am not a native English speaker
but I believed that "statements of opinion" means just that:
person does not know the truth, but makes a statement.
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>
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.
On Wed, 18 Dec 2024 23:46:21 -0600, BGB wrote:
... (what debug mechanisms I have, effectively lack any symbols
for things inside "ld-linux.so"'s domain).
nm -D /lib/ld-linux.so.2
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.
And Tim did not rule out using the standard library,
On 23/12/2024 08:46, David Brown wrote:
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)".
Isn't this just !n ? I don't think "!" was ruled out. This would also
work for negative n.
And Tim did not rule out using the standard library, which would
surely open up new possibilities.
printf (not sprintf) would be reasonable here to show results. Anything
else could be considered cheating.
The original context was a small subset of C that can be used to
represent a larger subset.
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
On Sun, 22 Dec 2024 20:41:44 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
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.
Janis
You make no sense. I am starting to suspect that the reason for it
is ignorance rather than mere stubbornness.
https://godbolt.org/z/EKo5rrYce
Show me conditional branch in the right pane.
Michael S <already5chosen@yahoo.com> writes:
On Sun, 22 Dec 2024 20:41:44 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
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.
Janis
You make no sense. I am starting to suspect that the reason for it
is ignorance rather than mere stubbornness.
https://godbolt.org/z/EKo5rrYce
Show me conditional branch in the right pane.
The 'C' in 'CSET' is short for conditional. Because
the branch is folded into the compare doesn't mean it
isn't there.
Michael S <already5chosen@yahoo.com> writes:
On Sun, 22 Dec 2024 20:41:44 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
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.
Janis
You make no sense. I am starting to suspect that the reason for it
is ignorance rather than mere stubbornness.
https://godbolt.org/z/EKo5rrYce
Show me conditional branch in the right pane.
The 'C' in 'CSET' is short for conditional. Because
the branch is folded into the compare doesn't mean it
isn't there.
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens years.
And it shows.
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
Michael S <already5chosen@yahoo.com> writes:
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens years.
And it shows.
I'm not sure whether to feel flattered or insulted. ;)
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>>
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.
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>
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.
Michael S <already5chosen@yahoo.com> writes:
On Sun, 22 Dec 2024 20:41:44 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
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 make no sense. I am starting to suspect that the reason for it
is ignorance rather than mere stubbornness.
https://godbolt.org/z/EKo5rrYce
Show me conditional branch in the right pane.
The 'C' in 'CSET' is short for conditional. Because
the branch is folded into the compare doesn't mean it
isn't there.
On 12/23/2024 1:02 PM, Tim Rentsch wrote:
Michael S <already5chosen@yahoo.com> writes:
On Sat, 21 Dec 2024 21:31:24 +0100
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
So your statement asks for some explanation at least.
I would guess that Tim worked as CS professor for several dozens years.
And it shows.
I'm not sure whether to feel flattered or insulted. ;)
AHAHA! lol. You forced me to laugh here. wow. :^D
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters.
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters.
Hmm... I'm puzzled. Where does the unbounded store come from without
I/O? Do you take "C is Turing complete" to mean that there is a theoretically possible implementation of C sufficient for any given
problem instance (rather than for any given problem)? That's not how different models are usually compared, and I think it would run into
some rather odd theoretical problems.
There is a somewhat informal version of "C (with the restrictions you
have stated) is Turing complete" which just means "you can do anything
you want provided you don't hit an implementation limit".
On 23/12/2024 03:41, Waldek Hebisch wrote:
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are opinions _about facts_, or if you prefer, opinion
about truth value of some statements.
You can program in C without the "normal" conditional statements or expressions. You can make an array of two (or more) function pointers
and select between them using your controlling expression, and that
should be sufficient for conditionals. (There may be other methods too.)
So as far as I can see, Tim gave statements of fact, not opinion.
You can say that Tim's posts were patronising, arrogant, and irritating.
/That/ would be an opinion - a /justified/ opinion because it is
backed up in the evidence of these posts and corroborating evidence from previous posts and discussions from Tim. But without some kind of
precise definition of the terms involved and a robust and repeatable
method of classification, it could not be called "fact".
You could say that Tim's posts were intended to be annoying, or you
could say that he has refused to give an answer to how C can be used
without the "normal" conditionals because he realises he was wrong in
his posts and won't admit it. That would be /unjustified/ opinion - or "speculation" - because we have no way of knowing his motives or
anything more than what he wrote in his posts.
You could, quite fairly, characterise Tim's posts as unjustified
statements of fact - because he has stated his claim as fact, but has
given no justification or reasoning, and it is not something that is
obvious or well-known to people.
They are
no more statements of opinion than a statement about whether the
Riemann Hypothesis is true is a statement of opinion. Someone
might wonder whether an assertion "The Riemann Hypothesis is
true" is true or false, but it is still a matter of fact, not a
matter of opinion.
It is reasobable to assume that you do not know if Riemann Hypothesis
is true or false.
I think if anyone knew the truth of falsity of the Riemann Hypothesis - i.e., they had a proof one way or the other - we'd have heard about it!
So if you say "Riemann Hypothesis is true",
this is just your opinion.
No, that would not be an opinion. It would be an unjustified claim.
"I /believe/ the Riemann Hypothesis is true" is an opinion.
I am not a native English speaker
but I believed that "statements of opinion" means just that:
person does not know the truth, but makes a statement.
No, an opinion is a personal preference or judgement. That's very different from not knowing about something factual. If I say "the
number 17 will turn up in next week's lottery numbers", that's not an opinion, it's a claim about facts. It's an unjustified claim, since I don't know if it is true or not, but it's not an opinion.
It is not always clear when something is a fact or not, and whether a statement is a justified statement of fact, an unjustified statement of
fact (i.e., it might happen to be true, but you have not presented
evidence of it), a justified opinion, or an unjustified opinion. I'm
sure there's a philosophy group on Usenet somewhere, but I doubt if cross-posting there would lead to any clarification!
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters. Except for a very small
set of functions -- eg, fopen, fgetc, fputc, malloc, free --
everything else in the standard library either isn't important
for Turing Completeness or can be synthesized from the base
set. The functionality of fprintf(), for example, can be
implemented on top of fputc and non-library language features.
On 12/23/2024 3:18 PM, Tim Rentsch wrote:
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters. Except for a very small
set of functions -- eg, fopen, fgetc, fputc, malloc, free --
everything else in the standard library either isn't important
for Turing Completeness or can be synthesized from the base
set. The functionality of fprintf(), for example, can be
implemented on top of fputc and non-library language features.
If I were to choose a set of primitive functions, probably:
malloc/free and/or realloc
could define, say:
malloc(sz) => realloc(NULL, sz)
free(ptr) => realloc(ptr, 0)
Maybe _msize and _mtag/..., but this is non-standard.
With _msize, can implement realloc on top of malloc/free.
For basic IO:
fopen, fclose, fseek, fread, fwrite
printf could be implemented on top of vsnprintf and fputs
fputs can be implemented on top of fwrite (via strlen).
With a temporary buffer buffer being used for the printed string.
...
Though, one may still end up with various other stuff over the interface
as well. Though, the interface can be made open-ended if one has a GetInterface call or similar, which can request other interfaces given
an ID, such as, FOURCC/EIGHTCC pair, a SIXTEENCC, or GUID (*1). IMHO, generally preferable over a "GetProcAddress" mechanism due to lower overheads; tough, with an annoyance that interface vtables generally
have a fixed layout (generally can't really add or change anything
without creating binary compatibility issues; so a lot of tables/
structures need to be kept semi-frozen).
Though, APIs like DirectX had dealt with the issue of having version
numbers for vtables and then one requests a specific version of the
vtable (within the range of versions supported by the major version of DirectX). But, this is crufty.
*1: Say: QWORD qwMajor, QWORD qwMinor.
qwMajor:
Major ID (FOURCC, EIGHTCC)
Or: First 8 bytes of SIXTEENCC or GUID
qwMinor:
SubID/Version (FOURCC or EIGHTCC)
Second 8 bytes of SIXTEENCC or GUID.
Where:
High 32 bits are 0, assume FOURCC.
Else, look at bits to determine EIGHTCC vs GUID.
Assume if both are EIGHTCC, value represents a SIXTEENCC.
Bit patterns for valid SIXTEENCCs vs GUIDs are mutually exclusive.
Names make more sense for public interfaces.
Leaving GUIDs mostly for private/internal interfaces.
Well, unlike Windows, where they use GUIDs for pretty much everything
here (and also, I didn't bother with an IDL compiler; generally doing
all this directly in C).
Well, and some wonk, like the exact contents of structures like BITMAPINFOHEADER being interpreted based on using biSize as a magic
number (well, sometimes with other stuff glued onto the end, as
understood based the use of the biCompression field), ...
But, it has held up well, this structure being almost as old as I am...
In a few cases, one might also take the option of using a "DriverProc()" style interface, where one provides a pair of context-dependent pointers
and uses magic numbers to identify the desired operation, or, intermediate:
(*ifvt)->QueryProc(ifvt, iHdl, lParm, pParm1, pParm2);
(*ifvt)->ModifyProc(ifvt, iHdl, lParm, pParm1, pParm2);
Where, QueryProc is intended for non-destructive operations, and
ModifyProc for destructive operations.
iHdl: Context-dependent integer handle;
lParm: Magic command number.
pParm1/pParm2: Magic pointers, often:
pParm1: Input data address;
pParm2: Output data address.
Where, vtable is usually provided in "VT **" form, hence the need to
deref the table before a method can be invoked.
Actually, some of this overlaps with how I had implemented the C library
for DLLs in my project:
Only the main binary has the full C library;
DLL's generally use a C library which calls back to the main C library
via a COM style interface (things like malloc/free and stdio calls are routed over this interface).
Note that this is partly because in my case:
1, DLLs only allow an acyclic dependency graph;
2, The mechanism does not currently allow sharing global variables;
3, There was a desire to allow dlopen/dlsym to dynamically load libraries.
1 & 3 mean that if a statically-linked C library is used for the main binary:
One needs to also statically link a C library to each DLL;
The C library needs to operate over a COM interface for shared interfaces.
Or, alternatively, that only a DLL may be used for the C library, and
all DLLs would need to use the same C library DLL.
Note that neither 1 nor 2 traditionally apply with ELF Shared Objects
(which usually both shared everything and allow for cyclic dependency graphs). But, traditionally ELF has other drawbacks, like needing to
access variables and call functions via a GOT (which has higher overhead than direct calls, or accessing global variables as a fixed offset
relative to a known base register, ...).
Note that having the kernel inject DLLs into a running process wouldn't really mix well with the way glibc approaches shared objects (where, it manages this stuff in userland, rather than having this left up to the kernel's program loader).
May not matter as much though as if providing an COM-like interface, one doesn't necessarily actually need dlopen/dlsym to be able to see the
symbols in the library that the interface came from.
Where, in this case, COM-like interfaces may be used in ways that
deviate from usual dependency ordering; and was more flexible. They are awkward to use directly, so it may make sense to provide C API wrappers (thus far, usually statically linked, but they can fetch the interfaces
they need from the main C library or the OS).
Where, in my case, the OS interface is a mix of conventional syscalls
and object-method-calls routed over the syscall interface (the target
being either in the kernel or in another process; or the OS might load a
DLL into the client process and return a process-local vtable).
If non-local, generally the method pointers are generic, and serve to forward the call over the syscall mechanism (the syscall interface being used in a somewhat different way from how it would be used in something
like Linux; where Linux generally just does not do things this way...).
On Sun, 15 Dec 2024 20:08:53 +0100, Bonita Montero wrote:
C++ is more readable because is is magnitudes more expressive than C.
And it is certainly more surprising than C. Often unpleasantly so.
You can easily write a C++-statement that would hunddres of lines in C
Yes, but *which* hundreds of lines, exactly, would be the correct C >equivalent?
On 12/23/2024 1:43 AM, David Brown wrote:
On 23/12/2024 03:41, Waldek Hebisch wrote:
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are opinions _about facts_, or if you prefer, opinion
about truth value of some statements.
You can program in C without the "normal" conditional statements or
expressions. You can make an array of two (or more) function
pointers and select between them using your controlling expression,
and that should be sufficient for conditionals. (There may be other
methods too.)
So as far as I can see, Tim gave statements of fact, not opinion.
Jumping back in:
That one can do this seems obvious enough;
Downside, as I see it, is that there is no current or likely
processor hardware where this is likely to be performance
competitive with the more traditional if-goto mechanism [...]
On 12/23/2024 3:18 PM, Tim Rentsch wrote:
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters. Except for a very small
set of functions -- eg, fopen, fgetc, fputc, malloc, free --
everything else in the standard library either isn't important
for Turing Completeness or can be synthesized from the base
set. The functionality of fprintf(), for example, can be
implemented on top of fputc and non-library language features.
If I were to choose a set of primitive functions, probably:
malloc/free and/or realloc
could define, say:
malloc(sz) => realloc(NULL, sz)
free(ptr) => realloc(ptr, 0)
Maybe _msize and _mtag/..., but this is non-standard.
With _msize, can implement realloc on top of malloc/free.
For basic IO:
fopen, fclose, fseek, fread, fwrite
printf could be implemented on top of vsnprintf and fputs
fputs can be implemented on top of fwrite (via strlen).
With a temporary buffer buffer being used for the printed string.
BGB <cr88192@gmail.com> writes:
On 12/23/2024 3:18 PM, Tim Rentsch wrote:
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters. Except for a very small
set of functions -- eg, fopen, fgetc, fputc, malloc, free --
everything else in the standard library either isn't important
for Turing Completeness or can be synthesized from the base
set. The functionality of fprintf(), for example, can be
implemented on top of fputc and non-library language features.
If I were to choose a set of primitive functions, probably:
malloc/free and/or realloc
could define, say:
malloc(sz) => realloc(NULL, sz)
free(ptr) => realloc(ptr, 0)
Maybe _msize and _mtag/..., but this is non-standard.
With _msize, can implement realloc on top of malloc/free.
For basic IO:
fopen, fclose, fseek, fread, fwrite
printf could be implemented on top of vsnprintf and fputs
fputs can be implemented on top of fwrite (via strlen).
With a temporary buffer buffer being used for the printed string.
Most of these aren't needed. I think everything can be
done using only fopen, fclose, fgetc, fputc, and feof.
On 12/28/2024 11:24 AM, Tim Rentsch wrote:
BGB <cr88192@gmail.com> writes:
On 12/23/2024 3:18 PM, Tim Rentsch wrote:
Michael S <already5chosen@yahoo.com> writes:
On Mon, 23 Dec 2024 09:46:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
And Tim did not rule out using the standard library,
Are you sure?
I explicitly called out setjmp and longjmp as being excluded.
Based on that, it's reasonable to infer the rest of the
standard library is allowed.
Furthermore I don't think it matters. Except for a very small
set of functions -- eg, fopen, fgetc, fputc, malloc, free --
everything else in the standard library either isn't important
for Turing Completeness or can be synthesized from the base
set. The functionality of fprintf(), for example, can be
implemented on top of fputc and non-library language features.
If I were to choose a set of primitive functions, probably:
malloc/free and/or realloc
could define, say:
malloc(sz) => realloc(NULL, sz)
free(ptr) => realloc(ptr, 0)
Maybe _msize and _mtag/..., but this is non-standard.
With _msize, can implement realloc on top of malloc/free.
For basic IO:
fopen, fclose, fseek, fread, fwrite
printf could be implemented on top of vsnprintf and fputs
fputs can be implemented on top of fwrite (via strlen).
With a temporary buffer buffer being used for the printed string.
Most of these aren't needed. I think everything can be
done using only fopen, fclose, fgetc, fputc, and feof.
If you only have fgetc and fputc, IO speeds are going to be
unacceptably slow for non-trivial file sizes.
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
antispam@fricas.org (Waldek Hebisch) writes:
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:
[...]A 'goto' may be used but it isn't strictly *necessary*. What *is*
Pretty much all higher level control flow can be expressed via goto. >>>>>>
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 [...]
What makes you think I didn't?
I made the same claim as you earlier and gave examples. You
did not acknowledge my posts. Why? For me most natural
explanation is that you did not read them.
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are opinions _about facts_, or if you prefer, opinion
about truth value of some statements.
They are
no more statements of opinion than a statement about whether the
Riemann Hypothesis is true is a statement of opinion. Someone
might wonder whether an assertion "The Riemann Hypothesis is
true" is true or false, but it is still a matter of fact, not a
matter of opinion.
It is reasobable to assume that you do not know if Riemann Hypothesis
is true or false. So if you say "Riemann Hypothesis is true",
this is just your opinion. I am not a native English speaker
but I believed that "statements of opinion" means just that:
person does not know the truth, but makes a statement.
antispam@fricas.org (Waldek Hebisch) writes:
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
The comments I made here, in two responses to postings of yours,
were not statements of opinion but statements of fact.
They are opinions _about facts_, or if you prefer, opinion
about truth value of some statements.
They are
no more statements of opinion than a statement about whether the
Riemann Hypothesis is true is a statement of opinion. Someone
might wonder whether an assertion "The Riemann Hypothesis is
true" is true or false, but it is still a matter of fact, not a
matter of opinion.
It is reasobable to assume that you do not know if Riemann Hypothesis
is true or false. So if you say "Riemann Hypothesis is true",
this is just your opinion. I am not a native English speaker
but I believed that "statements of opinion" means just that:
person does not know the truth, but makes a statement.
A statement of opinion is a statement concerning a subjective
question, such as "Do cats make better pets than dogs?"
A statement of fact is a statement concerning an objective question,
such as "Is every even number greater than 4 the sum of two prime
numbers?". A statement of fact can be right or wrong or true or
false, even if it isn't known at the present time which of those is
the case. The statement "Four colors suffice to color any planar
map such that adjacent regions do not have the same color" is a
statement of fact, both now and 60 years ago before the statement
had been proven. Both P==NP and P!=NP are statements of fact, even
though one of them must certainly be false; the key property is
that they are objective statements, subject to falsification. If I
say "The Earth is flat", that is a statement of fact, even though
the statement is false.
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
A statement of fact is a statement concerning an objective question,
such as "Is every even number greater than 4 the sum of two prime
numbers?". A statement of fact can be right or wrong or true or
false, even if it isn't known at the present time which of those is
the case. The statement "Four colors suffice to color any planar
map such that adjacent regions do not have the same color" is a
statement of fact, both now and 60 years ago before the statement
had been proven. Both P==NP and P!=NP are statements of fact, even
though one of them must certainly be false; the key property is
that they are objective statements, subject to falsification. If I
say "The Earth is flat", that is a statement of fact, even though
the statement is false.
I think you go too far. The word "fact" is not neutral as far as its
truth is concerned, and writing "a statement of fact" does not
significantly change that. Most dictionaries define a fact as something
that is true (or at least supported by currently available evidence).
One online essay[1] concludes that
"A statement of fact is one that has objective content and is
well-supported by the available evidence."
[1] https://philosophersmag.com/the-fact-opinion-distinction/
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
A statement of fact is a statement concerning an objective question,
such as "Is every even number greater than 4 the sum of two prime
numbers?". A statement of fact can be right or wrong or true or
false, even if it isn't known at the present time which of those is
the case. The statement "Four colors suffice to color any planar
map such that adjacent regions do not have the same color" is a
statement of fact, both now and 60 years ago before the statement
had been proven. Both P==NP and P!=NP are statements of fact, even
though one of them must certainly be false; the key property is
that they are objective statements, subject to falsification. If I
say "The Earth is flat", that is a statement of fact, even though
the statement is false.
I think you go too far. The word "fact" is not neutral as far as its
truth is concerned, and writing "a statement of fact" does not
significantly change that. Most dictionaries define a fact as something
that is true (or at least supported by currently available evidence).
One online essay[1] concludes that
"A statement of fact is one that has objective content and is
well-supported by the available evidence."
[1] https://philosophersmag.com/the-fact-opinion-distinction/
On 21.12.2024 22:51, Tim Rentsch wrote:
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
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?
(Unless you just wanted to say that in some HLL abstraction like
'printf("Hello world!\n")' there's no [visible] conditional
branch. Likewise in a 'ClearAccumulator' machine instruction, or
the like.)
The comparisons and predicates are one key function (not any
specific branch construct, whether on HLL level, assembler
level, or with the (elementary but most powerful) Turing
Machine). Comparisons inherently result in predicates which is
what controls program execution).
So your statement asks for some explanation at least.
Start with C - any of C90, C99, C11.
Take away the short-circuiting operators - &&, ||, ?:.
Take away all statement types that involve intra-function
transfer of control: goto, break, continue, if, for, while,
switch, do/while. Might as well take away statement labels too.
Take away setjmp and longjmp.
And also things like the above mentioned 'printf()' that most
certainly implies an iteration over the format string checking for
it's '\0'-end.
And so on, and so on. - What will be left as "language".
Would you be able to formulate functionality of the class of
Recursive Functions (languages class of a Turing Machine with
Chomsky-0 grammar).
Rule out programs with undefined behavior.
The language that is left is still Turing complete.
Is it?
But wouldn't that be just the argument I mentioned above; that a,
say, 'ClearAccumulator' machine statement wouldn't contain any
jump?
Proof: exercise for the reader.
(Typical sort of your reply.)
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 1,007 |
| Nodes: | 10 (0 / 10) |
| Uptime: | 196:47:38 |
| Calls: | 13,143 |
| Files: | 186,574 |
| D/L today: |
511 files (113M bytes) |
| Messages: | 3,310,136 |