5 ms·

I read the Hanson book ~10 years ago (he was briefly a coworker). It's interesting, and maybe worth checking out for experienced programmers, but NOT for someo

by chubot 4y ago

I read the Hanson book ~10 years ago (he was briefly a coworker). It's interesting, and maybe worth checking out for experienced programmers, but NOT for someone who wants to learn C in 2022 and be productive. The style doesn't match any C code you're likely to see. It basically presenting an STL-like set of data structures and standard library in C, not C++. That style of programming isn't idiomatic in C. One thing that took me a long time to realize is that C is NOT a modular language! 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! If you want the latter approach, C++ is better. It has better support for type safety, abstraction, and modularity (at great cost). i.e. if you compare code of commonly used codebases like Lua, CPython, sqlite, Redis, BSD kernels, Linux, etc. you will see patterns, and they don't look anything like Hanson's book

adalacelove 4y ago
> 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!
sfpotter 4y ago
I don't take the point of this book to be "how to implement an STL-like data structures and algorithms library in C"---although you were his coworker, so maybe you know better. I've always viewed it more as "how to build data structures with useful interfaces in C". In the book, the set of libraries presented are an example which illustrates how to approach this using the features that C provides. If you are new to C and don't know how to manage complexity by building up useful interfaces for your data structures, reading Hanson's book is a reasonable way to get some ideas. Another way to go would be to just read through the source of any of the libraries you mentioned, all of which do in fact use ideas which feature in this book. This is obviously not to say that Hanson's book originated these ideas. I also think focusing on the exact style of the code in this book is maybe a bit of a red herring.
- chubot 4y ago
  You could view it as an example not meant to be used, sure I'd say it's still easy to get the wrong idea -- the title is "C Interfaces and Implementations: Techniques for Creating Reusable Software" So the claim is that focusing on reuse is missing what C is good for. It's going against the grain; if you want that style, use C++ or Python Those were less viable choices when the book was written, which is another reason I wouldn't recommend this old book, especially to beginners. http://drh.github.io/cii/ http://drh.github.io/cii/ Also the techniques for real long-term reuse involve C ABIs and not C APIs, which are not covered in almost any book, including this one.
  - sfpotter 4y ago
    I'm sorry, I don't completely understand what your point. You seem to be alluding to "what C is actually good for", but it's not clear to me what that's supposed to be. I understand that you think C should not be used to develop generic components that are reused, and that data structures and such should be re-rolled or copy-pasted each time they're used. On the other hand, you do hint that you think C can be used reusably, provided that the ABI is the focus. I agree with this. In my opinion, the techniques discussed in the book are in fact useful techniques for accomplishing exactly this end. If you want reusability the ABI way, what you want is a small surface area which changes extremely slowly. Ideally, you want each ABI to be a subset of the last to avoid breaking changes. OK: accomplishing data hiding via opaque pointers in tandem with a simple, high-level interface is one way to accomplish this, and is the main lesson to be learned by reading this book. (I would argue you really only need to read a chapter or two to learn it, but that's a different story---I would argue that this book is in fact not very good for this reason, but whatever.) If you look at most reusable C libraries, they take this approach. Obvious this book takes a bit of an extreme approach where as much of the details of a data type are hidden as possible, but there is no real reason to do this provided that the details of a type are stable. Then it's OK to expose them as part of the interface. I suppose I take your point that in reading this book, one might get the idea that it's a good idea to develop an STL-style library to use with C and run with that. On the other hand, someone who is learning C might just as well read many books about it (or read lots of code), and be able to contextualize this book well enough to understand that it should be taken with a grain of salt. I think it's also important to point out that there are exceptions to these "rules". GLib is a generic STL-style library written in C which seems to be pretty widely used. At the other end of the spectrum, you have more people (I think mostly in the games community) developing "header only C libraries". YMMV.

by chubot 4y ago

adalacelove 4y ago

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

sfpotter 4y ago

I don't take the point of this book to be "how to implement an STL-like data structures and algorithms library in C"---although you were his coworker, so maybe you know better. I've always viewed it more as "how to build data structures with useful interfaces in C". In the book, the set of libraries presented are an example which illustrates how to approach this using the features that C provides. If you are new to C and don't know how to manage complexity by building up useful interfaces for your data structures, reading Hanson's book is a reasonable way to get some ideas. Another way to go would be to just read through the source of any of the libraries you mentioned, all of which do in fact use ideas which feature in this book. This is obviously not to say that Hanson's book originated these ideas. I also think focusing on the exact style of the code in this book is maybe a bit of a red herring.

chubot 4y ago
You could view it as an example not meant to be used, sure I'd say it's still easy to get the wrong idea -- the title is "C Interfaces and Implementations: Techniques for Creating Reusable Software" So the claim is that focusing on reuse is missing what C is good for. It's going against the grain; if you want that style, use C++ or Python Those were less viable choices when the book was written, which is another reason I wouldn't recommend this old book, especially to beginners. http://drh.github.io/cii/ http://drh.github.io/cii/ Also the techniques for real long-term reuse involve C ABIs and not C APIs, which are not covered in almost any book, including this one.
- sfpotter 4y ago
  I'm sorry, I don't completely understand what your point. You seem to be alluding to "what C is actually good for", but it's not clear to me what that's supposed to be. I understand that you think C should not be used to develop generic components that are reused, and that data structures and such should be re-rolled or copy-pasted each time they're used. On the other hand, you do hint that you think C can be used reusably, provided that the ABI is the focus. I agree with this. In my opinion, the techniques discussed in the book are in fact useful techniques for accomplishing exactly this end. If you want reusability the ABI way, what you want is a small surface area which changes extremely slowly. Ideally, you want each ABI to be a subset of the last to avoid breaking changes. OK: accomplishing data hiding via opaque pointers in tandem with a simple, high-level interface is one way to accomplish this, and is the main lesson to be learned by reading this book. (I would argue you really only need to read a chapter or two to learn it, but that's a different story---I would argue that this book is in fact not very good for this reason, but whatever.) If you look at most reusable C libraries, they take this approach. Obvious this book takes a bit of an extreme approach where as much of the details of a data type are hidden as possible, but there is no real reason to do this provided that the details of a type are stable. Then it's OK to expose them as part of the interface. I suppose I take your point that in reading this book, one might get the idea that it's a good idea to develop an STL-style library to use with C and run with that. On the other hand, someone who is learning C might just as well read many books about it (or read lots of code), and be able to contextualize this book well enough to understand that it should be taken with a grain of salt. I think it's also important to point out that there are exceptions to these "rules". GLib is a generic STL-style library written in C which seems to be pretty widely used. At the other end of the spectrum, you have more people (I think mostly in the games community) developing "header only C libraries". YMMV.