Skip to content
BranchesTags

Repository files navigation

lang — an experimental compiler

An experimental compiler for a language that mixes ideas from C++, Rust, Zig and Go — structural types, classes with constructors/ destructors and RAII, duck-typing interfaces, comptime generics — and translates to C++.

The authoritative language description is examples/tour.lang: a commented, executable tour that shows every feature and makes it checkable through assert — it translates to C++, terminates with exit code 42 and is checked continuously against the compiler in the test tour_example_runs_to_42. This document describes the compiler architecture and summarizes the language decisions.

The goal: a minimal, easily understandable codebase for experimenting with language design, not a production-ready compiler.

Quickstart

Prerequisites: Rust ≥ 1.88 (the crate uses edition 2024 and let chains) and a C++20 compiler (g++ or clang++). clang-format is optional — the emitted C++ is passed through it when it is on the PATH, purely for readability.

git clone https://github.com/glashoff/lang.git
cd lang

# Compile the tour to C++ and run it: prints 42, the tour's exit code.
./build.sh

The compiler itself is a single binary that reads one root .lang file (imports are followed transitively) and writes C++ to stdout:

cargo run -- examples/tour.lang > tour.cpp
g++ -std=c++20 -o tour tour.cpp
./tour; echo $?          # 42

On errors, diagnostics go to stderr and the exit code is 1 — nothing is written to stdout.

cargo test               # 6 unit + 338 end-to-end + 3 snapshot tests
cargo fmt --check
cargo clippy --all-targets -- -D warnings

The end-to-end tests compile and run generated C++, so they need g++ on the PATH. The snapshot tests use insta; review changed snapshots with cargo insta review.

Who is lang interesting for?

lang is an experiment, not a finished tool — but it aims at a concrete feeling: the ergonomics of modern systems languages without their respective ballast. Perhaps you recognize yourself here:

  • Rust, but without the borrow checker. You want move semantics, RAII, traits (here: interfaces), enums with match, Result + ? — but not the fight with lifetimes and borrowing rules. In lang, references are C++-like: no aliasing proof, no lifetime annotations. The move checker catches use-after-move; for the validity of references you are responsible. The trade is deliberate: fewer guarantees, less friction.
  • C++, but without the legacy. You like RAII, value types, templates and zero-cost abstractions — but not headers and the preprocessor, implicit widening conversions, uninitialized memory, the rule-of-five traps and the UB minefield. lang gives you a small, consistent core: overflow-checked arithmetic, range-checked indices, visible casts, explicit move/copy semantics — and emits readable C++ that a strong optimizer likes.
  • Zig, but with real interfaces. You like comptime as the generics mechanism and explicit control without hidden allocations — but want interfaces with dynamic dispatch (fat pointers), associated types and the separation structural vs. nominal (distinct) on top.
  • Go, but with values and without a GC. You like duck-typing interfaces and simplicity — but want value types with copy/move instead of garbage collection and monomorphized generics instead of runtime overhead.
  • Those interested in language design & compilers. A small, easily readable Rust codebase with clearly separated phases and C++ as the backend (no LLVM) — made for reading, following and experimenting with.

Rather not for you if you need memory-safety guarantees, a stable language, a mature ecosystem or production readiness today — none of that is there (some deliberately as a non-goal, other things simply not yet).

You get a feeling for the language fastest through the executable tour examples/tour.lang.

The structure of this document

This repository is the reference for two things, and the README is structured accordingly:

  • Part I — the language. What lang is: the semantics, the type system, the carrying design decisions. Canonical and executable is the tour examples/tour.lang — the section here summarizes the decisions.
  • Part II — the compiler. How lang is built: the Rust pipeline (lexer → parser → resolve → sema → emit), the data structures, the C++ backend, the diagnostics and the tests.

The preceding sections (the project goals, the non-goals) concern both and are therefore broken down into the language and the compiler in each case. Deeper design notes lie under doc/planned/.

Table of contents

Part I — the language

Part II — the compiler

Project goals

For the language (part I):

  • Combine interesting language features. In particular the combination of structural types (struct = tuple = array), C++-style RAII (constructors / destructors), Go-style interfaces with duck typing and comptime evaluation as the generics mechanism — under Zig principles (explicit control, no hidden allocations).

For the compiler (part II):

  • Clarity before performance. The compiler itself may be slow. The code has to stay readable, well structured and easily changeable.
  • Small, clearly separated phases. Every phase is a pure function with an understandable signature.
  • C++ as the backend. No LLVM, no code generator of our own. We lean on a strong optimizer and write readable C++.
  • A good first impression with error messages. Even a toy compiler should output helpful error messages.

Non-goals

Two sorts: permanent design decisions (deliberate, presumably for ever) and deferred things — not the current focus, but expressly not ruled out.

Permanent

For the language (part I):

  • No borrow checking. References follow the C++ model; the validity lies with the programmer (the reference model in examples/tour.lang).
  • No general reflection. Comptime evaluation itself is a goal (see the section of its own), and individual builtins like isClass<T> are fine — but a @typeInfo-like traversal of arbitrary types is a bottomless pit.
  • No generics mechanism separate from comptime. The Vec<T> syntax is only a surface — underneath, generic types are comptime functions that return types, monomorphized as in Zig.
  • No source or ABI compatibility with any of the model languages — we help ourselves to C++, Rust, Zig and Go, without being compatible with any of them.

For the compiler (part II):

  • No optimizer of our own, no SSA, no IR of our own for optimization — the C++ compiler takes that over.

Deferred (not ruled out)

These points are appealing and stay open — they are just not the current focus:

  • async — quite a candidate for the near future; there is already a design sketch (doc/planned/Async.md).
  • A package manager — simply not necessary for the present single repo, no fundamental exclusion; it comes into question as soon as there are several packages/users.
  • Self-hosting ("bootstrapping") — a legitimate distant goal, just not now (it presupposes a markedly more mature language).
  • A larger standard library — it grows with the need. Today only as far as the language carries itself (std/: Option, Result, Vec, Box, Rc, String, iterators).

Part I — the language

What lang is. Canonical and executable: the tour examples/tour.lang — this section summarizes the carrying decisions.

The language design (a short overview)

The complete description is examples/tour.lang. Here an extract and the carrying decisions:

// Structs are structural: struct = tuple = array, positional and
// named fields in the same [...] literal. Field names are part of the
// type identity. Structural types are pure data (no methods).
type Point = [x: Int, y: Int];
const v: Point = [2, 3];
assert(typeof(v) == [x: Int, y: Int]);

// Methods are free functions with a receiver (before the name), declared in the
// same module as their type — they travel with it. Only on *nominal*
// types (`class`/`distinct`), which is why `Vec2` is `distinct` here.
type Vec2<T> = distinct [x: T, y: T];
fn (s: &Vec2<T>).distance() = sqrt(s.x*s.x + s.y*s.y);

// Interfaces: fn signatures without a body. A concrete type converts
// *implicitly* (checked duck typing) as soon as an interface is expected;
// `auto(&x)` makes the same conversion optionally visible.
type Printable = interface [ fn (s: &Self).print() :> [] ];

// Classes are nominal (distinct) types: priv fields, init,
// move, deinit, implicit RAII at the end of the scope.
type Handle = class [ priv fd_: Int, /* fn ... */ ];

The carrying decisions:

  • Keywords are bare words (fn, const, type, if, …). Reserved is only the leading underscore: _ alone is the discard, and identifiers may not begin with _ — this namespace belongs to the language and the compiler internals (e.g. temporaries in the emitted C++). Trailing underscores (ptr_) are allowed.
  • One literal for everything: [...] is a struct, a tuple and an array at once (positional, then named fields). Types are comptime values — typeof(x) == [x: Int, y: Int] is an ordinary comparison. Structures are structurally typed and copy implicitly.
  • Slices []T / [] mut T are borrowed fat-pointer views { ptr, len } onto a run of T — the length at runtime. Construction through sub-slicing xs[lo..hi] (xs[..], xs[lo..], xs[..hi]) over an array or another slice; xs[i] is range-checked, xs.len() delivers the length. So fn sum(xs: []Int) is one function for every array length (without generalizing over N, without a copy). Mutability is expectation-driven ([] mut T only from a writable base); a copyable view, no borrow check (C++ reference semantics). The design/status: doc/planned/Slices.md.
  • Text (the core): UInt8 (std::uint8_t, with Int(b)/UInt8(n) casts) and str — a borrowed UTF-8 view, internally a distinct []UInt8 (a slice special case). String literals "…" point into static rodata (no allocation, no escapes); s.len() is the byte length, s[i]: UInt8 a range-checked byte. Plus the owning String (std/string.lang) — a move-only class over a heap byte buffer (String(str), len, asStr, pushStr with growth, RAII + move). Still without char/iteration, UTF-8 validation, str comparison and +. The design/status: doc/planned/Strings.md.
  • In [...] literals it holds that: : declares instance fields, = initializes them in value literals, fn defines type-level members.
  • distinct makes a nominal type out of every structural one, without changing the semantics (still copy, no RAII) — for exclusive method attachment and against accidentally mixing structurally equal types (type Meters = distinct Int;). Unnamed literals coerce into distinct target types; an explicit conversion in both directions through the cast syntax (Meters(5), Int(m)). class implies distinctness and adds move/RAII/priv.
  • A distinct [...] may carry methods — a nominal value type (copyable, no lifecycle) with methods. That fills the gap between a structural struct (no methods, because a method cannot "belong" to a shape) and a class (methods, but move/RAII). Because distinct is nominal, a method belongs unambiguously to this type. Methods stand — as everywhere — free-standing in the same module (fn (s: &Vec2<T>).first()…), not in the body; the body carries only fields. Fields are public (for priv there is class); generic variants are monomorphized per type argument. Construction through coercion/a cast (const v: Vec2<Int> = [x = 1, y = 2]).
  • Classes are nominal (class makes a distinct type) and concentrate the entire move/RAII complexity: priv fields, init (the constructor), move_init (which establishes the null state in the source), deinit (the destructor, which runs implicitly at the end of the scope and has to be a no-op on the null state). The null state is the prerequisite for a correct C++ mapping: C++ calls destructors on moved-from objects too. The move checker makes statically visible use-after-move a compile error (intraprocedural, flow-sensitive; x = … reinitializes; conditional moves count conservatively as "maybe moved"). Partial moves are tracked at field granularity: if you move h.b out of a struct, the remaining fields (h.tag) stay usable — only h.b and the value as a whole are locked until h.b is reassigned. For paths it cannot track — moves through references, aliasing, destructors — the null state stays the defined runtime semantics: no UB. The move is explicit: %x. Moving a move-only value out of a named variable (or a field: %h.b) has to be marked with the prefix operator % — the plain form is reserved for copies. The one point at which x falls into the null state thereby stands visibly in the code (the best safeguard without a borrow checker). Exceptions without a %: the return position (the local dies anyway — like C++'s implicit return move) and temporaries (a function result is already movable). On a copyable value, % is allowed and copies (the source stays valid) — so generic code can write %x uniformly, no matter whether T is move-only or copyable. Out of a const binding one can not move (not even with %: a move leaves the null state behind — that would be a mutation), out of a var one can. Function parameters are const-like by default; a var parameter (fn f(var x: T)) belongs to the function and may be moved — necessary in order to receive a move-only value and pass it on (e.g. the Box/Rc constructors). If move_init is missing, the compiler generates it: class fields are moved recursively, simple fields copied and nulled in the source. An exception ("the rule of five"): if the class defines a deinit, the transfer semantics has to be written explicitly — at least move_init (unique ownership, the null state) or copy_init (shared ownership, e.g. reference counting). A destructor implies resources, and their semantics must not be guessed by generation. Classes are move-only by default. A class becomes copyable through a self-defined copy_init (then implicit copies as with structs). A class may define both members — then the context chooses the fitting special member: %p moves (move_init), p copies (copy_init). copy_init is never generated — for resource types there is no automatically correct copy, and an implicit copy that allocates would be a hidden allocation. Expensive types instead offer an explicit .clone().
  • A user-defined deref operator wrapper.*. If a class defines the pair deref(& self): & T / deref_mut(& mut self): & mut T (the latter optional), wrapper.* delivers a reference to the inner value T — deref_mut on a mutable place, otherwise deref. Its methods/fields run on that perfectly normally (box.*.foo(), box.* += 1). The access stays deliberately explicit: no implicit box.foo() forwarding, no coercion, one level — the deref cost stands visibly in the code, and the wrapper vs. target namespaces are syntactically separated. Box<T>/Rc<T> use it. The justification and the rejected alternatives (forwarding, ->): doc/planned/Deref.md.
  • Structures may contain class fields. Copyability propagates: a structure is copyable if all its fields are — class fields therefore only with a copy_init. Otherwise the structure is move-only (the compiler generates the memberwise move).
  • No UB: integer overflow, division by zero, INT_MIN / -1, a shift width ≥ the bit width and an array index out of range lead to a panic. Division truncates towards zero (-7 / 2 == -3), % carries the sign of the dividend, shifts are two's-complement bit operations — exactly the native C++20 semantics; the emitter only plugs the UB holes with checks. In the comptime interpreter the same panic becomes a compile error.
  • Errors are values (the Rust style), not exceptions. Fallible functions return Result<T, E> (std/result.lang); the ? operator propagates the error case, match unpacks it. Optional values are Option<T> (std/option.lang). Both are ordinary generic enums of the stdlib, no language special case. panic stays reserved for bugs (an overflow, an index out of range, a failed assert). Details: doc/planned/ErrorHandling.md.
  • fn is the sole definition form for type-level functions: methods (the receiver before the name, in the type's module), associated functions (without a receiver), free functions and interface signatures. Overloading exists only through the receiver (const vs. mut), not through parameters. Methods are callable only in method syntax (v.distance()) — a free call form does not exist. Unnamed literals coerce as a receiver too ([2, 3].distance()); if more than one target type fits, it is a compile error.
  • Lambdas are function values ((x: Int) :> Int => x * x) and capture the variables used by value. A capturing lambda is an anonymous struct (the captures as fields + a call member) — no hidden heap allocation. Function types are bare function pointers — only capture-free functions coerce into them. The callable ladder, every rung with visible cost: a function type (static, capture-free) → a comptime generic fn apply<F>(f: F, …) (static, arbitrary callables, monomorphized) → an interface + Box (dynamic, for fields and containers).
  • Interfaces combine Go and Rust: structural conformance; the concrete→interface conversion runs implicitly at places with an expected interface type (an argument, a return, an annotation, a field), and auto(&x) marks it optionally. Parameter names are not part of the contract; only real fn members satisfy requirements. A distinct interface, by contrast, is nominal: a type joins it explicitly through impl I for T [ type Item = … ] (with associated types) and inherits its default methods — that is how the Iterator ecosystem (std/iter.lang) is built. Generic bounds (<T: Add>, where T::Item: Add) carry operators/methods onto bounded type parameters; a bare <T> is move-only, <T: template> the late-checked escape hatch. The design/status: doc/planned/Modules.md, doc/planned/GenericBounds.md.
  • builtin fn name(...) :> R; declares a function without a body whose implementation lies in the lang_rt prelude (lang_rt::name, with generics lang_rt::name<T>). Runtime primitives like alloc/free can thereby be addressed in lang and encapsulated behind RAII classes (examples/box.lang); with references instead of pointers the call stays in the safe core. Details: doc/planned/Builtin.md.
  • References after the C++ model, no borrow checking: &T is a read view without exclusivity, and several & mut T onto the same memory are allowed. Const propagates through ownership (fields, arrays, Box, Vec — mechanically via receiver overloading), not through borrows (the target mutability sits in the reference type). The address of a temporary extends its lifetime to that of the binding (like C++ const&).
  • Blocks are expressions and return the last expression not terminated with a ;. Assignments are statements.

Part II — the compiler

How lang is built: the Rust pipeline (lexer → parser → resolve → sema → emit), the data structures, the C++ backend, the diagnostics and the tests.

The implementation language: Rust

We evaluated several languages (see the chat history): OCaml, TypeScript, Swift, Kotlin, C#, Zig itself. The choice is Rust for the following reasons:

  • Enums + match cover 90% of the requirements on an AST. Exhaustiveness checking prevents a whole class of bugs when the AST grows.
  • The ecosystem for compiler construction is unrivalled: ariadne for diagnostics, insta for snapshot tests, logos as a lexer generator (if wanted), chumsky as a parser combinator (if wanted).
  • Cargo + rust-analyzer are a frictionless setup without configuration effort.
  • Robustness: if the project becomes serious one day, the language does not have to be changed.
  • A C-like syntax, which is readable for the author.

The deliberate costs of this choice:

  • Recursive data structures need Box or arena allocation. We choose the Box variant (see below) — it is the more readable of the two, and readability is project goal number one.
  • Symbol tables and annotated AST nodes are more laborious than in a GC language. We solve that with side tables (HashMap<NodeId, T>) instead of references in the AST.

The backend: C++

We emit C++20 (not C++23, in order to keep the compiler requirements low; individual C++23 features like std::expected we would rebuild ourselves as needed).

Why C++ and not LLVM or machine code directly:

  • C++ has native constructors and destructors. The mapping is direct and maintainable.
  • C++ compilers (clang, gcc) take over the optimization. We do not have to build an optimizer of our own.
  • Debugging the compiler is easier, because the output format is a human-readable program.
  • No LLVM setup, no inkwell dependency, no Cranelift.

The mapping principles (initial):

lang C++
a struct type [x: Int, y: F32] one deduplicated struct with a generated name per structural type
type Foo = [...] an alias onto the structural struct (no C++ type of its own)
type Foo = distinct T erased to the representation of T — the nominality exists only in the type system
type Foo = class [...] a class Foo with a move ctor/assignment (which establishes the null state); a copy ctor from copy, otherwise = delete
init / copy / move / deinit a constructor / copy ctor / move ctor / destructor
fn (s: &T).f(...) the method T f(...) const (free, in the module of T)
fn (s: & mut T).f(...) the method T f(...) (non-const)
an associated / free fn a static member resp. free function
a function type (x: Int) :> Int a function pointer int (*)(int)
a lambda without captures a function pointer resp. a C++ lambda
a lambda with captures a generated struct (the captures as members) with an operator()
an interface value a fat pointer { data*, vtable* }; the vtable generated per auto/manual conversion
&T / & mut T const T& / T&
*T T*
[] (the unit type) an empty struct Unit {} (not void, so that Unit is first-class)
var x = e; / const x = e; auto x = e; / const auto x = e;
a file (a module) an internal namespace lang_fN { ... } (the entry file stays global)
integer arithmetic overflow-checked (e.g. __builtin_add_overflow), an overflow → a panic
array indexing range-checked, out of range → a panic

A note on init: earlier designs mapped init as a static factory. The current init initializes through the & mut receiver (fn (s: & mut T).init(...)) in place — that corresponds exactly to a C++ constructor and is emitted as such. Named additional constructors are ordinary associated fns that internally call init.

Whole-program codegen — one translation unit: the compiler translates the whole program (all imported files) into one C++ file plus a fixed runtime prelude (panic, Unit, box helpers). Every file becomes an internal namespace (lang_f1, lang_f2, …), so that identically named free functions from different files do not collide; the entry file (never imported) stays global, and its main becomes lang_main. Methods need no namespace — their type tag (S0_sum) is already globally unique. There are no generated headers, no ODR risk, no include order. That fits the demand-driven sema: monomorphization, structural type deduplication and vtable emission are whole-program activities anyway. Separate compilation would be interesting for incremental building — a non-goal today, but designed as an expansion stage (see doc/planned/CompilerArchitecture.md and doc/planned/Modules.md). The emission order: the prelude, the type definitions, the forward declarations of all functions, then the definitions — order independence is thereby trivial.

Multi-file programs — file = module (the TypeScript style): every file is a namespace of its own; export on a top-level item makes it visible from outside, everything else is file-private. Module-local visibility within a file is governed by priv; the conformance and collision rules (inherent vs. interface methods, override for default methods, duplicate detection) are implemented (the module system part I). Incremental building across module boundaries (part II) is designed but not yet implemented — see doc/planned/Modules.md. import { A, B as C } from "./file.lang"; binds named exports (with an optional as alias) directly, import * as ns from "./file.lang"; binds a namespace alias for qualified access (ns.A, in type position too: ns.Point). An import binds names and pulls the target file transitively into the build — there is only this one mechanism. Loading happens from the root file, every file exactly once (dedup over the canonicalized path — import cycles are thereby harmless); paths are relative to the importing file. Internally every file gets a global offset range in a SourceMap (the rustc idea) — spans stay a (start, len) pair, and diagnostics compute back to file:line:column. Qualified calls (ns.f(x)) parse as a method call; resolve recognizes the namespace alias and fixes the reference at the call node, so that sema/emit treat it like a free call.

Methods — one form, bound to the type: a method is a free function with a receiver (fn (s: &T).m()) on a nominal type (class/distinct). There are no extension methods and no impl blocks for methods — methods always stand free in the module of their type, and a coherence rule replaces the earlier import visibility (the Go model). (impl I for T [ … ] serves solely the explicit join to a nominal distinct interface, not the defining of methods — see above):

  • A method has to stand in the same scope as the declaration of its type — the same file and the same block (method.file == type.file && method.parent_block == type.parent_block, checked in resolve through receiver_alias).
  • Thereby the whole method set belongs to the type and travels with it: if you have the type (imported too), you have its methods — no method import (import { T.m } is an error), no export on methods.
  • priv fields are accessible from the methods of the same type (= the same scope).
  • Self stands in a method for the fully applied receiver type (fn (s: &Box<T>).m() ⇒ Self = Box<T>) — in every position except the receiver head (there it is circular): further parameters (o: & mut Self), the return type (:> Self), a body annotation (const t: Self = [...]) and as a constructor Self(n) / Self([...]). The parser binds Self to the receiver type as soon as its head has been parsed.

Sema registers all methods in one table (methods, unique per (type, name)), emits globally through the (unique) type tag (Point_sum); the dispatch simply looks it up there and files the target in method_targets. Interface conformance (auto(&x)) uses the same lookup — the vtable is built from the type's fixed method set (auto_targets); nobody makes a type conformant after the fact through an import.

Local items — fn, type, methods in every block. Functions, types and methods may stand in every function body/block; a method of a local type stands in the same block as the type:

fn main() :> Int = {
    const a = dbl(10);              // block-hoisted: usable before the definition
    fn dbl(x: Int) :> Int = x * 2;

    type Meters = distinct [n: Int];
    fn (s: &Meters).get() :> Int = s.n;               // the same block as Meters
    fn (s: &Meters).doubled() :> Int = s.get() * 2;

    const m: Meters = [n = 5];
    a + m.get() + m.doubled()
};

The rules (as with Rust items):

  • No captures. A local fn sees its parameters, other items and globals — but no locals of the surrounding scope. For capturing there are lambdas.
  • Block-hoisted. Within their block, local items are visible everywhere, before the textual place too — mutual recursion included.
  • Strictly lexical. A local type/a local function does not leak into the file scope; a method of a local type has to stand in the same block as the type (the coherence rule — not in an inner one).

The parser lifts local items into the flat program vectors and marks them with a parent_block (the NodeId of the block). Resolve builds from that block_scopes (the items per block), block_parent (the nesting) and block_owner (a block → the enclosing function), and both the resolve walker (value position) and sema (type position) resolve through the stack of open blocks. In the C++, identically named local functions are made unique through an index suffix (helper__L7) and identically named local distinct types through deduplicated tags (Tag, Tag_2).

Local items in generic functions are monomorphized along: a local item in the body of a generic function is itself a template (sema/emit skip it, recognized via block_owner), and when instantiating the enclosing function, instantiate_fn clones the nested items with the same type arguments and re-hangs them onto the cloned blocks through a block-ID mapping (old→new) — recursively at arbitrary depth through a worklist. A local type/fn may thereby use the type parameter T, and every instantiation gets its own clones.

The emitted code is piped through clang-format, so that the output stays readable. That is valuable for us too when debugging the compiler.

The compiler architecture

The compiler is today a linear pipeline of pure functions. No plugin-like system, no middleware, no query-based design — for the current whole-program build the latter would be overengineering. A query model (the Salsa/rustc style) is recorded as a later goal, as soon as separate compilation or an IDE/LSP justifies it — see doc/planned/CompilerArchitecture.md.

source file (a String)
    │
    ▼
[lexer]                → Vec<Token>
    │
    ▼
[parser]               → an Ast (Box-based, NodeIds)
    │
    ▼
[name resolution]      → a SymbolTable (a side table)
    │
    ▼
[sema]                 → a TypeTable (per instance), a list of instances
 (type checking +
  comptime eval)
    │
    ▼
[C++ emitter]          → a String (C++ source code)
    │
    ▼
[clang-format]         → formatted C++
    │
    ▼
[clang++ / g++]        → an executable

Deliberate simplifications:

  • No high-level IR (HIR) or mid-level IR (MIR). We work directly on the AST plus side tables. We would only introduce a separate IR if we wanted to build optimizer passes — which is a non-goal.
  • Name resolution stays a pass of its own; type checking and comptime evaluation merge into one pass ("sema", as in Zig). The separation checker/interpreter is not tenable with comptime: the type of Vec<Int> only comes into being through the execution of Vec — the checker and the interpreter would have to call each other constantly. So they are one tree walker (details in the comptime section). Name resolution, by contrast, is purely lexical — comptime produces no new names — and stays an independently understandable pass. A known blur: method calls (v.distance()) can only be resolved once the type of v is known — the method resolution therefore takes place in sema. The resolve pass takes care of variables and free functions.
  • The AST is immutable after the parsing. All subsequent passes produce side tables, they do not mutate the AST.
  • A handwritten lexer and parser instead of a generator. With a small language, a recursive-descent parser with Pratt parsing for expressions is the clearest and produces the best error messages. We deliberately forgo logos and chumsky, in order to reduce dependencies and magic.

Comptime and generics

We adopt Zig's central concept: generics are no language feature but a by-product of comptime. A generic type is a function that returns a type at compile time — the <T> syntax is only sugar for comptime type parameters:

type Vec<T> = {
    // Blocks are expressions: arbitrary comptime checks for better
    // error messages, then the class type is returned.
    assert(T != Test);
    class [
        priv ptr_: *T,
        // ...
    ]
};

What holds for types by now holds for values too: an array length [T; N] is an arbitrary comptime expression ([Int; 2 * 4]), and <const N: Int> declares a comptime value parameter. It is — like a type parameter, without a turbofish — inferred from the call (e.g. from the length of an array argument: fn sum<const N: Int>(a: &[Int; N]) binds N to the field count) and monomorphized over the value: two Ns yield two instances. Type aliases take value arguments too: type Grid<const N: Int> = [Int; N], used as Grid<8> / Grid<MAX> / Grid<2 * 2> (mixed with types: Arr<Int, 3>). Where inference does not suffice, there is a turbofish in expression position — identity<Int>(x), constN<10>(x), Buf<3>(…) (unambiguous in lang, because a < b > c is always a type error anyway). Add to that top-level consts (const MAX: Int = 2 * 4;) — implicitly comptime at module level, baked in at every use (no C++ global) and nameable as an array length too ([Int; MAX]). Details in doc/planned/Comptime.md (stage 3).

Restrictions in version 1 (deliberate, all liftable later):

  • Comptime is pure. No comptime var, no pointers in comptime memory. Comptime pointers would need a memory model in the interpreter (aliasing, mutation, the reification of pointers into emitted constants) — historically the most error-prone corner of the Zig compiler.
  • Comptime values are only primitives, structures and types — no class values. Otherwise move semantics, the null state and implicit destructors would have to be implemented a second time in the interpreter, exactly consistently with the emitted C++. Comptime functions may of course return class types — that is exactly what they are there for.
  • No I/O, no external calls — as in Zig: the language minus the outside world.
  • An execution budget against endless loops (Zig's branch-quota idea).

The implementation — three ideas from the Zig compiler (but not its structure: the ZIR/AIR instruction IRs and incremental analysis serve performance goals we do not have; we work directly on the AST):

  1. Sema: the checker and the interpreter are one tree walker. Every expression evaluates to a (Type, Option<Value>). Some(value) means comptime-known; a comptime context simply demands a Some. Constant folding falls out for free, and there is no boundary between "checking" and "executing" that would have to be kept in sync.
  2. An InternPool: types and comptime values are interned (TypeId, ValueId). That resolves two identity questions in one go on the side: Vec<Int> has to be the same type at every call (the memoization of instantiations is semantically mandatory, not an optimization), and structurally equal types like [x: Int, y: Int] have to fall onto the same TypeId everywhere.
  3. A demand-driven analysis from the roots (main, exported functions). Generic bodies are only parsed and their names resolved; fully checked they are per instantiation (monomorphization): Vec<Int> and Vec<F64> are two separate, each completely checked instances. Side tables are correspondingly keyed with (NodeId, instance).

The mapping to C++: every monomorphized instance becomes a concrete C++ class/function with a mangled name (Vec__Int). Two obvious shortcuts we deliberately do not take:

  • No C++ templates. That would delegate our type checking to clang — errors in generic code would come back as template error messages in the generated code.
  • No constexpr. Then our compiler would not know the values, so they could not determine any types — and comptime errors would likewise be reported by clang instead of by us.

A consistency obligation: the interpreter and the emitted C++ have to have the same semantics (integer overflow, division/modulo with negative numbers, shifts). Every deviation is a miscompile: comptime f(x) would yield something different from f(x) at runtime. See the open questions.

The data structures: a Box AST + NodeIds

AST nodes own their children directly through Box<Expr>. In addition, every node gets a running NodeId at parsing, through which later passes file their results in side tables (HashMap<NodeId, Type>).

We initially considered an arena with typed IDs (the rustc pattern) but decided against it: the listed advantages were mostly performance — and "clarity before performance" is project goal number one. Since the AST is immutable after the parsing, &Expr traversals with Box work entirely without conflict.

The motivation for Box:

  • Direct pattern matching: match &expr.kind instead of a detour through arena[expr_id].
  • Traversals need no arena parameter — every function that has an &Expr sees the whole subtree.
  • #[derive(Debug)] simply works — no AstFormatter helper necessary in order to resolve IDs.
  • Side tables stay natural: a HashMap<NodeId, Type> instead of a field in the node (keyed per instance with generic code, see the comptime section). The AST thereby stays really immutable.

A sketch:

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct NodeId(u32);

pub struct Expr {
    pub id: NodeId,
    pub span: Span,
    pub kind: ExprKind,
}

pub enum ExprKind {
    Int(i64),
    Ident(Symbol),
    BinOp { op: BinOp, lhs: Box<Expr>, rhs: Box<Expr> },
    Call { callee: Box<Expr>, args: Vec<Expr> },
    // ...
}

Stmt/StmtKind and Decl/DeclKind follow the same pattern; all share the parser's NodeId counter.

The deliberate costs:

  • One allocation per node. Irrelevant for our project goals.
  • The mapping NodeId ↔ node exists only implicitly (the parser assigns IDs consecutively). Passes that have to get from a NodeId back to the node do not exist in the pipeline design — side tables are always read while traversing the AST.

Error handling and diagnostics

  • We collect errors instead of aborting at the first one. The compiler produces a list of Diagnostics after every phase. Only if the list is not empty does the pipeline abort.
  • ariadne as the diagnostics library. It delivers colourful, multi-line error messages with underlined source spans, notes and suggestions — comparable with rustc.
  • Every AST node gets a Span (a byte offset + a length in the source file), which is reused for diagnostics.
  • No panic! in the compiler code except with real internal bugs ("unreachable"). Language-level errors are always Diagnostics.

The testing strategy

We rely on snapshot tests with insta. For every compiler phase there are directories with input/reference files:

tests/
  parser/
    hello.lang               ← the input
    hello.lang.snap          ← the expected AST output (human-readable)
  emit/
    hello.lang
    hello.lang.snap          ← the expected C++ output
  errors/
    undefined_var.lang
    undefined_var.snap       ← the expected error message

With deliberate changes: cargo insta review shows the diffs and one accepts the new output. That is ideal for a compiler under development — regression detection without laborious test writing.

In addition:

  • End-to-end tests: a small lang program → C++ → clang++ → run the executable → check the exit code / stdout. Few, but important tests.
  • Unit tests only for non-trivial isolated building blocks (e.g. the Pratt-parser precedence tables).

We write no classical unit tests for every function, because that rarely helps with compiler code — the interesting state is mostly the entire AST.

The project structure

We start with a single crate, not with a workspace. A workspace only makes sense once we have several independent binaries or a public library.

lang/
├── Cargo.toml
├── README.md                  ← this document
├── src/
│   ├── main.rs                ← the CLI (parses arguments, calls the pipeline)
│   ├── lib.rs                 ← re-exports, the pipeline orchestration
│   ├── span.rs                ← Span, SourceMap
│   ├── diagnostic.rs          ← Diagnostic, Reporter (uses ariadne)
│   ├── lexer.rs               ← Token, Lexer
│   ├── ast.rs                 ← the AST types, NodeIds
│   ├── parser.rs              ← recursive descent + Pratt
│   ├── resolve.rs             ← name resolution
│   ├── types.rs               ← TypeId/ValueId, InternPool
│   ├── sema/                  ← type checking + comptime + generics (several modules)
│   ├── instantiate.rs         ← monomorphization (a template → an instance)
│   ├── movecheck.rs           ← the use-after-move analysis
│   └── emit/                  ← the C++ code generator (several modules)
├── examples/
│   ├── hello.lang            ← Fibonacci (exit 55)
│   ├── tour.lang             ← the authoritative language reference: a feature tour (exit 42, tested)
│   ├── box.lang              ← a Box over `builtin fn alloc`/`free` (exit 42)
│   └── multifile/            ← a multi-file program with `import … from`
└── tests/
    ├── parser/
    ├── emit/
    ├── errors/
    └── e2e.rs                 ← the end-to-end tests

Why no workspace now:

  • One crate = one cargo check, a shorter iteration.
  • Module boundaries in Rust are strong enough for a clean separation.
  • Splitting up is trivial later (cargo new --lib and setting the dependencies).

Why these module boundaries:

  • ast is central and is used by many modules — it stands alone.
  • resolve and sema are separate, because resolve works purely lexically and can be understood independently. sema unites type checking and comptime evaluation (why, stands in the comptime section).
  • emit knows nothing about resolve/sema internally, it only reads the side tables and the instance list. Codegen is thereby exchangeable.

The dependencies

Minimalistic. Every dependency has to justify itself.

The crate The purpose An alternative considered?
ariadne beautiful error messages codespan-reporting — ariadne is newer and a simpler API
insta snapshot tests self-written string comparisons — not comfortable enough
clap CLI argument parsing pico-args, manual parsing — clap is the standard and costs nothing

Deliberately not included:

  • logos (a lexer generator): handwritten is clearer and the lexer is short.
  • chumsky / lalrpop / pest (parsers): handwritten produces better error messages and is more readable with a small language.
  • inkwell / LLVM: we emit C++, not LLVM IR.
  • serde: we serialize nothing. It is not needed.

Open design questions

These points are deliberately only decided when they come up — with more context.

Currently none — all design questions so far are decided and documented in examples/tour.lang, the sections above resp. under doc/planned/. New questions land here.

A short reference for later

If this document is read in a few weeks, the most important points are:

  • Rust, one crate, no LLVM.
  • examples/tour.lang is the language reference — with contradictions it wins.
  • Structures structural + copy, classes nominal + move. Classes have init/move/deinit and a null state that move establishes in the source; deinit is a no-op on the null state, and RAII is implicit. Move-only by default — copyable only with a self-defined copy; move is generated if it is missing (except with a deinit — then explicitly). Statically visible use-after-move is a compile error (the move checker). distinct makes nominal types without class semantics.
  • fn for all type-level functions; overloading only through the receiver. : declares fields, = initializes. Lambdas capture by value (an anonymous struct); function types are function pointers. Structural interfaces through an implicit conversion / auto with a fat pointer + a vtable; nominal ones (distinct interface) through an explicit impl I for T. References after the C++ model; const propagates through ownership, not through borrows.
  • A Box-based AST with NodeIds, immutable after the parsing, side tables for the analysis results.
  • Comptime is the sole generics mechanism (<T> is sugar). Sema unites type checking and comptime evaluation: every expression delivers a (Type, Option<Value>). Types interned in the InternPool — for structural type identity too. Monomorphize ourselves — no C++ templates, no constexpr.
  • Comptime v1 is pure: no comptime var, no pointers, no class values, no I/O.
  • Errors are values: Result<T, E> + ?, Option<T> (stdlib enums); panic for bugs; no UB with integer arithmetic and indexing (the C++20 semantics plus checks).
  • A handwritten lexer + a recursive-descent parser with Pratt.
  • ariadne for errors, insta for tests.
  • C++20 as the backend, one translation unit for the whole program, clang-format as the post-processing.
  • Work in small, independently testable steps — every step ends runnable (cargo test green).

License

Licensed under either of

at your option — the dual license customary in the Rust ecosystem: MIT is short and permissive, Apache-2.0 additionally grants an explicit patent license.

Note that the emitted C++ contains parts of the compiler's own sources: the lang_rt preamble and whichever pieces of std/ the program uses. Both licenses permit that without imposing conditions on your program, so what you compile with lang stays yours.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

About

Specification and compiler for an experimental programming langauge

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages