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:
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:
- 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()
}
- 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]
- 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]
}
- 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"
- 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
}
- 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:
- 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
}
}
- 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
}
}
- 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
}
}
- 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
}
- 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:
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.
Comments