414 Fundamental

414: Recursive Macro Patterns

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "414: Recursive Macro Patterns" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Some computations and code generation tasks have naturally recursive structure: counting elements, reversing lists, checking if a value equals any of N options. Key difference from OCaml: 1. **Compile vs. runtime**: Rust macro recursion is compile

Tutorial

The Problem

Some computations and code generation tasks have naturally recursive structure: counting elements, reversing lists, checking if a value equals any of N options. In functions, recursion is straightforward. In macros, recursion works by having one arm handle the base case (empty input) and another arm peel off one element and recursively invoke the macro on the remainder. This compile-time recursion is bounded by Rust's macro_recursion_limit (default 128) and computes entirely at compile time, producing efficient code with no runtime recursion.

Recursive macros are used in matches!, compile-time string concatenation, recursive DSL parsers, and any macro needing to process a variable-length input sequentially.

🎯 Learning Outcomes

• Understand how recursive macros use base case and inductive step arms

• Learn the @acc (accumulator) pattern for building up results recursively

• See how count! uses 1 + count!(rest) to count at compile time

• Understand the reverse_list!(@acc [...] ...) pattern for tail-recursive macros

• Learn about the recursion_limit attribute and when to increase it

Code Example

macro_rules! count {
    () => { 0 };
    ($head:expr $(, $tail:expr)*) => {
        1 + count!($($tail),*)
    };
}

macro_rules! reverse_list {
    (@acc [$($acc:expr),*]) => { [$($acc),*] };
    (@acc [$($acc:expr),*] $head:expr $(, $tail:expr)*) => {
        reverse_list!(@acc [$head $(, $acc)*] $($tail),*)
    };
    ($($x:expr),*) => { reverse_list!(@acc [] $($x),*) };
}

fn main() {
    println!("count: {}", count!(1, 2, 3, 4, 5));
    let rev = reverse_list![1, 2, 3];
}

let rec count = function
  | [] -> 0
  | _ :: t -> 1 + count t

let rec reverse_acc acc = function
  | [] -> acc
  | h :: t -> reverse_acc (h :: acc) t

let reverse lst = reverse_acc [] lst

let () =
  Printf.printf "count: %d\n" (count [1;2;3;4;5]);
  Printf.printf "reverse: %s\n" 
    (String.concat "," (List.map string_of_int (reverse [1;2;3])))

Key Differences

Compile vs. runtime: Rust macro recursion is compile-time token transformation; OCaml's equivalent would use module system recursion or PPX, both more heavyweight.

Recursion limit: Rust imposes a recursion_limit (default 128, adjustable with #![recursion_limit = "512"]); OCaml has no equivalent constraint.

Accumulator pattern: The @acc arm naming convention is a Rust macro idiom for internal state; OCaml uses standard accumulating function parameters.

Error locality: Rust macro recursion errors can produce deep expansion traces; OCaml recursive function errors appear at the function definition or call site.

OCaml Approach

OCaml PPX generates recursive code via recursive OCaml functions operating on AST nodes. A compile-time list-reversal PPX processes the actual list data during compilation. OCaml's let[@unrolled] rec attribute can unroll recursive functions. For true compile-time computation, OCaml uses its module system with recursive functors, though these are rarer than Rust's macro recursion.

Full Source

#![allow(clippy::all)]
//! Recursive Macro Patterns
//!
//! Macros that call themselves for compile-time computation.

/// Count elements at compile time.
#[macro_export]
macro_rules! count {
    () => { 0usize };
    ($head:expr $(, $tail:expr)*) => {
        1usize + count!($($tail),*)
    };
}

/// Reverse an array at compile time using accumulator pattern.
#[macro_export]
macro_rules! reverse_list {
    // Internal: accumulator-based recursion
    (@acc [$($acc:expr),*]) => {
        [$($acc),*]
    };
    (@acc [$($acc:expr),*] $head:expr $(, $tail:expr)*) => {
        reverse_list!(@acc [$head $(, $acc)*] $($tail),*)
    };
    // Public entry point
    ($($x:expr),* $(,)?) => {
        reverse_list!(@acc [] $($x),*)
    };
}

/// Check if value equals any of the options.
#[macro_export]
macro_rules! one_of {
    ($val:expr, $single:expr) => {
        $val == $single
    };
    ($val:expr, $first:expr $(, $rest:expr)+) => {
        $val == $first || one_of!($val $(, $rest)+)
    };
}

/// Concatenate strings with separator.
#[macro_export]
macro_rules! join_with {
    ($sep:expr; $single:expr) => {
        $single.to_string()
    };
    ($sep:expr; $first:expr $(, $rest:expr)+) => {
        format!("{}{}{}", $first, $sep, join_with!($sep; $($rest),+))
    };
}

/// Sum values recursively.
#[macro_export]
macro_rules! sum_rec {
    () => { 0 };
    ($single:expr) => { $single };
    ($first:expr $(, $rest:expr)+) => {
        $first + sum_rec!($($rest),+)
    };
}

/// Maximum of values recursively.
#[macro_export]
macro_rules! max_rec {
    ($single:expr) => { $single };
    ($a:expr, $b:expr) => {
        if $a > $b { $a } else { $b }
    };
    ($first:expr $(, $rest:expr)+) => {
        {
            let rest_max = max_rec!($($rest),+);
            if $first > rest_max { $first } else { rest_max }
        }
    };
}

/// Generate nested tuples (cons-list style).
#[macro_export]
macro_rules! nested_tuple {
    ($single:expr) => { $single };
    ($head:expr, $($tail:expr),+) => {
        ($head, nested_tuple!($($tail),+))
    };
}

/// Power of 2 at compile time (for small n).
#[macro_export]
macro_rules! pow2 {
    (0) => {
        1usize
    };
    (1) => {
        2usize
    };
    (2) => {
        4usize
    };
    (3) => {
        8usize
    };
    (4) => {
        16usize
    };
    (5) => {
        32usize
    };
    (6) => {
        64usize
    };
    (7) => {
        128usize
    };
    (8) => {
        256usize
    };
}

#[cfg(test)]
mod tests {
    #[test]
    fn test_count_empty() {
        assert_eq!(count!(), 0);
    }

    #[test]
    fn test_count_single() {
        assert_eq!(count!(42), 1);
    }

    #[test]
    fn test_count_multiple() {
        assert_eq!(count!(1, 2, 3, 4, 5), 5);
    }

    #[test]
    fn test_reverse_list() {
        let rev = reverse_list![1, 2, 3, 4, 5];
        assert_eq!(rev, [5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_reverse_list_empty() {
        let rev: [i32; 0] = reverse_list![];
        assert_eq!(rev, []);
    }

    #[test]
    fn test_one_of_true() {
        assert!(one_of!(3, 1, 2, 3, 4, 5));
    }

    #[test]
    fn test_one_of_false() {
        assert!(!one_of!(10, 1, 2, 3, 4, 5));
    }

    #[test]
    fn test_one_of_single() {
        assert!(one_of!(42, 42));
        assert!(!one_of!(42, 0));
    }

    #[test]
    fn test_join_with() {
        assert_eq!(join_with!(", "; "a", "b", "c"), "a, b, c");
        assert_eq!(join_with!("-"; "x"), "x");
    }

    #[test]
    fn test_sum_rec() {
        assert_eq!(sum_rec!(), 0);
        assert_eq!(sum_rec!(5), 5);
        assert_eq!(sum_rec!(1, 2, 3, 4), 10);
    }

    #[test]
    fn test_max_rec() {
        assert_eq!(max_rec!(42), 42);
        assert_eq!(max_rec!(3, 7), 7);
        assert_eq!(max_rec!(5, 2, 9, 1, 6), 9);
    }

    #[test]
    fn test_nested_tuple() {
        let t = nested_tuple!(1, 2, 3);
        assert_eq!(t, (1, (2, 3)));
    }

    #[test]
    fn test_pow2() {
        assert_eq!(pow2!(0), 1);
        assert_eq!(pow2!(3), 8);
        assert_eq!(pow2!(8), 256);
    }
}

(* Recursive macros in OCaml — demonstrated via recursive functions *)

(* Stack-based reverse using recursion *)
let rec reverse_acc acc = function
  | [] -> acc
  | x :: xs -> reverse_acc (x :: acc) xs

let reverse xs = reverse_acc [] xs

(* Recursive list processor *)
let rec process_ops acc = function
  | [] -> acc
  | `Add n :: rest -> process_ops (acc + n) rest
  | `Sub n :: rest -> process_ops (acc - n) rest
  | `Mul n :: rest -> process_ops (acc * n) rest

let () =
  Printf.printf "reverse [1;2;3;4;5] = [%s]\n"
    (String.concat ";" (List.map string_of_int (reverse [1;2;3;4;5])));
  let result = process_ops 0 [`Add 10; `Mul 3; `Sub 5] in
  Printf.printf "ops result = %d\n" result

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    #[test]
    fn test_count_empty() {
        assert_eq!(count!(), 0);
    }

    #[test]
    fn test_count_single() {
        assert_eq!(count!(42), 1);
    }

    #[test]
    fn test_count_multiple() {
        assert_eq!(count!(1, 2, 3, 4, 5), 5);
    }

    #[test]
    fn test_reverse_list() {
        let rev = reverse_list![1, 2, 3, 4, 5];
        assert_eq!(rev, [5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_reverse_list_empty() {
        let rev: [i32; 0] = reverse_list![];
        assert_eq!(rev, []);
    }

    #[test]
    fn test_one_of_true() {
        assert!(one_of!(3, 1, 2, 3, 4, 5));
    }

    #[test]
    fn test_one_of_false() {
        assert!(!one_of!(10, 1, 2, 3, 4, 5));
    }

    #[test]
    fn test_one_of_single() {
        assert!(one_of!(42, 42));
        assert!(!one_of!(42, 0));
    }

    #[test]
    fn test_join_with() {
        assert_eq!(join_with!(", "; "a", "b", "c"), "a, b, c");
        assert_eq!(join_with!("-"; "x"), "x");
    }

    #[test]
    fn test_sum_rec() {
        assert_eq!(sum_rec!(), 0);
        assert_eq!(sum_rec!(5), 5);
        assert_eq!(sum_rec!(1, 2, 3, 4), 10);
    }

    #[test]
    fn test_max_rec() {
        assert_eq!(max_rec!(42), 42);
        assert_eq!(max_rec!(3, 7), 7);
        assert_eq!(max_rec!(5, 2, 9, 1, 6), 9);
    }

    #[test]
    fn test_nested_tuple() {
        let t = nested_tuple!(1, 2, 3);
        assert_eq!(t, (1, (2, 3)));
    }

    #[test]
    fn test_pow2() {
        assert_eq!(pow2!(0), 1);
        assert_eq!(pow2!(3), 8);
        assert_eq!(pow2!(8), 256);
    }
}

Deep Comparison

OCaml vs Rust: Recursive Macros

Side-by-Side Code

OCaml — Recursive functions

let rec count = function
  | [] -> 0
  | _ :: t -> 1 + count t

let rec reverse_acc acc = function
  | [] -> acc
  | h :: t -> reverse_acc (h :: acc) t

let reverse lst = reverse_acc [] lst

let () =
  Printf.printf "count: %d\n" (count [1;2;3;4;5]);
  Printf.printf "reverse: %s\n" 
    (String.concat "," (List.map string_of_int (reverse [1;2;3])))

Rust — Recursive macros

macro_rules! count {
    () => { 0 };
    ($head:expr $(, $tail:expr)*) => {
        1 + count!($($tail),*)
    };
}

macro_rules! reverse_list {
    (@acc [$($acc:expr),*]) => { [$($acc),*] };
    (@acc [$($acc:expr),*] $head:expr $(, $tail:expr)*) => {
        reverse_list!(@acc [$head $(, $acc)*] $($tail),*)
    };
    ($($x:expr),*) => { reverse_list!(@acc [] $($x),*) };
}

fn main() {
    println!("count: {}", count!(1, 2, 3, 4, 5));
    let rev = reverse_list![1, 2, 3];
}

Comparison Table

Aspect	OCaml Functions	Rust Macros
When runs	Runtime	Compile time
Recursion limit	Stack (TCO helps)	Expansion limit (~128)
Accumulator	Function parameter	Internal `@acc` pattern
Type checking	Static, once	Per expansion site

The Accumulator Pattern

For compile-time list reversal:

macro_rules! reverse_list {
    // Internal rules (start with @)
    (@acc [$($acc:expr),*]) => {
        [$($acc),*]  // Base: return accumulated
    };
    (@acc [$($acc:expr),*] $head:expr $(, $tail:expr)*) => {
        // Move head to front of accumulator, recurse with tail
        reverse_list!(@acc [$head $(, $acc)*] $($tail),*)
    };
    // Public entry point
    ($($x:expr),*) => {
        reverse_list!(@acc [] $($x),*)  // Start with empty acc
    };
}

The @acc prefix marks internal rules that users shouldn't call directly.

5 Takeaways

Macros recurse at compile time, not runtime.

The result is fully expanded before execution.

**Use @internal patterns for helper rules.**

Keeps the public API clean.

Accumulator pattern works in macros too.

Same technique as tail-recursive functions.

Rust has a recursion limit (~128).

Very deep macro recursion will fail to compile.

Each expansion is type-checked independently.

Errors show up at call sites, not macro definition.

Exercises

Compile-time sum: Implement const_sum!(1, 2, 3, 4, 5) that expands to the literal sum 1 + 2 + 3 + 4 + 5 and verify with const SUM: i32 = const_sum!(1, 2, 3).

Unique macro: Write unique_types!(i32, f64, i32, String, f64) using recursive macro expansion to deduplicate types and generate a tuple type containing only unique types from the list.

Zip lists: Implement zip!(($a1, $a2, ...), ($b1, $b2, ...)) using recursive macro arms that peel one element from each list per step and accumulate ($a1, $b1) pairs.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust