6 ms·

Concepts: The Future of Generic Programming [pdf]

90 points by matt_d 10y ago

vmarsy 10y ago
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-cxx17/ http://honermann.net/blog/2016/03/06/why-concepts-didnt-make... [2] https://www.codeproject.com/KB/cpp/791461/errors_temp.PNG https://www.codeproject.com/KB/cpp/791461/errors_temp.PNG
- pjmlp 10y ago
  Even though they aren't here, auto parameters, constexpr if, static_assert, and enable_if can already simplify some of those errors.
chubot 10y ago
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 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.
- fungos 10y ago
  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. :)
  - chubot 10y ago
    So do Rust traits do all the stuff that concepts do? Everything is zero-overhead?
    - steveklabnik 10y ago
      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.
      - cpeterso 10y ago
        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.
        tatterdemalion 10y ago
        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.
        pdpi 10y ago
        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.
alkonaut 10y ago
What makes concepts different from interfaces (Java/C#), traits (Rust) or protocols (Swift)? Is it different enough to need a completely new term?
- fungos 10y ago
  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).
  - vvanders 10y ago
    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.
- gpderetta 10y ago
  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.
  - throwaw12ay 10y ago
    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.
rawnlq 10y ago
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?
- openasocket 10y ago
  What you're talking about is dependent types (https://en.wikipedia.org/wiki/Dependent_type 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.
  - saghm 10y ago
    > 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/ http://www.idris-lang.org/
- vmarsy 10y ago
  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-language-and-program-verifier-for-functional-correctness/ https://www.microsoft.com/en-us/research/project/dafny-a-lan...
ambrop7 10y ago
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 http://ideone.com/yPaZ17

90 points by matt_d 10y ago

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-cxx17/ http://honermann.net/blog/2016/03/06/why-concepts-didnt-make... [2] https://www.codeproject.com/KB/cpp/791461/errors_temp.PNG https://www.codeproject.com/KB/cpp/791461/errors_temp.PNG

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

chubot 10y ago

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 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.

fungos 10y ago
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. :)
- chubot 10y ago
  So do Rust traits do all the stuff that concepts do? Everything is zero-overhead?
  - steveklabnik 10y ago
    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.
    - cpeterso 10y ago
      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.
      - tatterdemalion 10y ago
        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.
        pdpi 10y ago
        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.

alkonaut 10y ago

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

fungos 10y ago
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).
- vvanders 10y ago
  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.
gpderetta 10y ago
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.
- throwaw12ay 10y ago
  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.

rawnlq 10y ago

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?

openasocket 10y ago
What you're talking about is dependent types (https://en.wikipedia.org/wiki/Dependent_type 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.
- saghm 10y ago
  > 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/ http://www.idris-lang.org/
vmarsy 10y ago
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-language-and-program-verifier-for-functional-correctness/ https://www.microsoft.com/en-us/research/project/dafny-a-lan...

ambrop7 10y ago

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 http://ideone.com/yPaZ17