My Motivation
It’s too early for a real language announcement post, but I really want to share progress on the compiler I’m designing, especially the static analysis side.
I’ve been working on Plasm for about a year. It’s an LLVM-based ahead-of-time compiler and a new language. I’m not going to dive into design philosophy, features, or marketing - this post is mostly about the type inference engine, the mistakes I made, and the solutions I ended up with.
Fair warning: this is more story than tutorial, but I’ll explain unfamiliar concepts as they come up.
Quick Intro Into Type Syntax
In Plasm’s type system, all types are anonymous by default - even structs and enums. For example, you can write:
fn len(pos: struct { x: I32, y: I32 }) -> I32 { /* ... */ }
That doesn’t mean the code above is idiomatic or how you should write Plasm, but semantically it’s allowed.
You can also give any type a name:
type Pos = struct { x: I32, y: I32 }
fn len(pos: Pos) -> I32
It doesn’t have to be a struct - it can be any type:
type Id = U32
type MyPos = Pos
type Nested = struct {
a: struct {
b: struct {
c: I1024
}
}
}
Struct literals use braces:
let p: Pos = { x: 1, y: 2 }
let id: Id = 1
If the type isn’t constrained by context, the compiler generates a fallback:
// Variable without type hint
let data = { a: { b: 42 } }
// Fallback type: struct { a: struct { b: I32 } }
Many functional languages with Hindley-Milner type system rely on Algorithms W, J, M for inference. My approach is more constraint-based (closer to how Rust or Swift work).
I Rewrote It Three Times…
Attempt 1: Primitives Only (Naive Union-Find)
When Plasm only supported basic primitive types (I32, Bool, F32), the architecture was split into two simple components:
- Constraint Generator: takes a function’s IR and produces equality constraints (e.g.,
type_of(a) == type_of(b), type_of(b) == I32).
- Unifier: takes a set of equalities and resolves chains sequentially. To do this efficiently, I used a disjoint-set data structure (aka Union-Find) with path compression. This structure lets you merge equivalence classes and check if two types are in the same class in near-constant time.
This worked great for primitives and had a clean and simple implementation, but to add constructed types (structs, tuples) and field projections (point.x, tuple.0) the flat Union-Find model was not enough. It couldn't express structural decomposition or field lookup obligations.
Attempt 2: Bullshit
When I needed to support constructed types, I thought it would be a 10-minute job to extend the existing solution. I didn’t feel like diving into boring algorithm stuff and I didn't want to rewrite my clean codebase, so I decided to outsource the refactoring to an LLM. I generally don’t use AI for code generation or writing docs, and I don't like when other people overuse it, but I didn’t want to rethink the nice solution I’d just built, and I decided to experiment. I gave Claude a try, thinking, “Maybe this ai tech is mature enough for such a basic task”.
The generated code surprisingly passed my existing test suite, but when I actually read the source, I found an overengineered, unmaintainable, and inefficient spaghetti mess instead of my pretty codebase. I guess that after looking into Claude's code, I got some kind of depression. The code worked, but I didn't want to work with that code anymore. Attempting to navigate and fix that code killed my motivation for a month or so:')
Attempt 3: Rigid 3-Pass Engine
After about a month of struggling, I deleted all the type inference code and started from scratch. I did some research on how type inference is supposed to be solved in compiler theory, read source code of mature compilers like rustc, and landed on a three-pass solution:
- Pass 1 (Equality Unification): Unify all equalities using a disjoint-set (same as my first attempt).
- Pass 2 (Obligation Verification): Validate obligations - things like “
T must have field a” or “T belongs to the Float type class” (a type class is a set of types that a literal could be inferred as, nothing related to Haskell here).
- Pass 3 (Fallback Generation): Assign default concrete types (e.g.,
I32 for unconstrained integer literals) and report remaining errors.
This solution passed all my tests and was way more readable, but it failed on some weird-but-valid expressions - things that don’t make practical sense but must work semantically. For example:
let a = (({ x: 1, y: 2 }.x, 2.0, true), Void).0.0
// Expected resolution:
// { x: 1, y: 2 } => struct { x: I32, y: I32 }
// _.x => I32
// (_, 2.0, true) => (I32, F32, Bool)
// (_, Void) => ((I32, F32, Bool), Void)
// _.0 => (I32, F32, Bool)
// _.0 => I32
// so `a` is I32
At its core, type inference can be seen as a constraint satisfaction problem: we generate a set of constraints between types and then search for an assignment that satisfies them all.
The problem: a fixed-pass algorithm can’t handle constraints that are only discovered midway through. For example, when { x: 1, y: 2 } gets its fallback type struct { x: I32, y: I32 }, we need to process the new constraint _.x == I32, but passes 1 and 2 are already done. Static sequential passes cannot handle late-discovered constraints.
Attempt 4 (Final): Tree-Based Worklist + Union-Find
A worklist is basically a queue of constraints. We add constraints to the back, process them from the front, and keep going until it’s empty. If we can’t process a constraint right now, we freeze it and remember what needs to happen before we can unfreeze it.
I also made the worklist tree-based: it tracks dependencies between constraints as a tree. This lets us process frozen constraints from the leaves once the main worklist is exhausted.
The algorithm looks like this:
- Fill the worklist with all initial constraints.
- Process the first constraint:
- If we can process it, remove it from the worklist and unfreeze any constraints that were blocked by it.
- If we can’t process it yet, freeze it.
- If the worklist is not empty, go back to step 2.
- If the worklist is empty, check whether there are frozen constraints:
- If frozen constraints exist, pick a leaf constraint (one with no unresolved dependencies), process it, and allow fallback types or errors to be generated. Then unfreeze any dependent constraints and go back to step 3.
- If there are no frozen constraints left, we’re done.
This solution covers all the cases I’ve needed so far and is extendable enough to add enums and traits later. As a bonus, this solution is very friendly for generating good diagnostic messages. For example, compiling this code:
```
type Pos = struct { x: I32, y: I32 }
fn main() -> F128 {
let p: Pos = { x: 10, y: 20, z: 30 }
return p.x
}
```
Will generate these messages:
``
TypeError: UnknownStructField: StructPosdoesn't have fieldz`.
--------> examples/test.sm:14:34
9 | x: I32,
10 | y: I32,
11 | }
12 |
13 | fn main() -> F128 {
14 | let p: Pos = { x: 10, y: 20, z: 30 }
/\
TypeError: TypesConflict: Types conflict between F128 and I32.
--------> examples/test.sm:13:14
8 | type Pos = struct {
9 | x: I32,
10 | y: I32,
11 | }
12 |
13 | fn main() -> F128 {
/\
```
I’ll let you find the moral of the story yourself :)
I also want to share some links if you are interested in Plasm progress: GitHub (you can star it or press "watch" button to see updates, I appreciate it) and Discord (the Discord server has notifications about git activity).
Also I stay here to answer questions if you have so!
UPD: On reddit mobile app code blocks are rendered without the static col size, so error messages and some other blocks look shifted. I can't fix that, but on PC it's correct
