Could someone explain to me how effects are radically different from types? Every time I see them introduced, it's always "type and effect system", not just "extending the type system with effect types", yet the rules the effects obey seem to be fundamentally the same that e.g. the constrained generics follow.
I would describe an effect system as the part of a type system which describes actions and side effects rather than values. Under this definition, effects are radically different from types in the sense that apples are radically different from fruit.
This requires a somewhat broad notion of what types are in the first place. I think most people have a mental model of types that describes data types like int or string, but anyone familiar with Java knows what effects are because Java has the “throws” keyword, which is an effect. If your method in Java throws IOException, the method must be marked “throws IOException” or it is a type error.
So I think our definition of “type” should be broad enough to include effect systems.
Types usually describe values. Compilers use types to prove various things about possible values, like their size, alignment, valid bit patterns, etc.
Effects describe code. For example, a "panic" effect states that function may trigger panic/exception during its execution. In other words, existence or absence of an effect is a function property. You can view effects as special types which are used only for functions (to be slightly more precise, signature + effects form function type), but you would need to use a slightly more advanced notion of type system which includes subtyping, e.g. function "panic fn(u32) -> u64" can be used in place of "panic io fn(u32) -> u64".
As the proposal points out there are already a number of projects for adding an effect system to C. There are also other approaches to aid in correctness, from formal methods to coding standards like MISRA. I think merging any approach into the C standard would be problematic because (1) it limits perceived choice by “blessing” one approach over others and (2) it standardizes an approach which history might prove to be flawed. I would encourage the authors to consider implementing their effect system as a separate tool and observe its practical reception.
IIRC, I think the standards committee does have “is it in a commercial implementation and has it been commonly used?” as a standard for evaluating features - although I’m not sure whether than refers to GNU C extensions (for example), or to ideas lifted from other manually managed languages like Rust etc.
…although I’ll admit that didn’t quite feel the case for type generic macros.
Yep. Basic hash table. Spec out all undefined behaviour. Standardize abi. Etc. so many things to do with c to actually make it useful instead of c++ lite
What's with this strange desire to mandate One True Way to implement function calls in every language implementation? If I want to use rbx/r11/r10/r9 for argument passing and return results in rdx/rsi by default and have to use
That in no way conflicts with the existence of a standard. A standard is just a common default, you can deviate from it. And this being C the ability to do so when needed would be expected.
I get why people want those things but you can’t spec out undefined behavior and end up with a version of C that people want.
Not sure what “standardize ABI” is supposed to mean… each platform has its own ABI, and most of those ABIs are already standardized. The standards are just not part of the C standard.
- It involves making too many decisions on behalf of users. C++ dodges the question somewhat by making hash tables templated, so you can customize them.
- There are a hojillion hash table libraries out there which are written in C—just pick one and use it.
Is there a hope in hell of the C committee actually accepting an effects system (not necessarily this particular proposal)? I have the impression that they are quite a conservative group en masse, and this feels like a very uphill battle
Yes, there's a hope. The C committee can actually be quite receptive to new features. On the other hand, I'd say a feature like this is decently likely to get stuck in a rut of "well, we like the idea, but there's something off so... try again?"
Syntactically, I'm not sure why you wouldn't use attributes on the type or function. The syntax in the proposal's examples seems extremely disruptive and unfriendly to macro-ification.
So...uh, how could a compiler actually check for this? Is this merely a way to hint to the compiler to make certain optimisations? C is not known to be for these kind of things. I mean, you could always add attributes, no?
ISO C should love this. It's really complicated. It adds ad hoc compile time guards to stuff. C++ doesn't have this yet so they get to lead the way for a moment.
I hate it but whatever - my love for C ended sharply after C99 fno-strict-aliasing anyway.
That it's not default, and the strict aliasing rules break the illusion that C is "close to the metal" and that "the C programmer is in charge, not the C compiler". This illusion was never really true but it persists.
The default aliasing model interacts extremely poorly with atomic and vector types. It also means "malloc" can't be written in C, which really should be a sign that the language was devolving into nonsense. I don't want to write malloc in asm because ISO think C is a plausible candidate for writing application code.
(I also want to do things like mutate bytes of the machine code but overall I can make peace with doing that in buffers that aren't currently executing. It's very much not allowed to cast some bytes to a function pointer, even if you've got the ABI right, and that's ridiculous)
Pointers to unallocated memory are not allowed to be read from, in any form. You have to manage memory with uintptr_t arithmetic which arguably makes pointer arithmetic in C almost completely useless for writing malloc().
That's not a consequence of effective type (i.e., strict aliasing) rules, that's a consequence of pointer provenance rules. And a little more generally, it's a consequence of malloc having special object system behavior that there's no way to express in pure C code.
Well, I am glad to inform you that I am writing a language (working name "Troglodyte") that will have exactly the desired ("do what I wrote, damn it!") semantics with regards to memory allocations, pointer casting etc. specifically for cavemen like me who sometimes want something more high-level than assembler but still low-level enough to be able to accidentally drop a sharp rock on my foot.
It will have machine-native integers, arrays of such integers, arrays of bytes, functions that take/return machine-wide integers, and that's pretty much it for the data types. All arithmetic is two-complement, signed or unsigned as you desire, and pointers are just numbers as well. Quality-of-life features include being able to straight-up include arbitrary binaries as function definitions:
func [[raw]] builtin_assembler_is_too_much_work(a, b) "\x48\x89\xF8\x48\x99\x48\xF7\xEE\xC3";
I'm very sympathetic to wanting a language that gives you direct access to the same control assembly does while letting you delegate register allocation / isel / calling convention and so forth to a compiler where it doesn't matter so much.
LLVM IR is interesting in that respect. Some libraries are written in it directly (all compiler runtimes afaik but there are probably others). The ergonomics on it are rather poor but writing exactly the control flow graph you want does work. It doesn't give control over register allocation or scheduling but does give control over the CFG and a decent approximation to instruction selection.
Some years ago I wrote compute kernels in terms of vector types and compiler intrinsics, including some that could target DSP style compute-and-branch operations. Adjusting the code and the compiler simultaneously worked really well - matched and thus replaced the handwritten assembly for the simpler cases. I miss that ISA / toolchain combination.
I'd be curious to hear what troglodyte can handle that C with compiler extensions and the type aliasing optimisations discarded cannot. Specifically the "language" I really should get around to writing for x64 and/or amdgpu would be "C" with:
1. an intrinsic for each instruction, with a function type. Probably as a header file with a lot of declarations in it.
2. mark variables as allocated to specific registers, or maybe in a set of registers. Syntax.
3. some notation for bespoke calling conventions. Syntax.
4. some notation for ordering instructions (i.e. scheduling them)
5. a lattice of address spaces (global outlives stack etc, a bit gpu specific)
The intrinsic per instruction definitely works. That gives a pretty way to write AVX code or similar. Marking variables as allocated to specific registers also works (gcc does this to an extent with the asm annotation). Point 3 and onwards is where I get hazy on how to make it work sensibly. Custom calling conventions work really well in a compiler backend, and in C they need to be expressed in the function type, but I'm still obsessing how best to do that.
I'm confused. C99 is a standard of C, while fno-strict-aliasing is a non standard compiler switch for a specific implementation. Did you mean to put those two things next to each other? Especially since that switch appears to mean "violate the standard in a specific way", and that thing to violate (strict aliasing) goes back at least at far back at the original C89 standard.
I basically agree with the flags the linux kernel are using. Those that I'm missing are probably mistakes on my part. The iso standard isn't of much use to me but the language implemented by compilers with various flags certainly is.
Specifically calling out 99 as the one before 11 introduced _Generic where it could have been overloadable, and atomic where it should have been the gcc intrinsics. That feels like a tipping point between making the language better and diverging from reality.
The op actually references an implementation (QAC? presumably a C compiler) which is nice. The current ISO language would have been improved if "has been implemented and some people use it" was a requirement on adding things to the language. I cannot believe anyone programmed with _Generic and thought yeah, this is what I want.
C99 did not introduce the “strict” aliasing rules, C89 says more or less the same thing about that. It’s just that the inexorable (relative) slowing down of RAM and the gradual extinction of low-hanging optimization fruit led compiler authors to seriously consider aliasing-based optimizations at around the same time.
Could someone explain to me how effects are radically different from types? Every time I see them introduced, it's always "type and effect system", not just "extending the type system with effect types", yet the rules the effects obey seem to be fundamentally the same that e.g. the constrained generics follow.
I would describe an effect system as the part of a type system which describes actions and side effects rather than values. Under this definition, effects are radically different from types in the sense that apples are radically different from fruit.
This requires a somewhat broad notion of what types are in the first place. I think most people have a mental model of types that describes data types like int or string, but anyone familiar with Java knows what effects are because Java has the “throws” keyword, which is an effect. If your method in Java throws IOException, the method must be marked “throws IOException” or it is a type error.
So I think our definition of “type” should be broad enough to include effect systems.
Types usually describe values. Compilers use types to prove various things about possible values, like their size, alignment, valid bit patterns, etc.
Effects describe code. For example, a "panic" effect states that function may trigger panic/exception during its execution. In other words, existence or absence of an effect is a function property. You can view effects as special types which are used only for functions (to be slightly more precise, signature + effects form function type), but you would need to use a slightly more advanced notion of type system which includes subtyping, e.g. function "panic fn(u32) -> u64" can be used in place of "panic io fn(u32) -> u64".
As the proposal points out there are already a number of projects for adding an effect system to C. There are also other approaches to aid in correctness, from formal methods to coding standards like MISRA. I think merging any approach into the C standard would be problematic because (1) it limits perceived choice by “blessing” one approach over others and (2) it standardizes an approach which history might prove to be flawed. I would encourage the authors to consider implementing their effect system as a separate tool and observe its practical reception.
IIRC, I think the standards committee does have “is it in a commercial implementation and has it been commonly used?” as a standard for evaluating features - although I’m not sure whether than refers to GNU C extensions (for example), or to ideas lifted from other manually managed languages like Rust etc.
…although I’ll admit that didn’t quite feel the case for type generic macros.
How about some basic hash table support in the standard library first? I know this is snarky, but ISO's priorities over the past couple decades... :(
Yep. Basic hash table. Spec out all undefined behaviour. Standardize abi. Etc. so many things to do with c to actually make it useful instead of c++ lite
> Standardize abi
What's with this strange desire to mandate One True Way to implement function calls in every language implementation? If I want to use rbx/r11/r10/r9 for argument passing and return results in rdx/rsi by default and have to use
to interoperate with one particular implementation of libc for one particular OS on one particular ISA, then that should be perfectly fine.
That in no way conflicts with the existence of a standard. A standard is just a common default, you can deviate from it. And this being C the ability to do so when needed would be expected.
I get why people want those things but you can’t spec out undefined behavior and end up with a version of C that people want.
Not sure what “standardize ABI” is supposed to mean… each platform has its own ABI, and most of those ABIs are already standardized. The standards are just not part of the C standard.
I would rather not:
- It involves making too many decisions on behalf of users. C++ dodges the question somewhat by making hash tables templated, so you can customize them.
- There are a hojillion hash table libraries out there which are written in C—just pick one and use it.
The latter point is a very strong argument for a hash table implementation in the standard library.
I don’t see how that argument follows.
If everyone is reinventing the same wheel, then...
Furthermore, those wheels aren't necessarily interoperable the way something built into the standard library would be; it's not just a convenience.
Is there a hope in hell of the C committee actually accepting an effects system (not necessarily this particular proposal)? I have the impression that they are quite a conservative group en masse, and this feels like a very uphill battle
Yes, there's a hope. The C committee can actually be quite receptive to new features. On the other hand, I'd say a feature like this is decently likely to get stuck in a rut of "well, we like the idea, but there's something off so... try again?"
Syntactically, I'm not sure why you wouldn't use attributes on the type or function. The syntax in the proposal's examples seems extremely disruptive and unfriendly to macro-ification.
So...uh, how could a compiler actually check for this? Is this merely a way to hint to the compiler to make certain optimisations? C is not known to be for these kind of things. I mean, you could always add attributes, no?
ISO C should love this. It's really complicated. It adds ad hoc compile time guards to stuff. C++ doesn't have this yet so they get to lead the way for a moment.
I hate it but whatever - my love for C ended sharply after C99 fno-strict-aliasing anyway.
what's wrong with no-strict-aliasing?
That it's not default, and the strict aliasing rules break the illusion that C is "close to the metal" and that "the C programmer is in charge, not the C compiler". This illusion was never really true but it persists.
The default aliasing model interacts extremely poorly with atomic and vector types. It also means "malloc" can't be written in C, which really should be a sign that the language was devolving into nonsense. I don't want to write malloc in asm because ISO think C is a plausible candidate for writing application code.
(I also want to do things like mutate bytes of the machine code but overall I can make peace with doing that in buffers that aren't currently executing. It's very much not allowed to cast some bytes to a function pointer, even if you've got the ABI right, and that's ridiculous)
What part in aliasing prevents malloc() to be written in C? All pointers can be cast to char * and back. Casting from void * is also legal.
Pointers to unallocated memory are not allowed to be read from, in any form. You have to manage memory with uintptr_t arithmetic which arguably makes pointer arithmetic in C almost completely useless for writing malloc().
That's not a consequence of effective type (i.e., strict aliasing) rules, that's a consequence of pointer provenance rules. And a little more generally, it's a consequence of malloc having special object system behavior that there's no way to express in pure C code.
Well, I am glad to inform you that I am writing a language (working name "Troglodyte") that will have exactly the desired ("do what I wrote, damn it!") semantics with regards to memory allocations, pointer casting etc. specifically for cavemen like me who sometimes want something more high-level than assembler but still low-level enough to be able to accidentally drop a sharp rock on my foot.
It will have machine-native integers, arrays of such integers, arrays of bytes, functions that take/return machine-wide integers, and that's pretty much it for the data types. All arithmetic is two-complement, signed or unsigned as you desire, and pointers are just numbers as well. Quality-of-life features include being able to straight-up include arbitrary binaries as function definitions:
I'm very sympathetic to wanting a language that gives you direct access to the same control assembly does while letting you delegate register allocation / isel / calling convention and so forth to a compiler where it doesn't matter so much.
LLVM IR is interesting in that respect. Some libraries are written in it directly (all compiler runtimes afaik but there are probably others). The ergonomics on it are rather poor but writing exactly the control flow graph you want does work. It doesn't give control over register allocation or scheduling but does give control over the CFG and a decent approximation to instruction selection.
Some years ago I wrote compute kernels in terms of vector types and compiler intrinsics, including some that could target DSP style compute-and-branch operations. Adjusting the code and the compiler simultaneously worked really well - matched and thus replaced the handwritten assembly for the simpler cases. I miss that ISA / toolchain combination.
I'd be curious to hear what troglodyte can handle that C with compiler extensions and the type aliasing optimisations discarded cannot. Specifically the "language" I really should get around to writing for x64 and/or amdgpu would be "C" with:
1. an intrinsic for each instruction, with a function type. Probably as a header file with a lot of declarations in it.
2. mark variables as allocated to specific registers, or maybe in a set of registers. Syntax.
3. some notation for bespoke calling conventions. Syntax.
4. some notation for ordering instructions (i.e. scheduling them)
5. a lattice of address spaces (global outlives stack etc, a bit gpu specific)
The intrinsic per instruction definitely works. That gives a pretty way to write AVX code or similar. Marking variables as allocated to specific registers also works (gcc does this to an extent with the asm annotation). Point 3 and onwards is where I get hazy on how to make it work sensibly. Custom calling conventions work really well in a compiler backend, and in C they need to be expressed in the function type, but I'm still obsessing how best to do that.
> C99 fno-strict-aliasing
I'm confused. C99 is a standard of C, while fno-strict-aliasing is a non standard compiler switch for a specific implementation. Did you mean to put those two things next to each other? Especially since that switch appears to mean "violate the standard in a specific way", and that thing to violate (strict aliasing) goes back at least at far back at the original C89 standard.
I basically agree with the flags the linux kernel are using. Those that I'm missing are probably mistakes on my part. The iso standard isn't of much use to me but the language implemented by compilers with various flags certainly is.
Specifically calling out 99 as the one before 11 introduced _Generic where it could have been overloadable, and atomic where it should have been the gcc intrinsics. That feels like a tipping point between making the language better and diverging from reality.
The op actually references an implementation (QAC? presumably a C compiler) which is nice. The current ISO language would have been improved if "has been implemented and some people use it" was a requirement on adding things to the language. I cannot believe anyone programmed with _Generic and thought yeah, this is what I want.
C99 did not introduce the “strict” aliasing rules, C89 says more or less the same thing about that. It’s just that the inexorable (relative) slowing down of RAM and the gradual extinction of low-hanging optimization fruit led compiler authors to seriously consider aliasing-based optimizations at around the same time.