Comment by tialaramex | Hacker News Reader

Comment by tialaramex | Hacker News Reader

Parent Full thread

STL stands for Standard Template Library, which is an important piece of Generic Programming - it provides algorithms which are generic over the container types, so there's one library implementation of say sorting, and you can (but shouldn't) sort a linked list if you want to. When you see people asking why language X doesn't have "generics" this is the feature they're asking about - it's so fundamental now but in the 1990s it wasn't even obvious that you might want to write software this way. Generic Programming had been tried before, but the STL is an important idea and WG21 (the C++ Standards Committee) were persuaded to include it in the requirements for the new ISO standard.

However, in C++ because the STL is a big part of their Standard Library, and because Microsoft insists on naming their entire implementation of the Standard Library STL, it's usual to say STL to mean the entire stdlib, even though many parts of it aren't about generic programming at all.

So the STL is a crucial idea and inventing that was a tremendous accomplishment - but the C++ stdlib, which may be called "STL" and is in this article, is not a very good realisation of that idea. Indeed I'd argue the C++ programming language isn't a good realisation of that idea either - it was possible to write the STL for C++ and so that's what was done, but knowing this is a good idea you'd design the language differently. And people have.

Thank you for an educational comment, the historical context was interesting to learn about.

The last paragraph hints that there are more modern languages than C++ which implement generic programming in a better way, truer to its original conception?

I'm convinced, at this point, that Zig is that language, with comptime. Caveats: the system is not mature, Zig isn't 1.0 yet, there are some arbitrary limitations, the comptime type system is somewhat all-or-nothing, TL;DR it isn't done. All of this is immaturity, rather than an essential limitation of the design.

The breakthrough with C++ templates, was to provide a macro system which creates an AST for a static language, at compile time, using (surprise!) a template of the desired code. Contrast with the C preprocessor, which works on the token stream (there's more to it if you're curious, but in a way that makes it worse, not better).

Of course, a macro system operating on the AST is an older idea than C, this is one of the essential features of Lisp. But Lisps have always been dynamic languages. In some other timeline, there was an s-expression language for writing static programs, which used Lisp-style macros, and thereby avoided the problems with C++ templates. But we don't live in that timeline, it's a road not taken.

This template system enabled C++ programmers to write code which was generic over not just types, but features of types, and much else, it's all rather complex.

The problem, in essence, is that it was thought that template-expansion could be a decidable process implemented using a sub-Turing-complete language. So it was built using a second syntax, which was intended to be restrictive but flexible. Uh-oh!

C++ templates are Turing complete, as it turns out. So what C++ has is a second language. You could write your entire program in that language, and execute it at compile time. For everything you can do in C++, there's a second way to do it in templates, with its own syntax and semantics. Invariably, this language is much more verbose, and just... weird, in big and small ways. The sum of this is a system which is difficult to understand, and which generates notoriously terrible errors. This isn't intended as a complete summary of C++ template's shortcomings and weird features. That would take longer.

Zig just lets you run Zig at compile time. It's much, much better. Instead of trying and failing to make the problem decidable, Zig brute-forces the question by providing a branch quota: this is similar to gas in the EVM, or what Piccolo, a Rust implementation of Lua, calls "fuel". Comptime comes with a complexity limit, after which it quits, and which can be boosted for operations where the quota is insufficient.

So there aren't two languages to learn, just the one: Zig. That glosses over some things, like loop and switch constructs have inline equivalents for comptime, but the general premise holds.

There are other things which C++ makes easy which are less easy in Zig, like runtime polymorphism. But comptime is just a massive improvement over templates.

Oh that's a great response, much appreciated. I'm glad I asked the question.

From what I understand, a disadvantage of this templating capability in C++ is that it makes the language "unpredictable" in terms of static analysis, so that, for example, intellisense in code editors cannot be implemented without having a full C++ compiler. ..But then again, maybe that's true of any language with macros, where the code can dynamically modify itself.

That's an interesting point too, about how C++ templating is a second language that runs at compile time, making the code more complicated to understand. Whereas in Lisps, macros are written in the same language, working with the same AST in a unified way. It's conceptually simpler, a more elegant way to achieve the same result.

I'd heard of comptime in Zig, but didn't know that there was a "complexity limit". Fascinating. It makes sense how it's related to the concept of "gas" in the Ethereum virtual machine, and "fuel" in Piccolo. (I remember seeing the latter language recently.)

https://ziglang.org/documentation/master/#setEvalBranchQuota

https://kyju.org/blog/piccolo-a-stackless-lua-interpreter/#f...

https://ethereum.org/en/developers/docs/gas/

..Whew, many tempting rabbit holes there. :) I'd been interested in Zig, reading about it here and there, but your comment convinced me to get more serious about studying it. Thanks!

Interesting that you seem to consider Zig a pioneer in comptime templating, when, as other commenter mentioned, D has been doing that for two decades.

https://tour.dlang.org/tour/en/basics/templates

https://tour.dlang.org/tour/en/gems/compile-time-function-ev...

As far as I can tell, D's templates and CTFE are as powerful as Zig's comptime (not sure if they're exactly equivalently powerful, but if they're not, the difference is not very large in practice or I'm pretty sure I would've noticed).

> As far as I can tell, D's templates and CTFE are as powerful as Zig's comptime

You might very well be right. I didn't realize that D's templating was much different from C++, I don't know much about the language. I'll also note that the sibling comment you refer to wasn't posted when I wrote my reply.

I'll note that a careful reading of my post, and the one it was responding to, will reveal that I didn't claim that Zig was the only, or first, language to improve on C++ templates. Only that it's an example of a more modern language which has done so. But I'm also largely ignorant of the ins and outs of D.

It seems that you, however, are not. Here's an example of Zig building a data structure at comptime:

https://ziglang.org/documentation/0.12.0/std/#src/std/compti...

Is this an example of something D could do as well? If so, I'll be sure to give the language credit the next time the topic comes up.

I admit I am no expert in D, I've written just a couple of hobby projects in it... but this sort of thing is actually much easier in D because it has associative arrays.

About comptime, it seems to me it's trivial to do that in D.

I started a little implementation of StringMap based losely on the Zig example, but I just did enough to show how D's templates and associative arrays could be used to implement that:

https://godbolt.org/z/o7GoobbKb

You can see that the creation of the map does not generate any Assembly, so it's run at comptime:

        // comptime values!
 static immutable entries = ["foo": 1, "bar": 2, "zort": 3];
 enum map = mapOf(entries);

Notice that in D, "enum" can be used as a compile-time only variable, see https://dlang.org/spec/enum.html#manifest_constants

The Assembly seems to be almost all related to the associative array implementation generated by the D compiler.

EDIT : if you want to try to continue the impl, have a look at the D's template tutorial: https://github.com/PhilippeSigaud/D-templates-tutorial/blob/...

D templates can do pretty much anything.

Cool.

> it has associative arrays

Zig also has a variety of generic data structures in the standard library for this purpose, HashMap and ArrayHashMap and variants. The main limitation in the current implementation of comptime is that it can't handle heap allocations, so these can't be used at comptime yet. D has a garbage collector, which makes that sort of thing easier. It's also about fifteen years older, which also helps.

That limitation won't be there forever, though, this is just the immaturity I referenced in my first post.

But fair enough, you've convinced me: D is also a language which has improved on C++ templates using compile-time execution.

Looks like C++ itself is another such language! The last time I used it was well before the later constexpr and immediate mode function features described here existed. https://en.wikipedia.org/wiki/Compile-time_function_executio...

Yes, D. D has great support for compile-time function execution, and generics. You can generate code at compile time and use it with generics. It's what C++ should have been.

We have the libc - what makes the STL such a crucial idea and tremendous accomplishment? Hell, they seem to share many of the same deficiencies even - caring about things they shouldn't, then doing a terrible job of it.

It's hard to even tell what you think you're commenting on here, so I'll be generous and assume you're comparing the libc qsort to the STL's sort algorithm.

The libc qsort is type erased and only works on arrays. So to sort Widgets we note down how big a Widget is and how many there are, then we forget these are Widgets and we provide qsort with just a type erased pointer to the array [of Widgets], the size and count, and we provide a function pointer (we'll need to ensure it's suited for specifically sorting Widgets) to a custom function we wrote which receives a pair of type erased pointers [to Widgets] to decide which comes before the other.

A lot of performance optimisations are left on the table when we do this, and of course because it's type erased it also loses type safety. We can't reliably apply our algorithm to any other collection, and we can't easily re-use the comparison functions either.

The STL's generics mean you preserve type safety and you can use this for any (conforming) collection type, and you can re-use comparisons because those are generic too. Along the way you pick up the performance optimisations that were lost with type erasure.

Better still, all of this is optional. You can perform the type erasure explicitly if, for example, you have a thousand different types and want to emit code to sort them all even if it's a little slower, rather than emit a thousand different sort implementations, if the code size is crucial for example.

libc doesn't really have a concept of containers or iterators. The only container it knows is an array.

The one well-known "generic" algorithm in libc is qsort. But qsort only works with pointers, and so can only sort continuous containers. You can't sort a linked list with qsort. In contrast, the STL has a more general concept of iterators that know how to fetch their next element (and some iterators can do more than just that). This allows the STL to have a std::sort algorithm that works on arrays, linked lists, trees, and whatever other data structure you want to come up with.

So the crucial idea is that the STL provides a large set of algorithms that work on all containers. No matter what kind of weird container you have, as long as you can provide an iterator for it, you can use most of the ~100 different standard algorithms on it. You can sort, find specific elements, partition, find the max element, filter elements, etc.

And the idea also goes the other way around. The STL also provides common containers that you'll need, such as linked lists, growable arrays, associative containers, strings. Of course, all the STL algorithms work with the STL containers.

Then, if you want to write your own algorithm, you only need to write it once in terms of iterators and then you can use it with all the different containers. No need to write the same routine twice.

The last big accomplishment is that all this can be done with almost no runtime overhead. All the types are resolved at compile-time, and generic algorithms can be specialized if you have a more efficient implementation for a specific container. This means that if you wrote a manual implementation of an algorithm that specifically matches one container, it would not be much faster or consume fewer resources than just using the generic STL algorithm. At the time the STL was originally incorporated, I think this was unique and no other language was actually capable of doing this.

Reply on news.ycombinator.com