Where does the term witness table come from?

Development Compiler
1

Where does the term witness table come from? What are the witnesses that are being recorded in the table? I'm not familiar with this term and haven't found much use of it online. The few references I've found to it in a non-Swift context are in relation to pattern-matching algorithms.

2 Likes
2

If you're asking about what it contains, you may want to check out this WWDC2016: Understanding Swift Performance - WWDC16 - Videos - Apple Developer. It should still be largely relevant and I find it educational.

tl;dw, there are Protocol Witness Table that stores protocol requirements, and Value Witness Table that stores common instance functionality like initializing, deinitializing, etc.

If you're asking about the history of the naming, :woman_shrugging:.

1 Like
3

Thanks for replying so quickly :slight_smile:

Yeah, I'm asking specifically about the history of the name. Everyone seems to use it like it's this well known term of art but apart from its use in Swift, I can barely find it being used at all.

4

Method implementations which satisfy a protocol conformance are said to “witness” that conformance.

The mental image is that someone is asking, “Why should I believe this type conforms to that protocol?”

So you trot out a line of witnesses to provide evidence, one requirement at a time.

10 Likes
5

There’s an academic paper that coined the term… I believe @jrose linked to it at some point.

6

That’d be @John_McCall, I’m afraid.

7

I think it borrows from Haskell's terminology. Search for type witnesses in Haskell for a similar concept.

8

Swift and Haskell both borrow this term from a common source, constructive logic, where proof terms serve as witnesses for their propositions and, in particular, where you prove an existential proposition ∃x:T . P(x) by producing an x which satisfies P and thus serves as a witness to the truth that such an x does indeed exist.

You can think of a protocol requirement as the proposition "there exists a declaration which satisfies this", for which the only possible constructive proof is a witness: a concrete declaration that satisfies it. Value witnesses serve the same purpose for the more basic propositions "values of this type can be copied", "...moved", "...destroyed", etc.; again, the only possible constructive proof is a function which does the operation.

I've been amused over the years by the number of people who assume I just made the term up.

54 Likes
9

Thanks everyone for all the responses and thanks especially to @John_McCall for clarifying things. It's all very clear now.

10

Do you think an ordinary programmer, let's say middle level, should have a strong knowledge of this?

11

If I were interviewing someone about this topic as a mid level engineer for the team I'm on (Swift Standard Library) I would not find it notable if they were unfamiliar with the exact details of how Swift implements dynamic dispatch.

I would probably expect them to understand how dynamic and static dispatch differ in semantics and performance, ideally would like to see them discuss inlining, bonus points for discussing devirtualization.

Also if they didn't already know when Swift uses different dispatch strategies they would need to pick that up fairly promptly on the job in order to be successful (e.g. the dispatch differences between a protocol requirement, a protocol extension, and a protocol customization point are very relevant).

For a senior candidate it would depend on their background, but if I were discussing this topic with them I'd probably expect them to be able to discuss more specifics of how method dispatch works in their primary language (e.g. if they have a long C++ history I wouldn't necessarily expect them to know witness tables, but I would expect a competent discussion of vtables, and we could iterate from there to derive how witness tables work).

YMMV on other projects though, the standard library is obviously a somewhat unusual one, with correspondingly slightly unusual needs in candidates (and this isn't a topic I actually ask about in practice, this is just "if I did")

9 Likes
12

wtable = vtable + 1
vwtable = wtable + 1

You heard it here first, the next dispatch mechanism in Swift will be called wwtable.

17 Likes
13

From what source is one supposed to learn these things?

14

agree, but i would consider this a basic concept of the language, it’s not really an implementation detail…

admittedly as a community, we are not good at teaching this (or async/await for that matter). the only advice i can really give is to learn by doing (implementing libraries, building full-stack swift applications, etc.). it’s not really something you pick up overnight. a good place to start though would be to learn about protocol types (some people call them 'existentials') and how they are different from generic and concrete types.

2 Likes
15

Which things? If you’re referring to:

these are all very well-studied concepts in language design and implementation. There are a variety of ways a candidate could come across such knowledge, including prior job experience, participating in OSS, reading academic papers, formal education, and peer knowledge transfer.

16

Sounds like a bug waiting to happen.

1 Like
17

This is a perfect example of what a big gap is between knowing and "knowing" existentials (or any other concept). I do Swift daily since literally day one it was introduced. And yes it happened that I came across static and dynamic dispatch terms and was curious about it. This happened maybe even before Swift. I also can recall I read somewhere that Swift has (od had?) also something in between static and dynamic dispatch but was unable to look it up when I wanted to. To this day I don't exactly know how much more expensive can dynamic dispatch be. The referred protocol types has zero information about semantics and performance, yet one think they understand how are they supposed to work. Until they hit PATs and the learning process naturally continues and potentially can lead to terms like static and dynamic dispatch...

Now, projects I've worked on so far haven't required to trade readability / design for performance. And my rule of thumb is to not to do any premature optimizations. It is rather common if not working on libraries. Not speaking about that most optimization tools are underscored. This slows down my learning curve. I'm picking up knowledge rather slowly if not applying in real world. And god I'm so forgetting things I don't use. I would have hard times to write something clean in C / ObjC. My point is, that I would love to have an easy access to more in-depth knowledge about Swift and beyond (computer science concepts directly related to Swift). One that I could browse and return back to anytime. The canon.

Sorry for the off-topic. Sometimes it is just frustrating - hard way isn't the best way.

9 Likes