128 Advanced

Type-Level Booleans

Type SystemPhantom TypesCompile-Time Safety

Tutorial Video

Text description (accessibility)

This video demonstrates the "Type-Level Booleans" functional Rust example. Difficulty level: Advanced. Key concepts covered: Type System, Phantom Types, Compile-Time Safety. Encode `true`/`false` as compile-time *types* rather than runtime values, so the compiler can enforce logical constraints (e.g., "both validated AND logging must be enabled before calling `execute()`") without any runtime checks or panics. Key difference from OCaml: 1. **Representation:** OCaml phantom types use a single record with an ignored field; Rust uses `PhantomData<T>` which compiles to nothing.

Tutorial

The Problem

Encode true/false as compile-time types rather than runtime values, so the compiler can enforce logical constraints (e.g., "both validated AND logging must be enabled before calling execute()") without any runtime checks or panics.

🎯 Learning Outcomes

• How zero-sized marker structs (struct True; struct False;) carry type-level information with zero runtime cost

• How PhantomData<T> lets a generic struct hold a type parameter that has no corresponding field

• How implementing a method only on a specific type instantiation (impl Config<True, True>) turns missing setup steps into compile errors

• How associated types in traits (trait Not { type Output: Bool }) encode type-level logic that the compiler evaluates statically

🦀 The Rust Way

Rust uses empty structs (struct True; and struct False;) as type-level labels and PhantomData<V> to include a phantom type parameter in a struct without storing data. Methods are gated by writing impl Config<True, True> — only the fully-setup instantiation exposes execute(). Any attempt to call it prematurely is a compile-time type error, not a runtime panic.

Code Example

use std::marker::PhantomData;

pub struct True;
pub struct False;

pub trait Bool { const VALUE: bool; }
impl Bool for True  { const VALUE: bool = true;  }
impl Bool for False { const VALUE: bool = false; }

// Type-level NOT via associated type
pub trait Not { type Output: Bool; }
impl Not for True  { type Output = False; }
impl Not for False { type Output = True;  }

(* Phantom types: 'b is never stored — it's only a compile-time label *)
type true_t = True_t
type false_t = False_t

type 'b flag = { _phantom : unit }

let mk_true  : true_t  flag = { _phantom = () }
let mk_false : false_t flag = { _phantom = () }

(* GADT-based type-level bool *)
type _ tbool =
  | TTrue  : true_t  tbool
  | TFalse : false_t tbool

Key Differences

Representation: OCaml phantom types use a single record with an ignored field; Rust uses PhantomData<T> which compiles to nothing.

Type-level logic: OCaml reaches for GADTs or module functors for type-level AND/OR; Rust uses traits with associated types (trait And<B> { type Output: Bool }).

Enforcement mechanism: OCaml hides constructors via module signatures; Rust simply doesn't define the method on the wrong type instantiation.

Safety guarantees: Both approaches make invalid states unrepresentable, but Rust's error messages point directly to the missing method call, while OCaml's point to a type mismatch.

OCaml Approach

OCaml uses phantom type parameters — a type variable that appears in the type signature but not in the data representation. type 'b flag = { _phantom : unit } is a record whose field carries no information; only the type parameter 'b distinguishes true_t flag from false_t flag. Module signatures hide constructors so callers cannot forge an invalid state.

Full Source

#![allow(clippy::all)]
//! Example 128: Type-Level Booleans
//!
//! Encode `true`/`false` as *types* instead of values so the compiler enforces
//! logical constraints without any runtime checks.

use std::marker::PhantomData;

// ── Approach 1: Marker structs ────────────────────────────────────────────────
// Two zero-sized structs that act as compile-time labels.

pub struct True;
pub struct False;

/// Lift a type-level boolean to a runtime value.
pub trait Bool {
    const VALUE: bool;
}

impl Bool for True {
    const VALUE: bool = true;
}

impl Bool for False {
    const VALUE: bool = false;
}

// ── Type-level NOT ────────────────────────────────────────────────────────────

pub trait Not {
    type Output: Bool;
}

impl Not for True {
    type Output = False;
}

impl Not for False {
    type Output = True;
}

// ── Type-level AND ────────────────────────────────────────────────────────────

pub trait And<B: Bool> {
    type Output: Bool;
}

impl<B: Bool> And<B> for True {
    type Output = B; // True AND B = B
}

impl<B: Bool> And<B> for False {
    type Output = False; // False AND _ = False
}

// ── Type-level OR ─────────────────────────────────────────────────────────────

pub trait Or<B: Bool> {
    type Output: Bool;
}

impl<B: Bool> Or<B> for True {
    type Output = True; // True OR _ = True
}

impl<B: Bool> Or<B> for False {
    type Output = B; // False OR B = B
}

// ── Approach 2: Builder enforced at compile time ───────────────────────────────
//
// `Config<Validated, Logged>` where each type parameter is either `True` or
// `False`.  The `execute()` method is defined *only* on `Config<True, True>`,
// so calling it before completing both setup steps is a compile error — the
// method simply doesn't exist on the other variants.

pub struct Config<V, L> {
    pub host: String,
    pub port: u16,
    // PhantomData holds the type parameters without storing any data at runtime.
    _validated: PhantomData<V>,
    _logged: PhantomData<L>,
}

impl Config<False, False> {
    pub fn new(host: impl Into<String>, port: u16) -> Self {
        Config {
            host: host.into(),
            port,
            _validated: PhantomData,
            _logged: PhantomData,
        }
    }
}

// validate() is available whenever V = False (transitions V: False → True).
impl<L> Config<False, L> {
    pub fn validate(self) -> Config<True, L> {
        Config {
            host: self.host,
            port: self.port,
            _validated: PhantomData,
            _logged: PhantomData,
        }
    }
}

// enable_logging() is available whenever L = False (transitions L: False → True).
impl<V> Config<V, False> {
    pub fn enable_logging(self) -> Config<V, True> {
        Config {
            host: self.host,
            port: self.port,
            _validated: PhantomData,
            _logged: PhantomData,
        }
    }
}

// execute() only exists on the fully-configured type.
impl Config<True, True> {
    pub fn execute(&self) -> String {
        format!("Executing on {}:{}", self.host, self.port)
    }
}

// ── Approach 3: Tagged value — attach a type-level boolean to any value ────────

pub struct Tagged<T, B> {
    pub value: T,
    _marker: PhantomData<B>,
}

impl<T, B: Bool> Tagged<T, B> {
    pub fn new(value: T) -> Self {
        Tagged {
            value,
            _marker: PhantomData,
        }
    }

    pub fn is_true() -> bool {
        B::VALUE
    }
}

// get_verified() only compiles when the tag is True.
impl<T> Tagged<T, True> {
    pub fn get_verified(&self) -> &T {
        &self.value
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────

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

    #[test]
    fn test_bool_values() {
        assert!(True::VALUE);
        assert!(!False::VALUE);
    }

    #[test]
    fn test_not() {
        assert_eq!(<True as Not>::Output::VALUE, false);
        assert_eq!(<False as Not>::Output::VALUE, true);
    }

    #[test]
    fn test_and() {
        assert_eq!(<True as And<True>>::Output::VALUE, true);
        assert_eq!(<True as And<False>>::Output::VALUE, false);
        assert_eq!(<False as And<True>>::Output::VALUE, false);
        assert_eq!(<False as And<False>>::Output::VALUE, false);
    }

    #[test]
    fn test_or() {
        assert_eq!(<True as Or<True>>::Output::VALUE, true);
        assert_eq!(<True as Or<False>>::Output::VALUE, true);
        assert_eq!(<False as Or<True>>::Output::VALUE, true);
        assert_eq!(<False as Or<False>>::Output::VALUE, false);
    }

    #[test]
    fn test_config_validate_then_log() {
        let result = Config::new("localhost", 8080)
            .validate()
            .enable_logging()
            .execute();
        assert_eq!(result, "Executing on localhost:8080");
    }

    #[test]
    fn test_config_log_then_validate() {
        // Order of setup steps doesn't matter — both paths reach Config<True, True>.
        let result = Config::new("example.com", 443)
            .enable_logging()
            .validate()
            .execute();
        assert_eq!(result, "Executing on example.com:443");
    }

    #[test]
    fn test_tagged_true() {
        let v: Tagged<i32, True> = Tagged::new(42);
        assert_eq!(*v.get_verified(), 42);
        assert!(Tagged::<i32, True>::is_true());
    }

    #[test]
    fn test_tagged_false() {
        let v: Tagged<&str, False> = Tagged::new("hello");
        assert_eq!(v.value, "hello");
        assert!(!Tagged::<i32, False>::is_true());
    }

    #[test]
    fn test_bool_const_evaluation() {
        // Verify that Bool::VALUE can be used in const contexts.
        const T: bool = True::VALUE;
        const F: bool = False::VALUE;
        assert!(T);
        assert!(!F);
    }
}

(* Example 128: Type-Level Booleans in OCaml *)

(* Approach 1: Phantom type booleans using type aliases *)
type true_t = True_t
type false_t = False_t

(* 'b is a phantom parameter — it's never used in the record body *)
type 'b flag = { _phantom : unit }

let mk_true  : true_t  flag = { _phantom = () }
let mk_false : false_t flag = { _phantom = () }

(* Extract the phantom type information at runtime via a module *)
module type BOOL = sig
  type t
  val value : bool
end

module TrueM : BOOL = struct
  type t = true_t
  let value = true
end

module FalseM : BOOL = struct
  type t = false_t
  let value = false
end

(* Approach 2: GADT-based type-level bool for type-safe branching *)
type _ tbool =
  | TTrue  : true_t  tbool
  | TFalse : false_t tbool

let tbool_value : type a. a tbool -> bool = function
  | TTrue  -> true
  | TFalse -> false

(* Approach 3: Builder pattern — track state in phantom parameters *)
(* OCaml uses abstract types and module signatures to hide constructors *)
module Config : sig
  type ('v, 'l) t
  val create        : string -> int -> (false_t, false_t) t
  val validate      : ('v, 'l) t -> (true_t, 'l) t
  val enable_logging: ('v, 'l) t -> ('v, true_t) t
  val execute       : (true_t, true_t) t -> string
end = struct
  type ('v, 'l) t = { host : string; port : int }
  let create host port = { host; port }
  let validate      cfg = { cfg with host = cfg.host }
  let enable_logging cfg = { cfg with host = cfg.host }
  let execute cfg = Printf.sprintf "Executing on %s:%d" cfg.host cfg.port
end

let () =
  assert (TrueM.value  = true);
  assert (FalseM.value = false);
  assert (tbool_value TTrue  = true);
  assert (tbool_value TFalse = false);
  let result =
    Config.(create "localhost" 9000 |> validate |> enable_logging |> execute)
  in
  assert (result = "Executing on localhost:9000");
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_bool_values() {
        assert!(True::VALUE);
        assert!(!False::VALUE);
    }

    #[test]
    fn test_not() {
        assert_eq!(<True as Not>::Output::VALUE, false);
        assert_eq!(<False as Not>::Output::VALUE, true);
    }

    #[test]
    fn test_and() {
        assert_eq!(<True as And<True>>::Output::VALUE, true);
        assert_eq!(<True as And<False>>::Output::VALUE, false);
        assert_eq!(<False as And<True>>::Output::VALUE, false);
        assert_eq!(<False as And<False>>::Output::VALUE, false);
    }

    #[test]
    fn test_or() {
        assert_eq!(<True as Or<True>>::Output::VALUE, true);
        assert_eq!(<True as Or<False>>::Output::VALUE, true);
        assert_eq!(<False as Or<True>>::Output::VALUE, true);
        assert_eq!(<False as Or<False>>::Output::VALUE, false);
    }

    #[test]
    fn test_config_validate_then_log() {
        let result = Config::new("localhost", 8080)
            .validate()
            .enable_logging()
            .execute();
        assert_eq!(result, "Executing on localhost:8080");
    }

    #[test]
    fn test_config_log_then_validate() {
        // Order of setup steps doesn't matter — both paths reach Config<True, True>.
        let result = Config::new("example.com", 443)
            .enable_logging()
            .validate()
            .execute();
        assert_eq!(result, "Executing on example.com:443");
    }

    #[test]
    fn test_tagged_true() {
        let v: Tagged<i32, True> = Tagged::new(42);
        assert_eq!(*v.get_verified(), 42);
        assert!(Tagged::<i32, True>::is_true());
    }

    #[test]
    fn test_tagged_false() {
        let v: Tagged<&str, False> = Tagged::new("hello");
        assert_eq!(v.value, "hello");
        assert!(!Tagged::<i32, False>::is_true());
    }

    #[test]
    fn test_bool_const_evaluation() {
        // Verify that Bool::VALUE can be used in const contexts.
        const T: bool = True::VALUE;
        const F: bool = False::VALUE;
        assert!(T);
        assert!(!F);
    }
}

Deep Comparison

OCaml vs Rust: Type-Level Booleans

Side-by-Side Code

OCaml

(* Phantom types: 'b is never stored — it's only a compile-time label *)
type true_t = True_t
type false_t = False_t

type 'b flag = { _phantom : unit }

let mk_true  : true_t  flag = { _phantom = () }
let mk_false : false_t flag = { _phantom = () }

(* GADT-based type-level bool *)
type _ tbool =
  | TTrue  : true_t  tbool
  | TFalse : false_t tbool

Rust (marker structs + trait)

use std::marker::PhantomData;

pub struct True;
pub struct False;

pub trait Bool { const VALUE: bool; }
impl Bool for True  { const VALUE: bool = true;  }
impl Bool for False { const VALUE: bool = false; }

// Type-level NOT via associated type
pub trait Not { type Output: Bool; }
impl Not for True  { type Output = False; }
impl Not for False { type Output = True;  }

Rust (builder enforced at compile time)

pub struct Config<V, L> {
    host: String,
    port: u16,
    _validated: PhantomData<V>,
    _logged:    PhantomData<L>,
}

// execute() only exists on Config<True, True>
impl Config<True, True> {
    pub fn execute(&self) -> String {
        format!("Executing on {}:{}", self.host, self.port)
    }
}

Type Signatures

Concept	OCaml	Rust
Type-level true	`true_t` (phantom param)	`struct True;`
Type-level false	`false_t` (phantom param)	`struct False;`
Phantom parameter	`'b flag` — `'b` unused in body	`PhantomData<B>`
Runtime reflection	Module value `val value : bool`	`trait Bool { const VALUE: bool }`
Type-level NOT	Separate type families	`trait Not { type Output: Bool }`
Conditional methods	Module functors / GADTs	`impl Config<True, True>`

Key Insights

Phantom types share the core idea — both OCaml and Rust use a type parameter that carries no runtime data; the "value" exists only in the type system.

Rust uses zero-sized structs; OCaml uses type aliases — struct True; compiles to nothing at runtime, exactly like OCaml's type true_t = True_t. Both are erased before execution.

Associated types replace GADT witnesses — OCaml's GADTs (type _ tbool) prove relationships between type indices at match sites. Rust's trait Not { type Output } encodes the same logic as a compiler-verified type mapping.

**impl specialization enforces preconditions** — defining execute() only on Config<True, True> means calling it prematurely is a compile error, not a runtime panic. OCaml achieves this with module signatures that hide the constructor.

**PhantomData prevents variance surprises** — Rust's ownership model requires declaring how a phantom type is used (owned, borrowed, covariant, etc.). PhantomData<V> tells the compiler Config is covariant over V and owns a notional V, which is the correct variance for a state-machine type.

When to Use Each Style

**Use idiomatic Rust (Bool trait + const VALUE) when:** you need to inspect the boolean at runtime (e.g., logging, serialization) while still encoding it as a type.

**Use the builder (impl Config<True, True>) when:** you want compile-time enforcement of a multi-step setup protocol with no runtime cost whatsoever — the type itself becomes the proof.

Exercises

Implement type-level And, Or, and Not operations on your True/False types and write tests that verify them at compile time using trait bounds.

Build a type-level natural number system (Peano encoding) that allows expressing Succ<Succ<Zero>> for two, and implement type-level Add that resolves to the correct type at compile time.

Use type-level booleans to implement a permission system: define CanRead, CanWrite marker types and restrict API methods to only compile when the phantom type parameter satisfies the required capability trait.

Open Source Repos

functional-rust

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

Rust