I’ve been on quite the adventure lately. The transition from memory-safe languages to C++ is like going from driving an automatic car with all the safety features to suddenly piloting a manual sports car with no guardrails – exhilarating but terrifying.

My recent fascination with metaprogramming began after I wrote about Rust’s procedural macros. There’s something magical about code that writes other code, and I wanted to explore this concept in both C++ and Rust. So I set myself a challenge inspired by an exercise I encountered while reading the Rust Programming book almost a year ago.

The challenge was deceptively simple: create a function that calculates the median of a sequence of integers, but with a twist – the function should return different types based on the length of the input. If the sequence has an even number of elements, it returns a floating-point number (since the median is the average of the two middle values). If the sequence has an odd number of elements, it returns an integer (the middle value itself). It is not good engineering practice to have a function that is ’type-confused’, but do treat this exercise as purely academic.

The C++ Approach: Template Metaprogramming

C++ template metaprogramming is like mental gymnastics. It’s a compile-time paradigm that feels like you’re writing code in a completely different language. I was fortunate to get help from some C++ wizards I met in a Telegram group, who guided me through this journey.

Here’s the core of my C++ solution:

template <typename... Args, typename = std::enable_if_t<all_same_type_v<Args...>>>
constexpr std::conditional_t<is_size_even_v<sizeof...(Args)>, float, int>
median(Args &&...args)
{
    std::array<int, sizeof...(Args)> sortedArr{std::forward<Args>(args)...};
    std::sort(sortedArr.begin(), sortedArr.end());
    constexpr int N = sizeof...(Args);

    if constexpr (N == 0)
    {
        return 0;
    }

    if constexpr (N % 2 == 0)
    {
        float middle1 = sortedArr[N / 2 - 1];
        float middle2 = sortedArr[N / 2];
        return (middle1 + middle2) / 2;
    }
    else
    {
        return sortedArr[N / 2];
    }
}

The magic happens in the return type: std::conditional_t<is_size_even_v<sizeof...(Args)>, float, int>. This is where C++ decides at compile time what type the function will return based on the number of arguments. If the number of arguments is even, it returns a float; otherwise, it returns an int.

I also created some helper type traits:

template <std::size_t N>
struct IsSizeEven : std::integral_constant<bool, (N % 2) == 0>
{
    static constexpr bool value = std::integral_constant<bool, (N % 2) == 0>::value;

    constexpr bool get() const
    {
        return (N % 2) == 0;
    }
};

template <std::size_t N>
constexpr bool is_size_even_v = IsSizeEven<N>::value;

And to ensure all arguments are of the same type:

template <typename... Args>
struct AllSameType : std::integral_constant<bool, true>
{
    static constexpr bool value = true;

    constexpr bool get() const noexcept
    {
        return value;
    }
};

template <typename Arg1, typename... Args>
struct AllSameType<Arg1, Args...> : std::conjunction<std::is_same<Arg1, Args>...>
{
    static constexpr bool value = std::conjunction<std::is_same<Arg1, Args>...>::value;

    constexpr bool get() const noexcept
    {
        return value;
    }
};

template <typename... _Args>
constexpr bool all_same_type_v = AllSameType<_Args...>::value;

The beauty of C++ templates is that all this happens at compile time. The compiler generates different versions of the median function based on the types and number of arguments. It’s like having a factory that produces custom functions tailored to your specific needs.

I also created an overload that works with std::array:

template <std::size_t N>
constexpr std::conditional_t<(N % 2) == 0, float, int>
median(const std::array<int, N> &arr)
{
    std::array<int, N> sortedArr = arr;
    std::sort(sortedArr.begin(), sortedArr.end());

    if constexpr (N == 0)
    {
        return 0;
    }

    if constexpr (N % 2 == 0)
    {
        float middle1 = sortedArr[N / 2 - 1];
        float middle2 = sortedArr[N / 2];
        return (middle1 + middle2) / 2;
    }
    else
    {
        return sortedArr[N / 2];
    }
}

Testing these functions shows that they work as expected:

C++ Code
Compiling C++...
Compilation successful
Output:

The Rust Approach: Procedural Macros

Rust takes a different approach to metaprogramming. While C++ templates are part of the language itself, Rust’s procedural macros are more like a preprocessing step. They manipulate Rust code as tokens before it’s compiled.

Here’s my procedural macro implementation for the median function:

use proc_macro::{TokenStream, TokenTree};
use proc_macro2::{Span, TokenStream as TokenStream2};
use proc_macro_error::emit_error;
use quote::quote;
use syn::{LitFloat, LitInt};

fn parse_tokenstream(input: TokenStream) -> Vec<u64> {
    let mut numbers = vec![];
    for token in input.into_iter() {
        match token {
            TokenTree::Literal(a) => {
                let span = a.span();
                let source = a.to_string();
                let num_ident = source.parse::<u64>();
                if let Ok(num) = num_ident {
                    numbers.push(num);
                } else {
                    emit_error!(
                        span,
                        "`{}` cannot be parsed into a value of type `u64`",
                        source
                    );
                }
            }
            TokenTree::Punct(_) => {}
            TokenTree::Group(g) => {
                let span = g.span();
                let source = g.to_string();
                emit_error!(span, "`{}` cannot be parsed into a value of type `u64` or into a punctuation, e.g. `,`", source);
            }
            TokenTree::Ident(i) => {
                let span = i.span();
                let source = i.to_string();
                emit_error!(span, "`{}` cannot be parsed into a value of type `u64` or into a punctuation, e.g. `,`", source);
            }
        }
    }
    numbers
}

fn calculate_median_return_f64(mut numbers: Vec<u64>) -> f64 {
    numbers.sort();

    let n = numbers.len();
    if n == 0 {
        return 0.0;
    }

    let middle1 = numbers[n / 2 - 1];
    let middle2 = numbers[n / 2];
    (middle1 + middle2) as f64 / 2.0
}

fn calculate_median_return_u64(mut numbers: Vec<u64>) -> u64 {
    numbers.sort();
    let n = numbers.len();
    numbers[n / 2]
}

fn convert_to_float_if_integer(input: &str) -> String {
    if input.chars().all(|c| c.is_digit(10)) {
        format!("{}.0", input)
    } else {
        input.to_string()
    }
}

pub fn median_impl(input: TokenStream) -> TokenStream2 {
    let punctuated_integers = parse_tokenstream(input);
    let returned_ts = if punctuated_integers.len() % 2 == 0 {
        let median = calculate_median_return_f64(punctuated_integers).to_string();
        let median = convert_to_float_if_integer(&median);
        let median_litfloat = LitFloat::new(median.as_str(), Span::call_site());
        quote!(
          #median_litfloat
        )
    } else {
        let median = calculate_median_return_u64(punctuated_integers).to_string();
        let median_litint = LitInt::new(median.as_str(), Span::call_site());
        quote!(
          #median_litint
        )
    };
    returned_ts
}

This macro parses the input tokens, calculates the median, and then returns either a literal integer or a literal float based on the number of input values. The beauty of Rust’s procedural macros is that they’re written in regular Rust code, which makes them more approachable than C++ templates.

Let’s break down how this procedural macro works:

  1. First, let’s understand the basic structure of a procedural macro:
// This is how you would use the macro
#[proc_macro]
pub fn median(input: TokenStream) -> TokenStream {
    // Convert the input tokens into actual numbers
    let result = median_impl(input);
    // Convert back to the original TokenStream type
    result.into()
}
  1. The token parsing process:
// Example input: median!(1, 2, 3, 4)
fn parse_tokenstream(input: TokenStream) -> Vec<u64> {
    let mut numbers = vec![];
    
    // Tokens can be: Literal(1), Punct(,), Literal(2), etc.
    for token in input.into_iter() {
        match token {
            // Handle actual numbers
            TokenTree::Literal(a) => {
                let source = a.to_string();
                if let Ok(num) = source.parse::<u64>() {
                    numbers.push(num);
                } else {
                    // Error if not a valid number
                    emit_error!(a.span(), "Not a valid number: {}", source);
                }
            }
            // Ignore commas
            TokenTree::Punct(_) => {},
            // Error on other token types
            _ => emit_error!(token.span(), "Invalid token")
        }
    }
    numbers
}

// Usage example:
// Input: median!(1, 2, 3, 4)
// Output: vec![1, 2, 3, 4]
  1. The median calculation functions:
// For even number of elements, returns f64
fn calculate_median_return_f64(mut numbers: Vec<u64>) -> f64 {
    numbers.sort();
    let n = numbers.len();
    
    // Example: [1, 2, 3, 4]
    // middle1 = numbers[1] = 2
    // middle2 = numbers[2] = 3
    // result = (2 + 3) / 2 = 2.5
    let middle1 = numbers[n / 2 - 1];
    let middle2 = numbers[n / 2];
    (middle1 + middle2) as f64 / 2.0
}

// For odd number of elements, returns u64
fn calculate_median_return_u64(mut numbers: Vec<u64>) -> u64 {
    numbers.sort();
    let n = numbers.len();
    
    // Example: [1, 2, 3]
    // result = numbers[1] = 2
    numbers[n / 2]
}
  1. Helper function for float formatting:
// Ensures that integer values are displayed as floats
fn convert_to_float_if_integer(input: &str) -> String {
    if input.chars().all(|c| c.is_digit(10)) {
        // Convert "5" to "5.0"
        format!("{}.0", input)
    } else {
        // Leave "5.5" as is
        input.to_string()
    }
}

// Examples:
// convert_to_float_if_integer("5") -> "5.0"
// convert_to_float_if_integer("5.5") -> "5.5"
  1. The main implementation that ties everything together:
pub fn median_impl(input: TokenStream) -> TokenStream2 {
    // Parse the input tokens into numbers
    let numbers = parse_tokenstream(input);
    
    // Choose return type based on length
    let returned_ts = if numbers.len() % 2 == 0 {
        // Even length: return f64
        let median = calculate_median_return_f64(numbers).to_string();
        let median = convert_to_float_if_integer(&median);
        // Create a float literal token
        let median_litfloat = LitFloat::new(median.as_str(), Span::call_site());
        quote!(#median_litfloat)
    } else {
        // Odd length: return u64
        let median = calculate_median_return_u64(numbers).to_string();
        // Create an integer literal token
        let median_litint = LitInt::new(median.as_str(), Span::call_site());
        quote!(#median_litint)
    };
    returned_ts
}
  1. Example usage and expansion:
// Input code:
let result = median!(1, 2, 3, 4);

// What the macro expands to (even number of elements):
let result = 2.5;  // f64

// Input code:
let result = median!(1, 2, 3);

// What the macro expands to (odd number of elements):
let result = 2;  // u64

The procedural macro works by taking the input tokens (like 1, 2, 3, 4), parsing them into actual numbers, and calculating the median based on whether there are an odd or even number of elements. It then generates new tokens that represent either a float or integer literal, returning these tokens which the compiler then uses in place of the macro call.

However, there’s a more elegant solution using Rust’s trait system, which I found on the Rust forum.

Let’s break down how this code works step by step:

  1. First, let’s look at the Invertible trait and its implementations:
// The Invertible trait defines a relationship between two types that can be "inverted"
// For example, i64 is invertible with f64 when calculating medians
trait Invertible {
    type Inverse: Invertible;  // The inverse type must also be Invertible
    fn median(values: &[i64]) -> Self;  // Calculate median returning Self type
}

// Implementation for i64 (used for odd number of elements)
impl Invertible for i64 {
    type Inverse = f64;  // i64's inverse is f64
    
    fn median(values: &[i64]) -> Self {
        // For odd number of elements, just take the middle value
        values[values.len() / 2]
    }
}

// Implementation for f64 (used for even number of elements)
impl Invertible for f64 {
    type Inverse = i64;  // f64's inverse is i64
    
    fn median(values: &[i64]) -> Self {
        // For even number of elements, average the two middle values
        (values[values.len() / 2 - 1] as f64 + values[values.len() / 2] as f64) / 2.0
    }
}
  1. Next, let’s understand the HasMedian trait:
// HasMedian trait defines types that can have a median calculated
trait HasMedian {
    type Median: Invertible;  // The median type must be Invertible
    
    fn len() -> usize;  // Returns how many elements this type represents
    fn append(self, vec: &mut Vec<i64>);  // Adds elements to a vector
}

// Implementation for a single i64
impl HasMedian for i64 {
    type Median = i64;  // Single value's median is i64
    
    fn len() -> usize { 1 }  // Single value has length 1
    
    fn append(self, vec: &mut Vec<i64>) {
        vec.push(self);  // Add the value to the vector
    }
}
  1. The recursive tuple implementation for multiple elements:
// Implements HasMedian for tuples of (i64, T) where T also implements HasMedian
// This allows for recursive tuple types like (i64, (i64, (i64, i64)))
impl<T: HasMedian> HasMedian for (i64, T) {
    // The Median type alternates between i64 and f64 based on total length
    type Median = <T::Median as Invertible>::Inverse;
    
    fn len() -> usize { 1 + T::len() }  // Length is 1 plus length of rest
    
    fn append(self, vec: &mut Vec<i64>) {
        self.0.append(vec);  // Add first element
        self.1.append(vec);  // Recursively add rest
    }
}
  1. The median function and macro that ties it all together:
// Generic median function that works with any HasMedian type
fn median<T: HasMedian>(x: T) -> T::Median {
    let mut vec: Vec<i64> = Vec::with_capacity(T::len());
    x.append(&mut vec);  // Collect all values into a vector
    vec.sort_unstable();  // Sort the values
    T::Median::median(&vec)  // Calculate the median
}

// Macro for creating nested tuples easily
macro_rules! list {
    ($value:expr) => { $value };
    ($value:expr, $($rest:expr),* $(,)?) => {
        ($value, list![$($rest),*])
    }
}

// Example usage:
fn main() {
    // Even number of elements (6) returns f64
    let even_median: f64 = median(list![1, 3, 2, 4, 5, 6]);
    println!("Median of even list: {}", even_median);  // Prints 3.5
    
    // Odd number of elements (5) returns i64
    let odd_median: i64 = median(list![1, 3, 2, 4, 5]);
    println!("Median of odd list: {}", odd_median);    // Prints 3
}
  1. Here’s how the type system ensures correct return types:
fn type_examples() {
    // For 1 element: returns i64
    let a: i64 = median(1);
    
    // For 2 elements: returns f64
    let b: f64 = median((1, 2));
    
    // For 3 elements: returns i64
    let c: i64 = median(list![1, 2, 3]);
    
    // For 4 elements: returns f64
    let d: f64 = median(list![1, 2, 3, 4]);
    
    // The pattern continues: odd count → i64, even count → f64
    println!("Types alternate based on count: i64 → f64 → i64 → f64");
}

Here’s a code snippet that you can try running directly in the browser:

Rust Code
Compiling Rust...
Compilation successful
Output:

This implementation showcases several advanced Rust features including associated types with traits, generic implementations, recursive types, macro system for syntax sugar, and type-level programming to determine return types. The elegance of this approach lies in its compile-time guarantees.

The code ensures at compile time that odd number of elements returns i64 while even number of elements returns f64. This isn’t just a runtime behavior - the type system itself enforces these rules statically, making it impossible to use the wrong return type. This demonstrates how Rust’s powerful type system can encode complex logic that would typically require runtime checks in other languages.

This solution uses Rust’s trait system to achieve the same result. The Invertible trait creates a relationship between i64 and f64, where each is the inverse of the other. The HasMedian trait is implemented for single values and tuples, with a recursive structure that flips the return type with each additional element.

The list! macro is a clever way to convert a comma-separated list of values into a nested tuple structure that the HasMedian trait can work with. It’s a beautiful example of how Rust’s type system can be used to achieve compile-time guarantees.

Comparing the Two Approaches

Working with both C++ templates and Rust’s metaprogramming has been an enlightening experience. C++ templates are incredibly powerful but can be difficult to grasp conceptually. They require a deep understanding of the language’s type system and how the compiler processes templates.

Rust’s approach, on the other hand, feels more accessible. Procedural macros are written in regular Rust code, which makes them easier to understand and debug. The trait-based solution is particularly elegant, showcasing Rust’s expressive type system.

Both languages offer powerful tools for metaprogramming, but they approach the problem from different angles. C++ templates are integrated directly into the language, allowing for complex compile-time computations. Rust’s procedural macros are more like a preprocessing step, manipulating Rust code before it’s compiled.

What fascinates me most about both approaches is how they push the boundaries of what’s possible at compile time. They allow us to write code that adapts to different situations without runtime overhead, leading to more efficient and type-safe programs.

My journey into metaprogramming is just beginning, but I’m already captivated by the possibilities. Whether you prefer C++’s template metaprogramming or Rust’s procedural macros and trait system, both offer powerful tools for writing more expressive and efficient code. The mental gymnastics required might be challenging, but the results are well worth the effort.