brendanzab/cpp-templates-vs-rust-generics.md

## cpp-templates-vs-rust-generics.md

      
    Raw
  

              cpp-templates-vs-rust-generics.md
            
          
NOTE: This was first authored on 26 Feb 2014. Things may have changed since then.

C++'s Templates

C++'s templates could be seen as forming a duck typed, purely functional code generation program that is run at compile time. Types are not checked at the initial invocation stage, rather the template continues to expand until it is either successful, or runs into an operation that is not supported by that specific type – in that case the compiler spits out a 'stack trace' of the state of the template expansion.
To see this in action, lets look at a very simple example:
template <typename T>
T fact(T n) {
    return n == T(0) ? T(1) : fact(n - T(1)) * n;
}

int main() {
    auto x = fact("hi");
}
This gives us the error:
Untitled 3.cpp:3:46: error: invalid operands to binary expression ('long' and 'const char *')
    return n == T(0) ? T(1) : fact(n - T(1)) * n;
                              ~~~~~~~~~~~~~~ ^ ~
Untitled 3.cpp:7:14: note: in instantiation of function template specialization 'fact<const char *>' requested here
    auto x = fact("hi");
             ^
1 error generated.

As you can see, the template has attempted to expand, and only errors once it is actually inside the templated function and can't find an appropriate operation for that type. This can be very confusing for a user of a library because the error messages expose implementation details. In template heavy code, the the error might only present itself very deep in the expansion, which causes C++'s famous mile-high error messages.
The advantage of C++'s template system, like any other duck typed language, is that it is very expressive and flexible. A templated function can be written without any interface needed up front, and will work for any type that implements the required operations. Like any duck type language however, this inevitably pushes the specifications into the documentation, and when these specifications are ignored (or never read!) incomprehensible errors will most certainly result. This has been the main driver behind the push for the 'concepts' feature in a future version of the C++ standard.
Rust's 'generics'

Rust's parametric polymorphism and type classes (of which I will now refer to under the more colloquial term, 'generics') follows in the ML and Haskell tradition in that the type checking is like constraint program that is run at compile time. When an generic item (or also in Rust's case, region labels, like 'a) is invoked, the specification of that type is immediately checked for consistency at the call site, otherwise the typechecking fails.
Let's have a look at the previous factorial example in Rust:
use std::num::{One, one, Zero, zero};

fn fact<T: Eq + Zero + One + Mul<T, T> + Sub<T, T>>(n: T) -> T {
    if n == zero() { one() } else { fact(n - one()) * n }
}

fn main() {
    println!("{}", fact("hi"));
}
This gives us the error:
Untitled 6.rs:8:20: 8:24 error: failed to find an implementation of trait std::num::Zero for &'static str
Untitled 6.rs:8     println!("{}", fact("hi"));
                                   ^~~~
note: in expansion of format_args!
<std macros>:2:23: 2:77 note: expansion site
<std macros>:1:1: 1:1 note: in expansion of println!
Untitled 6.rs:8:5: 8:32 note: expansion site

As you can see, the specification must be given up front, which means that any error is caught at the call site, as opposed to deep in a template expansion.
Rust's generics are much more principled than templates, but they are dependent on types conforming to specific APIs. If a type does not implement the required interface, then it is impossible to use the associated functions, even if they may be perfectly valid.
Macros and syntax extensions are not a replacement for templates

Those who are more experienced at Rust might be wanting to call me out, crying, "what about macros and syntax extensions?". Indeed Rust's macros are powerful. They share many qualities with templates. But they certainly feel like second class citizens in the language:

They exist in a separate, global namespace.
Exporting macros feels like a hack.
Importing macros feels like a hack.
They also do not follow the same conventions as other language constructs – for example they cannot have type parameter lists, and there is no way to invoke them like methods.

This is certainly not an extensive exposition on how Rust's macros do not fill the same gap as templates, but it at least gives you a taste.
Compile time computation

C++'s templates also provide a powerful, if unwieldy form of compile time computation, that can allow for advanced static code generation that enables libraries like Eigen. Rust on the other hand provides no answer to compile time computation apart from syntax extensions, of which I have written about previously.
Conclusion

Rust's current generics are powerful, safe, and provide excellent errors at compile time. They will most likely serve it well heading into the 1.0 release cycle. However templates are still more flexible and expressive. Whether Rust would benefit from having a templated extension to the language in the future is up for debate (I am not even sure), but we should be up front about the both the positives and negatives when comparing Rust to C++.

This was posted as a comment on /r/rust.
Disclaimer: I am still relatively inexperienced, so I could have made some mistakes and omissions, especially when talking about C++'s templates. Feel free to correct me.