a compiler for a small statically-typed, expression-oriented language with an affine ownership model, lexical regions & borrows, kinds, generics (monomorphised), and typeclasses, structured as a sequence of IR transformations from parsed source to LLVM IR.
requirements:
-
llvm-21 (
brew install llvm@21,apt-get install llvm-21, https://github.com/llvm/llvm-project/releases/tag/llvmorg-21.1.8) -
cc -
git clone https://github.com/andtsa/sand && cd sand -
cargo buildto compile the compiler & all utilities
now you have the 2 main binaries: target/debug/sand-cli and target/debug/sand-lsp, as well as several other utility binaries in target/debug/.
# use it to compile `.sand` files to executables:
sand-cli compile <path-to-file.sand> --output <output-file> -v # -v or -vv for verbose output
# or multiple files at once:
sand-cli compile <path-to-file.sand> <path-to-other-file.sand> ...
# dump the AST to stdout:
sand-cli compile <path-to-file.sand> --print-ast
# or emit LLVM IR:
sand-cli compile <path-to-file.sand> --emit-llvm
# ... and more
sand-cli --helpfor projects with multiple files, a sand.toml can be used to group them together:
[project]
name = "my-project"
sources = [
"src/",
"main.sand"
]sand-lsp
unfortunately most IDEs nowadays do not support custom LSPs out of the box, and instead require a plugin or extension to be installed (which doesn't exist for sand).however if you're using vim/nvim, you can add the lsp with:
vim.filetype.add({
extension = {
sand = "sand",
},
})
vim.lsp.config["sand"] = {
cmd = { "/path/to/sand-lsp" },
filetypes = { "sand" },
root_markers = { "sand.toml" },
}
vim.lsp.enable("sand")see examples/afp for sample files for each of the tasks in the project.
Sand is expression-oriented and statically typed. Every construct is an expression with a type.
def fib(n: Int): Int :=
if n ≤ 1 then n else fib(n - 1) + fib(n - 2)
def main(): Int := {
let mut x = 10;
x = fib(x);
println(x);
0
}
its grammar is defined in grammar.pest, and the parser is autogenerated by pest.
the type system, kinds, regions & borrows, ownership, generics, typeclasses, and the memory model, is specified formally in Calculus.md
Int, Bool, Unit, tuples ((Int, Bool)), user-defined enums/adts (type Ordering = Lt | Eq | Gt), OCaml-style polymorphic variants (without subtyping):
def check(x: Int): #one | #two | #other :=
if x < 0 then #one else if x > 0 then #two else #other
{ (stmt;)* expr? }
statements are executed in order,
the final expression is the block's value; omitting it gives Unit.
Statement ::=
| Declaration ("let" "mut"? pattern (":" type)? "=" expr ("else" expr)? ";")
| Assignment ((identifier | "*" expr) "=" expr ";")
| Expression (expr ";")
a declaration may bind a single name or destructure a tuple/constructor pattern; *r = e writes through a &mut.
let mut? name(: Type)? = value
variables are immutable by default, type annotations are optional.
let x = 10;
let y: Int = 20;
let mut z = x;
z = z + y;
anonymous functions are written fn (x: T) -> e. they are first-class values of function type T -> U, so they can be passed to higher-order functions like fmap. a lambda may capture locals from the enclosing scope; a closure that outlives the frame it captured from has its environment heap-allocated.
let bonus = 13;
let with_bonus = fn (x: Int) -> x + bonus;
fmap(Option#Some(21), fn (n: Int) -> n * 2)
match expr { variant => expr, variant => expr, _ => expr }
matches must be exhaustive. a match on an owned value consumes it; a match on a reference (&T / &mut T) destructures through the borrow, binding each field as a & / &mut borrow instead of moving it (which is how clone is written for non-Copy aggregates).
does not matter.
Multi-file projects; module::function call syntax; module name == file name, unless explicitly specified by module x; (possibly multiple modules per file).
type & lifetime parameters on def and type; instantiations are monomorphised away before codegen (no generics survive into MIR).
def id<a>(x: a): a := x
type Option<+a> = #none | #some(a)
every value is affine (used at most once). passing by value moves it; using a moved value is an error, unless the type is Copy. destruction is implicit (RAII): owned values are dropped at the end of their scope, in reverse declaration order, with a completing drop on branches where a value would otherwise leak.
let xs = make_list();
consume(xs);
consume(xs); // error: `xs` was already moved
&e / &mut e borrow a value without consuming it; *r reads through a reference and *r = e writes through a &mut. references carry a lexical region (&'r T), and a borrow may not outlive its referent; the escape check rejects returning a reference to a local.
def max<'a>(x: &'a Int, y: &'a Int): Int := if *x > *y then *x else *y
def incr(r: &mut Int): Unit := *r = *r + 1
typeclass / impl, with methods called as ordinary functions (resolved by argument type) and dispatched via monomorphisation
typeclass ToInt<T> {
def to_int(x: T): Int
def is_zero(x: T): Bool := if to_int(x) == 0 then true else false
}
impl ToInt for Bool { def to_int(x: Bool): Int := if x then 1 else 0 }
def use_it<T>(x: T): Int where T : ToInt := to_int(x)
any block with a top-level <- bind is a do-block over a Monad, desugared to nested bind calls. ordinary lets between binds stay pure; the trailing expression is the block's monadic result. the short-circuiting (e.g. on Option#None) comes from the instance's bind, not from the language.
def compute(d: Int): Option<Int> := {
x: Int <- safe_div(100, 5);
y: Int <- safe_div(x * 2, d);
Option#Some(x + y)
}
heap allocation is opt-in via deriving Heaped on a type; a (mutually) recursive type must derive it (else it would be infinite-sized). non-recursive types are stack tagged-unions. the compiler stays allocation-agnostic, since it knows only Ptr<T>, extern FFI, and a Heaped lowering protocol; malloc/free and the Unique strategy live in core.sand. drops free deterministically.
type Expr = Lit(Int) | Add(Expr, Expr) | Neg(Expr) deriving Heaped
The compiler has five named IRs, each a distinct Rust type. no IR is mutated in place, each pass produces a new immutable AST.
flowchart LR
src["Source:\n.sand files"]
hhir["HHIR:\nper-file, untyped,\n`String` names"]
qhir["QHIR:\nmerged, untyped,\nreferences resolved"]
thir["Typed HIR:\nmerged, typed,\nkinds + generics"]
mir["MIR:\nflat CFG,\nbasic blocks"]
llvm["LLVM IR"]
src -->|parse &\n build_ast| hhir
hhir -->|uniquify\n& qualify| qhir
qhir -->|type infer/check| thir
thir -->|heap lower,\nownership,\nmonomorphise| thir
thir -->|explicate control| mir
mir -->|llvm codegen| llvm
HHIR (Highest HIR) ir_types/hhir.rs
the direct output of parsing: an untyped, per-file AST.
identifiers are represented as String names.
variable representation is a three-variant sum type:
HirVar = Decl(OriginalVarRef) -- a binding site (let x = ...)
| Unqualified(String) -- a use site, name not yet resolved
| Uniq(UniqVar) -- already uniquified (mid-pass state)
Similarly, function calls are unresolved strings:
HirFnCall = Local(String) | External { module, name }.
Expressions carry source location (Range), and no types.
If statements don't need an else branch yet. in later passes the else will be filled in with Unit.
One ProgramModule corresponds to one source file.
QHIR (Qualified HIR) ir_types/qhir.rs
- all modules are merged,
ProgramModuleis replaced byProgram { functions: Map<FunRef, Function> },- all variable occurrences are
UniqVar: opaque integers, one per binding site HirVarsum type is gone,Stringnames no longer appear in the tree- all function calls are
FunReforIntrinsic, string names have been checked against the global function table - Constructor patterns in
matchare resolved to(EnumRef, variant_idx)pairs; bare#tagliterals remain asTag { variant: String }for the type checker to resolve.
Typed HIR ir_types/typed_hir.rs
the typed ast and final HIR.
Exprcarriesty: Tyandkind: Kind, every node in the expression tree is annotated with its type and ownership kind (Owned/Borrowed/BorrowedMut/Never).- the
elsebranch becomes mandatory: anifwithoutelsehas itselsefilled in with the unit value, requiring the type of theifto beUnit. - declaration types are resolved since type annotations are no longer optional in the tree.
- bare
Tagexpressions are eliminated,#gtin a context expectingOrderingbecomesConstructor { enum_ref, variant_idx: 2 }. - this is also the layer the three
TypedProgram -> TypedProgramtransforms operate on (heap lowering, ownership/drop insertion, monomorphisation) before it is lowered to MIR, so generics, kinds, andderiving Heapedtypes are all gone by the time MIR is produced.
MIR Control Flow Graph ir_types/mir.rs
a CFG-based, register-machine IR, that somewhat mirrors LLVM IR. the expression tree is gone, each function becomes:
MirFunction {
name: FunRef,
params: Vec<MirParam>,
ret_type: Ty,
locals: Vec<LocalDecl>, // all variables declared upfront
blocks: Vec<BasicBlock>, // linear sequence of basic blocks
entry: BlockId,
}
BasicBlock {
id: BlockId,
statements: Vec<Statement>,
terminator: Terminator, // Goto | Branch | Return | Unreachable
}a Statement is an Assign { dst, rvalue }, an Eval (an rvalue run for its side effects), or a Drop.
RValue is flat, with no nesting (ANF): Use, BinaryOp, UnaryOp, Call, IntrinsicCall, CallIndirect, Ref (address-of), Field, Aggregate, Closure, SizeOf.
control flow is explicit via Terminator::Branch { cond, then_bb, else_bb }
generated from MIR via inkwell
parsing & building the AST (passes/parse.rs, passes/build_ast/)
two steps treated as one, pest produces a parse tree, then build_ast folds it into HHIR.
the fold is a structural recursion over the grammar's rule tree, mapping each grammar rule to its corresponding HHIR node.
uniquify passes/qualify/uniquify/mod.rs
ProgramModule -> State ScopeStack (Result ProgramModule UniquifyError)
the pass is a fold over Expr that carries a mutable scope stack as state. The scope stack is Vec<Map<String, UniqVar>>, with enter_scope/exit_scope, bracketing each block and function body. Binding sites (HirVar::Decl) generate a fresh UniqVar and push it; use sites (HirVar::Unqualified) look up the innermost binding.
Qualify passes/qualify/mod.rs
Resolves HirFnCall::Local(String) and HirFnCall::External { module, name } to global FunRef indices by looking up the global function table in CompileCtx. Also resolves constructor names to (EnumRef, variant_idx). Merges the per-file ProgramModule values into a flat Program.
Type checking passes/type_ast/
bidirectional type checking1, split across two mutually recursive functions:
-
infer(ctx, env, expr) -> Result<TypedExpr, Error>: synthesises a type and kind bottom-up. EachTypeEnventry carries the binding's type, mutability, kind, and home region (the scope it was introduced in, used by the escape check); the env is threaded as an immutable reader -
check(ctx, env, expr, expected) -> Result<TypedExpr, Error>: verifies an expression against a known type, propagating it into sub-expressions. used to resolve bare#tagliterals, and to propagate the expected type throughif-branches and block tails
check delegates to infer for all forms it doesn't handle specially, then verifies the synthesised type matches the expected one
Block typing is a monadic fold (try_fold = foldM over Result):
statements.iter().try_fold((vec![], env.clone()), |(mut stmts, mut env), stmt| {
stmts.push(infer_statement(ctx, &mut env, stmt)?);
Ok((stmts, env))
})each statement extends the environment, threading it into the next
CompileCtx is passed as an immutable reference throughout (a ReaderM environment holding global tables (function signatures, enum definitions, variable names)).
the "mutable" TypeEnv is local to each function body, cloned at each branch point to preserve the scoping invariant.
it wraps an im::HashMap2 (a persistent immutable hash map) and is cheaply cloneable. "mutable" serves just as a rust annotation, not as actual runtime mutable state.
match exhaustiveness is checked by a usefulness algorithm: the match is exhaustive iff an all-wildcard row is not useful against its arms, i.e. no uncovered witness value exists. the same machinery flags unreachable arms (an arm that is useless against the ones before it). this handles literal and nested patterns, not just flat variant coverage.
this pass also resolves generic instantiations (unifying parameters against argument types), checks kinds, and enforces region safety: borrows carry a lexical region, and the escape check rejects any block result or function return whose type's free regions mention a region that does not outlive the boundary ('r ∉ freeRegions(T)). it does not check affinity; that is the ownership pass below.
Heap lowering passes/heap_lower.rs
TypedProgram -> TypedProgram
rewrites every deriving Heaped enum into a Unique<Node> handle over the core-lib allocator: a heaped E<a> becomes Unique<E$Node<a>> (a synthesised, non-recursive node enum), E#C(p) becomes unique_alloc(E$Node#C(p)), and a consuming match/let-pattern becomes unique_take + an ordinary node match. runs before ownership (so drops land uniformly on the resulting handles) and before mono (so the injected unique_* calls monomorphise normally). after this pass no heaped enum survives: every later pass sees only ordinary enums, Unique handles, and Ptr ops.
Ownership & drop passes/ownership/
TypedProgram -> Result<TypedProgram, OwnershipError>
a move/borrow dataflow analysis over the typed program. following the same RAII principles as rust,
it inserts drops. OwnershipEnv (an im::OrdMap keyed by UniqVar, so key order is declaration order) tracks each variable as Owned/Moved plus its live borrows. it enforces:
- affinity: using a non-
Copyowned variable marks itMoved; a second use is an error (hintingclone(&x)when the type isClone) &mutexclusivity: a mutable borrow conflicts with any other live borrow of the same place; borrows are released non-lexically, pruned once the holder's last use has passed (with a lexical block-exit restore as a backstop), andif/matchmerges union them- drop placement: at scope exit, every owned non-
Copylocal is dropped in reverse declaration order; at a branch merge, a value owned on one branch but moved on another gets a completing drop. these are recorded inBlock { drops }and lowered to a first-class MIRStatement::Drop.
this is where the affine discipline lives: the type checker's context is structural (it never removes a variable on use), so ownership is a separate analysis over the already-typed tree.
Monomorphisation passes/mono.rs
TypedProgram -> TypedProgram
specialises every generic function and enum for each concrete instantiation it is used with, reachability-driven from the non-generic roots (memoised, so recursive generics terminate). a generic method call becomes a concrete Call. the output has no Ty::Param and no Ty::App left, so MIR and codegen only ever see fully concrete types.
Explicate Control passes/explicate_control/
TypedProgram -> MirProgram
a continuation-passing lowering of the expression tree into basic blocks.
FnCx accumulates blocks and locals as mutable state, functioning as StateT.
this code is adapted (effectively 1-1) from the explicate control assignment of CS4555 Compiler Construction.
Persistence
Persistence is used very effectively in several places in the IR transformations.
Most notably, in the Ownership pass,
the OwnershipEnv state holds the ownership state for each variable.
When exploring branches of if/match statements, the state is cloned to preserve the state before the branch.
Since im uses a persistent map, cloning is cheap, and we can access the shared
history from within each branch without any additional overhead.
#[derive(Debug, Clone, Default)]
pub struct OwnershipEnv<'tcx> {
states: Map<UniqVar<'tcx>, OwnershipState>,
borrows: Map<UniqVar<'tcx>, Vec<Loan<'tcx>>>,
types: Map<UniqVar<'tcx>, Ty<'tcx>>,
}
pub fn merge(left: &Self, right: &Self) -> Self {
let mut merged = left.clone();
// merge with right's states, borrows, and typesLenses/Optics
There's two main places where optics are used:- over the multiple variants of HirVar
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum HirVar<'tcx> {
Decl(OriginalVarRef<'tcx>),
Unqualified(String),
Uniq(UniqVar<'tcx>),
}using the prism defined in lang::compiler::optics to review/expect the Uniq variant after the qualify pass.
- traversals over the AST IRs:
Concurrency
The pipeline can be roughly partitioned into 2 phases:
- building the context
- using the context
(context here being CompileCtx)
during the first phase, the code is very much sequential,
since the passes need an &mut CompileCtx to work.
the second phase though is completely parallelizable,
since the CompileCtx is now immutable after the first phase,
and the previously interior-mutable Arenas are now read-only.
the two examples I will highlight are:
- Ownership check:
pub fn check<'tcx>(
ctx: &CompileCtx<'tcx>,
mut program: TypedProgram<'tcx>,
) -> Result<TypedProgram<'tcx>, Vec<OwnershipCheckError<'tcx>>> {
let functions = program.functions;
let results = functions
.into_par_iter()
.map(|(name, mut func)| {
let checker = OwnershipChecker {
ctx,
module: func.src_module,
type_constraints: func.type_constraints.clone(),
liveness: Liveness::analyze(&func.body),
};
let mut env = OwnershipEnv::new();
func.parameters.iter().for_each(|param| {
env.declare(param.name, param.ty);
});
let new_body = checker.check_expr(&func.body, &mut env)?;
let param_drops = checker.scope_exit_drops(&env, &HashSet::new());
func.body = attach_drops(new_body, param_drops);
Ok((name, func))
})
.collect::<Vec<CheckResult<'tcx>>>();
let (errors, functions): (Vec<CheckResult<'tcx>>, Vec<CheckResult<'tcx>>) =
results.into_iter().partition(Result::is_err);
if !errors.is_empty() {
return Err(errors
.into_iter()
.map(Result::unwrap_err)
.collect::<Vec<_>>());
}
program.functions = Map::from_iter(functions.into_iter().map(Result::unwrap));
Ok(program)
}and 2. explicate control:
pub fn from_typed_program(prog: &th::TypedProgram<'tcx>, ctx: &CompileCtx<'tcx>) -> Self {
let functions = prog
.functions
.par_iter() // here the change was literally just `iter()` -> `par_iter()`
.map(|(name, func)| (*name, lower_function(func, ctx)))
.collect();
Self { functions }
}.
├── Cargo.toml // workspace root
├── README.md
├── Calculus.md // formal type-system spec
├── examples/ // .sand programs for showcase & testing
├── grammar.pest // parser grammar
├── lang
│ ├── Cargo.toml
│ └── src
│ ├── analysis/ // reused expression analysis from CS4555 Compiler Construction
│ ├── bin/ // small utilities for debugging & visualization
│ ├── castles/ // project discovery & initialization, for multi-file compilation
│ ├── compiler
│ │ ├── context
│ │ │ ├── arenas.rs // interning arenas for types, kinds, symbols
│ │ │ ├── compile.rs // CompileCtx, the main state during compilation
│ │ │ ├── doc.rs // doc-comment storage (for the LSP)
│ │ │ ├── mod.rs
│ │ │ └── project.rs // ProjectCtx, the state for a single project
│ │ ├── diagnostics/ // diagnostics & error formatting
│ │ ├── mod.rs
│ │ ├── optics.rs // prisms/traversals over the IRs
│ │ ├── structure
│ │ │ ├── adts.rs // `AdtDef` (enums & their variants)
│ │ │ ├── debug.rs // source code `Pos` and `Range`
│ │ │ ├── functions.rs // `FunRef` etc
│ │ │ ├── mod.rs
│ │ │ ├── mtl.rs // `mtl`-style transformer helpers (compiler-internal)
│ │ │ ├── projects.rs // `CodeModule`, `CodeFile`, `ModuleRef`
│ │ │ ├── type_params.rs // generic parameter declarations
│ │ │ ├── typeclasses.rs // typeclass & instance tables
│ │ │ └── variables.rs // `UniqVar` etc
│ │ └── tests/
│ ├── core.sand // core library, included in every compilation
│ ├── interpreter
│ │ ├── mir.rs // an interpreter for the MIR
│ │ ├── mod.rs
│ │ └── typed_hir.rs // an interpreter for the typed HIR
│ ├── ir_types
│ │ ├── display/ // pretty-printing for each IR
│ │ ├── hhir.rs // the first high-level IR (AST)
│ │ ├── mir.rs // the middle-level IR (control flow graph)
│ │ ├── mod.rs
│ │ ├── qhir.rs // the second high-level IR (qualified AST)
│ │ └── typed_hir.rs // the final HIR (typed AST)
│ ├── lang
│ │ ├── intrinsics.rs // intrinsics for the language (e.g. println)
│ │ ├── mod.rs
│ │ ├── ops.rs // operators (`Bop`, `Uop`, `CompOp`, etc)
│ │ └── types.rs // the `Ty` enum
│ ├── lib.rs // `SandLangError` and `compile_hir`
│ ├── passes
│ │ ├── build_ast/ // build the AST (HHIR) from pest's output
│ │ ├── explicate_control/ // lower typed HIR to MIR
│ │ ├── heap_lower.rs // rewrite `deriving Heaped` types into `Unique` handles
│ │ ├── llvm_codegen.rs
│ │ ├── mod.rs
│ │ ├── mono.rs // monomorphise generics
│ │ ├── ownership // fn check(ctx, TypedProgram) -> Result<TypedProgram, OwnershipCheckError>
│ │ ├── parse.rs
│ │ ├── qualify
│ │ │ ├── error.rs
│ │ │ ├── mod.rs // combine modules & qualify variable and function names
│ │ │ └── uniquify // uniquify variable names & scope check
│ │ └── type_ast // bidirectional type checking
│ │ ├── check.rs // check(qhir::Expr == ty) -> Result<typed_hir::Expr, TypeError>
│ │ ├── errors.rs
│ │ ├── infer.rs // infer(qhir::Expr) -> Result<typed_hir::Expr, TypeError>
│ │ └── mod.rs
│ └── util/
├── sand-cli/ // compiler CLI
├── sand-lsp/ // language server binary
├── tests/ // test suite
└── treesitter/ // tree-sitter grammar for syntax highlighting