Compiling Swift generics, Part I

Way back in 2016 I wrote a couple of (now mostly outdated) blog posts talking about how types and declarations are represented in the compiler, and at the time I promised a third installment which would discuss generics. A few of you have asked me about this over the years...

Well, I finally got around to starting a write up about how generics work last year, and I think I its finally in good enough shape that I can release the first part of what is going to be a three part series. So here it is:

The target audience is Swift compiler developers: if you've previously encountered GenericSignatures, GenericEnvironments, SubstitutionMaps and ProtocolConformances and found them slightly mysterious, this is definitely for you. You might also want to take a look if you're interested in programming language design or type systems in general.

(This won't actually teach you how to write generic code though! That's what The Swift Programming Language is for, I'm not trying to compete with that.)

There was a bit of scope creep. The first half of Part I begins with a big-picture overview of the key ideas behind Swift generics, and then goes on to talk about foundational material that's important to understanding the Swift compiler in general: the compilation pipeline, module system, request evaluator, types, and declarations. The second half of Part I actually dives into the details of the generics implementation in earnest; starting with the AST for generic declarations, and then going on to talk about generic signatures, substitution maps, conformances, and generic environments.

The still unfinished Part II will explain type resolution, building generic signatures, extensions and conditional conformances, conformance paths, opaque return types and existential types. Part III will talk about how the requirement machine implements generic signature queries and requirement minimization. The work-in-progress material is in the source but it needs a lot of work and it's conditionally compiled out of the PDF I'm releasing for now.

Enjoy!

111 Likes

I got around to reading this last night and I must say this is a fantastic resource for anybody working in the compiler, but also those who are just curious about how Swift generics work. It's very well written and goes over and teaches terms that I've seen before but haven't fully grasped (like what the heck is an unbound dependent member type).

Thanks!

18 Likes

I've definitely added this to my reading list. I've only done a cursory browse through it so far but it is wonderfully written and approachable. Thanks for what must have been (and still is) a huge undertaking!

Will there be a print version when it's completed? :slight_smile:

10 Likes

Adding my preliminary praise. The very first paragraph of chapter 1

Swift generics were designed with four primary goals in mind:

  1. Generic definitions should be independently type checked, without knowledge of
    all possible concrete type substitutions that they are invoked with.
  2. Shared libraries that export generic definitions should be able to evolve resiliently
    without requiring recompilation of clients.
  3. Layouts of generic types should be determined by their concrete substitutions, with
    fields of generic parameter type stored inline.
  4. Abstraction over concrete types with generic parameters should only impose a
    cost across module boundaries, or in other situations where type information is
    not available at compile time.

already states something more clearly than I've seen it stated before; Swift's goals are not always the same as similar languages'. I look forward to reading this even as someone who knows a lot of it already, but I also look forward to having a true place to point people who want to learn more about Swift and generics design and generics implementation. Bravo, Slava!

EDIT: Are you accepting issues/PRs? For typos and unclear phrasing and such.

9 Likes

Oh wow that's a whole book. Looks like it was written using some LaTEX. I'll add it to my reading list. Well done Slava.

Yeah, of course! Filing issues is probably overkill but feel free to either send me typos as you find them or open a PR.

2 Likes

I have read all of the published part 1.

Studying compiler internals is my hobby.
I'm glad to get an overview of a particularly difficult part from the book.

I am building a library that does a bit of semantic resolution on AST from SwiftSyntax,
and I have been struggling with some parts of the design.
I found the contents of this book very helpful.

I am looking forward to part 2.

6 Likes