Noria

From source to a native binary

The compiler follows a facade pattern with checkpoints used for testing: StopAfter::Tokens, Ast, Typed, and Ir. C++ tests drive the same pipeline without writing files.

Ownership, no garbage collector

Strings, arrays, structs with heap allocated fields, and the stdlib containers are managed. Each one is freed exactly once. There is no garbage collector.

let b = a;                 // deep clone; a and b free independently
sequence_push(s, x);       // borrow; mutation is visible to the caller
return owned;              // move the local to the caller
return param;              // clone so the caller still has a valid value
holder.nested = [];        // free the old value, then store
let numbers: Sequence<i32>; // empty default is still owned
print("xy" + "z");         // concat allocates; the parts are freed
s[i]                       // string element: clone
a[i]                       // array element: borrow

Generated code tracks whether each value is owned. Arguments are borrowed, so a callee can mutate a container without taking it. Returning an owned local moves it; returning a parameter clones. Overwriting a field or index frees what was there first. Each scope has a flag containsPtr that is used to free resources on scope exit.

; block exit, only if scope.containsPtr

owned ← load bool from %buf.owned
if not owned: goto next_local

ptr ← load ptr from %buf.slot
call @free(ptr)                   ; [i32] heap buffer

; same owned-bit gate for other managed locals:
call @__noria.rt.drop_str(str_ptr)
call @sequence_drop$s.i32(handle) ; one monomorphized specialization

next_local:

; scalar-only scope (containsPtr = false)
; → no instructions inserted

Memory model & structs

Structs are stack-allocated value aggregates, with members accessed through compile-time known offsets.

Array data lives on the heap; the variable itself is a stack pointer to that buffer. Empty arrays and array concatenation are owned.

Function arguments borrow that pointer, so kth_largest(nums, k) sees the same buffer as the caller. let copy = nums is different: that's a deep clone, and the two arrays drop independently.

Passing nums borrows the pointer into the callee frame, both frames alias the same heap buffer. Assignment clones. Only scalars live entirely on the stack.

Compiler performance

Phase timings over 19,600 in-process compilations (196 inputs × 100 rounds, through LLVM IR) surfaced a hot path in monormphization and resolving stdlib imports. Through implementing frontier-only specialization and caching of frequently used AST components benchmark latency was reduced from 27.69s → 7.05s

Generics & monomorphization

Generic functions and structs infer type arguments at call sites, check implementation-tag constraints, then monomorphize only the reachable specializations before LLVM codegen. There is no type erasure and no vtable: each distinct T / I pair becomes a concrete body with a deterministic mangled name such as id$s.i32.

Abstract Data Types vs Data Structures

Many programming languages give users access to a wide variety of data structures, without having to define their interfaces. This can leave users confused about which data structures to use for which applications. For instance, in C++, vector, deque, and list are all sequences, but nothing about the name or high level code indicates that they are different from set.

Noria names the abstract data type first, then picks the structure as a compile-time tag, the user chooses the interface before the implementation. Leave the tag off and you still get a real default: Sequence<T> is arr, Dictionary and Set are hashmap. Changing a tag changes representation and complexity, not the API. Monomorphization erases the tag: there is no vtable and no runtime representation branch.

let seq: Sequence<i32>;                 // empty, impl arr
let map: Dictionary<i32, i32>;           // empty, impl hashmap
let tree: Dictionary<i32, i32, bst> = dictionary_new(0, 0);

Those representations are not compiler magic. Array growth, circular-sentinel lists, hashmap probing, BST links, and heapify live in stdlib/ as Noria. Heap algorithms are written against the Sequence interface, so a list-backed heap is still correct, and visibly slower, rather than special-cased.

fn sequence_new<T, I>(sample: T) -> Sequence<T, I> impl arr {
  let cap: i32 = 4;
  let header: __rt_ptr = alloc_bytes(16);
  let data: __rt_ptr = alloc_bytes(cap * size_of());
  let init0: i32 = store_i32_at(header, 0, 0);
  let init1: i32 = store_i32_at(header, 1, cap);
  let init2: i32 = store_ptr_at(header, 1, data);
  return Sequence<T, I> { handle: header };
}

fn sequence_new<T, I>(sample: T) -> Sequence<T, I> impl list {
  let sentinel: __rt_ptr = alloc_bytes(20);
  let self0: i32 = store_ptr_at(sentinel, 0, sentinel);
  let self1: i32 = store_ptr_at(sentinel, 1, sentinel);
  return Sequence<T, I> { handle: sentinel };
}

Case folding on names

Identifiers and keywords are folded to lowercase in the lexer so that an inconsequential capitalization difference is not a compile error. Count and count are the same binding; sequence_len and Sequence_Len are the same function. String literal contents keep their original casing, case still matters for data, not for names.

The decision is about what a name means. Accidental PascalCase after a camelCase declaration, or mixing a type-style capital with a later lowercase use, should not be a distinct symbol.

helper mean(values: Sequence<f64>) -> f64 {
  let Count: i32 = sequence_len(values);
  if count == 0 {
    return 0.0;
  }
  let i: i32;
  let Total: f64;
  while i < count {
    total = total + values[i];
    i = i + 1;
  }
  return total / (count as f64);
}

The lexer emits lowercase lexemes; type checking and codegen never see the original casing. Tests cover mixed-case source against the normalized token stream.

Headers that describe the function

fn, util, helper, and recfn are the same declaration as far as the compiler is concerned, they lex as one keyword and produce one AST node. The spellings exist so a header can state how the function is meant to be used without forcing a reader through the body.

Best practice in Noria source: fn for ordinary entry points and public operations; util for small, reusable operations (square, min, a cast wrapper); helper for logic that exists to serve one caller (merge, a partition step); recfn for functions whose interesting structure is recursion. The toolchain does not check that a recfn actually recurses, the annotation is a reading convention, not a second type system.

helper merge(values: Sequence<i32>, lo: i32, mid: i32, hi: i32) -> void {
  let i: i32 = lo;
  let j: i32 = mid;
  let k: i32 = 0;
  let tmp: Sequence<i32> = sequence_new(0);
  while i < mid && j < hi {
    if values[i] <= values[j] {
      sequence_push(tmp, values[i]);
      i = i + 1;
    } else {
      sequence_push(tmp, values[j]);
      j = j + 1;
    }
    k = k + 1;
  }
  return;
}

recfn sort_range(values: Sequence<i32>, lo: i32, hi: i32) -> void {
  if hi - lo <= 1 {
    return;
  }
  let mid: i32 = lo + (hi - lo) / 2;
  sort_range(values, lo, mid);
  sort_range(values, mid, hi);
  merge(values, lo, mid, hi);
  return;
}

Return types when they help the reader

A trailing -> Type is optional so headers are not forced to repeat what the body already determines. Best practice is the opposite of “always omit”: keep an explicit annotation on functions that other code calls often, so a reader can take the result type from the header. Omit it on internal helpers whose only job is to return whatever the body computes.

When omitted, the typechecker unifies every return into one result type, including across mutually recursive functions, generics, structs, and arrays. Bare return; infers void.

fn identity<T>(value: T) {
  return value;
}

fn even(value: i32) {
  if value == 0 { return true; }
  return odd(value - 1);
}

fn odd(value: i32) {
  if value == 0 { return false; }
  return even(value - 1);
}

fn main() {
  if even(6) {
    return identity(4) + 4;
  }
  return 0;
}

Variable declarations

Variable declarations accept name-first or type-first forms so you can write the order you are thinking in. value: i32 or i32: value are equivalent. The let keyword can be omitted from some declarations for shorthand. A bare identifier (no let keyword) on the left of = is always assignment. Default initialization is real initialization, omitting the initializer does not give a garbage value.

let x: i32 = 42;
x: i32 = 1;
i32: y = 2;
let n: i32;                 // 0
let text: str;              // ""
let values: Sequence<i32>;  // empty, impl arr
x = x + y;

End-to-end examples

Passing programs under examples/basic/ exercise imports, stdlib ADTs, generics, and codegen, not just parser smoke tests. Several are adapted from common interview problems to stress the full pipeline.

import std::heap::{heappop, heappush};
import std::sequence::{Sequence, sequence_len, sequence_new};

fn kth_largest(nums: [i32], k: i32) -> i32 {
  let heap: Sequence<i32, arr> = sequence_new(0);
  let i: i32 = 0;
  while i < len(nums) {
    if sequence_len(heap) < k {
      heappush(heap, nums[i]);
    } else {
      let smallest: i32 = heappop(heap);
      if nums[i] > smallest {
        heappush(heap, nums[i]);
      } else {
        heappush(heap, smallest);
      }
    }
    i = i + 1;
  }
  return heappop(heap);
}

noria: error: 2:10: typecheck: unknown local variable 'missing'