| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 43 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 94:19:14 |
| Calls: | 290 |
| Calls today: | 1 |
| Files: | 904 |
| Messages: | 76,378 |
- Use C as an intermediate language to feed a backend (any C compiler
can act as the backend).
The backend can then focus solely on code generation.
I am working on a C backend that generates simple C code.
You can test it here:
http://thradams.com/cake/playground.html
Objective
- Shift all the complexity of the C compiler to the frontend.
Why? This approach simplifies having one frontend and multiple backends. - Use C as an intermediate language to feed a backend (any C compiler
can act as the backend).
The backend can then focus solely on code generation.
- Code is not portable
Removed C89 Features
- Preprocessor
- sizeof
- typedef
- enum
- Constant expressions (the final result is precomputed during earlier stages)
- const
- I may also remove switch.
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.
I also think LLVM is too big.
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).
On 12/15/2024 5:22 PM, Thiago Adams wrote:
Em 12/15/2024 7:22 PM, Lawrence D'Oliveiro escreveu:
On Sun, 15 Dec 2024 07:44:34 -0300, Thiago Adams wrote:
I also think LLVM is too big.
How about QBE, then <https://c9x.me/compile/>.
QBE is just for linux and it does not generate code directly. C is
everywhere.
But I am reading QBE docs to see what is necessary in a IL.
I agree that both LLVM and GCC are too big.
I am not sure the minimum size of a usable C compiler, my current
estimate is probably somewhere in the area of 50-100 kLOC.
My current compiler is a bit bigger than this, and my own past attempt
to implement a C compiler in under 30k lines had failed.
If I were to estimate a feature set for a 3AC IL:
Basic UNARY and BINARY operators;
Also COMPARE and similar;
Load and Store Index operators;
With support for an immediate index;
GOTO
IF-GOTO
CALL (with a list of argument variables and a target variable).
[...]
Pretty much all higher level control flow can be expressed via goto.
[...]
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.
I agree that both LLVM and GCC are too big.
On 16/12/2024 17:12, Janis Papanagnou wrote:
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.
You would do away with just about the simplest feature of any language,
and insist users emulate intra-function branching via function calls?
I'd like to see your design of IL that doesn't have branching! I guess
it would also need closures and/or continuations. I suspect you either
don't quite understand what an IL is for, or forgot that's what this is about.
An IL is typically lower level than the source language, while higher
level than a native code target which makes it easier to generate code
for. A functional IL would make it harder than assembly.
As an IL, even C is a little overkill, unless turned into a restricted
subset ...
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
BGB <cr88192@gmail.com> writes:
[...]
If I were to estimate a feature set for a 3AC IL:[...]
Basic UNARY and BINARY operators;
Also COMPARE and similar;
Load and Store Index operators;
With support for an immediate index;
GOTO
IF-GOTO
CALL (with a list of argument variables and a target variable).
One doesn't need any higher-level control flow constructs.
Have you looked at C-- (cminusminus)?
https://en.wikipedia.org/wiki/C--
On 16.12.2024 19:37, bart wrote:
On 16/12/2024 17:12, Janis Papanagnou wrote:
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.
You would do away with just about the simplest feature of any language,
and insist users emulate intra-function branching via function calls?
Why are you, yet again, and still, making up nonsensical suppositions!
I'd like to see your design of IL that doesn't have branching! I guess
it would also need closures and/or continuations. I suspect you either
don't quite understand what an IL is for, or forgot that's what this is
about.
Why are you, yet again, and still, making up nonsensical suppositions!
I wasn't commenting on any "IL",
nor on any "emulation". I also didn't
restrict my view to any specific machine model (as you have obviously
been doing).
You can still see what I was commenting on in the single sentence that
I quoted in my post. (No more and no less.) - If you have anything to
say (without any nonsensical suppositions), concerning the quote and
my response, feel free to make another try.
If you want to talk about "IL" or "assembly" search another target for discussing your ideas.
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?
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?
bart <bc@freeuk.com> writes:
[SNIP]
In that case I've no idea what you were trying to say.
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?
I read Janis's post. I saw a suggestion that certain constructs are *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.
"""
On 17/12/2024 01:19, Keith Thompson wrote:
[...]
"""
[...] but it isn't strictly *necessary*. [...]
"""
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'.
[...]
On 16/12/2024 20:39, Janis Papanagnou wrote:
I wasn't commenting on any "IL",
The subthread was about ILs.
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 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>
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?
Information about it is quite elusive ...
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 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.
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 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.
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 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 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
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 ;-)
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 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.
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?
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 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 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.
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 [...]
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.
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.
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 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).
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.
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.
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 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 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 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.
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 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.
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 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.
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 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.
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 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.
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?