Just wanted to share a bit of an anecdote I had recently as someone dipping into implementing the middle-end and back-end of a compiler "properly" for the first time.

My compiler targets a Minecraft computer I'm developing, which runs 1 instruction every 20 real life seconds (haven't gotten around to optimizing the hardware yet). In an effort to make programs run fast, I decided to implement allocation with register coloring using Chaitin's algorithm instead of using naive register allocation that LOADs and STOREs on every variable lose.

I assumed it would be a 2 day job at best but I didn't realize it expects your program to be in a very certain form (SSA). This lead me to a rabbit hole of learning how to compute basic blocks and the control flow graph, then converting the CFG to SSA by computing dominators, dominance frontiers and the dominance tree. We didn't cover any of this in university and only built an tree-walking interpreter for the ast.

Only once I had the SSA could I run liveliness analysis, build the register interference graph and run Chaitin's algorithm to allocate the registers.

It was confusing to learn since the slides I were using assumed some stuff and glossed over some details like how to handle Phi-Nodes. Another issue I had was that I didn't see the big picture at the time and was wondering how what I was doing would help in the big picture, not seeing how SSA is helpful.

Now that I've gotten something the color map, I guess I can do some other dataflow optimizations, or I could proceed with code generation :).

Disclosure: I was consulting ChatGPT on what steps to proceed next once i've implemented a certain algorithm. All code was handwritten, but some comments may contain LLM outputs. I copied over the steps provided so that I didn't have to keep switching windows while writing code.

I was thinking of the ideal expression syntax for the programming language DQ. I started with the (dominating) C syntax.

Operators in C

In C the following operators have shared meanings:

• &: bitwise "and" operation OR address of
• *: multiplication OR pointer dereference
• /: truncated integer division OR floating point division

Further operators in C:

• %: integer division reminder
• && or and: logical "and"
• || or or: logical "or"
• ! or not: logical "not"
• ~: bitwise "not"
• ^: bitwise "xor"
• ?: ternary operator

Operators in DQ

I think for the good source code readability and clarity every different operation should have a different symbol. Therefore the shared symbols from C are not taken over. These operators are already fixed in DQ:

• &: address-of operator (widespread standard)
• ^: pointer dereference (standard in other languages)
• *: multiplication only
• /: floating point division only (standard in other languages)
• or: logical "or" (widespread standard)
• and: logical "and" (widespread standard)
• not: logical "not" (widespread standard)

These symbols are already fixed for special purposes:

• #: compiler directives (#ifdef etc)
• $: context local specials (e.g. myarray[0:$end-2])
• ?: inference marker
• @: namespace designator (e.g. @def.LINUX)

DQ cannot use the C standard &, |, ~, ^ for the bitwise operations, because the & and ^ is used for other (fixed) purposes. But we've run out of the good symbols. The obvious choice, that other existing languages also use, is reserving some words for the remaining operations. In DQ these (all-capital) words are reserved currently as operators:

• AND: bitwise "and"
• OR: bitwise "or"
• NOT: bitwise "not"
• XOR: bitwise "xor"
• IDIV: truncated integer division
• IMOD: integer division reminder

For the modify-assign statements with a word operator a leading = is required, otherwise it looks awkward:

regs.OSPEEDR OR= (1 << pinx2)  // invalid
regs.OSPEEDR =OR= (1 << pinx2)

Examples with All-Capital Operators

tmp = RCC.CFGR
tmp =AND= NOT 3
tmp =OR= RCC_CFGR_SW_HSI
RCC.CFGR = tmp
while (RCC.CFGR >> 2) AND 3 <> RCC_CFGR_SW_HSI:
endwhile

RCC.CR =AND= NOT RCC_CR_PLLON
while RCC.CR AND RCC_CR_PLLRDY != 0:
endwhile

var pllm : uint = basespeed IDIV pll_input_freq
var plln : uint = vcospeed  IDIV pll_input_freq
var pllq : uint = vcospeed  IDIV 48000000

RCC.PLLCFGR = (0
    OR (pllsrc << 22)
    OR (pllm   <<  0)
    OR (plln   <<  6)
    OR (((pllp >> 1) - 1) << 16)
    OR (pllq   << 24)
)

regs.MODER =AND= NOT (3 << pinx2)
regs.MODER =OR=      (n << pinx2)

if flags AND PINCFG_OPENDRAIN <> 0:
    regs.OTYPER =OR= (1 << apinnum)
else:
    regs.OTYPER =AND= NOT (1 << apinnum)
endif

regs.PUPDR =AND= NOT (3 << pinx2)
if flags AND PINCFG_PULLUP <> 0:
    regs.PUPDR =OR= (1 << pinx2)
elif flags AND PINCFG_PULLDOWN <> 0:
    regs.PUPDR =OR= (2 << pinx2)
endif

Prefixed Word Operators

I'm thinking to change the all-capital word operators with a % prefixed lowercase words:

• %and: bitwise "and"
• %or: bitwise "or"
• %not: bitwise "not"
• %xor: bitwise "xor"
• %div or %idiv: truncated integer division
• %mod or %idiv: integer division remainder

The sample code would look like this way:

tmp = RCC.CFGR
tmp %and= %not 3
tmp %or= RCC_CFGR_SW_HSI
RCC.CFGR = tmp
while (RCC.CFGR >> 2) %and 3 <> RCC_CFGR_SW_HSI:
endwhile

RCC.CR %and= %not RCC_CR_PLLON
while RCC.CR %and RCC_CR_PLLRDY != 0:
endwhile

var pllm : uint = basespeed %div pll_input_freq
var plln : uint = vcospeed  %div pll_input_freq
var pllq : uint = vcospeed  %div 48000000

RCC.PLLCFGR = (0
    %or (pllsrc << 22)  // select PLL source
    %or (pllm   <<  0)
    %or (plln   <<  6)
    %or (((pllp >> 1) - 1) << 16)
    %or (pllq   << 24)
)

regs.MODER %and= %not (3 << pinx2)
regs.MODER %or=       (n << pinx2)

if flags %and PINCFG_OPENDRAIN <> 0:
    regs.OTYPER %or= (1 << apinnum)
else:
    regs.OTYPER %and= %not (1 << apinnum)
endif

regs.PUPDR %and= %not (3 << pinx2)
if flags %and PINCFG_PULLUP <> 0:
    regs.PUPDR %or= (1 << pinx2)
elif flags %and PINCFG_PULLDOWN <> 0:
    regs.PUPDR %or= (2 << pinx2)
endif

Which version do you like more?

or

Do you have some other ideas for the operator notation?

EDIT

Version with band / bor etc, as "jason-reddit-public" suggested:

• band: bitwise "and"
• bor: bitwise "or"
• bnot: bitwise "not"
• bxor: bitwise "xor"
• idiv: truncated integer division
• imod: integer division reminder

​

tmp = RCC.CFGR  
tmp =band= bnot 3 
tmp =bor= RCC_CFGR_SW_HSI 
RCC.CFGR = tmp

while (RCC.CFGR >> 2) band 3 <> RCC_CFGR_SW_HSI:
endwhile

RCC.CR =band= bnot RCC_CR_PLLON
while RCC.CR band RCC_CR_PLLRDY != 0:
endwhile

var pllm : uint = basespeed idiv pll_input_freq
var plln : uint = vcospeed  idiv pll_input_freq
var pllq : uint = vcospeed  idiv 48000000

RCC.PLLCFGR = (0 
  bor (pllsrc << 22) 
  bor (pllm   <<  0) 
  bor (plln   <<  6) 
  bor (((pllp >> 1) - 1) << 16) 
  bor (pllq   << 24) 
)

regs.MODER =band= bnot (3 << pinx2) 
regs.MODER =band=      (n << pinx2)

if flags band PINCFG_OPENDRAIN <> 0: 
    regs.OTYPER =bor= (1 << apinnum) 
else: 
    regs.OTYPER =bor= bnot (1 << apinnum) 
endif

regs.PUPDR =band= bnot (3 << pinx2) 
if flags band PINCFG_PULLUP <> 0: 
    regs.PUPDR =bor= (1 << pinx2) 
elif flags band PINCFG_PULLDOWN <> 0: 
    regs.PUPDR =bor= (2 << pinx2) 
endif

EDIT / 2

As I was migrating microcontroller C++ code, where the bitwise operations are very intensively used, I decided to keep three bitwise operators with single symbols:

• &: bitwise "and"
• |: bitwise "or"
• ~: bitwise "not"

These operations are kept with word symbols:

• xor: bitwise "xor"
• div: truncated integer division
• mod: integer division reminder

​

tmp = RCC.CFGR 
tmp &= ~3 
tmp |= RCC_CFGR_SW_HSI 

RCC.CFGR = tmp 
while (RCC.CFGR >> 2) & 3 <> RCC_CFGR_SW_HSI:
endwhile

RCC.CR &= ~RCC_CR_PLLON 
while RCC.CR & RCC_CR_PLLRDY <> 0: 
endwhile

var pllm : uint = basespeed div pll_input_freq 
var plln : uint = vcospeed  div pll_input_freq 
var pllq : uint = vcospeed  div 48000000

RCC.PLLCFGR = (0 
  | (pllsrc << 22) 
  | (pllm   <<  0) 
  | (plln   <<  6) 
  | (((pllp >> 1) - 1) << 16) 
  | (pllq   << 24) 
)

regs.MODER &= ~(3 << pinx2)
regs.MODER |=  (n << pinx2)

if flags & PINCFG_OPENDRAIN <> 0:
    regs.OTYPER |= (1 << apinnum) 
else: 
    regs.OTYPER |= ~(1 << apinnum)
endif

regs.PUPDR &= ~(3 << pinx2) 
if flags & PINCFG_PULLUP <> 0: 
    regs.PUPDR |= (1 << pinx2) 
elif flags & PINCFG_PULLDOWN <> 0: 
    regs.PUPDR |= (2 << pinx2) 
endif

I've creted an open specification about these operators available here:

https://nvitya.github.io/pluops/

Hell everyone, i have an question. Im for long trying to make a cool, powerful "kinda" low level language similar to zig and rust, but im struggling to choice llvm as backend, sure i can generate C, but its makes compiler dependent on gcc or clang or other c compiler. LLVM seems hard to me, sure project like QBE exist, but QBE doesnt have C/C++ api like llvm's IRbuilder. So are there other ways? I tried thinking about using GCC infrastructure but GCC has poor api and not very documented api. Maybe just stick to generating C?

I made a video explaining macros, with the goal of making the viewer feel like they could have discovered macros. I'm new at making educational content like this, but I'm planning on making many more programming language videos like this one on my channel. Any thoughts, constructive criticism, or advice is more than welcome! Hope you all enjoy

I'm working on a language called threadon. And i don't now how i can properly program a package manager.

My first idea was a central github repo with links to other github repo's which contain the package you're searching for.

There are two main problems with it

1. If someone deletes his github repo with the package everything build on the package would collapse (like npm)

2. I think it would be slow when the number of packages grows.

I had an idea to of selfhosting it but i haven't access to the router (My dad owns it i'm 13) and i'm sure downdetector on my package manager site would be worse then github 😄. Like i would probably run sudo rm -rf / --no-preserve-root on the wrong machine.

So my question is how can i build a system that can store up to 20 GB at minimum at packages without the risk of someone nuking his project).

I loved Chapter 5 of Structure and Interpretation of Computer Programs. Building a virtual register machine with an assembler and compiler in Scheme. Are there any other books/online classes or resources that involve building a computing machine (or any machine) from scratch using code?

What are people's thoughts on proof-based programming languages based on Dependent Type Theory like Lean, Rocq/Coq, F*/Low*, Agda, etc. It seems like there is some subtle growing hype behind formal verification. Clearly, there is at least some appetite for better behavior guarantees as we can see with Rust.

What do you think, are these languages the future? Will they become more ergonomic over time. Or do you think the average programmer will never be willing to learn or program in such a language for their normal projects?

Hey everyone,

A couple of weeks ago, I posted about Kal, my programming language written from scratch.

I am really happy to share a glimpse of Kal's own package manager! Kal v0.1.0 shipped with a package system that lets you add and use third party Kal packages. But, that process was completely manual. You’d have to clone the package, place it in the right directory, clone the package’s entire dependencies all by yourself, one after another. :(

The package manager changes everything. One command automates all!

Instead of being a separate executable, the package manager ships as part of the Kal interpreter itself.

Here’s what it can do:

1. Install Kal packages from Github, or any git hosting service.
2. Creates/Updates a project.kal file to read and write package information (analogous to package.json).
3. Downloads all packages at the same hierarchy in parallel (yup, it’s multi-threaded).
4. Resolves sub dependencies of the main package automatically to any depth and installs them too.
5. Upgrades/Downgrades packages based on their git tags.
6. Auto-resolves cyclic dependencies to prevent an infinite loop.

The Kal Package Manager will officially ship with the next Kal release. Its current source code is available on Github.

Kal: https://kal-lang.vercel.app
Github: https://github.com/KILLinefficiency/Kal
Package Manager: https://github.com/KILLinefficiency/Kal/blob/pkg/pkg.hpp

Kal is completely free & open source. You can show your support by giving the Github Repository a star.

Until the next update!

About a month ago, I made a post asking for resources on building a very small compiler/interpreter before jumping into something larger like Crafting Interpreters.

I decided to stop looking for the perfect resource and just start building the smallest thing I could understand end-to-end.

Today I got the first version of a simple arithmetic interpreter working in Python.

Right now it supports:

• Integer literals
• Addition and subtraction
• Multiplication and division
• Operator precedence
• Parentheses
• Unary minus
• Basic syntax errors
• Division-by-zero handling
• An interactive REPL/CLI

For example:

calc> 2 + 3 * 4
14

calc> (2 + 3) * 4
20

calc> -10 + 5
-5

The structure is currently:

Source text
    ↓
Lexer
    ↓
Tokens
    ↓
Recursive-descent parser
    ↓
Evaluation
    ↓
Result

The lexer converts something like:

2 + 3 * 4

into tokens roughly equivalent to:

NUMBER(2)
PLUS
NUMBER(3)
MUL
NUMBER(4)

The parser implements a small grammar along these lines:

expr   → term (("+" | "-") term)*
term   → factor (("*" | "/") factor)*
factor → NUMBER | "(" expr ")" | "-" factor

One of the most useful things I learned today was how operator precedence can naturally come from the structure of the grammar. I initially assumed I would need to assign explicit precedence values to operators, but with recursive descent, expr, term, and factor already encode that hierarchy.

The parser currently evaluates expressions directly rather than producing an AST, so it is deliberately still very small. My next major step will probably be separating parsing from evaluation by building an AST.

I also spent some time turning it into a proper little Python project instead of keeping everything in one file. It now has separate lexer, parser, interpreter, and CLI modules, a src package layout, pyproject.toml, a command-line entry point, and Ruff for linting/formatting.

So this is obviously nowhere near a real compiler yet, but that was exactly the point of my original post. I wanted something small enough that I could understand every stage instead of immediately disappearing into a much larger implementation.

Building even this tiny version made concepts like tokenization, grammars, recursive descent, precedence, and parsing much less abstract than they were a month ago.

The plan from here is to keep extending it incrementally, probably with an AST, variables, and a few statements before eventually moving toward bytecode or compilation.

Name: Infinity Execute Plus (IE+)

License: open source

Concept: IE+ is actually the main (and currently only) VM console of my planned VM collection: Infinity Execute. It is an interpreted language i thought of making to combine speed with ease. I learned c++ solely for this project. IE+ is currently an interpreter that uses one shell executable and most of it's logic is stored in a collection of library files that handle/process different tasks. I plan in the future to allow multiple exportable formats (currently windows only, planning to make multiple releases for apple and linux): IE (text), IEBCS (bytecode), IAO (Infinity Assembled object. It's a linked file that allows precompiled importing on any supporting app), IEPCK (semi-compiled appilcation format that still needs runtime), native executable exporting.

Examples:

Available operations

# printing

print "Hello, World!"

# making a variable

var x = 5 # currently only supports dynamic typed. static typed will be added. currently supports: int, float, string, and bool vars. arrays and constants will come in future builds.

# printing a variable's value in string form

print (x)

some future planned features

# modifying variables

x += 2

# static typing

var y: string = "Hi!"

# multiline commands and creation of text script

compile = {
  var hello: string = "Hello, World!"
  print (hello)
}.IE.name = "helloworld"

Here's an example of a standard program written in IE+ that creates a car and prints out it's data using OOP

class car {
  private {
    var name = ""
    var price = 0
  }
  public {
    main(created_name, created_price) {
      name = created_name
      price = created_price
      self.new()
    }
  }
}

car.new("Cool Car", 50000)

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:

1. Constraint Generator: takes a function’s IR and produces equality constraints (e.g., type_of(a) == type_of(b), type_of(b) == I32).
2. 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:

1. Pass 1 (Equality Unification): Unify all equalities using a disjoint-set (same as my first attempt).
2. 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).
3. 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:

1. Fill the worklist with all initial constraints.
2. 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.
3. If the worklist is not empty, go back to step 2.
4. 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