This article explores the fascinating journey of attempting to emulate higher-kinded types in Rust, which unexpectedly leads to deep insights into mathematical logic, type theory, and compiler behavior. The author discovers that their attempts to create recursive type definitions trigger an inductive cycle in Rust's trait solver, exposing fundamental limitations in how Rust handles recursive type relationships.
The article begins with the author's seemingly straightforward goal: creating a scripting language with flexible type wrappers. Their initial attempt to abstract over different wrapper types (Spanned and Simple) leads them to desire higher-kinded types (HKTs), a feature that Rust doesn't natively support. The author provides an excellent explanation of what HKTs are, comparing them to type constructors that can be passed as generics - essentially "functions" that operate on types to produce new types.
The workaround they discover is using Generic Associated Types (GATs), which the author aptly describes as "discount HKTs." This approach allows them to create a trait with an associated type that can be parameterized, effectively emulating some aspects of HKTs. However, when they attempt to derive PartialEq on their recursive type definitions, they encounter an overflow error in the trait solver: "overflow evaluating the requirement Wrapper<Ast<SpannedMarker>, std::range::Range<usize>>: PartialEq.
This error leads the author on an intellectual journey through mathematical logic and type theory. They explore the concepts of induction and coinduction, explaining how mathematical induction works for proving properties of natural numbers, and how this concept extends to structural induction for more complex data types. The author connects this to the Curry-Howard correspondence, which establishes an isomorphism between proofs and programs - a profound insight that connects mathematical logic to type theory.
The author then experiments with Lean 4, a theorem prover, to implement and prove properties about inductively defined sets. This section demonstrates the practical application of the theoretical concepts they've been exploring, showing how they can define inductive types in Lean and prove properties about them using induction principles.
Returning to the original Rust problem, the author explains that the issue stems from Rust's trait solver using inductive reasoning, which requires finite proof trees. Their recursive type definitions create infinite proof trees that can't be resolved using induction alone. While Rust does support coinduction for certain traits (auto-traits, Sized, and WF-goals), PartialEq is not among them, leading to the overflow error.
The author then discovers a way to trigger an internal compiler error (ICE) using the next-generation trait solver, demonstrating that even the improved solver has limitations when dealing with coinductive reasoning. They provide a minimal reproducible example that causes the compiler to crash with an ICE when using specific compiler flags.
The implications of this exploration are significant. It highlights the tension between expressive type systems and compiler complexity. While Rust's conservative approach to type features ensures predictable compilation times and avoids undecidable type inference, it also prevents certain elegant abstractions that HKTs would enable. The author's journey shows that even seemingly simple type definitions can lead to complex theoretical problems when recursive relationships are involved.
From a broader perspective, this article illustrates how programming language design involves trade-offs between expressiveness, complexity, and decidability. The fact that the next-generation Rust trait solver still struggles with certain cases suggests that implementing full HKT support or coinductive reasoning for all traits is a non-trivial problem that requires careful consideration of these trade-offs.
The author's frustration with Rust's limitations is understandable, but their exploration also reveals the deep mathematical foundations underlying type systems. Their journey from a practical programming problem to mathematical logic and back again demonstrates the beautiful connections between different areas of computer science and mathematics.
In conclusion, this article is not just about a specific Rust limitation but about the fascinating interplay between practical programming, type theory, and mathematical logic. It shows how even seemingly simple language features can touch on profound theoretical concepts, and how exploring these boundaries can lead to deeper understanding of both programming languages and mathematics.
Comments
Please log in or register to join the discussion