Welcome, everyone, to one of the last talks in the Back to Basics track.
As I like to say in front all these talks, thank you for coming to the Back to Basics track this year...
Hope not to see you in the Back to Basics track next year...!
You get to go to other things. Or, welcome back. Right.
So again, please remember to provide feedback on the website. Rate the talks. Give us feedback for next year.
My name is Arthur O'Dwyer, and I'm here to talk to you about a slightly less basic topic today.
How many of you, by the way, were in my generic lambdas talk, "Lambdas from Scratch", just before lunch? [ https://youtu.be/3jCOwajNch0 ]
Cool. So, welcome back to... sort of a Part Two. Not really.
We're going to talk about type erasure.
This talk has an outline!
We're going to talk about representation, behavior, and something I like to call "affordances."
Which— the term is catching on! I I like that. And I'm going to tell you where I got that term.
And I'm going to show you: what is type erasure? why is it useful?
And then I'm going to build it from the ground up.
We're going to show some different layout strategies for type-erased types. We're going to do some case studies.
I'm going to show you a big screen full of code that I'm probably going to stumble over.
And then we're going to have some questions
So first of all, if you came to this talk based only on the title...
And you said, "Oh, type erasure. I know type erasure from C#. I know type erasure from Java."
Those languages actually use the words — the exact same words, "type erasure" — to talk about something completely different and unrelated from what I'm going to be talking about today.
And I could spend a couple slides explaining what THEY mean by it, but this is a C++ conference, and also I only have an hour.
So if you want the gory details on what THEY mean by "type erasure," see my blog post.
But I'm not gonna talk about those.
In C++, we can motivate this idea of type erasure by asking the question that I asked at the end of my lambdas talk:
How do I write functions that accept lambdas as arguments?
So, the STL way to accept lambdas as arguments...
is to say, I have a member function `for_each_book`, but it's not a function; it's a template.
It takes a type parameter `Func`, and whatever kind of thing you pass to this function `for_each_book`,
I will stamp out— the compiler will stamp out a copy of this template.
And specialize it, instantiate it, for that specific function type.
So if you pass in a lambda of one type, you get an instantiation of `for_each_book` for that specific lambda type.
You pass in a lambda of a different type, you're going to get a different instantiation of `for_each_book`.
This can lead to code bloat. This can lead to lots of very similar copies of the same function.
It also means that you have to define this template in a header file. Right?
Modules may eventually help with this; but, you know, as far as C++ as we know it today, templates go in header files.
And so that can also increase your compile time not to mention the compile time of stamping out all those copies.
So we're looking for a better way.
We're looking for a way to have a concrete call back type — `ConcreteCBType`, here.
This function is not a template.
It takes something of a concrete type.
And I can now move the implementation of `for_each_book` into a different .cpp file.
Compile it separately. I get the benefits of separate compilation now.
I have just a single implementation, but I can still call it with any kind of lambda.
I'm going to show you how to do that.
And that is the magic of type erasure. That is our goal: to get to this slide.
So type erasure essentially is a way of "concretifying" a template.
A template is not a real function, right? It's just a template. It's a textual mechanism for creating functions.
But type erasure makes us have a nice concrete function. I can compile it, get some machine code for it, and I can put that in an object file.
So to contrast these two examples, let's look at C++'s `std::sort`.
`std::sort`, in the algorithm header, that's a function template. It's templated on the comparator type. It can take any kind of comparator.
And it's a template. That means the compiler has to see it. It's in the header file. That's code bloat. That's slow to compile. Although it is very fast (at runtime)!
By contrast, the C standard library provides a sorting function called `qsort`.
How many people here have used `qsort`?
Oh, good. Explain it to your neighbor.
So `qsort` is a concrete function. I'm going to show you its signature on the next slide, from the man pages.
`qsort` can only take one specific function signature, and it's got a lot of void pointers in it.
Now, `qsort` is defined off in libc.o, or libc.so. It can't be inlined.
We're going to pay a performance penalty for it.
But the pro, the upside, is that we don't have to compile it every time we want to use it.
Yet another downside is that it's arguably not as type-safe as we'd like, because of all those void pointers everywhere.
We're trying to get the best of both worlds. We're trying to get something that is type-safe enough to use in C++...
...that we feel comfortable using, that we know we're not going to misuse.
And yet we want to be able to define them out-of-line. And we don't want to pay for template bloat.
So C has the `qsort` function...
And there's also another function you'll find, also in your libc. And that's `qsort_r`.
`qsort_r` is identical to `qsort`, except that the comparison function that you pass in doesn't just take pointers to two elements
and then, you know, cast them back to whatever type they're supposed to be and compare them.
Right. The idea is that with `qsort` you write this comparator yourself and you pass in a function pointer and it does casts internally to compare the two things.
Now, `qsort_r`: the comparison function takes a third argument, which I'm going to be referring to as the "cookie" parameter.
It takes the the two elements and also a little cookie that can parameterize the result of the comparison in some way.
For example, maybe we want to sort our array of books by author...
Maybe we want to sort our array of books by title.
Using the C standard library, I can make calls to `qsort_r`
That sort using this `byprop` comparator — comparison function —
that takes pointers to the two elements to compare, and also takes this cookie that tells which property I want to compare on.
So... Niklaus Wirth...
I think that's how it's pronounced. "Veert."
Americans say "Worth." They call him by value.
It's not my joke.
Wirth, in 1976, he wrote a book called "Algorithms + Data Structures = Programs."
So, in the same way, I could say that...
...if I have a behavior and a representation — an algorithm and a data structure, behavior and representation — equals data type.
What is a data type?
It's a representation (what do the bits look like) and it's a behavior (what do I do with them).
Put those together, we get data type.
So if we think about `qsort_r` in this way...
I'm not going to think of `compar` as a function that incidentally takes some extra data, a `cookie`.
I'm going to flip that around. I'm going to think of it as a data representation, `cookie`...
And that data representation has associated with it a behavior, which is typified by the `compar` function.
That is the behavior. The function defines the behavior, and then this `void*` is pointing to some representation.
Representation and behavior. If I find a way to package those up together, I have type
Also an influence on the way I think about type erasure is Don Norman, who wrote a book called "The Design of Everyday Things."
That was in the 1980s. There was a new version that came out later that I haven't read.
And he says,
"Affordances refer to the potential actions that are possible on an object."
He's talking about physical objects. This is not a programming book. This is a user-interface and real-world-design book.
So we don't— you know—
When we're writing a program, we would often talk about "this function requires this input," right?
"You have to pass this data to this function, so that the function can do what it does."
But that's not how we think in the real world.
In the real world, I don't say "In order to perform opening, I must supply a door."
Right? We see the door first, and then we decide that we are going to open it.
The door AFFORDS the action of opening.
When I see the door, I I know that it supports the action of "opening."
So I say it "affords" that action. That is an "affordance" of a door, a physical door.
So another way to think about `qsort_r` is not to think of that comparison function...
...as an action requiring you to supply a cookie in addition to other things.
(Right? It takes some things, and also a cookie.)
But think about what actions are afforded by the cookie itself — that piece of information, that data.
What can you do with a cookie?
The only action afforded by `cookie` is to pass it to the comparison function.
Right? It affords only one interesting behavior.
So I can take any callable object—
Going back to template-land now. No more C for the rest of this talk.
Hold your applause, please.
Given any callable function object — capital-C `Callable` —
If I have a reference to a `Callable` that affords calling with no arguments and returning an `int`...
Right? I have this object, I don't know anything about it, but I know that that's something I can do WITH it. It affords that action.
I can split it up into its representation and its behavior.
And here's how I'm going to do that.
I'm going to say its representation — the actual bits in memory —
Well, I can just get a pointer to the callable object and take its address. Now I have a pointer to it.
And I don't care about its type. I just care about the bits — the representation — so I'm going to make that a void pointer.
I no longer care about the type of those bits.
Because I'm splitting up my data type into a behavior and a representation. That was the representation part.
Now the behavior part. What does it do when I call it?
First of all, I need to pass in the representation. So `behavior`, when called, takes a representation.
And what is it going to do with that representation? It takes in a representation in the form of a `void*`. The parameter is named `r`.
It casts it back to the original callable type — whatever that type is. It could be a lambda type. It could be a function type. Whatever it is.
It dereferences it, and it calls it using its `operator()`.
Right? `Callable` here is a static type known to this template `foo`.
Whatever type `Callable` was passed in by the user, that's the type we're casting it to here.
And now I can plug those two things back together.
Behavior plus representation.
I pass in `representation` to this function that encapsulates everything about the `behavior` of this callable object.
When I call this, I get the same thing as if I had just called the `Callable` directly using its `operator()`.
I'm going to pause here and ask if there are questions, just in case.
Speak up, please.
[INAUDIBLE FROM AUDIENCE]
What— oh, plus before lambda. Plus before lambda, right.
If you were in my lambda talk [ https://youtu.be/3jCOwajNch0 ]
I mentioned that if I have a lambda, which is a class type — right? a lambda type is a class type — so this is an instance of a class type,
and I'm using unary plus on it...
Unary plus is like unary minus. Minus says negate the thing; plus says don't negate the thing.
But I need a thing, a scalar thing. I need an arithmetic or pointer type.
A lambda is not a pointer type, but it is implicitly convertible to a function pointer.
So putting a little plus in front of the lambda actually indicates— it's an idiomatic way of saying— please give me a function pointer instead.
So we started with an object of type capital-C `Callable`.
So we can't use that object — we can't call its `operator()` — without knowing that it has an `operator()`, right?
We have to know something about its static type. We have to know its type.
When we split it up into its representation and its behavior, we have erased all the inconsequential aspects of that type.
We no longer remember anything about that type's `sizeof`; its `alignof`; whether it's copyable; whether it's trivial;
whether it's trivially copyable; whether you can negate it; or add two of them.
All of that information about a type that we have in C++ is all gone.
All we remember is its representation and its behavior when called.
And those are objects of very simple known types.
In fact, trivial types, right? One is a `void*`; the other is a function pointer.
Our original object's type, `Callable`, no longer appears in these declarations.
So we're now working our way toward type erasure.
But we've got this big mess of C-style void pointers, and things. I want to get rid of that.
But before we do, I want to point out this is not just for calls.
Any affordance can be split this way. If I have a `Negatable` object — that is to say, an object which affords negation — I can split it up in this way.
Let's suppose I have some `Negatable number` here which affords being bitwise-negated; and that operation returns an `int`.
Let's just say that it returns an `int`. I know in real life it might return another `Negatable`, but we're going to ignore that for the present.
We'll come back to that the end of the talk.
We split it up into its representation and its behavior. Its representation is just the bits at that address...
And the behavior when negated can be represented as a function pointer...
where I pass in the bits; cast them back to a `Negatable` object, of that original static type; and use bitwise-not on it.
And then that returns an `int`.
And again I assert that the behavior when negated of my representation is the same thing I get by using that operator on it directly
Right, so this is not just for calls.
Although it is certainly most useful for calls.
You can also have multiple different affordances.
Right? Maybe there's "bitwise negated" and there's also "boolean not." Boolean-not, let's say, has to return a bool; or something convertible to bool.
So I can have my representation and I can have two different behaviors.
One of these function pointers encapsulates and erases the idea of negation, bitwise negation. The other one encapsulates the idea of logical-not...
...by dispatching to the `operator!` associated with this static type, whatever it is. That's my template parameter.
So I have to use the template parameter in constructing this lambda—
right? In saying, "what is the behavior of this lambda." I put this inside my template, let's say.
But now I've erased everything about this type.
The type appears only in the behavior of the lambda, but not in its signature.
So I have two different lambdas here, controlling two different behaviors. I can have as many affordances as I want on a single representation.
So now what I'm going to do is, I'm going to wrap the representation and its behaviors up into a struct.
We're going to start building some C++ stuff on top of this.
I have my raw pointers. I'm going to wrap them up into a `struct TypeErasedNumberRef`.
I'm going to put those representation and behaviors as function pointers into this struct.
And I'm going to give it some member functions. I'm going to give it some overloaded operators.
When you call `operator~` on a `TypeErasedNumberRef`, that's just going to call the function pointer `negate_` on `representation_`.
That's going to return an `int`, which is going to get returned back to the user.
So now what I have is something that can reference any kind of numeric thing out there. Anything that has "negate" and "not."
As long as I set the representation and the behaviors — as long as I initialize those two functions with that behavior.
How do I do that?
Well, I do actually know — I have a recipe for — how to make a `TypeErasedNumberRef` out of any kind of number.
And when we turn that into C++, we should think well, I'm MAKING an object of this type — that's a constructor.
And I'm making it out of anything numeric.
So anything at all — any different type. Well, it's going to be parametrized by the type. It's going to be a template.
So I can write a constructor template that looks something like this.
So this is a template for stamping out constructors of `TypeErasedNumberRef`.
They're all implicit constructors, because I didn't use the `explicit` keyword. Which maybe I should, in this case. I'm not sure.
I take a reference to a `Number`.
My representation is just the address of that `Number` as a void pointer. It points to the bits of whatever that is that the user gave me.
And then I initialize my two function pointers to functions.
What are these functions?
By the way, I could have put the `+` in front of it here. I decided not to. It does implicitly convert, as well.
So this one function—
I'm using lambdas here, rather than named functions. I could use named functions if I wanted to.
But because the behavior of this lambda is pretty much described by what it does, I decided not to.
And also it fits on the slide better if I use lambdas.
All right, so we can use our constructor template now to wrap any kind of number — any template type at all —
into a concrete `TypeErasedNumberRef`. Notice that `TypeErasedNumberRef` itself is not a template.
It's a concrete type that always looks the same.
Its representation in memory is always a `void*` and a couple of function pointers.
Those function pointers can point to functions with very different behavior, but they always look the same. We always call them in the same way.
But they have different behaviors. Isn't this interesting?
At this point— in fact, I won't even go on, I'll just say it: At this point we have something that I would call "type erasure."
And if you're familiar with the `function_ref` proposal, this is very similar to a `function_ref`.
This is just a `NumberRef`. I decided to erase operations that were not function calls, just to show you that it can be done.
But what about ownership? Our `TypeErasedNumberRef`, as indicated by the name, it has reference semantics, right?
We capture the original object's address and then we `reinterpret_cast` that address.
So if the user gave us a reference to a number; we made it into a `TypeErasedNumberRef`; we passed the `TypeErasedNumberRef` around somewhere; we might end up with a dangling reference. That would be bad.
So we would like to see how to deal with lifetime and ownership.
The way that `std::function` does.
When I make a `std::function`... I put a lambda in it... I don't have to keep the original lambda alive.
I can pass that `std::function` around all over the place. You can even copy it.
How does that work?
Destructibility is an affordance. It's a behavior that an object has. Some objects afford destruction; some don't.
Admittedly, in C++ you don't usually run into indestructible objects. They're not very useful.
But they could exist, theoretically. And so, contrariwise, destructibility is an affordance.
All right, so let's start building a `TypeErasedNumber` with value semantics.
So, not reference semantics, but value semantics.
So we no longer REFER to an int or a double. We now capture an actual object of type int, bignum, et cetera, inside ourselves.
We're going to manage that object's lifetime.
In order to manage its lifetime, we are now taking on responsibility for destroying that captured object.
So we need to know how to destroy it. Does it even afford destroying at all?
If it doesn't, then we can't take ownership of it.
So the captured object has a representation, just like before; and it has some affordances, just like before.
But now destructibility is one of those affordances. I need to know— I need to ask the object, "How do you destroy yourself?"
The captured object can also be large.
When we capture an `int`, maybe we can store that inside ourselves, copy it inside ourselves.
But if it's a `BigNum`, some other very large type,
No matter what size we pick for the memory footprint of our `TypeErasedNumber`, the size of that user type might be bigger.
So we can't always store it inside ourself.
We're going to — sometimes, at least — need to allocate heap memory and store it out there. So I'm just going to always do that.
We're going to fall back and punt here. We're going to use the heap.
There are other options for doing small object optimization... but this is already pushing it for a Back to Basics talk. So we're not going to talk about small object optimization.
We're always going to allocate our captured object out there on the heap.
So here's how we might type-erase the affordance of destructibility.
I have my representation. I have a function pointer that takes the representation in. It doesn't return anything, but its side effect is going to be —
—here's the initialization for it in my constructor template—
The initialization is with a lambda that takes in that representation, casts it back to a `Number` (that's the template parameter to the constructor template),
and calls `delete` on that.
Okay? All good?
And then of course we call `new` here.
We heap-allocate an object of that type. We heap-allocate an `int` or a `BigNum` or whatever.
And then in my destructor, I have to manually call that type-erased `delete`.
I have to say — pass in the representation and — "please delete it for me."
Only this lambda's body, only this implementation, understands what it means to "delete." So I have to call that function.
And I have to set it up properly in my constructor template.
For copy, there are many— there are like, three different ways I can think to do copy. This is just the one I picked for these slides.
I make a lambda that takes a representation of a `Number`, casts it back to a `Number`, calls the copy constructor of `Number`, and allocates that object on the heap.
I'm calling that `clone_`, by analogy with Java.
And so this is how I would copy-construct a `TypeErasedNumber`.
I would say, its affordance (HOW you clone things) doesn't change. I'll just copy that function pointer over. That's that last line there.
The line above it is initializing my `void *repr_`, and it's initializing it with the result of calling the `clone_` behavior...
...on the `Number` representation of the right-hand side. Right? Behavior plus representation; put them together.
That uses the [original] type internally to figure out what `void*` to return to me. And then I can just store that in my `repr_`.
So our central strategy here is to list what operations must be afforded by a `Number` in order for `TypeErasedNumber` to do its job.
And special members also count as affordances.
In order to do my job, do I need to copy a number sometimes? If so, that's an affordance. I need to type-erase that.
I need to remember that in my list of affordances.
For each operation, I write it as a lambda in terms of representation, in terms of that pointer to the representation;
and in terms of that type parameter, which is a parameter to the constructor template.
Remember, my `TypeErasedNumber` type itself is not a template. It's a concrete type.
It has a fixed layout. But I have a constructor template.
So I need to have my constructor template do all that work of setting things up in terms of the `Number` type.
So each lambda's behavior depends on that `Number` type, but its signature is fixed.
But if I do everything this way, my footprint is growing, right? For every affordance I need a new function pointer.
You know, at this point I have `clone_`, `delete_`, and then I have my two original things (which were the whole point) of `negate_` and `not_`.
Now I've got 40 bytes in my struct.
It's now ten times the size of a 4-byte `int` that it's erasing.
How can we shrink its memory footprint?
Well, let's go to the diagrams. I love these diagrams.
Here's the stack. That's where our function call-stacks are. Here's where our local variables are, and our parameters.
We have the heap, over here, that we use for `new` and `delete`.
And we have global data. That's your global variables, and your vtables, and things like that.
So here's the structure that we have right now.
I have a representation as a `void*`, and I have a bunch of function pointers explaining the various behaviors— the various affordances that this representation affords me.
And right now I'm sticking it all inside my `TypeErasedNumber` struct, and so it's very big.
Those are very big. They're even bigger than the bignums they're storing.
But I could do something a little bit different.
One thing that's popular is to combine all of our behaviors into a single function, and give it one extra argument.
An enumerator, a discriminator tag, to say, "Which behavior do I want today?"
And then I would just assign numbers to my different behaviors. You know: "To copy, press one. To delete, press two." You know.
So I wrap them all up. And I can still make a lambda to do that. My lambda would have a switch inside it. I'm going to show you some code a little bit later for that, I believe.
In fact, I think it's the next slide. Is it the next slide? It's the next slide!
Notice in the upper right-hand corner there is a Godbolt link where you can see this code and you can run it. [ https://godbolt.org/z/IqpwBU ]
Just to prove that this is not just slide code, but also works. I'm not saying it's the best code ever; but it also doesn't have any typos that I'm aware of.
All right, so here's my `TypeErasedNumber`. It has only two data members. It has a pointer to void and it has a pointer to a function.
Where that function is going to be something with a big switch inside of it.
Over there on the right column, you can see that big function with a switch inside of it.
I didn't actually write it as a lambda. I wrote it as a named function.
I could have written it as a lambda, but I decided to pull it out (also for purposes of the slide) and make it a function template.
Which over here I am instantiating with that specific type `Number` that came in as a parameter to my constructor template.
So this would be a reasonable way to do that.
And then inside here I say: If they're asking for behavior 0, that's cloning. If they're asking for behavior 1, that's negating...
2 is boolean-notting, and 3 is deleting.
Those are the behaviors that you can get out of this function.
And then over here in my overloaded operators,
`operator~` delegates to the function pointer passing 1...
`operator!` delegates passing 2, destroying is number 3, and so on.
So this is just the machinery for how I would put together a complete type-erased type that I could then use.
Using these techniques we've already seen, right? Split up the behavior and representation.
Represent the behavior with a fixed signature, as a function pointer.
Something else I could do is, instead of just having the one behavior, I could leave my behaviors split out...
But I could put them into a structure of behaviors. `struct TE_Behaviors` here...
...is my structure of function pointers. Because those are always the same for any given type `Number` — for any type `T`.
So if I have two instances of my `TypeErasedNumber` that store the same type internally...
They could actually just have pointers into the global data, and point to a global table of behaviors for that particular type.
So it might look something like this.
And I would have a different table— This is the table for `BigNum`. I would have a different table for `int`. And so on.
So that's something I could do.
I could even — if I wanted to make the `TypeErasedNumber` representation even smaller — instead of having two pointers here...
I could actually take this pointer and move it over into what I heap-allocated.
And I could do that. I could put a pointer to the table of behaviors at the front of the thing I allocate.
Oh, now this is interesting. What does this look like?
This looks like a vptr to a vtable. A table of function pointers.
So now we can do something typesafe. This is basically a vptr; this is basically a vtable.
We can actually implement, in C++, type-safe type erasure.
As long as we're willing to use the heap for everything.
Which, as I said, we are, in this course. This class. Whatever this is. Session.
So I make my `struct TEBase` and I give it a bunch of virtual methods.
I give it those same affordances that we had been type-erasing.
What does it mean to clone this thing? to negate this thing? to "not" this thing? What does it mean to destroy this thing?
And then I'm going to make a derived class template.
Not a singular derived class, but a template for stamping out derived classes
Every one of these derived classes is going to derive from `TEBase`.
And it's going to override these various affordances.
It doesn't need to override destruction because that's going to get generated for me by the compiler implicitly. That's pretty cool.
But it needs to explain, "here's how you negate the thing: I'm going to negate my member. Here's how you not the thing: I'm going to not my member."
"And here's how you clone it: I'm going to make another copy of myself."
I'm going to use `make_unique` to do that. Because, as we saw in the smart pointers talk, "don't touch raw pointers with your hands." [ https://youtu.be/xGDLkt-jBJ4 ]
So this code, by design, doesn't use any raw pointers. It doesn't need to. It can be type-safe and leak-safe.
So over here in my actual `TypeErasedNumber` — my `struct TE` —
All I have here is a `unique_ptr`.
And I construct it by allocating a derived class stamped out from my derived class template.
(I've realized I've lost my timer down here, by the way.)
All right. So then we have a copy constructor. And what the copy constructor does is call the clone method, that virtual clone method.
That goes down and uses the information that it has erased.
Right? It has the same signature, but different behavior.
And again here I call the `negate_` and the `not_` method.
So this would be a way to do completely type-safe, completely leak-safe type erasure.
Of course this does have that mandatory heap allocation.
If you were going to use small object optimization— if you were going to implement small object optimization for your type—
you would not do it this way. You would go back to one of those previous slides and start from there instead.
So what can we make with type erasure?
In the standard library we have `std::function`.
Now `std::function` IS a template. But its template parameter has nothing to do with your lambda type — you know, the thing I've been calling capital-N `Number` throughout this.
That's actually just the signature that the function is callable with.
For example, it might say "I take two `ints` and return a `double`." That's just a very convenient way of specifying that signature that you're erasing.
It has no actual relation to a function type at all
`std::any` wraps anything that affords copying and destroying. That came in in C++17.
That's interesting. We're going to talk more about `std::any`.
`function_ref` and `unique_function` are both being proposed for the next version of C++ after C++20.
I refer to that as "C++2b," because I really hope it's not '23. I think we need more time.
But `function_ref` wraps anything that affords calling. It's very similar to our `TypeErasedNumberRef` that we started the lecture with.
`unique_function` is like `function`, but it is move-only.
It doesn't need for that type that it is wrapping to afford copyability, to afford copying.
It just needs to be destroyable, and it needs to be callable.
It doesn't even technically need to be movable. It can actually be immobile, for technical reasons.
`std::any` is a little funny one though, right? Because I said it wraps anything that affords copying and destroying...
But no operation! There's no calling, or negating, or anything. How do I get a value out of `std::any`?
There's nothing I can do with it but make another copy of it; but I've already erased all the type information about it. That's really weird. What do I use that for?
Well, `std::any` actually does support one more affordance,
and that is the "go fish" affordance.
So if I have a `std::any` that has an `int` inside itself—
So here, on this first line, I'm calling the constructor template of `std::any`, instantiated `[with T=int]`.
And it's figuring out how to copy an `int`, and how to destroy an `int`, and it's remembering all that in its table of function pointers inside the `std::any` object.
And it's also heap-allocating a copy of `42`
(modulo small object optimization).
So now I've got an `any` that has an `int` in it. But I don't know that it has an `int`, right? In the static type there's nothing that says `int`.
But what I can do is, I can ask it: "Do you have any `int`s?"
And if it does, it will say: "Yes, and here is the `int`."
I can put a `double` in it, and I can ask it: "Do you have any `double`s?" And it says: "Yes, here's my `double`."
Now I can put a `double` in it, and I can ask "Do you have any `ints`?" And it'll say: "Go fish!"
And it will throw `std::bad_any_cast`, rather than give me back a value.
So this itself is an affordance.
`std::any` can only store objects whose static type is able to tell you whether it is of that type or not.
Now, in C++, every object knows what type it is. So this is something that is true of all types.
They all know what type they are. Of course. That's their type. Right?
So this is, in a sense, a sort of vacuous or trivial affordance. Every type supports this operation.
But it is important because we're going to need to type-erase it. We're going to need it to be in our table of affordances that is initialized in the constructor.
We need to remember, when someone asks me for an `int`, if I am an `int`, I say "Here I am."
If someone asked me for something else, I'm going to say: "No, that's not me. Go fish."
So here's how we might implement that.
Here's my `std::any`.
So here's my `struct any` over here. Notice that it's not a template.
It just has one member, which is a `unique_ptr`.
Here's my `AnyBase`.
It has the ability to copy itself, and it has this function `addr()` that can just return me the actual data. Again, it's just its representation. I don't need any more than that.
My derived class, here, overrides that to return the address of the `T` stored inside itself.
And then I have this free function `any_cast`.
Now, this is a template, right?
The user is going to provide what type they think I have, and I'm going to tell them if they're right or not.
So one way that I could do this is, I could use `dynamic_cast`.
I have a pointer to an `AnyBase`. I know I have some kind of `AnyBase`.
I'm going to try `dynamic_cast`ing it to an `AnyDerived` of that type the user gave me.
Do I actually have a derived object of type `AnyDerived`?
If I do, then it has an `int` inside itself, so I can ask it for the address of that `int`, cast it back to an `int`, dereference it, and return that `int`.
If it's anything else, the `dynamic_cast` will fail — I'll get null. `d` will be null. I'll skip over that `return` and then I can throw `std::bad_any_cast` myself.
This is one way you COULD implement `any_cast`.
I am not saying this is how your standard library implements it.
Another way you could implement it— this is different, maybe worse—
is I could give another affordance into my table of affordances here.
I could say, I'm going to remember how to get the `type_info`, the `typeid`, associated with the erased type.
and I'm going to override that, in my derived class, to return the `typeid` of this static type `T` that I was instantiated with.
And in my constructor I'm going to construct an `AnyD`.
And down here in `any_cast` I'm going to ask that derived object, that heap-allocated object, "What is your `id()`?"
That's going to go over here. It's going to get me the `typeid` of, let's say, `int`.
I'm going to compare that with the `typeid` of whatever the user gave me — let's say `double` —
and, well, if they're the same `typeid`, then I'm going to return the same thing I returned before. Get the address of the object, cast it to an `int*`, return the `int`.
And if not, I'm going to throw `std::bad_any_cast`.
So this is another way you could implement `any_cast`. I'm not saying this is the way your standard library does it, but it is a way that works.
And just for fun...
There's a non-standard `any_cast` here.
This is something I just sort of thought up a while back.
Nobody does it this way because it would not be standard-conforming to do it this way.
But let's suppose that I wanted `any_cast` to be able to ask, "Do you contain a `Fruit`?"
And if the `any` contained an `Apple`, it would say: "Yes, and here it is."
Here's a reference to the `Fruit` part of that `Apple`.
`std::any_cast` doesn't do that.
`std::any` does not put that particular behavior in its list of affordances that it provides to its users.
But you could implement that. You'd have to be a little sneaky... What I'm doing here is, I'm throwing a pointer.
If I throw a pointer to an `Apple`, I can catch it as a pointer to a `Fruit`.
So, okay, I'll do that.
I'll use throw and catch, and use some more of that runtime type information to figure out what I've got.
So, just for fun.
What else can we make with type erasure?
Well, another thing I haven't mentioned yet... besides `std::function`, `function_ref`, and `unique_function`...
I could also mention that the low-latency study group, SG14, has in their GitHub repo an `inplace_function`.
`inplace_function` is parametrized not just by a signature, like all these other function types,
but also by a capacity.
You can say, I only want you to store things that fit inside this much capacity. And I want you to store them inside yourself, in your memory footprint.
Never do a heap allocation, ever.
If you try to put something too big into an `inplace_function`, you can get a `static_assert`.
Because it knows exactly how big an object it can put inside itself.
So you might be thinking, "Okay, so, even though he showed us this stuff with `operator~` and `operator!`..."
"Really it sounds like variations on `std::function` are really the killer app for type erasure."
And there is a reason for that.
When we use type erasure, we are erasing everything about its type except for certain behaviors.
Inside a type-erased type, we remember two things: the representation and the behavior.
But our user — the user of `std::function` — doesn't even care about the type's representation. They just care about its behavior.
So each behavior has a fixed signature. Well, a behavior, with a signature— That's practically the definition of `std::function`, right?
It type-erases some sort of behavior with a fixed signature.
So it's no surprise that variations on that are the most common use for type erasure.
This would also be a good time to mention that `std::function` has a lot of problems.
Problems that now can't be fixed because of ABI-compatibility concerns.
You know, it relies on runtime type information. It has issues with const-correctness. It's big and slow and does heap allocation.
And so part of why I enjoy talking about this kind of stuff is that I think a lot of people will find that at every employer you go to, you will implement `unique_function`.
Or you will implement `function_ref` in your codebase.
If your codebase doesn't have one of these — if you're passing around `const std::function&` to a lot of places —
you might consider going home and implementing some type erasure!
That's not going to change. Even if we get `unique_function`, `function_ref`, and `inplace_function` into the standard... or we get some generic kind of type-erasure mechanism as a library feature...
I think people are still going to end up implementing this themselves.
Another thing we can make with type erasure is...
If you went to my smart pointer talk [ https://youtu.be/xGDLkt-jBJ4 ]
you saw that the deleter associated with the controlled object of a `shared_ptr` is actually stored on the heap, in that control block.
So I can have two different `shared_ptr` objects — I can have `si` and `sj` —
Here I'm using the aliasing constructor to construct `si`. And for `sj` I'm just making an `int` on the heap.
`si`'s deleter, when I let `si` go out of scope at that curly brace, it's actually going to destroy the `Widget` that is controlled by the control block.
`sj`, when it goes out of scope, it's going to destroy an `int`.
Yet `si` and `sj` have the same static type. They're both `shared_ptr`.
So, in a sense, I have done type erasure here.
I have two things of the same concrete type; they have the same static type; their type is indistinguishable; but their behaviors are different.
And again, there's a reason for that; and that is that a deleter is just something where you pass it a pointer and it does some side effect and it returns `void`.
Anything that fits that signature I can use that as a deleter for a `shared_ptr`.
So that's awfully close, again, to `std::function`, right?
It's a single, sort of "unary," behavior, with a fixed signature.
What about non-unary behaviors?
So our `TypeErasedNumber`... I specifically picked all these unary operators to show off, right?
`operator()` is a unary postfix operator. `-` and `~` and `!`, those are unary prefix operators.
What about division?
If I have a `TypeErasedNumber one` storing an `int` and a `TypeErasedNumber two` storing a `double`,
can I somehow overload the division operator for `TypeErasedNumber` so that I can get a `TypeErasedNumber` out?
That can give me, you know, one-half? Like, `1` divided by `2.0`?
Can we do that?
Sadly, no, not easily. Probably not even difficultly.
This is the problem known as "multiple dispatch" or "open multimethods."
The idea that we would have to ask both the left-hand side and the right-hand side if they had an opinion on how division should be done.
C++ gets around this statically with rules such as integer promotion, arithmetic promotions...
where it will promote the one to a `double`, but it only knows that because the other side is a `double`.
There's a big table of all the possible permutations of things.
If I try to throw a `BigNum` in here, I'd have issues.
Essentially, this is very sad, but multiple dispatch is a very hard problem. It's not a problem that has a solution at the moment in C++.
For more on multiple dispatch, I highly recommend— Eli Bendersky has a series of blogs on multiple dispatch, and on what's known as the "Expression Problem."
So I recommend reading those. [ https://eli.thegreenplace.net/tag/multiple-dispatch ]
But if you're going to ask me for advice on how to do this, I'm going to tell you, "Can't be done (in the general case)."
Things to take away from this talk. Now that you've seen slides and slides full of code, and you're like, "What am I here for?"
The things I think you should take out of this room are...
Number one, what is type erasure?
`std::function` and `std::any` use type erasure.
Right? If someone says "What's type erasure?" then you say, "Oh, it's like `std::function`." That's a good answer.
That's a good Back to Basics result. "It's like `std::function`."
"Or `std::any`." Then you can show that you know C++17. So that's an even better answer.
Type erasure, what does it let us do? It lets us pass arbitrary types, arbitrary lambdas, across ABI boundaries.
It gives us the flexibility of templates, with the speed of separate compilation.
I can compile my actual algorithm just once. I don't have to recompile that same algorithm over and over for every different template parameter type.
The other thing I want you to take away from this...
Even if you didn't get all that code... I saw people taking pictures — Good for you. It's not going to come out. Wait for the video.
I want you to take away that type erasure is not too hard to write by yourself.
There are many different ways that you can do it. I showed a whole bunch. I showed three different ways to write `any_cast`.
But they all follow the same pattern.
And that is: List your affordances. What does this type afford? What does it need to afford, for me to be able to use it in my `TypeErasedNumber` or whatever I'm writing?
List your affordances. That includes special members. Copyability, destructibility.
Make your vtable. Make it manually with a bunch of function pointers. Do that type safe method. Whatever you want to do.
Initialize each behavior in a constructor template — using a bunch of lambdas. Using named functions if you want. Using a single named function with a big switch. But initialize those behaviors.
And remember the copyability and destructibility are affordances, just like any other operation on a type.
And that means you may not need them at all. And if you do need them, you're going to have to type-erase them. They're going to go in your list of affordances.
And with that...
We have about thirteen minutes for questions, because I thought there might be some.
So there are mics here and here.
And otherwise, thank you for coming.
[QUESTIONER] You mentioned that the one function approach is pretty popular these days...
[QUESTIONER] ...and then you moved on to talk about other approaches.
I'm just curious what you think the pros and cons are that approach? Does it have merit? Is it something we should take a closer look at?
Well, one reason I moved on is that I wanted to talk about the type-safe type erasure.
Which is the most naïve version.
When I've taught type erasure — for example, if you took my weekend class, I start with this and I go the other direction. I show the optimizations.
Here I started with `qsort_r` and I built up in that direction.
So, let's see, what was our problem with this...
Well, one problem with this is that if you look at the code that it generates,
we have the function that has the big table of behaviors, and it has a switch every time.
So just like the phone system analogy, right? You go dial the phone, and you have to sit through, "Oh, press 1 for this and 2 for this and..."
You're like, you know, "Oh, come on, get to the one I want!" Right? The same thing happens here.
It might be a little bit slower than if I just had a function pointer that I could just call and it would just do the thing I want.
Right? I have to do a switch. That's a little bit of extra indirection.
I get the same indirection if I go to the vtable approach.
Because then I have to go, in this case, follow the pointer; follow the pointer; index into the table; finally I have a function pointer I can use.
So if we can reduce indirection that can help.
For things like `function_ref`,
where it only has a single behavior, and I can just put that function pointer right there in the class — that can be extremely fast.
I don't have to do any of this. There's no trade-off for `function_ref`. It just has one behavior.
But for this, where I had a whole table of behaviors, I have to figure out how to do that lookup in a way that might be fast.
Of course, you know, it's all fast, right?
There is no zero-cost abstraction, but all of these costs are relatively small based on the benefit that they give you.
[QUESTIONER] Thanks for the talk.
[QUESTIONER] Quick question about slide 30. Yeah, so `negate_()` returns integer. [ARTHUR] Yes. [QUESTIONER] Should it be returning `Number`?
[ARTHUR] `negate_` cannot return capital-N `Number`,
because up here I do not know what type capital-N `Number` is. I can't put it in the signature.
I also can't even put it down here, because again down here I don't know what `Number`— well, down here I do know what `Number` is; but it might not be covariant.
It might not match what the base class says.
That relates to the multiple dispatch problem.
One thing I could do here: I could take the `std::any` approach. I could say `negate_` actually— uh, here. So, `operator~` on a `TE`. I said it returns an `int`...
Which is nice because then the user can go use that `int` They can `printf` it, or whatever. I could say `operator~` returns a `TE`.
But then, how do you get the result out of the `TE`, right?
You need at some point to be able to get it out. And you can do that either by providing methods like I have here, where they return a concrete type,
or by using the go-fish method of `any_cast`.
Saying, "I hope you have an `int` for me now," and then going and getting it.
But if they really had a `double` you wouldn't be able to get it out. So.
[QUESTIONER] Thank you.
Any other questions?
We've still got ten minutes.
All right. Thank you for coming. [APPLAUSE]