https://typesanitizer.com/blog/zig-generics.html
*
* About
* Blog (RSS)
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(x: T, y: MyGenericStruct)
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:
* Zig's language for metaprogramming is approximately a subset of
Zig. Flexible operations like matching on types and looping over
fields are easily doable with constructs that are similar to (or
the same as) ordinary Zig constructs.
* C++ template metaprogramming is somewhat notorious for having an
arcane set of rules which are hard to understand. Flexibility is
possible, but with a high cost in terms of code complexity.
* Circle adds a more C++-like metaprogramming language on top of
C++17, to support imperative metaprogramming.
* Terra is a systems programming language like C and C++ that
allows metaprogramming in Lua.
* D also allows metaprogramming in D itself. There are various
talks by Andrei Alexandrescu which show the powerful
metaprogramming capabilities of D.
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.
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.
C++ template errors are somewhat notorious for this, having known to
make many grown adults weep.
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.
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 past of least resistance, which means just write your code,
write some tests for instantiations you expect, check that work,
and call it done.
* The path of being a good library author, which is to do the above
and also write dedicated type errors for certain mistakes and
write negative tests for instantiations that should fail.
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:
* The type-checker accumulates facts about constraints about
unknown types, and can solve for unknown types in terms of the
known types and constraints.
* The type-checker understands how to derive constraints from one
another, and can synthesize complex chains of derivations without
explicit hand-holding.
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 read 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.
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).
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.
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...
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++.
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.