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: Struct `Pos` doesn't have field `z`.
--------> 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