Zig-style generics are not well-suited for most languages

Too long; didn’t read: Zig’s compilation scheme for generics shares a lot of similarities with C++, and hence the pitfalls too. Such a compilation scheme is not well-suited to all languages, so armchair suggestions about how other languages should embrace Zig-style generics are misguided. Ain’t nobody handing out free lunches in Generics Land.

I’ve seen one too many people claim that Zig’s implementation of generics is somehow perfect, and that other languages should copy it. Here is one such example from a recent thread in r/programming:

Zig has just taken the path that all languages should have taken by now and decoupled generics from their type system so you don’t end up with a bastardized language within a language that has weird, inconsistent rules and behaviors.

Zig saw that generics is literally just generating code at compile time and decided to ask “why on earth are we writing entirely separate turing complete programming languages for this?”

This comment is sitting at +17 at the time of writing.

This is just one example, but I’ve seen this repeated enough times that I got a little frustrated. Hence this post. (Yes, I know, XKCD 386: Duty Calls…)

Disclaimer

This post is meant to discuss reasons why Zig-style generics are not well-suited for languages other than Zig. Zig’s generics are in some sense well-suited to Zig, because they line up with the language’s philosophy that it is very important to have fewer concepts rather than more concepts.

However, most languages don’t share that philosophy, at least, not as strongly as Zig does.

It’s also not meant as a dig at people who enjoy Zig’s generics. If you’re writing mostly application code, by yourself or in a small team, I wouldn’t find it hard to believe that you enjoy using it. More power to you. All I ask from you is to read to the end of this post, in the hope that it will stop you from being an overenthusiastic youngster when talking about it to other people.

Zig generics for the uninitiated

(Skip this section if you already know how Zig generics work.)

Lack of constraints in signatures

The basic idea behind generic functions in any language is that the function declaration has one or more parameters for which it doesn’t know the entire type. The typical syntax looks something like:

func myGenericFunc<T, S>(x: T, y: MyGenericStruct<S>)

However, how do you do something (copy data, move data, transform data) with the corresponding values x and y if you don’t know about what operations are possible?

There are broadly two different design decisions possible here:

  1. Require specifying what operations are possible in the function signature. These can be checked at call-sites of myGenericFunc. There are various approaches to this – Go interfaces, Rust traits, Haskell type classes, C++ concepts and so on.
  2. Don’t require specifying the operations needed up-front; instead, at every call-site, instantiate the body of myGenericFunc with the passed type arguments (e.g. T = Int, S = Void), and check if the body type-checks. (Of course, this can be cached in the compiler to avoid duplicate work if one has a guarantee of purity.)

In addition, certain operations are always allowed by default, to reduce verbosity in the common case. For example, in Rust, unannotated generics parameters stand in for types which can be moved, but allowing deep-copying requires an explicit Clone constraint. In contrast, Swift and Go allow deep-copying by default. These choices reflect different priorities and perspectives on what is needless friction vs what is useful information.

Colloquially, the first group is often called “generics” and the second system is called “templates”. The most popular (read: notorious) example in the second group is C++. The problem is that “generics” is also overloaded to mean “any system for polymorphism”, so with that meaning, it would include templates as a subset. I’m going to keep using “generics” in the second sense of the word.

OK! So what does all of that have to do with Zig’s generics?

Zig’s generics are really templates, where you do not specify constraints up-front. Instead, you write a function which takes the type as a compile-time argument. Here is a code example:

(P.S. Code examples are tested with Zig 0.9.0, which is slightly old at this point.)

const std = @import("std");

const X = struct {
    f: u32,
};

pub fn main() void {
    optimistic(X, X{.f = 0});
}

fn optimistic(comptime T: type, t: T) void {
    std.debug.print(".f={d}\n", .{t.f});
}

This code type-checks fine.

Notice that the optimistic function accesses the field f on the parameter t without having any extra constraints in the function signature. The equivalent code would fail to compile in Go, Swift, Rust, Haskell etc. with a type error inside the optimistic function, but it would compile in C++.

The difference between Zig and most other statically-typed languages in the second camp is the language used for metaprogramming and the flexibility you have at compile time. Here is a non-comprehensive overview:

So Zig is somewhat similar to D and Circle here. However, compared to the most mainstream language on the list, which is C++, Zig makes the experience of metaprogramming more approachable.

Again, to re-iterate, the list is not meant to be comprehensive. For example, Rust also has a flavor of templates now with increasing support for compile-time evaluation and the ability to use compile-time functions in certain generic contexts.

I’m also not talking about dynamically typed languages here because this post is going to be too long anyways, and I’m primarily concerned about statically-typed languages.

Lack of stage information in signatures

While Zig features compile-time computation, information about when functions are available is not a part of function signatures. Here is a code example:

const std = @import("std");

fn xkcd_rand_u8() u8 {
  return 4;
}

fn rand_u8() u8 {
  var buf: [1]u8 = undefined;
  std.os.getrandom(&buf) catch { return 0; }; // no error here
  return buf[0];
}

pub fn main() !void {
  const x = comptime xkcd_rand_u8(); // OK
  const y = comptime rand_u8(); // error
  std.debug.print("{d} {d}\n", .{x, y});
}

Even though xkcd_rand_u8 and rand_u8 have the same signature, not both of them can be called in a comptime context.

In contrast, C++ code attempting to call non-constexpr functions (i.e. functions only accessible at run time) in a constexpr context (i.e. functions which are available both at compile time and run time) will give an error at the call site.

int f(int a) { return a; }
constexpr int g(int a) { return f(a); } // error

You don’t need to have a call to g for the error to be triggered. Rust has similar behavior as C++.

Why Zig-style generics are unsuitable for most languages

OK! Let’s get down to the main point of this post, which is why Zig-style generics are not a good fit for most languages.

One meta point to keep in mind: many of the points here mirror the downsides of dynamic typing in comparison to static typing (again, not to imply that dynamic typing is not sometimes useful), because in some sense, it is the same problem but in a different context – instead of run time vs compile time, we’re talking about instantiation time vs declaration time. Yes, you have more flexibility to do whatever you want, but the problem is that you have more flexibility to do whatever you want.

Limited compiler support when calling generic code

(Alt. subheading: Traumatic type errors when calling generic code)

Language designers usually care about error messages. The problem with templates is that you can get errors which are arbitrarily deep in generic code. A single type error can easily end up generating a generic instantiation trace that has dozens of error messages.

C++ template errors are somewhat notorious for this, having known to make many grown adults weep.

Most of the in-between ones are irrelevant, but they’re shown anyways, because that compiler does not (and almost cannot, by construction, I suppose barring some future applications of ML) have knowledge of which bits of the trace are actually relevant.

In other words, the compiler has no way of knowing whether the error is in the template’s implementation or if the caller instantiated the template with invalid parameters, or if the error is somewhere in the call chain in-between, so it needs to show the entire trace so that you can try to figure out what the true source of the error is. (Added based on wording suggested by u/sandwich_today in the r/programming discussion)

If one wants to support more complex type system features, like higher-kinded types or rank-2 polymorphism (or higher), the complexity of error messages becomes even worse.

EDIT(2022/10/10): An example of this is the code example from before, where the attempted call to os.getrandom fails inside a @ptrToInt call several function calls deep inside the implementation, instead of at the call site of os.getrandom.

EDIT(2022/10/10): One of the factors which makes template errors in C++ worse compared to Zig is that C++ supports function overloading and other fun stuff like SFINAE and ADL which influence name lookup in non-trivial ways.

Limited compiler support when writing generic code

Since templates cannot be fully type-checked by themselves – and depending on the flexibility you want to allow, they cannot be type-checked at all before instantiation – this means that you have two options when writing generic code, such as in a library:

The compiler gives you more flexibility, but OTOH if you want library users to have a good developer experience when they make mistakes, you need to do a bunch of extra work.

This also makes noticing breaking changes in generic code harder; if you accidentally require some extra constraints (e.g. a type be comparable, because you’re sorting), the function signature can still be unchanged.

The lack of explicit stage information also means that converting a compile-time accessible function to a run-time-only function is a breaking change, but again there is no signature change to indicate that. In contrast, such a change would immediately be flagged by a compiler for C++ or Rust, because you’d have to remove a constexpr/const annotation from the function signature.

Limited type inference

Type inference in languages like Swift, Rust, Haskell etc. is sophisticated in a couple of ways:

This enables various patterns like iterator chaining with typed iterators, using typed representations in UI frameworks (like SwiftUI), and conducting what is essentially proof search after specifying a bunch of simpler lemmas – all without a heavy annotation burden.

It also enables more “simple” type inference like relating literal types in collection literals and allowing argument types to influence a function’s generic arguments.

The reason why this all works out is because the constraint language is (erm) constrained enough to allow making inferences and solving for variables.

Making full-blown imperative programming available for metaprogramming and getting rid of constraints means that there isn’t really a good way to make any meaningful progress on evaluating type expressions with unsolved type variables.

In a loose way, this is the difference between Prolog and C; it is “easy” to evaluate programs forwards in C, in Prolog (without cut), it is easy to also evaluate the program backwards.

EDIT(2022/10/10): Couple of examples related to type inference here.

  1. Zig issue 2904 discusses “Type Inference in the Standard Library”. One of the questions posed in the issue description is: “When should the standard library make use of type inference for function parameters?” which makes sense in the context of Zig, but would generally sound strange in languages like Rust, Haskell etc., because type inference is always “on” at the language level, most libraries don’t need to do extra work to get reliable type inference out-of-the-box.
  2. The C++ standard library makes extensive use of template deduction guides, as well as helper functions (like std::make_pair) which essentially act like constructors but support type inference. There are a relatively large number of C++ resources which discuss class template argument deduction (CTAD) (indicating the need for understanding these for writing generic code) which do not have equivalents in ML-family languages.

Cannot distribute binary-only libraries with generic interfaces

Some languages like Swift and C# care about allowing binary-only libraries with generic interfaces.

In a template-based system, one need to make the source code for the templates available so that calling code can be type-checked. The other alternative is to only allow monomorphic code in interfaces or always expose generic code in interfaces (like C++ templates exposed in headers).

Zig doesn’t have this constraint because Zig is designed around whole-program compilation from the start (IIUC, its error union system requires knowledge of all possible errors up front**.

EDIT(2022/10/10): Examples related to binary-only libraries here. Apple distributes only interfaces for most of its frameworks in Xcode, which are available in a binary-only form as part of the OS. The Apple ecosystem also has 3rd party binary-only frameworks, which are supported by Swift Package Manager and Xcode. So for Apple’s groups developing software for iOS, macOS etc., Swift having C++ style templates instead of Haskell style type classes would not have been a practical solution (there is also the problem of code size, but this is a deal-breaker).

Tooling needs to do more work

In an IDE setting, if function signatures fully describe all constraints, one can avoid re-type-checking callers when only the body of a function changes. As Aleksey Kladov (@matklad) has written in Three Architectures for a Responsive IDE

[..] it’s not the incrementality that makes and IDE fast. Rather, it’s laziness — the ability to skip huge swaths of code altogether.

With templates, changing the body of a generic function means that the entire transitive call graph needs to (in principle) be type-checked again. One can try to be clever here in terms of incrementality, but the difficulty level has increased from a trivial problem to one that requires careful thought and extra book-keeping.

Even if compilation performance is not a problem, there is a couple of ergonomics issues.

First hover documentation is less useful by default, unless the author of the generic code carefully documents all required functionality in doc comments. Again, you can try to remedy this by extracting this information from function bodies (transitively), but that has its own set of challenges in terms of implementation and invalidation.

Second, autocomplete when trying to call methods on parameters doesn’t work well, because the IDE has no information to go on in terms of what methods you expect to be present.

EDIT(2022/10/10): If you’ve written some generic C++ code as well as Rust, you’ve probably run into how less useful autocomplete is inside generic functions compared to monomorphic functions. When arguments with templated types are involved, functionality like Go to Definition, Go to Type Definition, and Find References on method calls do not work reliably.

Inability to have non-determinism at compile time

Some languages are interested in allowing truely arbitrary computation at compile time, including non-deterministic computation. IIUC, Nim falls into this bucket.

However, allowing information to flow from compile-time evaluation to the type system introduces non-determinism in types, which is bad for quickly computing type equality, as caching results of compile-time evaluation becomes unsound.

Of course, non-determinism at compile time has its own downsides generally, and one can argue that it is a bad feature to want.

However, you’ll notice that non-determinism is in some ways central to most statically typed languages today, because the default hash table type generally does not guarantee iteration order over keys for better performance. This means that if your code is using hash tables, you cannot directly reuse it between compile time and run time unless you factor it out to swap out the underlying hash table…

EDIT(2022/10/10): Zig issue 7396 covers an example of how allowing compile-time non-determinism can be powerful in allowing “some unique abilities, like building a borrow checker and lazily creating a global list based on what functions or types get compiled” but it also creates problems with memoizing the results of compile time evaluation. Notice that the suggested fix essentially involves making compile time evaluation semantics diverge from run time evaluation semantics…

Inability to support polymorphic recursion

Some languages support polymorphic recursion, which means that code can be instantiated with successively varying generic types. It is arguably somewhat of an esoteric feature (albeit, see answers to this SO question for some use cases).

This drawback is shared by other languages which use monomorphization as a compilation strategy, such as Rust and C++.

EDIT(2022/10/10): It is not possible to reconcile templates with polymorphic recursion because templates require that all instantiations be type-checked, so you need to prove an infinite number of properties in finite time. Zig allows for compile-time reflection, which means that you can essentially branch on instantiation depth, so you can’t necessarily prove such properties reliably. The other point is, even if you get rid of compile-time reflection, proving an infinite number of properties at once essentially requires building a constraint system to infer what is a higher-order forall constraint from sets of simpler constraints. So now you’ve arrived what closely resembles a system of type classes, but which can only used by your type checker…

Closing thoughts

If you ever see someone advertise a language feature as “everything is an X”, your first reaction should probably be healthy skepticism, rather than delight. Programming languages generally tend to draw distinctions between distinct things for good reasons.

The C++ committee added concepts after decades of pain with templates, and even these do not overcome all the problems mentioned above. I would not be surprised to see Zig add a similar system (likely with its own twist to it) at some point if it keeps growing in usage.