776 Fundamental

776-const-fn-basics — Const Fn Basics

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "776-const-fn-basics — Const Fn Basics" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. `const fn` allows computations to run at compile time, moving work from program startup to compilation. Key difference from OCaml: 1. **Scope**: Rust's `const fn` can compute arbitrary values at compile time; OCaml's compile

Tutorial

The Problem

const fn allows computations to run at compile time, moving work from program startup to compilation. This eliminates initialization overhead for lookup tables, mathematical constants, and hash seeds. Stabilized incrementally since Rust 1.31, const fn now supports loops, conditional expressions, and recursive functions. It is used in phf (perfect hash functions computed at compile time), const-oid, and array-init crates.

🎯 Learning Outcomes

• Write const fn factorial(n: u64) -> u64 using recursive const fn

• Implement const fn gcd(a, b) and const fn pow(base, exp) for compile-time math

• Use const fn is_prime(n: u64) with a loop (available in const since Rust 1.46)

• Verify results with const X: u64 = factorial(10) — computed at compile time

• Understand which operations are forbidden in const fn (heap allocation, dyn Trait, etc.)

Code Example

pub const fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

// Evaluated at compile time!
pub const FACTORIAL_10: u64 = factorial(10);

(* Evaluated at module init time *)
let factorial_10 = factorial 10

Key Differences

Scope: Rust's const fn can compute arbitrary values at compile time; OCaml's compile-time computation is limited to simple constant folding.

Lookup tables: Rust computes full lookup tables in const fn; OCaml must either hardcode them or compute them at runtime initialization.

Recursion: Rust's const fn supports recursion; OCaml's constant expressions do not.

Restrictions: Rust's const fn cannot use heap allocation, dyn Trait, or floating-point sin/cos (they're not yet stable const); OCaml's limitations are different.

OCaml Approach

OCaml has no direct equivalent of const fn. Values that can be computed at compile time are limited to constant literals and simple arithmetic in module-level let bindings that the compiler evaluates. For lookup tables, OCaml uses [@@unrolled] loops or preprocessor-based code generation. ppx_const provides limited compile-time conditionals. Jane Street's ppx_sexp_conv generates code at compile time but doesn't compute arbitrary values.

Full Source

#![allow(clippy::all)]
//! # Const Fn Basics
//!
//! Functions that can be evaluated at compile time.

/// Factorial computed at compile time
pub const fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

/// GCD at compile time
pub const fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

/// Power at compile time
pub const fn pow(base: u64, exp: u32) -> u64 {
    if exp == 0 {
        1
    } else if exp.is_multiple_of(2) {
        let half = pow(base, exp / 2);
        half * half
    } else {
        base * pow(base, exp - 1)
    }
}

/// Is prime check at compile time
pub const fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    if n == 2 {
        return true;
    }
    if n.is_multiple_of(2) {
        return false;
    }
    let mut i = 3;
    while i * i <= n {
        if n.is_multiple_of(i) {
            return false;
        }
        i += 2;
    }
    true
}

/// String length at compile time
pub const fn const_str_len(s: &str) -> usize {
    s.len()
}

/// Check if byte is ASCII digit
pub const fn is_ascii_digit(b: u8) -> bool {
    b >= b'0' && b <= b'9'
}

/// Count digits in number
pub const fn digit_count(mut n: u64) -> usize {
    if n == 0 {
        return 1;
    }
    let mut count = 0;
    while n > 0 {
        count += 1;
        n /= 10;
    }
    count
}

/// Sum of digits
pub const fn digit_sum(mut n: u64) -> u64 {
    let mut sum = 0;
    while n > 0 {
        sum += n % 10;
        n /= 10;
    }
    sum
}

/// Reverse a number
pub const fn reverse_number(mut n: u64) -> u64 {
    let mut reversed = 0;
    while n > 0 {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    reversed
}

// Compile-time constants using const fn
pub const FACTORIAL_10: u64 = factorial(10);
pub const GCD_48_18: u64 = gcd(48, 18);
pub const TWO_TO_10: u64 = pow(2, 10);
pub const IS_17_PRIME: bool = is_prime(17);

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_factorial() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(1), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(FACTORIAL_10, 3628800);
    }

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(48, 18), 6);
        assert_eq!(gcd(17, 13), 1);
        assert_eq!(GCD_48_18, 6);
    }

    #[test]
    fn test_pow() {
        assert_eq!(pow(2, 0), 1);
        assert_eq!(pow(2, 10), 1024);
        assert_eq!(pow(3, 4), 81);
        assert_eq!(TWO_TO_10, 1024);
    }

    #[test]
    fn test_is_prime() {
        assert!(!is_prime(0));
        assert!(!is_prime(1));
        assert!(is_prime(2));
        assert!(is_prime(17));
        assert!(!is_prime(18));
        assert!(IS_17_PRIME);
    }

    #[test]
    fn test_digit_count() {
        assert_eq!(digit_count(0), 1);
        assert_eq!(digit_count(5), 1);
        assert_eq!(digit_count(123), 3);
        assert_eq!(digit_count(1000), 4);
    }

    #[test]
    fn test_digit_sum() {
        assert_eq!(digit_sum(123), 6);
        assert_eq!(digit_sum(999), 27);
    }

    #[test]
    fn test_reverse_number() {
        assert_eq!(reverse_number(123), 321);
        assert_eq!(reverse_number(100), 1);
    }

    // Compile-time test via const
    const _: () = {
        assert!(factorial(5) == 120);
        assert!(gcd(12, 8) == 4);
    };
}

(* const fn concept in OCaml
   OCaml evaluates module-level `let` at load time, not truly at compile time.
   We compare this to Rust's guarantee of compile-time evaluation. *)

(* These are computed at module initialization (load time, not compile time in OCaml) *)
let factorial n =
  let rec go acc n = if n <= 1 then acc else go (acc * n) (n - 1) in
  go 1 n

let fac10 = factorial 10        (* computed once at load time *)
let fac12 = factorial 12

(* Powers of two table *)
let pow2 n =
  let rec go acc n = if n = 0 then acc else go (acc * 2) (n - 1)
  in go 1 n

let pow2_table = Array.init 16 pow2   (* [1; 2; 4; 8; ...] *)

(* String hashing — FNV-1a *)
let fnv1a_32 s =
  let offset_basis = 0x811c9dc5l in
  let prime = 0x01000193l in
  String.fold_left (fun hash c ->
    let hash = Int32.logxor hash (Int32.of_int (Char.code c)) in
    Int32.mul hash prime
  ) offset_basis s

let hello_hash = fnv1a_32 "hello"  (* computed once *)

let () =
  Printf.printf "10! = %d\n" fac10;
  Printf.printf "12! = %d\n" fac12;
  Printf.printf "2^8 = %d\n" pow2_table.(8);
  Printf.printf "FNV32(\"hello\") = %ld\n" hello_hash

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_factorial() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(1), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(FACTORIAL_10, 3628800);
    }

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(48, 18), 6);
        assert_eq!(gcd(17, 13), 1);
        assert_eq!(GCD_48_18, 6);
    }

    #[test]
    fn test_pow() {
        assert_eq!(pow(2, 0), 1);
        assert_eq!(pow(2, 10), 1024);
        assert_eq!(pow(3, 4), 81);
        assert_eq!(TWO_TO_10, 1024);
    }

    #[test]
    fn test_is_prime() {
        assert!(!is_prime(0));
        assert!(!is_prime(1));
        assert!(is_prime(2));
        assert!(is_prime(17));
        assert!(!is_prime(18));
        assert!(IS_17_PRIME);
    }

    #[test]
    fn test_digit_count() {
        assert_eq!(digit_count(0), 1);
        assert_eq!(digit_count(5), 1);
        assert_eq!(digit_count(123), 3);
        assert_eq!(digit_count(1000), 4);
    }

    #[test]
    fn test_digit_sum() {
        assert_eq!(digit_sum(123), 6);
        assert_eq!(digit_sum(999), 27);
    }

    #[test]
    fn test_reverse_number() {
        assert_eq!(reverse_number(123), 321);
        assert_eq!(reverse_number(100), 1);
    }

    // Compile-time test via const
    const _: () = {
        assert!(factorial(5) == 120);
        assert!(gcd(12, 8) == 4);
    };
}

Deep Comparison

OCaml vs Rust: Const Fn Basics

Compile-Time Evaluation

Rust

pub const fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

// Evaluated at compile time!
pub const FACTORIAL_10: u64 = factorial(10);

OCaml

No compile-time evaluation. Closest is:

(* Evaluated at module init time *)
let factorial_10 = factorial 10

Using Const Values

Rust

// Compile-time computed constants
pub const GCD_48_18: u64 = gcd(48, 18);
pub const TWO_TO_10: u64 = pow(2, 10);
pub const IS_17_PRIME: bool = is_prime(17);

// Array sizes from const fn
const SIZE: usize = digit_count(12345); // 5
let arr: [u8; SIZE] = [0; SIZE];

Const Assertions

Rust

const _: () = {
    assert!(factorial(5) == 120);  // Compile-time check!
    assert!(gcd(12, 8) == 4);
};

Key Differences

Aspect	OCaml	Rust
Compile-time eval	None	`const fn`
Static assertions	None	`const { assert!() }`
Array size expr	Literal only	`const fn` result
Pure guarantee	Not enforced	`const` requires pure

Exercises

Write const fn is_power_of_two(n: u64) -> bool and use it in a const_assert! to validate a buffer size at compile time.

Implement const fn nth_fibonacci(n: u32) -> u64 using the iterative approach (more efficient than recursive for const contexts) and compute const FIB_50: u64.

Write const fn count_bits_set(n: u64) -> u32 (popcount) and verify count_bits_set(0b1010_1010) == 4 at compile time.

Open Source Repos

functional-rust

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

Rust