Generics and const generics in Rust

Normally we write a function or any user-defined type for solving a particular task by accepting Concrete type i.e the type is known when we pass it to them.

fn sum_i32(i: &[i32]) -> i32 {
    i.iter().sum()
}
fn sum_f32(i: &[f32]) -> f32 {
    i.iter().sum()
}
fn sum_i8(i: &[i8]) -> i8 {
    i.iter().sum()
}
    println!("{}", sum_i8(&[1i8, 4, 6, 7]));
    println!("{}", sum_i32(&[1, 2, 3, 4]));
    println!("{}", sum_f32(&[1.0f32, 2.0, 3.0, 4.0]));

In above code is used to sum the elements of a given slice. The problem here is, there are a total of ten Integers types, and two Floating types exist in Rust.

If we were to write the sum function for each type then we have totally had twelve implementations just for the summing task. What about other tasks like finding an element in a slice, the same amount of implementation is needed for every type we care about. Not only do we have more code for a simple task but also testing them is also nontrivial since we have to write a different test for the same type and for other types which increases the code size even more which in turn increases the possibility of bugs.

This is the same for any task that involves the same algorithm for different types. To remedy this, a programming language must provide a way to abstract over algorithms by defining generically rather than just concretely like our above code.

Each language provides some way to define them, here we see how Rust is able to define them generically and also the implication of that implementation. Before going into rust generics we have to talk about some glossaries related to Generics.

• Generic type or Abstract type: These are placeholder types such as T, A, or Service for the concrete type when we call them.
• Concrete Type: The actual type of the variable when we call it. For example, when we call the sum_u32 function with a slice of u32s, there is no abstraction.
• Static Dispatch: Note that not all languages, such as Python, Perl, and Ruby, know the type at compile time. Knowing the type at compile time allows the compiler to generate optimized code without any runtime overhead. This is called Monomorphization, i.e., the compiler generates a specific implementation for the type being called at compile time. This is not specific to generics; in fact, the compiler generates optimized code if the type is known at compile time, which is why a statically typed language is more efficient than a dynamically typed language where the type is only known at runtime. The downside of static dispatch is that it increases compile time and binary size because the compiler generates more code behind the scenes, even though it looks simple in our source code.
• Dynamic or Virtual Dispatch: Even in statically/compiled languages, having the type known at runtime provides flexibility and other advantages. This reduces the binary size and compile time since we don't need to generate any code until runtime. To correctly call the methods at runtime, the language has a pointer to them. In Rust, this is accomplished by a fat pointer, a two-word size, i.e., 16 bytes or 128 bits. No matter how many methods they have, the size is always 16 bytes at compile time.

Generics is a way to reuse the code or algorithm if they share some common operation and properties. And avoid the much boilerplate code significantly thus reducing the source code size which in turn represents less code maintenance and fewer bugs.

Advantage of Generics:

Benefits of Generics in the Context of Rust.

• Provide some form of abstraction since we don't have to know the details of implementation; we only need to know how to use them. Rust or C++ abstractions are zero cost in that what you don't use, you don't have to pay any cost, and also what you do use, you can't hand-code any better (Bjarne Stroustrup).
• Achieves polymorphism via traits because it can accept different types rather than a single concrete type.
• Type safety: The trait bounds protect us from passing an invalid type to the API either at compile time through static dispatch or at runtime through dynamic dispatch. This is similar to type classes in Haskell or C++ concepts for constraining types.
• Testing is less trivial than the nongeneric version since we only check the output for a different type with the same implementation. If bugs are identified through testing, then we just update the single implementation to reflect them in each type we used, which reduces the development time.
• Type inference: Rust is able to infer type most of the time without more explicit types.
• Code is more organized.
• Aid in better API design.

All the codes below are statically dispatched.

The Actual generic implementation of the above code is,

use std::iter::Sum;
fn main() {
    println!(
        "i8 Sum: {} \nu16 Sum: {} \nusize Sum: {} \nf64 Sum: {} \nf32 Sum: {} ",
        generic_sum(&[1i8, 4, 6, 7]), //The actual type is known at this line and the same for all calls.
        generic_sum(&[1u16, 5, 9, 56]),
        generic_sum(&[9usize, 34, 53, 57]),
        generic_sum(&[1.9, 4.6, 6.7, 7.9]),
        generic_sum(&[1.0f32, 2.0, 3.0, 4.0])
    );
}
//Generic Definition of the sum of elements.
fn generic_sum<T: Sum<T> + Copy>(slices: &[T]) -> T {
    slices.iter().map(|item| *item).sum()
    // or
    //slices.iter().copied().sum()
}

The type T is a generic type, and after the colon, they are called trait bounds which specify not just any type but only a type that implements both the Sum and Copy traits. This is the reason why Rust code like the one below won't even compile in the first place because not all types can be added. Here, Rust provides safety at compile time, and error messages give more context to the problem, unlike C++ templates.

fn add<T>(x:T,y:T)->T{
   return x+y;
}

The above code forces you to constrain the types, hence saving us from meaningless runtime errors later.

We can define as many types as we want in the function signature. But it's better to use a few types though.

fn add_mul<A, B>(x: A, y: A, w: B, z: B) -> B
where
    A: Add<A> + Copy,
    B: Mul<B, Output = B> + Copy,
{
    let var = x + y;
    w * z
}

Const Generics are generic over values rather than types. This is useful in a situation where we want the values to be generic instead of specific values when defining tasks. Const generics only support Integers, Bool, Char types in the stable channel as of this writing.

use std::fmt::{Debug, Display};
use std::iter::Sum;
use std::ops::{Add, Mul};
fn main() {
     //This is how we specify the type generic type explicitly.
   //In this code rust won't be able to infer the type themselves.
    const_generics1::<true, &str>("string");
    const_generics1::<false, i32>(67);

    //In this code rust is able to infer both the type and value.
    const_generics2([1, 2, 3, 4]);
    const_generics2(['a', 'b', 'c']);//[i32;4]
    let m: [char; 3] = ['a', 'b', 'a'];//[char;3]
}
fn const_generics1<const A: bool, T: Display>(i: T) {
    if A {
        println!("This is True");
    } else {
        println!("This is false");
    }
    println!("{}", i);
}
fn const_generics2<T, const N: usize>(i: [T; N])
where
    T: Debug,
{
    println!("{:?}", i);
}

Const generics are value not type, meaning we can't use them in places where the type is required. In array type [T;N], the T is a Type and N is value.

//Using const values as type is a compile error.
fn const_generics3<const T:char,const N:usize>(i:[T;N])
{
}

Here we can't use the const generics in the T place but can be used in the Nplace. Using const generics, we can encode invariants into our types without encountering them at runtime. If it compiles, there are no misconceptions at runtime. For example, the code here uses const generics to prevent errors when adding different CUDA (Compute Unified Device Architecture) device data. This would be a runtime error in Python's PyTorch, but in Rust, they are compile-time errors.

Implementing GPU Library in Rust is far more robust than a C implementation and is also able to use high-level language features like closure, and iterators in Low-level GPU code without causing memory error.

All the codes below are Dynamically dispatched

For some types, we can't know the size at compile time to statically dispatch them. Instead, they are used behind a pointer to dispatch dynamically, thus preventing the compiler from performing optimizations like inlining and monomorphization. However, we have the flexibility of dynamic programming languages.

Traits are not types themselves but rather describe the behavior of types in an abstract manner. This is why we can't use traits in places where types are required, as types have a size. For example, primitive types like i32 and f64, as well as arrays, are types and have a fixed size. Trait Objects are unsized, and as such, they must be used behind a pointer to obtain a size at compile time. This is because Rust needs to know the size of all types during compilation. In this context, the term "object" has nothing to do with objects in Object-Oriented Programming.

use std::mem::size_of;
fn main() {
    //let unsize1: ToString;
    //let unsize2: Fn(&str) -> bool;

    //Any type that implements Display trait.
    let sized1: &dyn ToString;
    sized1 = &45;
    let sized2: Box<String>;
    sized2 = Box::new(String::from(
        "Bytes are counted for memory-constrained devices",
    ));
    println!("{:?}", size_of::<&dyn ToString>());
    println!("{:?}", size_of::<Box<dyn Fn(&str) -> bool>>());
    println!("{:?}", size_of::<Box<String>>());
}

If we comment out the first two lines we get a compile error saying "doesn't have a size known at compile-time".

The size of sized1 and sized2 is 16 bytes. This is overhead for sized1 because a plain reference to an i32 is 8 bytes and a non-reference type is 4 bytes. For the sized2 this is an advantage since the plain String type takes 24 bytes but the Box<String> takes 8 bytes. Note that the Box of trait object takes 16 bytes, but the Box of plain types takes 8 bytes. There is a trade-off here. If you want no runtime overhead, then choose static dispatch. If you care about binary size over efficiency, choose dynamic dispatch. These are choices you have, not the default options.

just because the type is known at runtime, it doesn't mean a lack of type safety.

• We can't construct a type that doesn't implement the particular type you specified.
• We can't call a method that is not associated with the traits.

The function signature alone tells us whether they are statically or dynamically dispatched

use std::fmt::Display;
fn static_dispatc(param: impl Display) -> impl Display {
    param
}
fn dynamic_dispatch(param: &dyn Display) -> &dyn Display {
    param
}

If you read the previous post about slices, we can place a trait object behind a pointer, just like how infinite recursion breaks once we put it behind different pointers.

There is another advantage of impl trait. This will also help to avoid concrete type declarations when defining function parameters (both free functions and inherent methods) and return types without imposing any runtime overhead. In the above code, the static_dispatch function can accept any type that implements the Display trait and also return any type that implements the Display trait as well. The arguments and the return type are not required to have the same type, for example, you can pass an i32 value and return a String or a float, as long as both of them implement the common Display trait.

The usage of impl trait is heavily employed in Actix, Axum, and other web frameworks and libraries. Both the Responder trait in Actix and the IntoResponse trait in Axum are implemented for many more types. Without impl trait, the handler function in our backend code would be harder to read, with different types scattered. Look at the code below. Even though each handler function (the function that accepts an HTTP request and returns a response type) returns a different response type, the return type for all these functions is the same,

async fn return_string() -> impl Responder {
    format!("Hello world")
}
async fn return_json() -> impl Responder {
    Json(vec!["some response", "vector"])
}
async fn return_http_response() -> impl Responder {
    HttpResponse::Ok().body("Hey fellows")
}
async fn return_status_Code() -> impl Responder {
    (HttpResponse::Accepted().finish(), StatusCode::ACCEPTED)
}

Generics and Const Generics can be used in structs, enums, and traits too, but they are not covered here. Apart from using generic types and const, Rust also has generic lifetimes, which are generic over the lifetime.

Reference:

Generic Queue: