- But I'll just give you the background
as to how this talk came about.
Jon Kalb asked me to give a talk
and I said I didn't want to
and so he said, okay, we'll
expect it next Thursday.
So I submitted a talk and the
program committee rejected it,
which was fine, it' a lousy talk.
But then there was a
gap, somebody canceled,
so I was asked to give this talk
that was rejected, that
I didn't wanna give.
So I'm honor, obliged
to give a bad talk now
and I intend to deliver.
Last chance guys.
Okay, you asked for it.
Let me just ask one question.
What's the difference
between a mathematical proof
and an integer?
It turns out there's no difference at all.
We'll come back to that later.
That's warning number two. (laughs)
(audience laughs) Okay
so what we're gonna do
is talk a little bit about typelists.
They're very old
fashioned, but lots of fun.
They kept us highly amused in
the late '90s and early 2000s
and we wrote typelist meta-algorithms.
And the person who is
most guilty of doing this
is Andrei Alexandrescu
and they turned out to be quite useful.
It's nice to be able to calculate things
that compile time about types.
We have many more
sophisticated ways of doing things now.
We have more language features,
especially variadic templates
really help us to do these
compile time type calculations.
But we have all these
algorithms lying around
that do interesting things with
types, like partition types
or sort them or permute them
or get rid of duplicates,
or, you know, whatever.
And so instead of rewriting them all,
why don't we just leverage them.
And to do this, we're going
to use my third, fourth, fifth
second favorite feature in
modern C++ template typedefs.
I wanna use the templated usings
to do all the work for me.
Using is wonderful.
I mean people underappreciate using.
I know about underappreciation
and so using and I get along well,
'cause we have a lot in common.
But we're very useful, we work very hard,
and we're especially good
at cleaning up syntax.
If anybody's used an enable_if
with a long string of conditions
on it to do some SFINAE...
By the way, I used to
pronounce that S FINAE,
and David Vandevoorde
who came up with the term
emailed me an MP3 (laughs) of
him pronouncing it correctly.
(audience laughs)
I like to be taken down a peg, but anyway.
So basically we're gonna conclude
that all sequences are orthogonal,
whether they're types or
values or templates or anything
and everything is the same
and the only thing that is different
in the universe is process.
At least that my conclusion.
So what's a typelist?
How many people have actually
programmed with typelists?
Oh, that's nice.
Okay, yeah they're traditional,
but we haven't been
using 'em since C++ 11,
but we have all this old typelist code.
So a typelist is not really a list,
it's a deeply recursive type definition.
And it's pretty simple.
Typelist is a type followed by typelist.
And we have a null
typelist which is just some
selected empty class.
And course Andrei Alexandrescu
is mostly responsible
for wasting my time
throughout the early 2000s.
What can you do with typelists?
Well you usually do a recursive functional
calculation on a typelist
by doing recursive
template specialization.
And early typelists were hard to work with
'cause compilers were
not expecting to be asked
to do recursive template specialization.
And if you look at the
2003 standard in annex B...
I don't know why it's called annex B,
why not appendix B?
But anyway, in the annex B,
it sounds like a bad horror movie,
you will find minima, maxima
and where annex B actually says
the compiler should be prepared to handle
a depth of temple instantiation
recursion of length 17.
(audience laughs)
(laughs)
So I asked Herb, 17? (laughs)
Herb Sutter, and he said, oh
it's the most random number
we could think of.
(audience laughs)
So most compilers could handle
about 60 or 62 at the time,
then they die horribly.
Nowadays compilers regularly can recurs
couple thousand times
or until resource exhaustion or something.
But let's look at our
first typelist algorithm.
Very simple, how do you
know how long a typelist is?
Well the length of the typelist is one
plus the length of the tail.
That's easy enough.
When we start recursion, when
we reach a null typelist.
So if I ask the length of typelist
it'll recursively do
template specialization
until I reach this complete specialization
of a terminate recursion,
and I will recurs out,
adding one each time,
to the length of the typelist.
So this is pretty simple.
How do you make a typelist?
Don't ask.
It was really horrible in traditional C++.
Now that we have variadic
templates it's a whole lot easier.
But I'm still using
what's know as a first
rest implementation.
I think that term comes from
Scott Myers, I'm not sure,
but it's a very standard way
of doing template meta-programming.
It's been subsumed or augmented at least
by pattern matching and other things,
but it's still very handy.
A first rest algorithm simply says,
do something to the first element,
and then do the same thing to the rest
and now you're done.
So it's a very, kind of
straighforward way of doing something.
So that's what we're doing
here making typelists.
I'm not going to bore you by going on
into a lotta detail,
but this is a very standard pattern.
We have a primary template that's declared
but not defined.
We have no use of the definition
but we need to define something
that we can specialize.
And now I'm gonna use my second
or third favorite feature
in modern C++, a templated using,
just to make a convenient name
for this thing I'm doing.
So MakeTypelist is a synonym
for calling MakeTypelist
and then extracting the types,
so I don't have to write that ever again.
And then here's the termination condition.
I terminate when I have a null_typelist.
And the rest part is,
I create a typelist by
taking a head and prepending
that to a typelist
created from the tail.
So this is standard recursive
first, last manipulation.
But obviously,
most people have better
things to do than this.
Not me.
So one of the things we
used to do is create pretty
attractive algorithms for typelist.
Like here's a partition
that takes a typelist,
takes a predicate that asks a question
about a type, yes or no,
so this is like a type trait
and we could just make
it typelist of some sort,
and then we can partition it.
I'm gonna call Partition,
I'm gonna pass this type,
I'm gonna pass this predicate
and this is gonna return
a partitioned sequence of types.
What am I partitioning on?
Is it a pod?
And so, string is obviously
not gonna be in front of double
so string will be over here or something.
And this will partition them
according to the predicate
and return the partitioned
sequence of types.
This partition actually
would also tell you
where the partition
point was in the types.
And this was very useful for
generating conference talks.
(audience laughs)
But on occasion, you might
actually wanna do something.
And I wrote this code about
16 or 17 years ago.
So it's probably not very high quality,
'cause I was only a high
school student at the time.
(audience laughs)
All right, just kidding.
(audience laughs)
So I'm not gonna defend the code,
but I will say that it
does indeed appear to work.
The code is all available.
I'll send you to a website
to pick up the code.
So what about today, modern typelists?
Modern typelists are much easier,
we just have a sequence of types.
And this is a very common thing to have.
We occasionally will use
the variable as it is
or we may actually unwrap
the types into a pack
so we can do something
with the individual types.
And we can partition a type sequence,
but why bother,
because we can already
partition the typelist.
So why do extra work?
So what we can do is,
let's first see how we can
convert a type sequence into a typelist.
Well this is pretty easy to
do with pattern expansion.
So type sequence to typelist.
I can make the type,
I just call make_typelist with the types.
That was pretty easy and I'm done.
And then of course when you do using
we don't wanna say TS_2_TL
we wanna say type_sequence_2_typelist.
And so this is just a
somewhat syntactic improvement on this.
What about typelist to type sequence?
I wanna go back the other way too.
So, here's my primary template.
I'm gonna use the first
rest again on this,
probably due to lack of imagination.
So here's my primary template.
Here's my convenience templated using
typelist to type sequence is now a synonym
for the specialization of this template
plus getting rid of this
annoying dependent type name.
Termination condition,
if have a null typelist,
the type sequence is
correspondingly empty.
And then here's my usual case.
And there's nothing
interesting here except,
I don't know why nobody else does this.
I feel like I'm doing
something that maybe illegal
in some parts of the
Midwest, I'm not sure.
I know, that was unnecessary wasn't it?
(audience laughs)
I get even worse.
A lotta times we have to take a type
that contains a parameter pack
of interest and unwrap it.
So one way to do that is
you pass it to a function
and let template argument deduction
extract the parameter
pack for you and so on.
Another way to do that is
just to have primary template.
Here I've nested it inside
my TL_2_TS template.
I have a primary template
that takes some sort of type.
And then I have a specialization
that will do the unwrapping for me
and this tends to be
pretty convenient as well.
And of course, if you
wanna unwrap five packs,
you can have a quintupley
nested class template
inside your class template,
thereby earning yourself a pink slip.
Okay, now we can go from
typelists to type sequence
and type sequences to typelists.
So now we can do something.
Suppose we have a set intersection
algorithm on typelists.
It does exist.
It's in the code that goes with this talk.
It's probably correct.
I take two typelists, I
find there intersection
and create a typelist that
contains that intersection.
But I'd like to do that
also with type sequences.
So what I'm gonna do is
create a set intersection
for type sequences that
let's me call it like this.
And of course, this is
a compile time call.
So I specialize set intersection with two
type sequences, our modern
variadic typename pack sequences
and it computes the
intersection and there we are.
So how does it work?
It's easy, next.
No, okay.
I once gave a talk to a bunch of
actual human beings at our town hall,
'cause I had written
a website for the town
and I put up a slide
like this at one point
and asked if there were any questions?
(audience laughs)
And there weren't, I don't know why.
(audience laughs)
Does anybody have any...
Nevermind I won't ask
any personal questions?
Do you still talk to people?
Because we can get rather involved.
So if you've been looking
at this long enough,
this is kind of like,
you know how when mathematicians
think something's obvious
they say by inspection?
By inspection, this solves the problem.
Set intersection for type
sequences, what are we gonna do?
We're gonna turn our
sequences into typelists,
send them to set
intersection, get the result,
and convert it back to a type sequence.
That's all.
It's just a matter of
translation between formats.
It's like any other sort of
format translation you might do.
The nice thing is that we can
leverage the set intersection
and we don't have to do any work
and it does produce a correct result.
It's as correct as the original
set intersection algorithm was.
And we could use it like this.
We have a couple of type sequences,
we invoke our specialized
set_intersection_ts with it
and we'll get back a type sequence.
Well that's not too interesting.
Yep.
(audience member talking
in the background)
In this particular implementation no.
I tried to be STL like as possible.
I was being very pretentious for while
back there in the early 2000s
where I was gonna implement
the STL at compile time.
Didn't quite work out.
But in this, I believe
the set intersection...
That's an easy question
to answer, I don't know.
I think it does
remove, maybe.
I'll have to look at the algorithm again.
(audience member talking
in the background)
Yeah, there's an
implementation of unique too
that you could use to
facilitate this or not.
But the unique is STL unique,
so it only gets rid of
adjacent, equal types.
But there's a sort, so
you can sort the types
and then do...
(audience laughs)
This is the period of time in my life
where I almost went out of business,
because I was spending
all my time sorting types
instead of doing useful work.
Well, as always, we looked
at Andrei Alexandrescu
and we wanted to do something clever
and so one of the things he did
is had a nice facility
in his modern C++ design
for making an integer look like a type.
All you do is you,
he arrived at somewhat modernized
version of index to type.
It takes, isn't this nice, I can say auto,
I cannot commit to anything.
But I wanna commit a little bit
so I'm gonna make sure
that whatever type this is,
it's at least integral.
Or else I could just, you
know, be old fashioned
and say size t here or something.
But the point is, this
takes an integer type thing
and makes it look like a
type, because it is a type.
So I can create types.
So I can convert integers
to types, which is nice.
And then, once an
integer looks like a type
I can use my typelist algorithms
on sequences of integers.
So index sequences are really important
in modern C++ variadic
template programming.
We use them all the time to select,
typically to basically do
index parameter packs of types
or of arguments or whatever.
They're very, very handy. So
one of the things we like to do
is we create an index
sequence of a certain kind.
We could have a sequential
index sequence (mumbles)
starting C++ 14.
We can generate index sequence
from zero to n minus one.
There's a make index
sequence functionality.
If you have a lotta free time,
you can also create,
generate index sequences
of prime numbers and things that are even
and things that, whatever,
subway stops on the A train in New York
or whatever the sequence of interest is.
And so, you have an index sequence,
you might wanna do something like sort it
or partition it or do set intersections
with other index sequences,
but you don't really feel
like writing those algorithms,
although they're not to
hard if you are using
concepts for functions.
But here we decided to leverage our
existing typelist algorithms.
So here we're gonna
convert an index sequence
into a type sequence
and it's trivial to do
with pattern expansion.
All I do is say I wanna type sequence
consisting of these types and
I'll use the expansion here.
I'll use the index to type facility
here in the pattern and I'm done.
And then for convenience,
I'm gonna have my templated using here.
So I can say
index_sequence_2_type_sequence.
And of course, if I want to get
back the original index
sequence, which I will,
I'm gonna revert it.
I'm saying revert here,
because this indicates
that I can't convert
an arbitrary index into a type, yet.
We'll see about that.
So I can revert that
back to an index sequence
and with this in place,
I can leverage those typelist algorithms
for index sequences as well.
So at this point this is just
a quick hand wavy thing to say
that we can take a sequence of anything
and convert it to anything else.
We can take any typelist sequence,
convert it to a type sequence.
We can take a type sequence
and convert it to a index sequence.
We can take, as we'll
see a template sequence
and convert it into a index sequence
for fun and profit.
All right, but the point is,
we have a lotta of freedom.
So all these sequences are equivalent.
There's one, one mapping, as we've defined
between each side of
each of these sequences.
So now that we are there,
let's talk about
predicates and comparators.
So here's our partition again.
This takes typelist, it
takes a predicate over types
and so when we call it,
here's a typelist, we'll make a typelist
and we'll wanna partition it.
We want all these signed
types to come first
and then unsigned come afterwards.
And so this works very well.
The predicate asks
questions about the type
and then we can call
this typelist algorithm.
Well if I wanted to do a
partition of an index sequence,
I wanna ask a question
about an index not a type.
So I need to find someway to take
a question about an index
and turn it into a question about a type.
And this is the way we do it.
This is one way to do it
or it's the way I did it in any case.
So here is our index predicate.
Takes an index and tells me yes or no.
I'm going to simply throw this converter
and use this to specialize a converter
and I'm going to have a nested template
that treats the index predicate
like a type predicate.
So this type predicate
will simply evaluate the index predicate
and produce a true or false type result.
So it's a very quick and dirty conversion
of an index predicate to a type predicate
and we could use it like this,
but we probably don't want to.
So here's an IsOdd predicate.
It tells me if an index is odd
and I can create the
corresponding type predicate
by using our converter.
So I can convert IsOdd
and I can extract this nested template
and that will be my type predicate
that corresponds to the index predicate.
Painful is well chosen word here.
You don't wanna do this very much.
And I'm showing a little bit of kindness
not showing how to convert a comparator,
but it's similar.
So here's the thing,
we don't wanna be wet.
We don't wanna write
everything twice, wanna be dry.
So, all right, that joke
doesn't fly anymore.
(audience laughs)
So don't wanna repeat ourselves,
so instead of doing something like this
over and over and over again,
we can create converters.
So here's a converter
that takes a typelist meta-algorithm
and takes an index sequence
and a predicate on an index
and produces a corresponding
and actually produces
a partition algorithm
for sequences of indexes.
So here's again, another use of using.
So partition for index
sequences can be created
by specializing this
with an index sequence,
a predicate, and a
typelist meta-algorithm.
So this works with typelists.
Nobody's seen a typelist since 2011.
Nevertheless this will work.
I can take an index
sequence and a predicate
and I can partition it
and get the partitioned
result at compile time.
How do I write this?
It's of course, yet another use of using.
There's a certain beauty to it.
(audience laughs)
So let's see, the template arguments
are the index sequence the predicate
and the typelist meta-algorithm
which is something that takes a typelist
and a predicate on a type
and we know how to do that.
We know how to deal with this.
We're gonna convert the predicate.
We're gonna convert the index
sequence into a typelist.
We'll call the typelist meta-algorithm,
we'll get the result
and we'll convert it back
to an index sequence.
So it's actually very straighforward.
Once you start doing
this, it's very addictive
and you'll start trying
to convert, you know,
your neighbors into...
(audience laughs)
Okay, so let's...
I didn't mean anything unusual
with that last statement.
(audience laughs)
So let's use a converter.
So here again, we have our
partition index sequence.
I'm calling my convert algorithm one
and getting rid of this
annoying dependent typename.
And now with this in place,
here's my index sequence
and I can partition it
using an arbitrary predicate on indexes.
So I'll partition this so that all the odd
indexes come first and so on.
Now of course, that's not
very useful, but we've seen,
I have a tutorial (sighs)
it seems like ages ago,
yesterday, (laughs) or Sunday,
where it was important,
we were trying to use...
What's the user to find literal
that uses a character parameter pack?
Literal operator template, thank you.
And we had to actually had do,
we had to parse a user to
find literal at compile time.
We take a parameter pack of characters
and we would make sure the
pack was properly formatted
before we agreed to turn it
into, in this case, a date.
And the way we did that,
is we actually created an index sequence
of the correct structure,
extracted characters
from the parameter pack,
and then confirmed that they
where syntactically correct
and then we could calculate.
But this idea of manipulating
an index sequence
at compile time in order to
perform some other operation
is not uncommon.
Here's just another example
without going into the,
I went into the detail.
Without going into to the details here,
here's a set intersection
for index sequences
and once I create it, I can of course,
here I'm making an index interval.
This is non-standard.
And here's an index sequence,
an ad hoc index sequence
and I can find the
intersection of these two
by using that algorithm.
A lot of material, but the point is,
I really don't know why
people are not as infatuated
with using declarations as I am.
Templated using declarations
are so, so useful.
Alias templates or whatever
you wanna call them,
they are remarkably useful
and they're useful in two,
three particular ways.
One is half-specializing templates.
That's nice.
You can also make non-templates
look like templates,
temporarily, sometimes that's important.
Somebody wants a template,
you don't have one,
okay, I'll make this look
like a template, here you are.
Sounds like a used car lot.
And to simplify complex type expressions,
all of us who have been using enable_if,
you know, concepts will come sometime.
But all of us that are using enable_if,
know how complex those enable_if
SFINAE restrictions can be
and a using declaration is almost required
to make code readable by Java programmers
and things like that.
So the third us is to do
complex transformations
that are maybe not pleasant to set up
but make a lot of otherwise
complex things very easy.
Here's a one liner that somehow
manages to take some
sequences of integers,
turn them into typelists,
run a typelist meta-algorithm
and then convert the
result back into integers.
And it's very easy to use.
So I would like to end with a challenge.
Do the same thing for templates.
Create template lists, like this one.
Here's a template sequence.
I just took some type traits,
write something that
converts a template sequence
to a type sequence,
use that to create a unique
algorithm on a template sequence
and then revert it back
to a template sequence.
And this should be fairly
straighforward, maybe.
And I have one last question.
So what about going the other way?
We said at the beginning
that there's no difference between
a mathematical proof and an integer.
Remember Godel's incompleteness theorem?
I don't, but I remember
part of it (laughs)
and it was the part
that had me slack jawed
when I first saw it.
One of the things Godel did,
he said, okay let's take a theorem
and translate it into an integer.
Now let's prove things about the integers.
The same things must also
hold for the theorems.
And then he proved
that we didn't understand
the universe at all.
And then he killed himself.
(audience laughs)
I think.
But it's a very, very interesting theorem.
But the thing was, I was
fascinated by this some time ago,
so I tried to write a Godel
numbering of the C++ type system
and didn't quite succeed,
but I did generate several
thousand lines of codes
and made everybody else read them,
'cause I published it in CUJ.
So the thing is, can we convert
an arbitrary integer
into a type, or sorry,
an arbitrary type into an integer
and do index sequence operations on them
and then turn it back to a type.
Wouldn't it be nice to
convert a type to an integer,
do some arithmetic on the integer
and convert it back to a
type and see what you get?
So that's your next challenge,
to do a Godel number.
Okay, so you can see why
the talk was rejected.
(audience laughs)
But I think there have been
several useful techniques in here.
The unwrapping through a nested
specialized class template
is something I use all the time.
But just an appreciation
for the template type def,
it's just wonderful
addition to modern C++.
One of the two things that surprised me.
When it was proposed, I
said, okay, yeah fine great,
but it turned to be a very
central part of my programming.
It's kind of like of variable templates.
When they introduced variable temps,
I thought, don't you have
anything else to think about?
But it's great, I use them all the time.
So some of these features
turn out to be very nice.
So, if you want these slides
and the code that accompanies this,
you have to go to my wife's
campaign site. (laughs)
(audience laughs)
You may accidentally click
on the donate link. (laughs)
(audience laughs)
Or not. (laughs)
So far, nobody else has found it.
But anyway I...
(audience laughs)
Any political questions
will be answered off camera.
(audience laughs)
And that's all I have to say
except to apologize for
what's happened to you.
So anyway, you will find the code here,
and you'll find the slides there
and thank you for coming very much.
(audience applauds)
