Hacker News Reader

Comment by travisgriggs | Hacker News Reader

Computer language inventors are torn between a voice whispering “use the language Luke” and and a more gravelly “let your feelings for the compiler grow, embrace the syntax side.”

I did a two-day sprint through Zig a month ago and really really liked it. It has some quirks that I would have done differently, but overall I think it’s pretty cool. I just need a good small scale project to try it out on now.

My favorite example of the “use the language” ethos is the way Zig does generics. I have hated generics/templates in every language I use them in. They are the gordian knot of confusion that most languages in pursuit of some sort of unified type theory impale themselves on (yes, I’m mashing metaphors here). But Zig just uses its own self to define user types and generics come along for free. It resonates (with me at least) as a realization of what Gilda Bracha has shared about how to reify generics.

[1] https://gbracha.blogspot.com/2018/10/reified-generics-search...

View on HN

The way zig does generics is brilliant, and made me think "this is how every language should do it". One of those things that seems obvious in retrospect: just pass the types as normal parameters, and for generic data structures just represent their type as a function that receives those parameters and returns a new type. Man that's just beautiful. Only downside is, i suppose the types can never be inferred so they always need to be explicitly passed. But being explicit seems to be their thing anyway.

Zig's approach isn't unique, it's basically what dependently typed languages do. The problem is that if you don't do it right, it's too expressive and the type checker can loop forever.

Of course, this is also true of C++ templates since they're Turing complete, but it's not true of generics in most languages.

This isn't a gripe directed at you specifically.

I've noticed that when somebody says they like a growing language (Rust, Zig, ...) for this or that feature, people often come out of the woodwork to claim that it isn't unique, that some research project did it 5 years ago, etc. etc.

First, that's not even what they were saying. They like a feature of the language, they weren't making a claim about the novelty of it.

Second, even if they did erroneously make a claim about the feature's novelty, I think the theory type of people dismiss these sorts of languages too readily. Yes, somebody did it before. But it is usually very hard to bring these features into the mainstream or even adjacent to it.

It's just annoying when we're appreciating a language and the work that went into it and somebody pops their head in and says "Ackshually, Joe Gringoff published a paper in '95 detailing that exact thing, so it isn't anything new." Like I'm trying to enjoy "Samson and Delilah", I'm not really thinking about who did that kind of lighting first, so why are you using the lack of novelty to diminish the effort put into the lighting? If you want to say, "Fun fact, Giorno Capucelli was the first one to popularize that kind of lighting!" Then that's cool, but instead these people always use these facts to diminish something else instead of enhancing it. Just let me enjoy their handiwork!

I'm going to bring it back to the comment you are responding to. It's saving grace, is that it introduces to the thread the idea, "it's basically what dependently typed languages do". That has a couple of benefits, the commenter he's responding to can find out if that's true - https://en.wikipedia.org/wiki/Category:Dependently_typed_lan... (Zig isn't on there, I see other's are debating the point). If it does turn out to be true, the person might find a whole class of languages that share a feature he seems to really like. So while I kinda get your frustration, at least in this case it seems useful.

I argue to the contrary that it's quite disappointing to see features developed without referencing previous work. The annoying "Actually, so-and-so" is really just a symptom of the general lack of citations.

Maybe it's possible to design a language de novo without being aware of previous designs in the space, as Zig seems to be doing, but it seems quite dangerous - one wrong step and you've locked in a bad design. Whereas using proven designs (as Rust claims to be doing in their FAQ) is at least making use of some form of validation.

and what was the proof of these existing designs? peer review?

There is nothing new under the sun. What matters is what is /useful/ and that seems to be the focus for Zig, to be useful. The proven design it tries to improve on is C.

Really? You're using the Bible to argue with me?

Computing is still a young field, only 80 or so at this point. There are many areas that haven't been explored. For example polyhedral optimization only became a thing in the past 20 years. Zig only gets away with being shallow because LLVM does all the heavy lifting. If you follow LLVM you will find a steady flow of academic papers (it even started as an academic project).

When someone says "I like feature F in system S", I for one appreciate the response "F is actually called F' and exists in a purer form in system S'". It broadens my view of F in two ways! There might be nicer ways to phrase the response (along with links, maybe), but I for one appreciated the direct and very googleable approach the comment you're responding to took.

Comments like that provide context that you could use as search terms for finding more documents from which you could learn learn more about the feature.

If you're interested in programming languages in particular, the earlier papers could tell you about the philosophy and rationale about how and why the feature came about in the first place.

While I understand your reaction, I wasn't really diminishing anything. The OP I was responding to was saying other languages should do generics like Zig, and I basically just replied that other languages have done it that way (or rather, that Zig did it their way), and also pointed out some common pitfalls.

Zig may of course have found a better set of tradeoffs to make this feature more ergonomic, but I think this is more due to comptime than generics specifically. comptime would restrict the expressiveness that would normally lead to undecidability when reifying types as values, if I understand its semantics correctly.

> Second, even if they did erroneously make a claim about the feature's novelty, I think the theory type of people dismiss these sorts of languages too readily. Yes, somebody did it before. But it is usually very hard to bring these features into the mainstream or even adjacent to it.

It is, because people are unwilling to use them in existing languages. So it's extremely frustrating when what feels like the same people who've been trashing Haskell for ten years get all excited about how their new trendy language has this brilliant new feature... that is the same thing they were complaining about being pointless academic complication when Haskell did it.

> but it's not true of generics in most languages

not sure how true that is.

* TypeScript: https://github.com/microsoft/TypeScript/issues/14833

* Rust: https://sdleffler.github.io/RustTypeSystemTuringComplete/

* Haskell (GHC): https://mail.haskell.org/pipermail/haskell/2006-August/01835...

* Scala: https://michid.wordpress.com/2010/01/29/scala-type-level-enc...

* Java: https://arxiv.org/abs/1605.05274

Most of that cleverness requires generics + something else, usually some kind of subtyping. This is the case at least for Java, Haskell, Scala and Rust. Generics alone typically do not admit Turing complete expressions.

In Zig and dependently typed languages where types are ordinary values, you typically have the regular looping/recursion available, and so Turing completeness follows naturally unless you take steps to mitigate this. Zig makes a hard distinction between runtime and comptime which might solve this, and dependently typed languages have termination checkers which extend this sort of distinction in more flexible ways.

Dependent types go beyond what Zig does by removing the distinction between comptime variables and runtime variables (so types can depend on runtime variables). Zig goes beyond dependent types in the sense that the comptime/runtime distinction allows Zig to handle all comptime values at compile time, which is important for efficiency. It would be interesting to combine the two approaches, via partial evaluation or staging.

To my understanding, comptime is a form of partial evaluation. PE is typically done by a "binding time analysis"; comptime declarations are explicit binding time declarations.

You can also see Zig as a three stage language (comptime+compile time+runtime), where most compiled languages are two stage languages (compile time+runtime). There's a lot of overlap here.

> the type checker can loop forever

Oversimplifying: Zig anyways gives you "compiler branching tokens" so your type system can't loop forever, if I'm not mistaken

Kind of how Ethereum uses "gas" to make sure that bad/lazy actors won't waste CPU cycles when running smart contracts.

sure, but you aren't going to run out of compiler tokens unless you are trying to do something really crazy, like generate a precompiled table of prime numbers, as I have done. And I don't think you use them up in general, just when your compiler is taking certain branching operations (i don't actually know what the rules are)... I believe you can have a long program that consumes as many tokens as a short program, if their typesystems are the same and you don't ever use compile-time branches in the functions you're writing.

Do you have a preferred (favorite) implementation of dependent types?

Quickly scanning the list on wiki... Ada is the only imperative language listed.

Corecursive has had a few episodes about dependent types. Here's two:

https://corecursive.com/015-dependant-types-in-haskell-with-...

https://corecursive.com/023-little-typer-and-pie-language/

Learning more is on my to do list. To noob me, the descriptions remind me of Eiffel's constraints (asserts, pre/post-conditions). And maybe user defined typedefs, like constraining dayOfWeek to values 0..6, a bit like enums.

It looks very nice and I look forward to using it.

A downside for package authors (once Zig gets to the point of having a package ecosystem) will be that syntax errors are checked only with the comptime parameters that are actually used at call sites. To maintain compatibility, authors of public APIs will need tests with commonly-used comptime parameters.

It seems like a good way to avoid lots of type-level complexity in the language, though.

I've grown used to the idea that generics (data structure macros, C++ templates...) aren't that useful. If I find myself in a situation where I'm thinking of a solution that involves generics, I stop and ponder what is actually the essence of the repeated stuff. It rarely is on the syntactic level, often it runs deeper. Probably the commonalities can be distilled into a data structure.

Simple example: Intrusive linking headers (e.g. Linux kernel list.h). While those can benefit from an optional very very thin generics layer on top, essentially the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded.

Getting this right simplifies the code but can also speed up compile times.

How do you write a generic quicksort function without generics?

There are two ways I know of: (1) throw type and memory safety out the window and use void pointers plus size/alignment like qsort(3) does; (2) require that users manually write an interface with a swap(int i, int j) function like Go before generics does. Both solutions are really bad.

Void pointers also add an unfortunate layer of dereferencing.

In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.

Well, a modern optimizing compiler can get rid of the indirection if it inlines qsort() and then inlines the comparison function. Of course, it needs to be able to see the source of qsort() to do so (which might be a problem if it's dynamically linked).

If I'm understanding correctly, you're saying a compiler will optimize out "void*" to instead be the value put into it, so theres no pointer dereference to get to it?

That's what I am talking about. I don't know much about modern C optimizations.

There isn't any pointer to optimize out really, I don't think - at the machine level, a pointer is a pointer is an integer number regardless of its type at the source code level.

What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.

In the case of qsort, void* isn't a problem, since sort() would always take a pointer, but there absolutely is a difference at the machine level between void* and int - one is a value, the other is the address of a value. One is used for calculations, the other is used for calculations OR loading data from memory.

At the machine level there is absolutely a difference. one means your data is right here, the other means the data is elsewhere. That poor data locality can cause cache misses and always consumes extra cycles.

What is "right there"? If the computer should sort an array that is located in main memory, it needs to know their addresses (pointers) to even load them. There is no way around.

It depends on how many times removed it is.

Lets say it's 4 8bit ints. It can be sequentially and directly in memory like:

  stack: [0x01, 0x02, 0x03, 0x03]

Each int is directly next to each other in memory. But it could instead be pointers to the ints, like:

  stack: [0x07002412, 0x0700241A, 0x07002424, 0x070036A0]

  heap (or stack, really):
  0x07002412: 0x01
  0x0700241A: 0x02
  0x07002424: 0x03
  0x070036A0: 0x04

The CPU needs to dereference that pointer, and the cache is getting all screwed up.

That is what "void*" is doing. You're using a pointer instead of a value.

In C# this is what generics allow you to avoid.

  // This is like my first memory layout above.
  struct Foo<T> { public T MyField; }

vs:

  // This is like the second layout above.
  struct Foo { public object MyField; }

Among other things, yes, compilers will do that.

That seems strange because you'd think you may need the guarantee the pointer remains a pointer for an ABI? Or does it only do this in very limited circumstances? Do you know the term I can use to Google more info about this?

It only works if you use link-time optimization or the qsort() definition is otherwise available for the compiler to see.

The similarity of this optimization and what is typically thought of as "generic programming" is interesting.

I rarely ever do need a sorting algorithm for what I do. I might not have done even one sort call in 2021. Usually the data I have is sorted by construction, or doesn't need to be sorted in any particular order.

When I do need to sort, I just use qsort from libc. It's also easy to write my own version of qsort.

I once measured qsort vs std::sort on plain ints (basically the most pessimistic case for qsort vs std::sort) and the difference was like 2x. If this becomes a bottleneck then it's worth investigating how to take advantage of additional context to speed up the sorting much more than any generic sorting algorithm could do anyway. Simple example: bucket sort. (I'm 100% confident sorting performance hasn't ever been noticeable in my career so far, but I've done simple optimizations like that once in a while for fun).

> Both solutions are really bad.

Due to what I described above, I'm actually in favour of qsort - no new code is generated, just a simple library call that takes a pointer to the comparison function. Really really easy to use.

Maybe it’s lack of imagination but I cannot see how qsort is easier to use than std::sort.

In particular because std::sort is templated you can use anything callable including a lambda or function pointer as the comparator. But if you already have operator< defined for the type you don’t even need to define a comparator.

It seems like std::sort is shorter and simpler to write, safer, faster and generic across container types (including c arrays).

I _believe_ std::sort used to be more complicated because you had to define a class with a compare method for custom comparison functions, or something like that. Looking here https://en.cppreference.com/w/cpp/algorithm/sort , I cannot be arsed to find out what works since which version of C++. Come on, look at that link and tell me with a straight face you can't grok the qsort() signature much more easily than that mess.

Other than that, the STL is generally slower compiling compared to only including plain C headers, which is also taxing on the "ease of use" department.

`sort(begin(foo), end(foo))`

Has worked in C++ for ~25 years as long as `foo` is a container of items with an `operator<`. It has never required defining a separate class. It will also optimize better than qsort when qsort fails to inline.

Your main point is correct, but std::begin and std::end were added in C++11. You would have used pointers or begin/end member functions for most of those 25 years.

qsort is a horrible function, and infamously so. First, since it's part of the C stdlib, it is almost universally dynamically linked, precluding any chance for it to be inlined, and even worse, it calls a function pointer.

Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.

It does not matter. Your concerns are entirely academic. Simplicity wins.

> I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)`

Don't do this. Do "qsort(a, n, sizeof *a, compare)"

> with absolutely no way for the compiler to tell me I'm doing something obviously wrong.

In the event that it does not work, two things are very likely true. 1) it was a really dumb mistake. 2) you will notice immediately and can fix the mistake.

The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Stop worrying about hypothetical problems that aren't problems in practice. There are enough real problems to work on.

> you will notice immediately

No, you won't notice immediately. You will only notice when you run your code, because it will crash. And it might not crash right away, because the bad code is not being run, so you have a crash waiting to happen at some time in the future, which might have been avoided with a competent type system.

Users of statically typed languages have a different understanding of "immediately" than you do. If the compiler knows my code will crash, it should simply refuse to compile it until I fix it.

> The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved.

Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%".

That's not how the world works. Static types provide not just non crash guarantees but plenty of other advantages (automatic refactorings, performance, code that's easier to read and maintain, etc...).

You have just gotten used to a crappy developer experience because you are using a dynamically typed (or very badly typed) programming language. Get out of that boiling pot and be more exigent from your programming language, there are some very good ones available today which will make you go back to your statements above in a few years and think "Yeah... that was a pretty silly thing to say, but I know better now".

> You will only notice when you run your code

How did you infer that that's not immediately?

> If the compiler knows my code will crash, it should simply refuse to compile it until I fix it.

Sure but what if it doesn't know that, then I won't complain about the next best opportunity, which is pressing F5 once and seeing the code I just typed doesn't work as intended.

> Static types provide not just non crash guarantees

How about no?

> Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%".

If using a void-pointer parameter once in a blue moon for some convenience (callback function pointer), how is that 0% and not 99%? I recognize I've written too many comments, seeing as the replies are starting to get extremely poor. Ignoring the rest.

Since type safety is entirely academic, you should take a look at void (https://github.com/kyouko-taiga/void-lang), it seems like the perfect programming language for you.

You should take a look at what I wrote, because I did not make any such claim.

I've taken a look at pretty much all of your comments on this story, and that seems to be the logical conclusion of your stance on generics. I'm not really sure how you could think otherwise and write the comment I replied to, and lots of others in here.

To someone that said "Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly." you replied "It does not matter. Your concerns are entirely academic. Simplicity wins.". Type safety is a real concern, and lack of it has conséquences in the real world, often in the form of bugs or vulnerablities, but you seem deaf to any arguments so I don't see the point of arguing with you. Instead, I've linked you something that you might like.

My point is there is no need to be so preconcerned about a rarely used function that requires giving up a little safety (in a place with very little "code entropy" even). Doing so does not equal giving up type safety completely, not even 1% of it. There are way bigger issues to address even in the best of codebases.

> Type safety is a real concern, and lack of it has conséquences in the real world, often in the form of bugs or vulnerablities

To me type safety is first and foremost a usability feature - already a primitive type system like C's saves tons of time when changing code. But is it a great concern with regards to bugs and vulnerabilities? Type safety is static, once you've run a particular section of code, you can be relatively sure that there are no type issues on that path. (Granted that to run all code sections even once can be lots of work). That is contrary to other types of bugs which might only show up on rare occasions, and possibly require malicious intent.

Type safety is a soundness guarantee and can be , in some implementations, a usability feature.

I don't know what you do, but for our codebase, we run transactions against the database in most of the integration tests. We can't generally be sure the database won't return rows in some order it likes that aren't the rows we expect -- so if we don't have a generic sorting function we will have flaky tests.

If you can't bring the database to return the values in a well defined order, absolutely go ahead and sort it! No need for _generics_ though, qsort() will do just fine.

(C probably isn't great for DB interop in any case).

You may not need to sort, but std::rotate? std::partition? std::all_of? The list goes on. Without templates, these wouldn’t provide the value they do. (Thanks Stepanov!)

Use Smalltalk?

Don't you mean "If you use a late bound language, you don't need to chase down the type rabbit hole and encounter the nasty teeth that are generics along the way"?

An example of which is Smalltalk, but could also include Dart 1, Python, Elixir, CLOS/Lisp, JavaScript, etc.

Smalltalk is an interesting exhibition of a similar principle though. If you did add types to Smalltalk, you'd likely solve this containment parameterization problem the same way you do nearly everything in Smalltalk: by binding some new behavior (adding a method) to some data (a class object). You'd add a message to the MetaClass types that could create flyweight class types parameterized on the fly. And when you compiled, you'd send messages to the instance of the class itself to manufacture that synthetic on-the-fly type. Hand wave, hand wave, hand wave.

The "let's see where naval gazing on a unifying principle goes?" that is employed in Zig is to use the same language itself to recurse on itself when defining itself, types included.

What happens in more traditional/mainstream/Algol derived languages, is that each part of the system gets a sort of sub department of the language. You have a set of keywords/syntax for expressing run time behavior. And then someone says, but how do actually bring data to life--a sort of "Creatio ex nihilo" problem--and the answer is we need a new department in the language, so we get keywords/syntax for constructors. When behavior/construction needs to be parameterized across compilation paths, we get another set of keywords/syntax. And another for type definition. And yet another for scope management. And then again with meta things. And maybe a preprocessor.

I do think there's a trick to finding a sweet spot in these "turtles all the way down" systems. In Smalltalk, I was happy with how the "don't know what's going on? just follow the message sends", but at the same time still providing enough structure/composition to have to be reflecting/introspecting all the time. Forth is event simpler, but I found I had to constant recompile things in my head to resolve. I'm relatively new on the Elixir curve, and am beginning to worry this happens with macros there. Figuring out how Plug works really messes with my brain. I haven't done enough with Zig to know where it's @comptime ends up in this balance.

Generics are the way that useful semantics can find their way into useful libraries. A collection of useful libraries is what is needed to make a language useful.

This is why C++ usage is still growing fast: almost every new feature makes it possible to write more powerful libraries that get, thereby, easier to use.

> This is why C++ usage is still growing fast: almost every new feature makes it possible to write more powerful libraries that get, thereby, easier to use.

LOL no, it's growing because people can't get the performance and battery life they want out of other languages and it's a hugely entrenched player with a gigantic existing ecosystem and is able to seamlessly call into all existing C code as well. Language features after C++11 (arguably C++98) have very little to do with new growth except keeping interest by showing it's alive and spurring book sales and conference tickets. Most libraries still target old versions of the standard and don't use most new features. C++14 vs C++17 vs C++20 makes very little difference for 99% of users. Most people are not using polymorphic allocators to deserialize Unicode inside their constexpr DSL parser.

C++ pre-11 was in decline. Since 11, it has exploded. Every ISO meeting, 3 times/year, had more attendees than any previous meeting. It is impossible to explain that change except by the extra features that showed up in 11, and subsequent Standards. Many of the important new features are in the standard library, that are useful building blocks for other libraries.

Most of the use of new features has been to make libraries more powerful, and easy and safe to use. So, users of those libraries don't need to use the new features directly to benefit from them.

Which was my point.

This is a blanket assertion. Why should useful semantics require generics? Why can't they come with simple fixed data structures? If you can provide a nice counterexample to the example that I gave, this would be more convincing.

Absent the absolute necessity of generics to support essential semantics, I'm probably in favour of a simpler generics-less version. I don't see why "more powerful libraries" get automatically easier to use. It could often be the opposite.

There is a tradition in some C++ subcultures where they try to cram in as many invariants as possible into types, concepts, templates, etc. at all costs. I tend to think that if all this heavy machinery is needed, the functionality might be too complicated from the start.

If you were writing a library, and a language feature made it possible to make your library easier to use safely, why would you not?

You might as well say, "I don't see why a more expensive dinner has to be tastier."

It is always easy to make libraries that are hard to use, in any language, but those do not become popular if there are better alternatives.

We need generics because users have types that they need libraries to work with. Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that. This is why C programs are crammed with so many custom one-off hash tables: You cannot code a useful hash table library in C.

Libraries start simple, and accumulate your "heavy machinery" as they are made more useful and usable for their growing family of users. A library that lacks users does not.

It's more like, "I don't see why a tastier dinner has to be more expensive". It's a tradeoff situation, and while I might be willing to buy a great $50+ meal from time to time instead of just a $20 one, I don't have any inclination to pay $1000 even if the meal is a tiny little bit better than the just-great one.

It's a matter of tradeoffs. Library design is a balancing act.

> We need generics because users have types that they need libraries to work with.

This is right where I become sceptical. Most libraries shouldn't care for the user's types at all. They should expose their own types so you can work the library - not the other way around.

Please provide an actual use case where the library has to "know" about the user's types (and please don't mention std::sort. It's as common an example as is "Dog :: Animal" examples to argue for class inheritance, and is just as irrelevant).

> Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that.

As I mentioned, linked list can tangentially benefit from a very very thing generics layer on top of a fixed data structure implementation. The layer does nothing more than "instanciate" the types, but there is no code generated. But then again, the added convenience / safety is minimal, I once wrote a C++ implementation that I was quite happy with, and never used it.

> This is why C programs are crammed with so many custom one-off hash tables

There are probably not huge issues with a design like "HashTable ht = { .hash = &foo_key_hash, .equals = &foo_key_equals }" (if quick results are what you're after), but yes it is nice to have a few lines of type-safe wrap generated over some generic container interface.

An alternative reason why you'll find a good amount of custom hashtables in C code bases is, I suppose, that there are a lot of different ways to implement hash tables. Also writing a little code here might not be so bad. I've had 1 use case for a "hash" table in 2021 (glyph hash table for a new iteration of my font rendering code) and I've gotten away without even implementing it - the for-loop I've written has never shown up in any performance profile.

Considering that container data structures are probably the highest profile application for generics, I'm still not convinced that generics are needed in a systems programming language...

> This is right where I become sceptical. Most libraries shouldn't care for the user's types at all. They should expose their own types so you can work the library - not the other way around.

This is an utterly bizarre statement. Should people convert collections of Xs from library 1 to other kinds of collections of Ys to work with library 2?

A very basic use case that shows up all the time everywhere, especially in systems programming, is that I have an array of items and I want to pass it to some library. But, to work with an array, you need to know the size of elements of the array, so that arr[x] knows how to compute the address of x. There are exactly 3 ways to achieve this:

1. The library only accepts arrays of some specific type (e.g. int[]). If you have some other type, you have to find some way of converting to the type known in the library - in O(n) time.

2. The library expects arrays of some fixed-size type that can hold any value (e.g. void*[]). This typically adds huge overhead, since now the elements of the array are not together in memory, they are scattered all over the place; and the library must fetch them from memory before doing anything with them.

3. Generics - the library accepts T[], and can easily do sizeof(T) to know how to access arr[x].

Even qsort is actually an example of C's convoluted support for generic arrays: you're explicitly passing the array base and its type (the number of bytes) to qsort. C's extremely basic type system anyway essentially identifies types with byte sizes in practice, so it's not obvious that qsort works like this (and of course, it's less safe, since instead of passing an int, you have to pass void* + sizeof(int), potentially getting them mixed up).

> A very basic use case that shows up all the time everywhere, especially in systems programming, is that I have an array of items and I want to pass it to some library.

My thinking is this. Either a library function cares about what type of data you pass to it because it is designed to do some operation on it - then it will accept only a specific type, like "void func(Foo *foos, int count)". Or, the function does not care about the type of data but just wants to send it somewhere else. In this case, you can pass a void-pointer + size to it.

Interfaces like sorting functions can be seen as exceptions under the umbrella term "container library". Like the qsort() example, usually all you need is a few metrics for the data type - size, maybe alignment - and at most a few "method calls" - equality, simple get/set operations - and that's it. For all I can say these situations are not very common in systems programming, at least not for what I do. This stuff tends to come up in application level programming. It's definitely very common in my Python scripts. When it does come up in systems occasionally, a vtable struct is a good way to deal with the situation generically. In the qsort() case, the function pointer can be passed directly.

> 1. The library only accepts arrays of some specific type (e.g. int[]). If you have some other type, you have to find some way of converting to the type known in the library - in O(n) time.

Considering how computers work, I don't think it is much of a constraint to assume that arrays are of the form "Foo *foos". Coincidentally C _does_ have builtin "generics" for arrays of things, and real machines do have assembly instructions to quickly compute addresses based on hardcoded element size.

> (and of course, it's less safe, since instead of passing an int, you have to pass void* + sizeof(int), potentially getting them mixed up).

There is little real chance of getting them mixed up. If you actually run the code you will notice.

> void-pointer + size to it

How do I make sure they always stay in sync ? (adding removing elements)

Because the ever increasing number of CVE's where brilliant programmers who screw this up, says doing this manually is prone to error.

Sure you could do everything without generics. But its a lot more error prone. Generics can in addition with other language construct provide better safety.

Generics also provide a tradeoff, that library code is more complicated, but its usage its easier to read.

You don't. A pointer is a pointer, an int is an int. Memory is memory. Dynamic Arrays that support "adding or removing" elements are a high-level feature that don't mesh well with direct memory manipulation. If you are really really concerned you can try to code in Rust with its ownership tracking system. Otherwise, try to write simple enough code and test it as good as you can. You can use a language or compiler switch that at least supports "fat pointers" for implicit bounds checking, but this won't deal with reallocations.

But in general "systems programming" means "buffer processing" i.e. a lot of "streaming" and most buffers are short lived - they are never overwritten and you drop them soon after they were created - or they never change in size. (reallocation incurs unnecessary copies, and there are many good reasons to chunk large data sets up into fixed-width sizes). All this makes "stay in sync" very much a non-problem. I haven't had to worry about this in years. It's almost an academic exercise that only exists to prove that we need garbage collection ;-)

> Because the ever increasing number of CVE's where brilliant programmers who screw this up, says doing this manually is prone to error.

If you code in a memory unsafe language like C, things can go horribly wrong and your code can be exploited. If you code in a memory safe language, you can end up with horribly slow and unmaintainable code and you might still be exploited.

> Generics can in addition with other language construct provide better safety.

Better than using a hash table with generics, is not using a hash table at all...

Or, best, not even programming at all?

Or, in practice, hiring somebody who actually understands how to program, understands what makes a library or language a good choice, and understands how to get the most value from both, without insane blinders.

You miss the point. You can get more money for the dinner only if you deliver more. Your $20 meal delivers more than your $2 meal. If you can only deliver the $2 meal, you aren't getting $20 for it.

I have already cited two separate examples, which you have studiously ignored. Look online and find them in their thousands. It is hard to find even one C++ library that is not made better by its ability to integrate with users' choices of types.

Updated to not ignore your examples.

If std::vector, std::array or std::unique_ptr could somehow have been implemented better without the use of templates in the C++ standard library, I think you'll find that they would have been implemented that way.

I don't know what you mean by "essential semantics", but the fact remains, as ncmncm says, that templates is the feature that allows new types of type safe generic abstractions to be built and added to the arsenal of C++ programmers. It's the feature that, most of all, has kept the C++ language alive and thriving over the past 20 years, in my opinion. Without it, the language would probably be dead.

> This is a blanket assertion. Why should useful semantics require generics? Why can't they come with simple fixed data structures?

What do you mean by "fixed data structures"?

> If you can provide a nice counterexample to the example that I gave

I may be missing somehing but I don't understand your example. The idea of a list is that we want it to hold any data, so the API to a list by necessity becomes generic. Unless you cas everything to void*.

---

I have another counterexample from userspace. Our internal APIs all use the same converntions which make working with them predictable and same from any language. An API returns:

  {
     result: [a list of data],
     nextPageToken: 
  }

Different APIs will of course have different data. Some API will return a list of contracts. Another API will retur a list of media. A third API will... etc.

I had the misfortune of working with these APIs in Go before generics. Welcome to copy-pasting code that deals with this. Or cast from interface{}/void* to proper data in runtime. Any sane language of course lets you write something like GetAllData<T>()

> the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded.

Why should that be so? It's particularly NOT true for one of the simplest and most efficient data structures in any program: the array. The code that needs to work with an array needs to know exactly the size of each element of the array, so you basically can't have an efficient language that doesn't support generic arrays. Haskell maybe sometimes gets by with a very smart compiler and heavy use of laziness, but even C has support for generic arrays.

You can totally make array iteration generic, just pass the element size. Not saying it is necessarily a good idea.

I agree that there are cases where the "there should be a single central piece of code" argument is not a strong one, because the generic code is so simple that it should be inlined into the usage code. Arrays iteration is one example - but note that for example sorting code is, while the sorting algorithm might be generic, more than just generic array iteration.

Doubly linked lists already profit from shared code in some ways, and definitely I'd find it a bad idea to replicate for example tree mutation code (RB tree or similar) for each node type. Embedding the header structure and keeping the links just between these embedded headers, to be able to reuse a common (compiled) piece of code is a very good idea here IMO.

Reply on news.ycombinator.com