Hacker News Reader

Comment by adalacelove | Hacker News Reader

> The best way to use C is to roll your own (or copy and paste) data structures for your problem, not try to use canned ones!

I committed atrocities until I realized this. C is not suitable for generic programming.

View on HN

Yup, same!

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

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.

citation needed

We're talking about abstract data types

Common Lisp yes, and its research predecessors, but not Lisp in 1972

CLU itself was based on Algol, and influenced C++

This tiring requests for citations...

DEFINE STRUCTURE + type functions + function/procedures is all one needs in PL/I to achieve similar workflow,

https://www.ibm.com/docs/en/epfz/5.1 (No earlier online version found)

And if you want to read PL/I documentation that uses the term "abstract data types",

https://www.ibm.com/docs/en/z-netview/5.4.0?topic=SSZJDU_5.4...

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

https://www.softwarepreservation.org/projects/LISP/interlisp...

And going back to CLU,

> 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.

"Programming with Abstract Data Types (1974)"

https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136...

Maybe, I'm not seeing it from those links

Either way, it doesn't really matter, as it's clear that C does not include any of those ideas, and the CII style isn't idiomatic

Especially when it was created, but even today!

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.

I guess those books are for the folks that will never touch anything besides C, no matter what.

Anyway, I agree with the sentiment.

typo: It's a minimal layer meant to generate machine code that will work on multiple different machines

i.e. it's about code generation, not abstraction, not type checking, etc.

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.

It's not either-or, both things can be true

There are apps where absl:flat_hash_set isn't optimal either

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.

Reply on news.ycombinator.com