And I just looked it up -- C was invented BEFORE abstract data types were! This explains a lot.
Programmers think "hash table", stack, queue, set, etc. are "the way you program", because that's how it's taught in CS 101. It's also asked a lot in interview questions.
But that line of thinking was invented AFTER C. I recall that Liskov did foundational work on ADTs, and Wikipedia agrees
Programming with abstract data types (Liskov and Zilles, 1974)
At MIT she led the design and implementation of the CLU programming language, which emphasized the notions of modular programming, data abstraction, and polymorphism
-----
Meanwhile C was developed around 1972-73 to make the Unix kernel portable. It's a minimal layer meant to generate machine different machine instructions that will work on machines; it doesn't feature strong abstraction.
So what Hanson was trying to do is to add abstraction to C, but you need a language more like CLU or C++ to do that. Arguably Bjarne was "doing it right" -- actually changing the language.
----
HOWEVER I also had a recent experience that vividly shows the folly of ADTs even in C++, a language designed for them.
In C++, unordered_set<void star>::insert() is shockingly slow -- slower than malloc(1) !!! And it is slow BY THE SPEC. Because of the abstract operations that the C++ standard requires (e.g. iterators and invalidation), you have to use a slow closed-addressing/linked list implementation that allocates for EVERY element !!!
I hit this when working on the garbage collector for https://www.oilshell.org/ -- we're making a fork() friendly collector (no intrusive mark bits) that works with arbitrary addresses returned by malloc.
It made some of our benchmarks 10x slower in TOTAL runtime!
So basically the hash table in C++ is a shockingly bad default, and it has to with a bad ADT design.
Doing ADTs in C is even worse. Hanson's book is more like a thought experiment in merging two distinct lines of thinking -- not something you should actually use and base your code on!!
----
This would be a good blog post -- I would title it something like C Was Invented Before ADTs, and C++ Isn't Great Either
I don't see how this observation that C++ STL containers aren't very good somehow "shows the folly of ADTs" ?
The fact these are abstract types doesn't seem relevant, if you explicitly implemented this feature set for, say, the long type and named it "chubots_long_set" it would still suck, but it's not abstract, the abstraction played no part.
I don't have any problem with ADTs or abstraction ... In fact I'd say the strength of C++, and why I use it, is precisely that you can create your own abstractions, more so than C.
I'm just saying that using a canned set with "many useful" operations is suboptimal, design by committee is suboptimal, etc.
As opposed to analyzing the ops your app needs and creating custom data structures. i.e. there are many different ADTs for "hash table" or "set"
That might seem obvious, but it's not how software development is being done today. There's a lot of code reuse that leads to suboptimal software; it would actually be better to copy and paste and refine more.
I still think you're mostly conflating "the C++ standard library provides bad implementations of this stuff" which is famously true, with "generic solutions are just bad" which is at least non-obvious and I'd argue generally false.
> copy and paste and refine more.
That doesn't get you better algorithms, which is what you need. If you start with the C++ standard library's unordered_set implementation in a source file and you "refine" that you won't get from there to absl::flat_hash_set except in the same sense you could start with the footage from "Grease" and end up making "Bugsy Malone". Start over with a different design.
Picking from a handful of options like absl::flat_hash_set rather than always hand-rolling is a clear win for productivity. As with anything else in performance, measure first and only solve problems you actually have applies to the idea that maybe the choice doesn't work - even for the abysmal std::unordered_set if you don't have measurements showing it's a problem then it probably just isn't a problem.
I am quite sure JOVIAL, ESPOL/NEWP, ALGOL and PL/I dialects, Lisp, which predated C in more than a decade have enough abstraction capabilities, even by their state in 1972.
Interlisp initially created in 1970, besides the lists everyone knows, introduced atoms, string, arrays and compound data types, which alongside macros provided the necessary foundation to create abstract data types
> The language which most closely resembles, in form, the language presented here is SIMULA 67. 8
SlMULA class definitions have many similarities with cluster definitions.
Yeah it doesn't, that is why there are enough papers and books how to implement them with incomplete types, and translation units with statics as poor man's replacement for modules.
Again, there is already a well known solution for this problem -- C++
And it's trivial to upgrade to from C
So basically, use EITHER idiomatic C, which means long functions / few internal interfaces, reuse with ABIs not APIs, bespoke data structures, etc.
OR use C++ and ADTs (type safety, abstraction, polymorphism). Or use Rust if you don't need compatibility.
So books like CII are of very limited use, especially not for beginners. They will be fighting with the language and not understanding what it's about.
And I just looked it up -- C was invented BEFORE abstract data types were! This explains a lot.
Programmers think "hash table", stack, queue, set, etc. are "the way you program", because that's how it's taught in CS 101. It's also asked a lot in interview questions.
But that line of thinking was invented AFTER C. I recall that Liskov did foundational work on ADTs, and Wikipedia agrees
Programming with abstract data types (Liskov and Zilles, 1974)
https://dl.acm.org/doi/10.1145/942572.807045
i.e. the origin of abstract data types is in this work on the CLU language.
Her 2008 Turing Award cites this work: https://amturing.acm.org/award_winners/liskov_1108679.cfm
At MIT she led the design and implementation of the CLU programming language, which emphasized the notions of modular programming, data abstraction, and polymorphism
-----
Meanwhile C was developed around 1972-73 to make the Unix kernel portable. It's a minimal layer meant to generate machine different machine instructions that will work on machines; it doesn't feature strong abstraction.
So what Hanson was trying to do is to add abstraction to C, but you need a language more like CLU or C++ to do that. Arguably Bjarne was "doing it right" -- actually changing the language.
----
HOWEVER I also had a recent experience that vividly shows the folly of ADTs even in C++, a language designed for them.
In C++, unordered_set<void star>::insert() is shockingly slow -- slower than malloc(1) !!! And it is slow BY THE SPEC. Because of the abstract operations that the C++ standard requires (e.g. iterators and invalidation), you have to use a slow closed-addressing/linked list implementation that allocates for EVERY element !!!
I hit this when working on the garbage collector for https://www.oilshell.org/ -- we're making a fork() friendly collector (no intrusive mark bits) that works with arbitrary addresses returned by malloc.
It made some of our benchmarks 10x slower in TOTAL runtime!
Best comment I found that explains it:
https://old.reddit.com/r/programming/comments/5pwgtn/hash_ma...
Chrome message from 2017:
https://groups.google.com/a/chromium.org/g/chromium-dev/c/rd...
So basically the hash table in C++ is a shockingly bad default, and it has to with a bad ADT design.
Doing ADTs in C is even worse. Hanson's book is more like a thought experiment in merging two distinct lines of thinking -- not something you should actually use and base your code on!!
----
This would be a good blog post -- I would title it something like C Was Invented Before ADTs, and C++ Isn't Great Either