Kō Compiler Engineer’s Handbook
A practical guide for adding language features to the Kō compiler.
Table of Contents
- The Pipeline
- Adding a New Token/Operator
- Adding a New Keyword
- Adding a Builtin Function
- Adding a New AST Node
- The Typechecker Deep Dive
- The Codegen Deep Dive
- Testing at Each Stage
- Common Pitfalls
The Pipeline
Two paths share the same frontend (Lexer → Parser → Typechecker), then diverge:
- LIR path (
--use-lir): AST → HIR → [5 passes] → LIR → [pattern match] → LLVM IR (experimental, 40/42 .ko files pass) - Legacy path (default): AST → codegen → LLVM IR (stable, all .ko files pass)
Shared Frontend
Source (.ko)
|
v
+---------------------------------------------+
| LEXER (src/lexer.zig) |
| Source string -> Token stream |
| Handles: whitespace, INDENT/DEDENT, |
| keywords, operators, literals |
+---------------------------------------------+
| Token[]
v
+---------------------------------------------+
| PARSER (src/parser.zig) |
| Token stream -> AST (src/ast.zig types) |
| Recursive descent, significant whitespace |
| Entry: parse_program() -> Program |
+---------------------------------------------+
| Program { imports, definitions, package }
v
+---------------------------------------------+
| TYPECHECKER (src/typecheck.zig) |
| AST -> Hindley-Milner type inference |
| Entry: inferProgram() |
| Produces: expr_type_tags (expr -> tag) |
+---------------------------------------------+
| Typed AST + type annotations
|
+-----> (default) ----+
| |
v v
LIR Path (—use-lir)
+---------------------------------------------+
| AST -> HIR (src/hir_lower.zig) |
| A-normal form, explicit closures, |
| tagged patterns, SourceSpan on every node |
+---------------------------------------------+
| HirExpr[] + HirDef[]
v
+---------------------------------------------+
| HIR OPTIMIZATION PASSES (src/hir_*.zig) |
| 1. Beta reduction (hir_beta.zig) |
| (\x -> body) arg -> let x = arg body |
| 2. Let simplification (hir_let_simpl.zig) |
| identity, dead, single-use literal inline|
| 3. Known-match reduction (hir_known_match.zig)
| match (Ctor a b) | Ctor x y -> ... |
| reduces to: let x = a; let y = b; ... |
| 4. Constant folding (hir_fold.zig) |
| add(3,4) -> 7, if true then a -> a |
| 5. Dead code elimination (hir_dce.zig) |
| reachability from roots |
+---------------------------------------------+
| Optimized HirExpr[]
v
+---------------------------------------------+
| HIR -> LIR (src/lir_lower.zig) |
| Decision tree compilation (Maranget algo): |
| pattern matrix -> column split -> |
| tag comparison -> field extraction -> |
| merge block with phi nodes |
| I/O builtins: 5-param *_with_tag convention |
| Panic/assert with source locations |
| Lambda lifting, closure conversion |
| Reference counting placement (Perceus) |
+---------------------------------------------+
| LirFn[] (basic blocks, |
| statements, terminators)
v
+---------------------------------------------+
| LIR -> LLVM IR (src/codegen_lir.zig) |
| Two-pass: declareFn -> codegenFn |
| Block params -> LLVM phi nodes (SSA) |
| declareRuntime() emits all stdlib |
| switch_ -> LLVMBuildSwitch |
+---------------------------------------------+
| LLVM Module
v
+---------------------------------------------+
| EXECUTION |
| JIT: LLVM MCJIT (mapLirJitResultFns) |
| AOT: not yet supported |
+---------------------------------------------+
Legacy Path (default, —no-lir)
+---------------------------------------------+
| CODEGEN (src/codegen.zig + |
| src/stdlib_codegen.zig) |
| Typed AST -> LLVM IR |
| Two-pass: declareFn -> codegenFn |
| Pattern matching: comparison chains + phi |
| Inline error handling: assert, assert_eq, |
| panic with source locations |
| Entry: codegenProgram() |
+---------------------------------------------+
| LLVM Module
v
+---------------------------------------------+
| EXECUTION |
| JIT: LLVM MCJIT (mapBuiltinsToNative) |
| AOT: Object file -> ld -> executable |
+---------------------------------------------+
Data Flow Between Stages
| Stage | Input | Output | Key Struct |
|---|---|---|---|
| Lexer | []const u8 | Token[] | Tokenizer |
| Parser | Token[] | Program | Parser |
| Typechecker | Program | expr_type_tags | Inferer |
| HIR Lower | Program + tags | HirExpr[] | HirLower |
| HIR Passes | HirExpr[] | HirExpr[] (optimized) | hir_beta, hir_let_simpl, etc. |
| LIR Lower | HirExpr[] | LirFn[] | LirLower |
| LIR Codegen | LirFn[] | LLVMModule | CodegenLir |
| Legacy Codegen | Program + tags | LLVMModule | Codegen |
| Execution | LLVMModule | result | Jit / Aot |
Adding a New Token/Operator
Step 1: Lexer (src/lexer.zig)
Find the Token.Tag enum (line ~12). Add your new token:
// In Token.Tag enum:
my_operator, // e.g., ??: or !!
Add the lexeme to lexeme() (line ~91):
.my_operator => "??:",
Add human name to humanName() (line ~166):
.my_operator => "operator ??:",
If it’s a keyword (not an operator), add to the keywords map (line ~241):
"mykeyword" => .keyword_mykeyword,
Add scanning logic in Tokenizer.next() (line ~326):
'?' => {
if (self.peek() == '?') {
self.pos += 1;
return self.makeToken(.my_operator, start);
}
return self.makeToken(.question, start);
},
Step 2: AST (src/ast.zig)
If it’s a binary operator, add to BinaryOp enum (line ~72):
pub const BinaryOp = enum {
// ... existing ops ...
my_op,
};
If it’s a unary operator, add to UnaryOp enum (line ~90).
If it’s an entirely new expression form, add to the Expr union (line ~98) and update getLoc()/setLoc().
Step 3: Parser (src/parser.zig)
Add parsing at the correct precedence level. The expression parser chain (outermost to innermost):
parse_expr->parse_assign(:=)parse_pipe(|>)parse_cons(::, right-associative)parse_or(||,or)parse_and(&&,and)parse_equality(==,!=)parse_compare(<,<=,>,>=)parse_term(+,-)parse_factor(*,/,%)parse_unary(-,not,!,ref)parse_postfix(., function application,?)parse_primary(literals, identifiers, etc.)
Step 4: Typechecker (src/typecheck.zig)
Add inference in inferBinary() (line ~1100). Find the switch on .op:
.my_op => blk: {
try self.unify(left, try self.newType(.int));
try self.unify(right, try self.newType(.int));
break :blk try self.newType(.int);
},
Step 5: Codegen (src/codegen.zig)
Add IR generation in codegenBinaryOp() (line ~680):
.my_op => blk: {
const result = core.LLVMBuild...(self.builder, l, r, "my_op");
break :blk result;
},
Step 6: Test
echo 'fn main = println (5 ??: 3)' > /tmp/test_myop.ko
ko --run /tmp/test_myop.ko
ko --emit-ir /tmp/test_myop.ll /tmp/test_myop.ko
zig build test --summary all
Adding a New Keyword
Step 1: Lexer
Add to Token.Tag:
keyword_foo,
Add to keywords map:
"foo" => .keyword_foo,
Add lexeme and humanName entries.
Step 2: Parser
Add to top_level_stops if it terminates blocks at the top level:
const top_level_stops: []const Token.Tag = &.{
// ... existing ...
.keyword_foo,
};
Add parsing in parse_program() or parse_primary().
Adding a Builtin Function
This is the most common task. Builtins are functions available without importing (like println, Int.pow).
Step 1: Typechecker (src/typecheck.zig)
Find inferProgram() (line ~592). Add type scheme registration:
// Example: my_fn : Int -> Int -> Int
const a = try self.newVarType("a");
const b = try self.newVarType("b");
const result = try self.newVarType("c");
const inner = try self.allocator.create(Type);
inner.* = .{ .arrow = .{ .from = b, .to = result } };
const fn_type = try self.allocator.create(Type);
fn_type.* = .{ .arrow = .{ .from = a, .to = inner } };
const quantified = try self.allocator.alloc(usize, 3);
quantified[0] = a.variable.id;
quantified[1] = b.variable.id;
quantified[2] = result.variable.id;
try self.global.set("my_fn", .{ .quantified = quantified, .body = fn_type });
For simpler cases (monomorphic):
const fn_type = try self.allocator.create(Type);
fn_type.* = .{ .arrow = .{ .from = try self.newType(.int), .to = try self.newType(.int) } };
try self.global.set("my_fn", .{ .quantified = &.{}, .body = fn_type });
Step 2: Stdlib Codegen (src/stdlib_codegen.zig)
Add a new codegen method:
pub fn codegenMyFn(self: *StdlibCodegen) void {
var params: [2]types.LLVMTypeRef = .{ self.i64Type(), self.i64Type() };
const fn_val = self.createFunction("my_fn", self.i64Type(), ¶ms);
const entry = core.LLVMAppendBasicBlockInContext(self.context, fn_val, "entry");
core.LLVMPositionBuilderAtEnd(self.builder, entry);
const a = core.LLVMGetParam(fn_val, 0);
const b = core.LLVMGetParam(fn_val, 1);
const result = core.LLVMBuildAdd(self.builder, a, b, "result");
self.buildRet(result);
}
Call it from generateAll().
Step 3: Codegen Registration (src/codegen.zig)
In declareBuiltins() (line ~254), register the function:
const my_fn = core.LLVMGetNamedFunction(self.module, "my_fn") orelse blk: {
var params: [2]types.LLVMTypeRef = .{ i64_type, i64_type };
const fn_type = core.LLVMFunctionType(i64_type, ¶ms, 2, 0);
break :blk core.LLVMAddFunction(self.module, "my_fn", fn_type);
};
_ = self.named_values.put("my_fn", my_fn) catch {};
Step 4: Test
echo 'fn main = println (my_fn 3 4)' > /tmp/test_builtin.ko
ko --run /tmp/test_builtin.ko
zig build test --summary all
Adding a New AST Node
Step 1: AST (src/ast.zig)
Add to the Expr union:
pub const Expr = union(enum) {
// ... existing ...
my_node: struct {
value: *Expr,
loc: Loc,
},
};
Update getLoc() and setLoc() for the new variant.
Step 2: Parser
Add parsing logic:
fn parse_my_node(self: *Parser) Error!*Expr {
const start = self.current().loc;
_ = self.advance();
const value = try self.parse_expr();
return try self.newExpr(.{ .my_node = .{ .value = value, .loc = start } }, start);
}
Step 3: Typechecker
Add case in inferExpr():
.my_node => |n| {
const inner = try self.inferExpr(env, n.value);
return inner;
},
Step 4: Codegen
Add case in codegenExpr():
.my_node => |n| {
const val = try self.codegenExpr(n.value);
return val;
},
The Typechecker Deep Dive
Key Concepts
Types (Type union in src/typecheck.zig):
pub const Type = union(enum) {
int, float, bool, char, string, unit,
con: struct { name: []const u8, args: []*Type },
arrow: struct { from: *Type, to: *Type },
tuple: []*Type,
record: RecordType,
ref: *Type,
variable: *TypeVar,
};
Type Variables: Mutable references that get unified (resolved) during inference.
Schemes: Scheme { quantified: usize[], body: *Type } — polymorphic types with bound variables.
Environments: Env maps names to schemes. Scoped (child envs shadow parents).
The Inference Flow
inferProgram()— registers builtins, then infers each definitioninferDef()— forfn, creates type vars for params, infers bodyinferExpr()— dispatches on AST node, returns inferred typeunify()— constrains two types to be equal (resolves variables)
Adding Type Constraints
// "This expression must be Int"
try self.unify(inferred_type, try self.newType(.int));
// "This expression must be a function from Int to Bool"
const expected = try self.allocator.create(Type);
expected.* = .{ .arrow = .{
.from = try self.newType(.int),
.to = try self.newType(.bool),
} };
try self.unify(inferred_type, expected);
Runtime Type Tags
typeToTag() maps types to integer tags for runtime dispatch:
| Tag | Type |
|---|---|
| 0 | Int |
| 1 | Float |
| 2 | Bool |
| 3 | Char |
| 4 | String |
| 5 | Unit () |
| 6 | Constructor (sum types) |
| 7 | Record |
| 8 | Function |
| 9 | Tuple |
| 100 | Variable/Ref (unknown) |
The Codegen Deep Dive
LLVM Value Representation
All Kō values are i64 in LLVM:
| Kō Type | LLVM Representation |
|---|---|
| Int | i64 (raw value) |
| Float | i64 (bitcast from double) |
| Bool | i64 (0 or 1) |
| Char | i64 (ASCII code) |
| String | i8* pointer -> i64 (ptrtoint) |
| Unit | i64 (0) |
| Constructor (0-arg) | i64 (tag value) |
| Constructor (N-arg) | i64 (ptrtoint of heap struct) |
| Function | i64 (function pointer or closure pointer) |
Memory Layout
Heap-allocated structs (constructors with args):
[ i64 tag ][ i64 arg1 ][ i64 arg2 ]...
^
pointer returned by ko_alloc (what codegen sees)
Closure struct (partial application):
[ fn_ptr total_arity applied_count applied_args... ]
Reference Counting
All heap allocations use ko_alloc which sets rc=1. Functions must:
- Call
emitIncref()when storing values in parent structures - Call
markConsumed()to skip decref at function exit - Call
ko_decref()on values they own but don’t return
Two-Pass Codegen
- Pass 1 (
declareFn): Creates LLVM function declarations, registers innamed_values - Pass 2 (
codegenFn): Generates function bodies
This allows forward references (functions calling functions defined later).
Testing at Each Stage
Test File Organization
src/tests.zig -- All Zig tests (lexer, parser, typechecker, codegen)
src/tests_ko/ -- .ko test programs (47+ files)
01_literal.ko -- Basic literals
15_sum_type.ko -- User-defined types
44_cons_operator.ko -- List operations
50_comptime_lists.ko -- Compile-time evaluation
Adding a New Test
- Write
.kofile insrc/tests_ko/(must have trailing newline) - Add
@embedFileentry intests.zigparser test section - Verify it parses:
ko your_test.ko(should show “Parsed: N definitions”) - Run full suite:
zig build test --summary all
Test Commands
# Full test suite (ALWAYS use --summary all)
zig build test --summary all
# JIT-execute a program
ko --run file.ko
# Dump LLVM IR to stdout
ko file.ko
# Emit LLVM IR to file
ko --emit-ir out.ll file.ko
# Emit object file
ko --emit-obj out.o file.ko
# Emit linked executable
ko --emit-exe out file.ko
Testing a New Feature
- Lexer test: Add token test in
tests.ziglexer section - Parser test: Add
.kofile, add@embedFileentry - Typechecker test: Add
testInfer()call intests.zig - Codegen test: Use
ko --runorko --emit-ir - Integration test: Full
.koprogram that exercises the feature
Common Pitfalls
Lexer
@embedFilereturns null-terminated*const [N:0]u8— do NOT append++ "\x00"#comments must fully disappear from token stream- Indentation can emit multiple
dedenttokens — queue them
Parser
parse_blockfromparse_fn_defvsparse_let_expr_in_block— useallow_let_in_bodyflag- Field access binds tighter than function application:
println pt.x=println(pt.x) inspect Some(42)without parens is parsed as(inspect Some)(42)— use parens
Typechecker
next_type_idstarts at 2 (Bool=0, Result=1) — must match codegenregisterTypeDefcalled from multiple passes — guard withif (!type_ids.contains(name))- Imported module types may not propagate to main inferer
Codegen
LLVMBuildCall2needs function type fromLLVMGlobalGetValueType, NOTLLVMTypeOf- String literals include quotes — strip them in codegen
- Float literals produce
double— bitcast toi64for builtins trackHeapAllocstoresptrtoint(i64), NOT raw pointeremitDecrefAllmust skip return value (caller takes ownership)- Allocas for conditional allocations must be before entry block terminator
LLVMAddGlobalMappingdoesn’t override functions with bodies in MCJIT
Testing
- Always use
zig build test --summary all— default output is misleading - Every
.kotest must parse before it can test typecheck/codegen - Use
ArenaAllocatorwrappingstd.testing.allocatorfor parser/typechecker tests - Never use
page_allocatorfor tests (bypasses leak detection)
Known Issues
Parser
- Negative numbers as args:
f -3must bef (-3)(GitHub #17) - Multi-line pipe:
|>doesn’t work across lines (GitHub #18) letin non-indented blocks: parser may consume next def as body
Codegen
- Let-bound constructor display: Shows raw pointers (element-level type tags lost at LLVM IR level)
- List element printing: Non-integer list elements print as raw pointers (tag=100)
- Division by zero at runtime: Only a literal divisor is caught at compile time.
10 / zwherezis 0 traps (SIGFPE) on both the legacy and LIR pipelines.
LIR Pipeline
- REPL: Not yet ported to LIR pipeline
String Design
Strings are KoString at LLVM level: a 32-byte header followed by NUL-terminated
bytes, laid out to share ko_decref with heap constructors. A string value points
at its bytes, so the header is read at negative offsets: refcount -32, type tag
-24, byte length -16, field bitmap -8. The byte length occupies the generic
header’s arity slot, which is unused for strings. Operations use C library functions.
Known limitations:
- No UTF-8 awareness:
String.lengthcounts bytes, not code points String.toUpperCaseuses Ctoupper(ASCII-only)String.splitLLVM IR body is empty (only Zig JIT fallback works)- No efficient building: every
String.appendallocates + copies (O(n²))
Design goals: UTF-8 by default, length-prefixed internally, efficient building, comptime/runtime parity.
See Also
- Codegen: how LLVM IR generation works
- Language Reference: syntax and semantics
- Tutorial: getting started guide