Hindley-Milner Type Inference & AST Lowering in Rust

The Architecture of Vitalis

The Vitalis compiler is a high-performance self-hosting compiler written from scratch in Rust. It compiles domain logic into native machine code 100x to 6,750x faster than Python. At the core of Vitalis is an implementation of Algorithm W (Hindley-Milner type inference), allowing developers to write clean, untyped code that the compiler strictly proves at compile time without runtime checks.

Unification Algorithm in Rust

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Type {
    Int64,
    Float32,
    Boolean,
    Var(usize),
    Function(Box, Box),
}

pub struct TypeInferenceContext {
    substitutions: std::collections::HashMap,
}

impl TypeInferenceContext {
    pub fn unify(&mut self, t1: &Type, t2: &Type) -> Result<(), String> {
        let t1 = self.resolve(t1);
        let t2 = self.resolve(t2);

        match (t1, t2) {
            (Type::Int64, Type::Int64) => Ok(()),
            (Type::Float32, Type::Float32) => Ok(()),
            (Type::Boolean, Type::Boolean) => Ok(()),
            (Type::Var(id), other) | (other, Type::Var(id)) => {
                self.substitutions.insert(id, other);
                Ok(())
            }
            (Type::Function(a1, r1), Type::Function(a2, r2)) => {
                self.unify(&a1, &a2)?;
                self.unify(&r1, &r2)
            }
            (a, b) => Err(format!("Type mismatch: cannot unify {:?} with {:?}", a, b)),
        }
    }

    fn resolve(&self, t: &Type) -> Type {
        match t {
            Type::Var(id) => self.substitutions.get(id).cloned().unwrap_or_else(|| t.clone()),
            _ => t.clone(),
        }
    }
}