el_pollo_diablo

6 ms·

1.
by el_pollo_diablo 13d ago
> declared in separate translation units Now if I include both library headers in code that attempts to plug them together, the types will be incompatible. Although not a proof in itself, GCC and Clang seem to agree: https://g
2.
by el_pollo_diablo 13d ago
> Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" It may differ, depending on the precise notion of provenance being applicable. If provenance only has alloca
3.
by el_pollo_diablo 13d ago
> how does this work? Like this: struct thread { // Entry in the list of threads of the containing process list_node process_entry; // Entry in this thread's scheduling queue list_node
4.
by el_pollo_diablo 13d ago
We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types ha
5.
by el_pollo_diablo 13d ago
> The structs list_of_A and list_of_B are compatible. No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.
6.
by el_pollo_diablo 13d ago
> IIRC GCC and Clang lets character types alias to any type. It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it
7.
by el_pollo_diablo 13d ago
> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned. You can certainly store an object of arbitrary type, but here it is done throu
8.
by el_pollo_diablo 13d ago
> as long as the struct tags are the same Exactly. Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. And what about typedefs? If A is a
9.
by el_pollo_diablo 13d ago
> There is no OoB access of an array Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to ac
10.
by el_pollo_diablo 13d ago
> I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. I have some experience with this, and while this is one of these things that are feasible, I find them signifi
11.
by el_pollo_diablo 13d ago
Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];). But even if you did that, strict aliasing implies that 'payload' can
12.
by el_pollo_diablo 13d ago
The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a tradi
13.
by el_pollo_diablo 2mo ago
> a single proof covering the most precise description of the program's behavior is more compact Yes, and a program is most compact when all modules have been merged, and all functions with a single caller inlined. We have compilers
14.
by el_pollo_diablo 2mo ago
In my view, a major selling point of dependent types when it comes to reasoning, is that by bundling logical properties with a runtime value, they require no separate effort to prove the propagation of the logical properties as the value is
15.
by el_pollo_diablo 2mo ago
I am not sure what you mean. Of course proving a new property generally implies reasoning on each elementary step of the program. My point is that, assuming you have already proved a property, proving a new one shouldn't lead you to al
16.
by el_pollo_diablo 2mo ago
I have already written it, and I will write it again: dependent types and total functions do not scale. Maintenance is terrible. Suppose that you have managed to write a non-trivial piece of software with dependent types encoding all sorts
17.
by el_pollo_diablo 4mo ago
> probably meaning on an address that’s a multiple of sizeof(int), but who knows Sigh. s/sizeof(int)/_Alignof(int)/. There are good reasons for an implementation to have sizeof(int) = _Alignof(int) and not a mere multiple
18.
by el_pollo_diablo 4mo ago
Type punning via unions is not UB in C in general, but it is in C++ IIRC. I write "in general" because, as with other forms of memory reinterpretation (memcpy or copy through a character type), evaluating a trap representation tri
19.
by el_pollo_diablo 5mo ago
So there are now two ways to represent the same state: None or Some(struct whose fields are all None). Even though one of these representations is never produced by the deserialization routine, anyone could construct it if the constructor i
20.
by el_pollo_diablo 6mo ago
This reminds me of Jacques Carelman's Catalogue d'objets introuvables. Highly recommended. It has already been mentioned on HN: https://news.ycombinator.com/item?id=9789216
21.
by el_pollo_diablo 9mo ago
Capturing invariants in the type system is a two-edged sword. At one end of the spectrum, the weakest type systems limit the ability of an IDE to do basic maintenance tasks (e.g. refactoring). At the other end of the spectrum, dependent typ
22.
by el_pollo_diablo 11mo ago
Years ago the research team behind OCaml released Chamelle, a version of the language localized in French, as an April fool's joke: https://gallium.inria.fr/blog/ocaml-5/
23.
by el_pollo_diablo 11mo ago
I would put the emphasis on a different word: > This article is made and published by Anna Hartz, which may have used AI in the preparation Which , not who . They're not even sure the author is human!
24.
by el_pollo_diablo 1y ago
Head and tail make sense for persistent lists in functional languages with value semantics, yes. The intrusive, mutable, doubly-linked loops with reference semantics under discussion are quite different. Although all entries behave identica
25.
by el_pollo_diablo 1y ago
> Are you saying the only real way to program is with generic data structures? Certainly not. As I said, the experienced programmer knows when (not) to use them. Some programs are better off without them, such as... most of the low-level
26.
by el_pollo_diablo 1y ago
You mean the downside that we also already know, i.e. that there are some situations where a custom data structure would be superior for various reasons (e.g. smaller footprint)? Experienced programmers know when to reuse a generic library
27.
by el_pollo_diablo 1y ago
Absolutely. Wrapping the distinguished entry point in a new structure type equipped with a thin type-safe wrapper API that covers the most common use case is the way to go.
28.
by el_pollo_diablo 1y ago
Not to mention that they insist on calling every entry of the list a "list head", which makes no sense (hysterical raisins, maybe?). The structure is made of a uniform loop of entries, one of which is used as the actual head &
29.
by el_pollo_diablo 1y ago
None, but that is not my point. Before C23, fn() already meant the same thing as fn(void) in function definitions , which the situation under discussion here. C23 changed what fn() means outside a function definition.
30.
by el_pollo_diablo 1y ago
Sure, but it is also very common for C programs to contain data structures that have one use in the program, and could still be instances of a generic type. You mentioned red black trees, which are a perfect example of that.

More ›