Concepts: The Future of Generic Programming [pdf] | Hacker News Reader

Concepts: The Future of Generic Programming [pdf]

stroustrup.com

90 pointsmatt_d40 comments

Great stuff for people working with C++ Templates! I've seen it explained by Bjarne and Andrew Sutton, the benefits are clear for people used to work with the STL. Unfortunately, Concepts won't be there yet, they are not coming in C++17 [1]

I can't wait the day when, we can avoid crazy long errors like this [2], which ends with a cryptic error "not match for operator + in iterator<foo<bar<.......> > >::ref " we will get clear, english errors that can be defined by the library writers : "The items in this collection needs to be summable" or "This collection must be sortable" , etc. etc.

[1] http://honermann.net/blog/2016/03/06/why-concepts-didnt-make...

[2] https://www.codeproject.com/KB/cpp/791461/errors_temp.PNG

Even though they aren't here, auto parameters, constexpr if, static_assert, and enable_if can already simplify some of those errors.

What makes concepts different from interfaces (Java/C#), traits (Rust) or protocols (Swift)? Is it different enough to need a completely new term?

Warning: // 1990s style generic code: from the article describes me and C++, though I do understand more modern C++ at a basic level, I'm not an expert. You might say I'm.... rusty...

ahem.

One huge difference in general between C++ templates and Rust's generics (I _believe_ Java/C# are more like Rust here, and I'm not sure about Swift) in that C++ templates generally don't check that their calling code actually supports the type that's passed into the template. In other words, the check happens after the template is expanded. (This is the sort example on page 3). Rust's generics system does the opposite: it requires that if you call a method on some generic parameter, that generic parameter is constrained by a trait that has that method. This happens before expansion. So concepts are, in some ways, an attempt to make the C++ system closer to Rust's system. (This is ignoring the actual chronology here, of course: concepts have been in development a long time).

The way "requires" works here is very different than in Rust, as well. In Rust, you define a trait the same way you'd define regular methods. If those methods have a body, then it's used as a default implementation, if it does not, then you must implement that method. The equivalent of "must have an iterator type" is associated types, you add "type Name;" instead of a method signature.

So the equivalent of the "Sequence" type on page 7 would be

  trait Sequence {
      type Value;
      type Iterator<Item=Value>; // Iterator itself has an associated type, Value
    
      fn begin() -> Self::Iterator;
      fn end() -> Self::Iterator;
  }

roughly speaking. I don't think this exactly works, but just to give you some idea of how the syntaxes roughly compare. In general, I know that a Sequence trait in Rust would require higher kinded types or associated type constructors, which Rust does not yet have, and so the concept is probably not directly expressible.

That's my impressions after reading this. I have been meaning to read about concepts for a while, but since I only have so much time, have mostly waited to see how they shake out before really digging in. It's slightly slower going since my C++ isn't spectacular. This post mostly represents my understanding of the differences, I'm not trying to make any judgements here, etc.

Can concepts be used like traits in non-generic code? Which is to say, can it be used as a type name of a variable or function argument? Because there seems to be a lot of overlap between a concept and a pure virtual class, both of which define function signatures. But if concepts are only for templates, and you still have to use pure virtual classes to express traits, that seems like a missed opportunity to me. But I may be missing some nuance here.

> can it be used as a type name of a variable or function argument?

If I understand correctly, placeholders may work for this. This use is described in the "Programming with placeholders" section of the "Introducing concepts" article: https://accu.org/index.php/journals/2157

The remaining articles in Andrew Sutton's C++ concepts series are pretty good, too; so, just in case anyone is interested, here are the links:

- "Defining Concepts" - https://accu.org/index.php/journals/2198

- "Overloading with Concepts" - https://accu.org/index.php/journals/2316

If I understand the first article about placeholders correctly, concepts are indeed intended to be used where you can use ordinary types, just like traits. That looks really cool, if it ends up in the standard.

It's not clear to me; I didn't see it in this pdf but might have missed it.

Concepts are similar to Rust Traits, (I think) Swift Protocols and Haskel Type Classes, but different (significantly more expressive) than Interfaces.

The name has been used in the C++ community since at last mid 90s as it originated from Alex Stephanov work on the STL. Stephanov himself might have used the name even earlier than that. Formalization of concepts which has been attempted at least since the early 00s was influenced by Haskell and in turn did influence both Rust and Swift.

I really love traits in Rust. It's in my opinion the best way to implement interfaces. I'm really thinking about writing a toy language that looks like Rust 99% but without the borrow checker. The ownership thing annoys me. I know it helps creating secure programs but I'd be fine with a language that has Rust syntax/generics/traits/pattern matching with garbage collection. My goal isn't to create a C replacement, but a better Go. Go gets concurrency and syntax right but its type system is shitty. Go is a missed opportunity.

I'm actually a huge fan of their ownership model. I find that in languages where you can't enforce it(Java, etc) architecture tends to suffer. Single owner(with tools to break out when you have to) is a fantastic model.

I feel that lazy ownership gets really gnarly when you start associating large native resources with objects and then can't clearly be sure who's owning a reference to what(see Activity/Context leaking in Android).

All of this stuff is solveable with proper diligence but I prefer my language to enforce it.

> All of this stuff is solveable with proper diligence but I prefer my language to enforce it.

This is why I love Rust in a nutshell (okay, there are actually a lot of reasons, but this is a big one). Given the choice between my ability to write perfectly bug-free code and the compiler to make sure that my code is correct, I'll pick the compiler any day of the week. And that's before taking into account the fact that like most programmers, I have to work with code that's not mine as well.

> All of this stuff is solveable with proper diligence but I prefer my language to enforce it.

Exactly. Everyone trying to defend C always makes this argument, well you just need perfect programmers who write code without mistakes! Why can't everybody just write good C? But some of us live in the real world where those mistakes mean huge vulns.

(Not hating on C in general, just in any security-sensitive context)

Rust's concurrency story is built on top of ownership. Its how Rust prevents data races.

>My goal isn't to create a C replacement, but a better Go. Go gets concurrency and syntax right but its type system is shitty. Go is a missed opportunity.

Have you considered forking Go and replacing the type system? If such an experiment was successful this could be the fabled Go 2.0...

Have you looked at Swift? In some ways, it's a bit like Rust without strict lifetimes Swift has GC (ref counting under the hood) and a fairly expressive type system.

Type classes in Haskell are similarly awesome and where Rust's traits originate from. It's way more flexible and expressive than OO interfaces.

That is more related (not the same) to Java/C# Generics than Interfaces.

That is, it is resolved at compilation time and not at run-time as these that you cited except for some cases in Rust where Traits can be both run-time or compile-time depending on how you use them.

For decades C++ has the equivalent of these, it is called virtual pure classes (we may even consider virtual in general).

Yup, I'm a big fan of how rust does dispatching. It's awesome to not have static/dynamic dispatch tied to the type but the explicit usage.

Besides what the others have replied, C++ already has interfaces, they are pure base classes (virtual if destructors are required).

But those cannot really fulfill the role of concepts in templates.

I like this idea of zero-overhead interfaces at compile time, but I wonder if it would make sense to translate into these features into another language with less baggage.

Kind of like EvilML maybe: https://github.com/akabe/evilml

Everything is generic in ML but it's not clear what runtime overhead there is. The compiler does so many transformations that it's hard to reason about.

This is how I see Rust and why I really like it. As a car analogy, basically under the hood it has the C and C++ engine (more true yet using all llvm optimzations for clang) but it has more modern Teslaish/Ferrarish body. :)

So do Rust traits do all the stuff that concepts do? Everything is zero-overhead?

Traits can be used in both dynamic and static dispatch contexts:

  trait Foo { } // pretend this has methods

  fn static_dispatch<T: Foo>(x: &T) {}
  fn dynamic_dispatch(x: &Foo) {}

One area in which dynamic dispatch works differently in Rust is that &Foo there is a "double pointer": it's a (pointer to data, pointer to vtable), which is different than how C++ does it. The static dispatch code will get monomorphized for each T that it's called with.

Given Rust's focus on zero runtime overhead, I'm surprised that the static dispatch case requires more awkward syntax. People will write code using the simpler, more familiar syntax and incur the dynamic dispatch overhead.

There's some nuance but a lot of us regret the dynamic dispatch syntax and wish we had done something like this:

    fn dynamic_dispatch(x: &virtual Foo) { }

    fn static_dispatch(x: &Foo) { }
    // is just syntactic sugar for
    fn static_disatch<T: Foo>(x: &T) { }

As "consolation," dynamic dispatch is usually harder to wrangle with for semantic reasons and so people generally don't use it unless they need to.

I guess it's a bit a matter of taste, but to me "x: &Foo" seems unambiguously like dynamic dispatch (given that Foo is a trait). The only thing you know about the type of your parameter is that it is an instance of Foo, therefore you need dynamic dispatch, whereas the T: Foo, x: &T reads like "x is of a specific concrete type that's an instance of Foo", which gives you static dispatch.

I think this is informed by the fact that that's what it means today. If Rust didn't have any dynamic dispatch at all, and it was suggested we have this `&Foo` means `&T: Foo` sugar, I can't imagine anyone saying "That syntax looks like dynamic dispatch!" "What dynamic dispatch? Rust doesn't have that feature."

And since users almost never specify the implementing type manually (type inference figures it out with very few exceptions), the whole notion that this is a function parametric over types is obscured for many users.

There are trickier issues though about the fact that in return positions we'd want it to mean something different (existential vs universal), and there are "higher order" positions in which its very difficult to determine which of the two semantics you meant here. This has a resemblance to covariance & countervariance.

Actually, I think that it's because of how each syntax maps to other languages I've used before.

The parametrically polymorphic version reads a lot like Haskell, and both will monomorphise and use static dispatch:

    fn doStuff<T: Foo>(x: T) -> T
    doStuff :: Foo t => t -> t

Whereas the Trait Object syntax Reminds me more of Java's syntax, and both use dynamic dispatch:

    fn doStuff(x: &Foo)
    public void doSttuf(Foo x)

I don't think there's anything intrinsic about either syntax that suggests it _must_ use the dispatch style it does, but when I first started learning Rust, these similarities made it click for me which syntax went with what.

It's two conflicting desires: should the simple case do the right thing, or should the language be more consistent? You're not wrong, but language design isn't easy!

Will concepts (currently or in the future) be able to constrain on anything other than types?

For example in the Number concept, can you have a PositiveNumber concept (e.g., require Number > 0)? Or given some container, that it is sorted? Or if you have a binary operator, that it is associative?

Maybe with some magical compiler that can tell you that after calling abs() or exp() the "double" type becomes a positive number concept, or that after calling sort on a vector and only doing binary inserts that the vector is still sorted.

Basically a lot of contracts on how to use a function correctly is not captured by just type system or whether you can call certain functions on a type. Is there an easy way to attach a "concept" to an output in an ad hoc way?

What you're talking about is dependent types (https://en.wikipedia.org/wiki/Dependent_type). The problem with these is that, in general, determining whether or not an object is of one of these types (PositiveNumber, PrimeNumber, ListWithAtLeastThreeElements, etc.) at compile time is undecidable. This isn't horrible, as template meta-programming already allows you to encode Turing Complete programs into compilation, but unlike templates, where evaluation is somewhat straightforward, evaluating dependent types requires general theorem proving. There are languages with dependent typing, but of them I only know Coq, and Coq sidesteps the issue by the language not being Turing Complete.

> There are languages with dependent typing, but of them I only know Coq, and Coq sidesteps the issue by the language not being Turing Complete.

There's also Idris, which I haven't really used, but from what I understand, it's sort of like Haskell with dependent types.

http://www.idris-lang.org/

What you're describing is more in the domain of program verification,

there's already work like this, for instance dafny [1], where you can have functions like this:

    method Abs(x: int) returns (y: int)
       ensures 0 <= y
    {
       ...
    }

or:

    method MultipleReturns(x: int, y: int) returns (more: int, less: int)
       requires 0 < y
       ensures less < x < more
    {
       more := x + y;
       less := x - y;
    }

[1] https://www.microsoft.com/en-us/research/project/dafny-a-lan...

You can do this with coq/agda/idris (fully general dependent types) or Haskell (LiquidHaskell). Not C++.

LiquidHaskell is nice because it's all written in comments next to or in a separate file from your Haskell code. This means the Haskell compiler doesn't even have to know about it. On the other hand, when you're using something like Idris for formal programming, you often find your program full of proof witnesses that you aren't actually using for your real code you want to write. You can prove all sorts of things, like that a function only returns negative multiples of 3, or only returns vectors of length 5n+1.

I believe the contracts (preconditions, postconditions, assertions) proposal may address this issue.

The latest proposal is P0380, "A Contract Design": https://wg21.link/P0380.

An earlier work, "Simple Contracts for C++" (https://wg21.link/P0287), gives some further background and motivation.

Notably, contracts are currently solely in the proposal stage (and not in the upcoming standard).

The failed C++0x proposal did include axioms that would have allowed the specification of such constraints, but axioms werent supposed to be checked by the compiler itself (other than syntactic correctness). Axioms were intended to be used for documentation and checked by static/dynamic analysers and possibly used for optimisations.

The current concept proposal is significantly reduced in scope and doesn't include anything like axioms.

Besides what everyone else is replying about dependent typing, you can get that in C++ by a mix of concepts, classes and operator overloading.

It isn't as clean, but it does the job.

For example you could have a PositiveNumber class, with the mathematical operators overloaded that always validated the invariant of the number being positive.

You just described dependent types, they´re available in Idris.

I've taken a quick look at current C++ concepts, but from what I understand, they have the following problems considering what I would like to see in C++:

- Weird syntax, the requires thing. I should be able to write a "static interface" in much the same way that I can write pure virtual functions, that is a bunch of functions.

- Ideally one could write the same "interface" and use it either statically (just checking a specific type) or dynamically (vtable calls).

- It is not verified at compile time that the code is using ONLY the defined interface and not something else accidentally.

I really think C++ should go toward something like Rust traits, which work pretty much like what I described above.

Actually in C# interfaces and generics work similarly, save for the fact that they cannot generally do static dispatch, just static verification. In a C# generic method it is not possible to use features of a generic type other than those implied by the "where" constraints.

EDIT: Here's my quick hacky "implementation" of static interfaces in C++. http://ideone.com/yPaZ17

Reply on news.ycombinator.com