Torturing Rustc by Emulating HKTs
3 days ago
- #Type Systems
- #Rust
- #Functional Programming
- The author attempted to create a functional programming scripting language and encountered issues with Rust's lack of Higher Kinded Types (HKTs).
- Higher Kinded Types (HKTs) allow generics to have generics, which Rust does not natively support, leading to workarounds using Generic Associated Types (GATs).
- The author explored mathematical concepts like induction and coinduction to understand Rust's trait solver behavior, particularly with recursive types.
- A minimal reproducible example demonstrated an inductive cycle in Rust's trait resolution, causing a compiler error.
- The author experimented with Lean 4 to formalize proofs related to type systems, highlighting the connection between mathematical proofs and programming (Curry-Howard Isomorphism).
- Rust's trait solver uses inductive reasoning, which fails with infinite proof trees, whereas coinductive traits (like auto-traits) can handle cycles.
- The author humorously critiques Rust's limitations and complexity, while acknowledging the educational value of exploring these topics.