Torturing Rustc by Emulating HKTs

Torturing rustc by Emulating HKTs, Causing an Inductive Cycle and Borking the Compiler

**Reading time:**32 min read

Table of Contents

Prelude

On the 28th day of February of the year 2026, I was attempting to start writing an FP scripting language for fun.

So I wrote up an Ast

enum for a basic calculator to start:

I realized that I wanted to add a way to include spans when I wanted or not. So here’s something I cooked up:

Of course, since this is my project and I wanted to be a little bit silly, I went ahead and abstract this like a Java Enterprise Software Engineer but in an alternative universe where everything is Haskell.

So uh let’s add that to our Ast

struct.

Uh oh! We forgot something. That is…

Rust does not have HKTs, kinda

Higher kinded types, or HKTs, is the notion that generics can have generics. That is, in something like struct Foo<T>(T<i32>);

, T

would be any specific type that hypothetically accepts one generic type. In that sense, T

is a type constructor that has an arity of one that accepts a generic. In this case, we construct a new type T<i32>

by passing i32

as an argument to the T

type constructor.

…

Okay let’s take a step back.

Type systems usually live in their own universe. They have similar analogues to the current universe we live in. If we have values, the universe above us has types. If we have functions, the universe above us has type constructors. So T

is a “function” accepting a type and returns a new, different type.

Okay you got that? Uh? What’s the “kinded” part mean? What’s a universe?

Uhhhh.

Okay. Let’s think about types. Generic types, that is.

Contrary to some people’s belief, Vec

is not a type.

Huh?

Well, let’s demonstrate:

Let’s follow the logic:

accepts_a_type

, well, accepts a type. Any type, in fact.- We try to pass in a Vec

. - It fails to compile.

• Ergo, Vec

is not a type. - QED.

Such bulletproof logic.

So what is Vec

? By itself, it’s not a type. Vec<i32>

for instance? That’s a type. See:

Tada! Proof by compilation.† † Foreshadowing. 👻

So Vec<i32>

is a type. And i32

is also a type.† † The proof is left as an exercise to the reader. But not Vec

. What is it exactly? In the parlance of type systems, Vec

is a type constructor. You can think of it as fn(type) -> type

, where it accepts a type, i.e. i32

, and spits out a new type Vec<i32>

. Let’s consult the comparison table:

| Values | Types | | |---|---|---| | function | fn(bool) -> bool e.g. unary not ! | fn(type) -> type e.g. Vec | | argument | an bool e.g. true | a type e.g. i32 | | output | an bool e.g. false | a type e.g. Vec<i32> |

Ah, so !

has a type which is effectively fn(bool) -> bool

, † † People would write it as bool -> bool

ala Haskell style. Starting now, let’s write it like that for simplicity and brevity. and !true

has the type bool

. bool

and i32

what people consider a base type, which are primitive to the language itself and cannot be formed with other types. These base types can be rearranged to form different new types, like bool -> bool

and i32 -> String

. An example of an i32 -> String

value is i32::to_string

.

Both bool -> bool

and bool

are types. In other words, bool -> bool

and bool

has the kind type

.

If there are base types, then are there base kinds? Yes! Most languages only have one base kind, the type

kind. Rust has two: the type

kind and the lifetime

kind. Although in this post, we are going to mostly ignore the lifetime

kind.

Next, can we form new kinds from rearranging base kinds? Yes! If we had a bool -> bool

type earlier, then we could have a type -> type

kind. Well, according to the comparison table, we do have a kind in the form of type -> type

, it’s Vec

!

Of course, higher kinded terms like these don’t stop at type -> type

. Result

is type, type -> type

,† † Be quiet, Haskellers, I’m not writing actual Haskell here. and Cow<'a, T>

is lifetime, type -> type

.

Finally we can define some terms. These stuff such as type -> type

are called type operators and type operators that evaluate to a type are called type constructors.

There are even higher order type operators, which are operators that take in type operators. Like (type -> type) -> type

or fn(fn(type) -> type) -> type

. These are what we consider as higher kinded types, since these abstract over type constructors.

Does rust have higher kinded types?

No.† † because Rust is a bad language 😔

Well.

Sorta kinda.

The explanation earlier is not that original; I copied it from the Generic Associate Types RFC. And GATs are kinda discount HKTs, so uh close enough?

The problem we have with the nonexistence of HKTs is that we don’t have a way to pass in type constructors to generics. Take this non-syntactically valid example we introduced earlier.

Theoretically we could pass in a Vec

as a type constructor:

Which when applied gives us effectively a:

But generics only accepts types, not type constructors. We just proved that in our bulletproof earlier before. So what’s the workaround for this?

Enter GATs.

Let’s make up a new trait:

Prior to 1.65, the <T>

part in type Wrapper<T>

isn’t possible. Now, given this newfound power, we can define a dummy marker struct like so:

Now, since VecAsTypeConstructor

is a type and not a type constructor, we can now rewrite Foo

and pass the VecAsTypeConstructor

as a concrete type to the generic.

Let’s check if Bar

’s inner

field is actually of type Vec<i32>

.

Yay! Gets? Okay gets.

Here’s the full code:

Just ugly and nasty. Too bad.

Ugh.

Okay, let’s go back and remind you of our initial problem.

I wanted to make a wrapper type that abstracts between Simple

and Spanned

? Why? Because type-fu is fun!

Anyways, given the newfound Wrap

superpower, let’s rewrite this. On second thought, wrapping every field in W::Wrapper

is a stupid idea. Should have been just the Ast

.

Uhhhh, W::Wrapper<Ast<W>>

?

That looks recursive.

What’s 1 + 1? A trait requirement evaluation overflow, of course

Okay let’s make a simple test. "1 + 1"

should parse to effectively Binary(Value(1), Plus, Value(1))

and evaluate to 2

. A simple calculator! We derive Debug, PartialEq

on all relevant types.

Then wrote this test.

I was using Spanned

as my wrapper in this case.

Anyways, i was gonna run this test.

It should’ve panicked. Because every function was stubbed with todo!()

.

But it gave a compiler error.

Uh oh.

error[E0275]: overflow evaluating the requirement

Wrapper<Ast<SpannedMarker>, std::range::Range<usize>>: PartialEq

What the hell is that?

I tried rewriting the PartialEq

derive manually. No dice.

This error was confusing to me, so I—as a good rustacean would do—made a minimal reproducible example.

I guess a step down from a tree would be a cons list.

Similar error.

I posted this snippet to the RPLCS Discord Server. Fortunately, Helix† † theemathas on GitHub, notable for finding a lot of bugs in rustc. helped with me in debugging this snippet.

After some back and forth with him, the horrible truth set upon me.

Uh oh.

What the fuck is coinduction?

A detour into mathematical proofs and logic

Let’s open the Wikipedia article on “Coinduction”.

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)

This article may be too technical for most readers to understand. (October 2011)

This article relies excessively on references to primary sources. (November 2019)

Okay let’s not.

Let’s do a different link.

Mastering Coinduction in LogicA Comprehensive Guide to Understanding Coinduction Principles in Mathematical Logic

Sarah Lee (AI generated) (Llama-4-Maverick-17B-128E-Instruct-FP8)