Doug Gregor

The idea is we wanted real like first-class support for generic programming, the discipline, in C. And generic programming, I, you know, I learned about it in college and I thought it was amazing because it's this idea that you can write an algorithm or a data structure in its like most abstract form, right? This this beautiful thing that you know looks like it's in a textbook, and yet it compiles down to efficient code for any data type that it works with. And C was pretty good at making a lot of that possible.

Conor

In this multi-episode series, we start off by talking about the history of C OX concepts. Very excited to introduce our guest for today, and probably over the next couple episodes, because we usually split these things up into you know two or three. Our guest is Doug Greger, who I actually don't remember what episode we casually mentioned that probably one of Doug's friends or coworkers listens to this episode, and we put like a call out into the wild that we wanted to have Doug on. Sure enough, I'm not sure. We'll let Doug mention if he wants to uh, you know, name that individual that ended up reaching out to him. And if you don't know, Doug has worked at Apple. I looked it up, and correct me if I'm wrong, for 15 plus years. So a counterexample to the folks that like to jump around from company to company. And while he's worked at Apple, I don't actually know what you did necessarily before working on Swift, but you are one of the main individuals. I don't know if there's like a top N that you fit into, but definitely you were probably in that top N for uh your work on the Swift language. And before Swift, I know that you were uh massively involved in the C community. I'm not sure how much of that uh tied in with your work at Apple. And my guess is that you went to a bunch of C nows. I could be wrong about that. And hopefully, one of the topics we will get to today is talking about the original C concepts, or I guess concepts light is what we ended up getting, but there was this original OG uh concept proposal that ended up not making it, and then out of that proposal came the concepts that we have today. And I think, if my memory serves correctly, that is how your name came up is we were talking about concepts as they are today, and we made a reference back to that we we at one point we had the hope of sort of a better concepts. And I think I think most of the C community has kind of acknowledged at this point that the original proposal did give you know the the future concepts more than what we have today. Uh at the time, maybe that wasn't clear. There was a lot of discussion, and I think I think Doug was involved in those discussions. So we were gonna we're gonna get a firsthand account of what went what happened a decade ago. And uh yeah, I think maybe I'll leave it there. I'll throw it over to you, Doug, if you want to fill in or Bryce is gonna add something.

Bryce

You also you neglect to mention that Doug uh was uh uh been heavily involved in the LLVM community and in Claying prior to uh being Mr. Swift. Um yeah. But but yeah, like I think when we were talking about concepts in previous episodes, and we this has come up a few times in the podcast where I've said effectively that like I would like a refund on the concepts that we've gotten, because um almost none of the of the things that we were hoping to get out of concepts have materialized. Um like the one the one that I think is just a real egregious um uh uh uh crime is that like a large part of the starting point of concepts is that, oh, we're gonna get better diagnostics, better error messages, which is like if anything, it's worse. Um uh I feel in in many cases. Um and uh to the point that um I feel like I I tell people only use concepts when you need to um use them to like disambiguate like overloads, like use it as like a proper form of SVNA, um, and otherwise like be very careful about where you use it, like maybe use it in some of your interfaces, but don't put it everywhere because then the the the diagnostics will be awful. Um and uh yeah, um so I I I I feel like we could have done better. And uh I think it will be interesting to hear about the saga of how we got to where we are.

Doug Gregor

Well, it's great to be here. Uh I think the saga of how we are should start with what we were actually trying to build in in COX concepts, because the idea here wasn't better error messages, although that was one small piece of the expected outcome. The idea is we wanted real like first-class support for generic programming, the discipline, in C. And generic programming, I you know, I learned about it in college and I thought it was amazing because it's this idea that you can write an algorithm or a data structure in its like most abstract form, right? This this beautiful thing that you know looks like it's in a textbook, and yet it compiles down to efficient code for any data type that it works with. And C was pretty good at making a lot of that possible. So the template system, uh, especially with Svena and with overloading, you could get an expression of generic programming that worked, but it took a ton of effort. You had to be a wizard with C templates to sort of make it happen. And uh the idea behind the C concepts um effort was you shouldn't have to be a template wizard. It should just be easy to figure out what your concepts are, write your generic algorithms in a manner that's always going to work. So, yeah.

Conor

That was the initial goal. And did this come from because I know uh in the elements of programming, concepts uh are used even though they didn't exist. And I think that was one of the things that have been it's been talked about for a long. It's like uh, you know, when Alexander Stepanov was was writing his you know first initial drafts, like in the comments of his implementation, like were the concepts, but just he didn't have a way to explain, he didn't have concepts then. And then fast forward, you know, until C20 and a version of concepts got in. But this is an idea that's existed for like two plus decades, maybe even more. I'm not sure actually where the genesis of it comes from.

Doug Gregor

So much more than that. So like the first paper on generic programming was from 1989, and it was actually Alexander Stepanov and uh Professor Dave Musser, who I met. I got to meet in college. That's he's got me interested in generic programming. And they actually used ADA in their paper, which is fun. Uh, this was before they discovered that C was the closest thing to express their ideas. Um, but the idea of concepts, Dave Musser was working on it in his own uh little like proof programming language called Tekton to get the ideas developed. Uh, but it wasn't really until 2003 when there is this first paper on, hey, let's bring concepts into the C language as part of COX. And the paper is interesting. It actually lists, I counted them, 14 design aims for this feature called concepts, which is a lot. Uh, but it's interesting because it covers all the bullet points we talked about. So it should make it easier to program with generic programming. It should have this thing called concepts to abstract over types. It talked about, you know, when you call a generic algorithm, we should check all the requirements there and give you nice error messages if you got it wrong. And if it passes that, well, the the definition should have been separately type-checked, so you wouldn't get one of these instantiation time failures. It talked about performance, it even talked about separate compilations of templates, uh, which is a tall order, uh, even beyond concepts. But it really did lay out the ideas for what this feature could and should do. And the, you know, the ideas were great. Um, some you know, colleagues and I at Indiana University uh when I was there thought the idea of putting generic programming into Swift was great, but we had a little we had different views on exactly how it should be done. And so uh we wrote a separate proposal for C OX concepts in early 2005 that laid out this model based on a research language they were working on that had full support for like expressing concepts and uh separate type checking of templates using concepts.

Bryce

Um and when you were at Indiana, that was with uh you were there with Andrew Lumsdain, right?

Doug Gregor

Right. So Andrew Lumsdain uh ran the Open Systems Laboratory.

Bryce

One of the legendary C university shops of the good old days.

Doug Gregor

Absolutely. Lots of generic programming, high performance computing. Uh the Boost Graph library came from those folks. Uh lots of paper on formalizing the notions of uh generic programming support for uh programming languages. Uh it's a really fun place to be. And so yeah, we we worked on the concept effort from there.

Bryce

It was it's interesting that you say 1989 as being the first paper because um while while that's you know a good time ago, a few, a couple of years, not that many years, but a couple of years before I was born. Um I almost feel like it's surprising that it's not older. It feels like uh I wouldn't have been shocked if you'd told me, oh, there was somebody in the 60s wrote this paper on that was the foundations for generic programming, but is it really is it really that new, or is there some older computer science lore and theory um uh in which the idea of generic programming originally comes from?

Doug Gregor

There's certainly older lore and theory, and that and there are languages that had abstraction mechanisms that could be used for generic programming. I think of that paper as the one where uh Step Stepanov and Musser really laid out the process of generic programming. So, you know, when I think about generic programming, what is the idea? And the the core idea is this thing, uh we call it lifting, where you take an algorithm or a data structure that's really concrete. You know, it's it's all concrete types all the way down and it works. And now you want to make it more abstract, so it's more reusable. And so you sort of lift away concrete requirements to discover the true requirements behind the algorithm. And you keep going up until the point where you have to make this compromise of say, well, I can make it more general, but I lose some efficiency guarantee. And then it's a good place to stop. And so I think I think of the beginning of generic programming as we know it as when that process was defined, which is this paper. And it's it's exactly what the programming language should support if you're gonna do generic programming well.

Bryce

Can you maybe tell us a little bit about um the concepts model that y'all came up with at Indiana?

Doug Gregor

Yeah, sure. So um the model we came up with had three parts. So then and really that model translated directly into the C OX model. So I can describe them both. I'll use the C OX terms because it's easier for folks. But essentially there's only three pieces to it. So the first part is concepts. So this is a way of describing in the language that there are certain types that have these capabilities, right? You can use the plus operator on them. There's a nested type, named value type, whatever they are, right? And if you know C20 concepts, the idea here is the same, even though the syntax was very different back in the C OX days. The second major piece is constraints on templates. And so the idea here is you have a template, and essentially the template as you write it can do nothing with any of its template arguments, because there's no constraints. So you haven't said that they can do anything, therefore they can do nothing. So to actually implement behavior, you need to add a constraint to your template to say, well, I need this type T to be equatable, meaning it has an equal equal operator. And now I can use the equal equal operator in the body of that template. The foundational thing here is the separate type checking. If you don't have a constraint that gives you access to some particular operation and tells you what the types involved in that operation are, you cannot write it in a template. Now the flip side of that is once you've satisfied the compiler, you know your template is good. So, you know, I talked about lifting, right? Imagine you start with just a simple algorithm that's just summing all of the elements in an array of doubles. Super easy. Now make it an array of t's for some template to argument t. Well, what do you need? Compiler won't tell you. You know, we will know, well, okay, we need a plus operator that takes two t's and returns a t, whatever. Um, but you just have to know that. In the C model, the compiler will tell you, well, you can't add two t's, please go add a concept requirement. And you add that, and then you get to the next error, which is maybe, well, you don't have a zero value. You can't turn zero into your t's. So you add a concept constraint for that. And once you finish with this process, you know your function is good. So if you go and try to call it with something like, I don't know, some type that doesn't have a plus operator, you will get a nice error message that says, well, this type U that you gave me, it doesn't actually meet the constraints of this template. So the final piece uh we called concept maps. Now these are really interesting. So what concept maps do is they establish a mapping between types and concepts. These don't exist in the C20 concepts model, but they're really powerful. And so the the basic idea is you might have a type, and this type has a completely reasonable interface to do what you want to do with some other generic library from some other place. You want to use them together. What do you do? If you're lucky, you might be able to add some free functions at name space scope and adapt things or add some operators. If you're unlucky, that template was written with member functions or some kind of syntax that you can't just go and add, right? So you start writing wrappers. With concept maps, you're basically saying here's how this type over here meets the requirements of this concept over here. And you could actually put in the body of that concept map extra declarations that were only used and definitions for the purpose of establishing that mapping. So there's useful things and cool things you can do with this. So, for example, you know, is an uh array of double values a container? I think it is, right? We've we've defined it such that we can make it a container in C. Now, there was a time when the begin and end functions were always member functions and you would have written them as member functions. That in C20 concepts precludes you from using a built-in array as a container because you can't add member functions to a built-in array. Concept maps let you do this sort of thing. So with a concept map, you could say, well, any array of T's is a container. Here's what the begin and the end functions look like. Here's the the value type you need to express what the type of that container is. And you could build this mapping sort of as a third party. The important part is this also fit the notion of separate type checking. So again, uh here's a question. You know, when when is a vector equatable? Like you have a std vector of something, when is it equatable? It's not always equatable. If you had a vector of things you can't compare, then you can't compare the vector because it's an element on the vector.

Bryce

Do you mean like when it's com when it's equatable with another vector?

Doug Gregor

Yeah. When can you take two vectors of the same type and compare them?

Bryce

Oh, okay. Just um well, yeah, it's a property of of whether the two things are equatable, like whether the element types are equatable.

Doug Gregor

Right. So this is this is a a conditional notion. And so the way you would express this in a C OX concept map is to say, you know, vector of t is equatable, but that requires that t itself be equatable. Right. And you can express this notion, this sort of conditional modeling of the behavior, and it would be fully type checked. So had you tried to forget, you know, had you forgotten to write that requires t, you know, equatable t on your uh your concept map for a vector, you would have gotten a compiler error that said, nope, there's no equal equal that works.

Bryce

Gotcha. Now how does this differ from the model that we end up having?

Doug Gregor

Right. So the concepts are fairly similar with a with a giant asterisk there on the syntax side. Yeah, yeah.

Bryce

Okay, maybe maybe you can comment a little bit on that about how is the syntax different for the OX concepts.

Doug Gregor

Uh sure. So the syntactic difference uh is that in C20 concepts, what we have today, you you essentially write sort of how you would uh use a type. Right? So if I have a type T, I say, well, okay, you can write X plus Y and it's convertible to a T. In C OX concepts, it used this approach that was referred to as pseudo-signatures. Basically, you write a declaration. So you would write in the concept T operator plus that takes T, T.

Bryce

Yeah. And and and while the syntax differences are maybe not the most significant thing. I personally found pseudo signatures far easier to reason about than writing this the C20 concepts thing where you're writing these like usage patterns. Um, and I think that they're just far more expressive. And and I I back this up with if you look at pre-C11 code that has concepts written in comments, they were almost always written in sort of pseudo-signature form, but like, hey, we you you need like a struct that kind of looks like this sort of thing, with like a, you know, here's the things that needs to have it inside of it. And that just always, you know, that's always what made more sense to me. Um yeah.

Doug Gregor

I that's been my my view was that the benefit is the of the there's two benefits, I would say, to pseudosignatures. One is technical. Uh when you have them, it makes it easier to do the mapping into what you need to do separate type checking, to like type check the definitions of templates because you have a signature you can use. Right, right. That's helpful. But the other part is is more what you're saying, which is you know, what do you want to do with the concept usually? Sometimes you want to use it to write an algorithm against. And in that sense, a pseudo-signature is just like looking at a type and writing against a type. Like we know how to look at a declaration and figure out how to call it. So I think that's easier. And it's much easier when you're saying, oh, I need to create a type or make my type match the requirements of this concept. I'll just copy and paste the definition into my type and do some replacements to make it work. And I find that a lot easier. Certainly that's what we did in Swift, and it it has been much easier.

Bryce

Aaron Powell And it feels more like C ⁇ . I feel like every time I read a concept declaration, a C20 concept declaration, it's like a different language, and uh it's it's hard to parse what exactly the requirements are. Whereas a pseudo signature, it's like it it looks like C. It's like almost like a little pseudocode, like I can understand what it what it wants of me.

Doug Gregor

I think so too. I mean, to be fair, there was history for usage patterns. So the the standard template library before concepts used usage patterns. So there was a history of doing it that way. I always found it awkward, which is which is why we end up with pseudo-programming.

Bryce

And I thought I thought that elements of programming also did the usage patterns thing. I could be wrong about that, but I thought that that was partially where it came from.

Doug Gregor

It could be, although most of this predates the actual publishing of Elements of Programming.

Bryce

Oh, okay.

Doug Gregor

We're still back in 2005, 2006.

Bryce

So so yeah, but back to the how how does uh how does the C OX concepts differ from the C20 concepts?

Doug Gregor

So you talked about concepts as being the same notion between the two kinds of concept features with differences in in syntax. Um the constrained templates, again, the notion is the same. You have the requires clause that you can put on templates to add constraints in terms of concepts. That notion is the same. The massive difference is that C OX concepts check the template definition at the point that you wrote it. Whereas C20 concepts only do a check when you're using a template. So they check that the template arguments you've given to the template actually meet the constraints that were written down. But nothing checks in C20 concepts that the template definition you wrote is only using the operations. That are stated in its requires clause. So doing like, it's a it's like a contract, but only one side of the contract is actually held to it. So this is really fundamental.

Bryce

You look skeptical.

Conor

No, no, no. I just rem- I just my brain uh uh mapped what Doug was saying to how I actually described this in a talk that I gave in 2020, I think. So it was a while ago, but I remember uh at kind of surface level digging into the differences between Swift protocols and uh Rust traits and Haskell type classes and D type constraints and uh C concepts. And I think my my vision for the talk was a lot more grander than it ended up being because I I got I tried to include too much in the languages, and by the time I was done, like two basic examples, my 60 minutes was up, which is you know biting off more than you can chew. But I do recall at one point having a slide that, and and maybe you could this is a small question, uh, but I've always been curious about it, that kind of grouped the these different language facilities that in some cases are basically kind of like one-to-one, even if the features are different, but you know, in all cases superficially represent the same thing. Um but they they were they I I had these uh these two names, one was kind of constraining and the other one was consenting, which is what I think Doug is describing here in different words, and that in certain models, if you don't add any constraints, you basically can't do anything with the function. And as you add constraints, the ability to add things, the ability to do other things, you basically grow the number of operations and things that you can do with this function. Whereas in the other model, you start with the world. You can do everything, and until you put constraints on it, you basically are restricting what you can and cannot do. And like these, and what I so I I think you just said earlier that you were like that the two models are like basically diametrically opposed. Like one, you're starting with nothing and adding constraints, and the other one you're kind of just like restricting over time, which leads to the small question is what the first time I ever heard constraint, like my semantic attachment to that word is kind of when you have a constraint like cuffs on your hands, you are now limiting what you can do. Whereas really in this sense, type constraints, I guess, because depending on the language feature, they do one or the other, but as you were using it in C OX concepts, the constraint is really enabling you to do something. Like when you constrain the type on a function, you are now enabling it to do the addition operator. So I've always been confused on why the word constraint in in my mind kind of means the opposite. Like, or I guess it's it's maybe like where you're starting from. Like if if you start off from not being able to do anything other than basically like the identity function, then you uh you can increase it's it's anyways, I don't know if what I'm saying is making sense, but uh No, no, I I I I I I follow you.

Bryce

Like if you if you start off with the entire world, if you can do everything, then you know, a constraint like like the idea of a constraint of just limiting what you can do makes sense. Whereas if you start off with a world where you can do nothing, and then it's more like a capability. You know, it's like saying it's give it's now you can do a thing.

Doug Gregor

It depends on who you're thinking, like the perspective you're taking. If you're taking the perspective of the person that's implementing the template, it's you know, not having a constraint means you can't do something. If you're thinking of the person that's using the template, each constraint that's added gives you fewer choices for what you can pass into the fewer types that you can pass into the template. This is why unfortunate that Contracts has a very definitive meaning in the C world, because thinking about this as an interface contract is really valuable because it's saying this is a thing that is promised. And the implementation of the template, the definition of the template, promises to only use those things that are in the requires clause, and the user of the template promises to provide at least what is specified in the requirements clause. And if both sides maintain stick to that particular interface constraint, then uh the instantiation will succeed. You won't get a failure. Right. So I would say C20 concepts actually do have that notion that the requires clause is supposed to be this interface contract, but only it's only enforced on the client that's trying to call the template. It's not enforced on the person implementing the template. They just have to be careful.

Bryce

Right, right.

Doug Gregor

That seems less useful.

Conor

Or maybe not less useful is the wrong description. You're you're getting less from your tools and your compiler.

Doug Gregor

Uh right. So so this is where I think without so that the property of separate type checking is both side both sides are being kept to to that set in the requires clause. When you have that, that's when you get a lot of the benefits of language integration for this feature, because you can go and write your generic algorithm and you could discover the requirements. So uh a very long time ago, um, after we did the the initial Indiana proposal for concepts, I did an implementation, a prototype in GCC. It was called concept GCC, and I did a demo of it at the committee meeting. And we did exactly this lifting exercise of starting from a concrete algorithm and then lifting it up to be a fully generic algorithm. It was probably building accumulate out of summing an array of doubles. And along the way, you discover the iterator concepts and you discover the numeric concept that you need to deal with the zero value and so on. And every step of the way, you say, ooh, I want to generalize here and you know work on an array of keys or replace the array with an arbitrary container. The compiler would tell you, hey, you don't have this operation, please go add it somewhere. And so you'd build the concept and have this nice feedback loop to help you discover what are the right abstractions to express my algorithm.

Bryce

And does it does the concepts OX model make it easier to diagnose when you give something to a constrained algorithm and you're missing some operation?

Doug Gregor

For sure.

Bryce

So how how does it because this this is a uh it with the C20 concepts model, this is a common problem where like you know, you've passed in some iterator and it's missing like some one of the many iterator operations in some subtle way. And instead of getting like a clear, like this thing is missing, you get a uh a message that's like it failed to satisfy this concept, which is a refinement of this concept, which is a refinement of this concept, which is refinement of this concept, and then you have to like go all the way down the chain. And does does that to me is not very good in the diagnosis side. Um uh instead of just being like, hey, like you need to have this. And in in the OX concepts model, did we have a better way of of diagnosing like uh uh uh a failure on the the the provider side or the the person who calls the algorithm side?

Doug Gregor

We so we it's interesting. We did. So the concept GCC prototype was pretty good at diagnostics of error messages. The the thing that's strange is I think compilers could be doing a whole lot better with C20 concepts than they are. Um and so I think there's some aspects of C OX concepts that made things easier. So we did have the notion of a concept map. So when you wrote a concept map that said, hey, this type meets the requirements of this concept, we would tell you right there if it worked or not. So it's it's much more localized. You can do something similar in C20 with a static assert, but you're static asserting based on a given type. You're not saying all instantiations of this template type work this way. And so you don't get quite the feedback. I do think there is something in the design that made C OX concepts a little easier, and it's actually getting back to pseudo signatures. Because with a pseudo signature, you check for each of the pseudo signature, say, okay, I need a plus plus or plus operator that takes two T's and returns a T. Go try to do that, right? As part of establishing the concept map. And if it's not there, I can point to here's this plus operator, you need something that looks like this. Right. Right. Um, and we did go as far as to say, if your type looked like it met all the syntactic requirements of the concept, but it didn't have a concept map to say it, concept GCC would say, Hey, I think you're just missing this concept map definition. Here's what you should write in your code to try to guide you along.

Bryce

Did it ever was it ever onerous to have to write these concepts maps that like like in the in the C20 model, you don't have to write like things either satisfy the concept or they don't. And isn't that isn't that better?

Doug Gregor

Great question. Uh so it was certainly a major point of contention and concern, uh, the fact that you need to write concept maps. Uh, C OX concepts uh did have a notion of an auto concept, which is one where if you met all the syntactic requirements, the compiler would just automatically create the concept maps for you. And in fact, most of the concepts that we'd specified for the standard library were auto concepts because it met the backward compatibility constraints that the committee had for our design. And so it's a little interesting because it worried people a lot for backward compatibility reasons. And it worried people a lot because people might have to learn about this concept map feature and concepts before they were ready. And so there's a lot of concern about that. I feel like that concern was well overblown. We've seen a lot of other languages that require something like concept maps. Like Swift requires you to explicitly say, you know, my type conforms to this protocol. And it is not a concern for beginners. It's it's really easy for people to pick up. And they actually most of them come back and say, actually, I like it being explicit because I know this happens and I know it's checked.

Bryce

So is the is the benefit of the concept map that that that explicitness that you get the check?

Doug Gregor

I would say so yes. So that I guess there's maybe two benefits. So one is that you get the check. And the other is that there's there's some implicit meaning behind these, which is in addition to meeting the syntax requirements of the concept, I also have the right semantics. Right. So this happens with C20 concepts as well, right? Like what is the difference between an input iterator and a forward iterator? Yeah. It's kind of nothing except the semantics of what happens if you start over iterating a second time.

Bryce

Aaron Powell, or like what's the difference between like a range and a view, or like you know, a range that happens to be movable in a view. Um, yeah. Um uh where you have the these semantic requirements on on uh views that you don't necessarily have on ranges. It's interesting. I I feel like one of the major themes throughout the evolution of C has been this uh this struggle between um uh more implicit ways of doing things that maybe have foot guns and more explicit ways of doing things that uh people worry maybe too too verbose. Um in fact, this is this famously happened with C20 concepts, where the reason that we have this uh the abbreviated uh concept syntax, um uh we have, you know, if you if you want to use a concept uh in a parameter list without uh uh putting it uh without having a template, you know, open brace, close brace list before, you have to put concept name auto, you know, name of the parameter. And the auto is there to make it very clear that this thing is a concept and that you've now turned this function into a template. Um and that was a major uh a major source of contention because the there was someone in the committee who felt like we had to have that because otherwise you could just be reading code and you just see like thing, you know, like like parameter, like thing that looks like a type, and then the name of the parameter, and then you wouldn't know that that was a concept and that that made this thing into a template. And there's just multiple cases of I feel like almost all of C's woes are either from uh uh making the wrong decisions about implicit or explicit or picking the wrong defaults about things.

Doug Gregor

That that certainly does happen. And I think there there is this notion of when when something is new, it's always a little bit scary. There's always something to learn, and you're you're worried that it's gonna sneak up on you, so you want to make it more explicit. Yeah. And so sometimes we we make these decisions more, I don't know, out of fear, I guess, of being surprised uh than about than thinking about where we want people to be after they've gotten over the hump. I think this this happened with C OX concepts a little bit. Like people are worried, like, oh no, you might encounter this concept map and know what what it you don't won't know what it is, you have to go learn it. Right. On the other hand, if you do that system, once people learn concept maps, well now they can really do generic programming and get all the benefits of this feature that we built rather than hiding it. And so there's- there is a balance here, right? You don't want to keep throwing complexity at users all the time and have things changing under underneath them all the time. But you need to aim for where you want them to be a couple years from now, not where they are today.

Bryce

Connor, you look um you look you look either troubled or thoughtful.

Conor

I mean uh both. I'm just conf I'm uh I'm surprised to hear that like the main it sounds like, correct me if I'm wrong, that one of, or if not one of, the main problem with uh getting this through the committee and standardizing it was this worry about the complexity of concept maps. And that is very surprising for someone who is a massive fan of language. Like, you know, you'll you'll hear Sean Parent say that you know software engineering is a profession, it's you know beholden upon us to know about the history and to treat it as a profession. If you know it's a lot of professions, lawyers, doctors, etc., they have continuous learning and there's becomes you know better tools and things, and you have to continuously read, whether it's the academic papers or seminars and stuff, so that you're not a doctor operating you know with 50-year-old techniques uh because you know the best practice is constantly evolving. And I I love that sentiment, I love that statement. You know, it's uh part of the reason why I love ranges and and these kinds of interfaces because one of the biggest arguments against things like ranges, or you know, they're they're called different things, but like the iterators in Rust, et cetera. Uh Swift has sequences and um multi-pass, uh, I can't remember what they're called, sequences. What's the other one in Swift? Collection. Collection, yeah. And and you can build these kind of pipelines of operations. I love, I absolutely love the elegance and in my opinion, the readability of these kinds, this kind of code. It's this kind of data flow model where you start with an input, you do a bunch of operations, and then you end up and you can read it. It's linear, it's beautiful. However, you go to Reddit, you go to certain corners of the internet, and there's a huge faction of folks that will argue that, like, holy smokes, this is very complicated. It's not the way I'm used to writing code. You know, for loops and if statements are so much easier to reason about. Every language has those, not true, but the languages they know all have them. And anyway, so so the same kind of argument at a certain level exists for other language features, or I guess this is a library feature that ended up getting into C that is the exact same kind of like, oh, this requires learning. You're gonna have to go and learn what is a filter, what is a transform, what is uh an adjacent, you know, et cetera. All these things, what is a chunk buy? But if you go and learn them, you would now have a tool that is much more powerful and the ability to write these kind of expressive pieces of code, you now have. And to try and do that with a for loop and an if statement, it's gonna be way more complicated. And monologue is coming to an end, uh, which is that like, you know, range has got in. Um, and I'm sure that there were some people arguing the same thing. Uh, so how come like concepts in the version that they were uh presented, like like how did it's too complicated? It will require people to learn too much. How did that create like a stump, a stumbling block to the extent that like we needed to go and redesign it or rip some stuff up? Anyways, that was what the frown on my I was thinking like ranges got in, and there's a lot of people that are upset about the complexity of ranges, but it's a tool that you need to learn, and if you learn it, you you get special powers, basically. And it sounds very similar to this concepts OX with you know, concept maps. I'm hearing this, it's it's sure a little more complicated. You will have to go learn. But if you do, you get these tools and these powers that you won't have otherwise. Anyway, so uh that was what the FRAM was for. I'm not sure if you can inform what I what I'm saying, Doug, or Bryce has something to say.

Bryce

So so before we uh before we we ask Doug the uh the question, which is the the the reason that we're here, of course, uh I'll I'll read from uh uh the isocpp.org, the the C the standard C foundation's website has an FAQ, and one of the FAQ pages is uh C OX concepts history. And uh there's a section that talks that that and that has a question what happened to C OX concepts? And it says, quote, they were overly complex for COX slash C11. And so we're removed from that standard so that work could continue to simplify them for a future standard. That work has been ongoing in a radically simplified version. Concepts light will be part of the C14 wave of deliverables as a technical specification. So I guess, Doug, the question is um, what happened to C OX concepts? Why was C 11 late? And are you to blame?

Doug Gregor

Oof, wow. So I am not gonna take blame for C11 being late, but I think what happened to C OX concepts is a little what Connor's monologue was all about. So uh so concepts they were in the draft standard in 2008. There was wording, which I think ran something like 30 pages of wording with new chapters for concepts and constrained templates and all that. Uh there were 10 proposals that came along with it, adding concepts to all of the standard library. So you know, we had fundamental concepts and iterator concepts, container concepts, all the algorithms got constraints.

Bryce

We had all these in a much more comprehensive way than the current conceptification of the standard library, right?

Doug Gregor

Yeah, I mean this was this was the real the sorry, I don't want to say the real standard library, but you know, the things that were already there, the C 9803, those containers and algorithms, got concept constraints. They were backward compatible and they were checked. So they were in the concept GCC's implementation standard library and checked the template dep template definition time. So we knew they were right by checking, not by you know just thinking through it. So it was pretty far along. It was it was in the the 2008 drafts, and then uh there was a discussion on the committee mailing list with the provocative title Are concepts required of Joe Coder? Which was a thread basically saying oh no, with the way concepts are designed and the way you need to write concept maps in some cases to make you know a type meet the requirements of a concept. The sort of average Joe Coder, the C programmer out there that's been ignoring everything we've doing we're doing in the committee, is going to be forced to learn this new big feature and you know will resent us for it or whatever. And that they'll be forced to learn this feature and they're gonna be upset with us because we we broke their existing code and the feature's too hard for them to learn. And that there were a bunch of side discussions that were sort of weird, but getting at this overall unease with complexity. Uh things like if you wanted to use the brand new for each loop with a built-in array, you might have to include the the iterator concepts header. Like if if you had nothing else in your CPP file that pulled in the the iterator concepts header, you needed to pull that in to get the concept map that made built-in arrays into a container or a view that you could iterate over. And the compiler told you, but you know, this was considered a potentially massive stumbling block for C OX.

Bryce

So you said that there was a concern about breaking existing people's code. Was this about a concern about breaking existing people's code who were using the standard library, which was being conceptified?

Doug Gregor

Interestingly, it wasn't about breaking people's working code, because we handled backward compatibility in a standard life pretty well. I mean, we didn't have it rolled out through millions of lines of code, but we could run like the entire um lib standard C test suite against the conceptified STL and it worked and it worked the same way. And the performance was pretty close. So it was more about, you know, I as a user, maybe I'm writing, you know, dealing with one of these the concepts that wasn't auto, or I'm using a library that is expressed in concepts. Now I have to go and learn about this concept map feature. And the expectation here, I think, is that all concept maps would be empty. So you could write an empty concept map if your interface already matched up exactly with what the concept expected.

Bryce

Oh, okay.

Doug Gregor

And then it became basically just an assertion that says, yes, this is true. Make sure you check it for me. And I think the concern was, well, we're going to be writing lots and lots of empty concept maps everywhere that aren't providing value.

Bryce

Right. I can certainly see how that would be a concern the committee would have. But that would only be the case for concepts that were not auto-concepts, right?

Doug Gregor

Right.

Bryce

Okay. Right.

Doug Gregor

And nearly every concept was an auto concept. And for things like iterators, where you know having an auto concept between input and forward iterator would be a little dangerous, right? You would get it wrong. We uh in the concepts version of the STL, we would um write concept maps that were able to go and inspect the iterate the existing iterator traits to see which iterator tag was used so that we could map over the hierarchies sort of seamlessly.

Bryce

And and so at some point a decision was made to remove concepts from the standard or to remove C OX concepts from the standard, yes. And and then at that point, all of the work to conceptify the standard library had to be rolled back. And there were there were presumably other things like any work that was using concepts now had to be rolled back. Um and and my I think my understanding of that time was that that that was partially um uh one of the reasons why C11 was was took longer than anticipated, right? Because we decided to remove this large feature late in the process.

Doug Gregor

Maybe. So there was some unwinding to do. So we had 11 or 12 proposals full of wording that had to be backed out of the standard. There weren't that many features that depended fully on concepts. The one I can think of is the for-each loop. So the foreach loop was in expressed in terms of a concept that had begin and end and the iterators. That had to be recast in terms of what you see today, which is uh informed by the concepts discussion. So it you know, it looks for a begin function, I think, as a member function, and if not, it falls back to a free function and then has some fallbacks, I think, for built-in arrays, because we don't want to force someone to include a header to use the forin loop. That one turned around pretty quick. I think I may have written the wording for the forein loop because I felt so guilty uh about it having been tied to my concepts feature that then died. Uh, but there weren't that many features like that that had gone all in on concepts and had to be backed out. I think the other thing that we would have gotten, but didn't get is there were some proposals for iterator concepts that came out of the Boost Iterator library to improve to separate out traversal from access. That was a proposal, it was in good shape early on in the C OX timeframe, got subsumed into the concepts effort, partly because it was the same people, and then didn't get a chance to come back for C OX, and it wasn't really until Rangers came along that you started to see that that that formalism come back. Interesting.

Conor

So Joe Coder killed C Ox concepts.

Doug Gregor

I I I think projections of the thinking onto a mythical Joe Coder is the main thing here. There were other complaints, so there was concern about the compile time performance of the Concept GCC prototype. Because it was doing all this template definition checking for the algorithm setter, and so it compiled slower.

Conor

Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

Bryce

Low quality, high quality, that is the tagline of our podcast.

Conor

It's not the tagline. Our tagline is chaos with sprinkles of information.