4 ms·

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

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

chubot 4y ago
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 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 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/ 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_map_benchmark_stdunordered_map_seems_very/ 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/rdxOHKzQmRY?pli=1 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
- pjmlp 4y ago
  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.
  - chubot 4y ago
    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++
    - pjmlp 4y ago
      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 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.0/com.ibm.itnetviewforzos.doc_6.2/dqi_str.htm 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_family/ 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.3043 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136...
      - chubot 4y ago
        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!

chubot 4y ago

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 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 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/ 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_map_benchmark_stdunordered_map_seems_very/ 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/rdxOHKzQmRY?pli=1 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

pjmlp 4y ago
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.
- chubot 4y ago
  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++
  - pjmlp 4y ago
    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 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.0/com.ibm.itnetviewforzos.doc_6.2/dqi_str.htm 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_family/ 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.3043 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136...
    - chubot 4y ago
      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!