Section 18: Const Generics

Goal: Enable type parameters that are compile-time constant values

Criticality: Medium — Type-level programming, fixed-size arrays

Dependencies: Sections 1-2 (Type System Foundation), Section 5 (Type Declarations — for compound type eligibility in 18.8) Blocked by: Monomorphization infrastructure — base monomorphization must be complete before const generics can be compiled through AOT. The GenericArg enum and MonoInstance pipeline handle both type and const value arguments.

Design Decisions

Question	Decision	Rationale
Value types	`int`, `bool` initially	Start simple, expand later
Const-generic syntax	`$N: int`	Consistent with Ori’s `$` sigil for immutable bindings
Fixed-capacity list syntax	`[T, max N]`	Reads naturally, distinct from fixed-size arrays
Fixed-size array syntax	`[T, size N]` (future)	Clear distinction from max capacity
Const expressions	Limited initially	Avoid complexity
Default values	Supported	API ergonomics

Reference Implementation

Rust

~/projects/reference_repos/lang_repos/rust/compiler/rustc_middle/src/ty/consts.rs    # Const type representation
~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir/src/def.rs             # ConstParam definition
~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir_typeck/src/lib.rs      # Const generic checking

18.0 Const Evaluation Termination

Proposal: proposals/approved/const-evaluation-termination-proposal.md

Specifies termination guarantees and limits for compile-time constant evaluation, preventing infinite computation during compilation.

Implementation

18.1 Const Type Parameters

Proposal: proposals/approved/const-generics-proposal.md

Spec section: spec/08-types.md § Const Generic Parameters

Syntax

// Const parameter in type (using $ sigil for const)
type Array<T, $N: int> = {
    data: [T, max N],
    // len is known at compile time: N
}

// Usage
let arr: Array<int, 5> = Array.new()
arr[0] = 42

// In functions
@zeros<$N: int> () -> Array<int, N> = ...

let five_zeros: Array<int, 5> = zeros()

Grammar

TypeParameter = Identifier [ ':' TypeBound ]
              | '$' Identifier ':' ConstType ;
ConstType     = 'int' | 'bool' ;

Implementation

18.2 Fixed-Capacity Lists

Proposal: proposals/approved/fixed-capacity-list-proposal.md

Inline-allocated lists with compile-time maximum capacity and runtime-dynamic length.

Syntax

// Type: list of T with maximum capacity N
[T, max N]

// Examples
let buffer: [int, max 10] = []
buffer.push(1)          // OK
buffer.push(11)         // PANIC after 10 elements

// Generic over capacity
@swap_ends<T, $N: int> (items: [T, max N]) -> [T, max N] = ...

Implementation

18.3 Fixed-Size Arrays (Future)

Spec section: spec/08-types.md § Fixed-Size Arrays

Note: This is a future extension. Fixed-capacity lists ([T, max N]) are prioritized first. Fixed-size arrays always have exactly N elements, unlike fixed-capacity lists which have 0 to N elements.

Syntax (Proposed)

// Array type with fixed size (always exactly N elements)
let arr: [int, size 5] = [0, 0, 0, 0, 0]

// Array operations
let len = len(collection: arr)  // Const 5, known at compile time
let elem = arr[2]               // Bounds checked at compile time if index const

// Distinct from fixed-capacity: cannot have fewer than N elements
// [int, size 5] ≠ [int, max 5]

Type Rules

[T, size N] where N: int (const)
- Length always exactly N, known at compile time
- Inline allocated (no heap)
- Cannot be empty, cannot grow, cannot shrink
- Bounds checks can be optimized away for const indices

Implementation (Deferred)

18.4 Const Expressions in Types

Spec section: spec/08-types.md § Const Expressions

Syntax

// Arithmetic in const position
type Matrix<$ROWS: int, $COLS: int> = {
    data: [float, max ROWS * COLS],
}

// Const function in type
$double (n: int) -> int = n * 2

type DoubleArray<$N: int> = {
    data: [int, max $double(n: N)],
}

// Conditional const
type Buffer<$SIZE: int> = {
    data: [byte, max if SIZE > 0 then SIZE else 1],
}

Allowed Expressions

Const parameters: N, M
Literals: 5, true
Arithmetic: N + M, N * 2, N / 2
Comparison: N > 0, N == M
Const functions: $func(n: N)
Conditionals: if N > 0 then N else 1

Implementation

18.5 Const Bounds

Proposal: proposals/approved/const-generic-bounds-proposal.md

Spec section: spec/08-types.md § Const Bounds

Formalizes const generic bounds (e.g., where N > 0), including allowed constraints, evaluation semantics, constraint propagation, and error handling.

Syntax

// Bound on const parameter value
@non_empty_array<$N: int> () -> [int, max N]
    where N > 0  // Const bound
= ...

// Multiple bounds (combined with && or separate where clauses)
@matrix_multiply<$M: int, $N: int, $P: int> (
    a: Matrix<M, N>,
    b: Matrix<N, P>,
) -> Matrix<M, P>
    where M > 0 && N > 0 && P > 0
= ...

// Arithmetic and bitwise in bounds
@power_of_two<$N: int> ()
    where N > 0 && (N & (N - 1)) == 0  // Bit trick for power of 2
= ...

// Bool const generics with bounds
@either_or<$A: bool, $B: bool> () -> int
    where A || B  // At least one must be true
= if A then 1 else 2

Implementation

18.6 Default Const Values

Spec section: spec/08-types.md § Default Const Values

Syntax

// Default value for const parameter
type Buffer<$SIZE: int = 1024> = {
    data: [byte, max SIZE],
}

// Usage
let buf: Buffer = Buffer.new()           // SIZE = 1024
let small: Buffer<256> = Buffer.new()    // SIZE = 256

// In functions
@create_buffer<$SIZE: int = 4096> () -> Buffer<SIZE> = ...

let default_buf = create_buffer()         // 4096
let custom_buf = create_buffer<8192>()    // 8192

Implementation

18.7 Const in Trait Bounds

Spec section: spec/09-properties-of-types.md § Const in Traits

Syntax

// Trait with const parameter
trait FixedSize {
    $SIZE: int
}

impl [int, max 5]: FixedSize {
    $SIZE: int = 5
}

// Use in bounds
@total_size<T: FixedSize, $N: int> () -> int = T.SIZE * N

// Associated const in generic context
@print_size<T: FixedSize> () -> void = {
    print(msg: `Size: {T.SIZE}`)
}

Implementation

Section Completion Checklist

All items above have all checkboxes marked [ ]
Spec updated: spec/08-types.md and spec/09-properties-of-types.md const generics sections
CLAUDE.md updated with const generic syntax
[T, max N] fixed-capacity lists work
$N: int const parameters in types work
Const expressions in type positions work
Const bounds work
All tests pass: ./test-all.sh

Exit Criteria: Can implement a matrix library with compile-time dimension checking

Example: Matrix Library

type Matrix<$ROWS: int, $COLS: int> = {
    data: [float, max ROWS * COLS],
}

impl<$ROWS: int, $COLS: int> Matrix<ROWS, COLS> {
    @new () -> Matrix<ROWS, COLS> = Matrix {
        data: [],  // Will be filled with zeros
    }

    @get (self, row: int, col: int) -> float = {
        assert(condition: row >= 0 && row < ROWS)
        assert(condition: col >= 0 && col < COLS)
        self.data[row * COLS + col]
    }

    @set (self, row: int, col: int, value: float) -> void = {
        assert(condition: row >= 0 && row < ROWS)
        assert(condition: col >= 0 && col < COLS)
        self.data[row * COLS + col] = value
    }

    @rows (self) -> int = ROWS  // Compile-time constant

    @cols (self) -> int = COLS  // Compile-time constant
}

// Matrix multiplication with dimension checking at compile time
@multiply<$M: int, $N: int, $P: int> (
    a: Matrix<M, N>,
    b: Matrix<N, P>,
) -> Matrix<M, P> = {
    let result = Matrix.new()

    for i in 0..M do
        for j in 0..P do
            let sum = 0.0
            for k in 0..N do
                sum = sum + a.get(row: i, col: k) * b.get(row: k, col: j)
            result.set(row: i, col: j, value: sum)

    result
}

// Usage
let a: Matrix<2, 3> = Matrix.new()
let b: Matrix<3, 4> = Matrix.new()
let c: Matrix<2, 4> = multiply(a: a, b: b)  // Types checked at compile time!

// This would be a compile error:
// let bad: Matrix<2, 5> = multiply(a: a, b: b)  // Error: dimension mismatch

18.8 Expanded Const Generic Eligibility (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 3

Replace the {int, bool} whitelist with: any type with Eq + Hashable is const-eligible. This expands const generics to str, char, byte, user enums, user structs, and compound types.

Blocked by: Section 5.5 (Compound Type Inference) — needed for [int] and (T, U) eligibility

Implementation

Implement: Type checker — replace hardcoded matches!(type, Int | Bool) with trait registry lookup for Eq + Hashable
- Rust Tests: ori_types/src/check/tests.rs — const eligibility check tests
Implement: Update E1040 error message — “requires Eq + Hashable” instead of “only int and bool allowed”
- Ori Tests: tests/compile-fail/const_generic_not_eligible.ori
Ori Tests: tests/spec/types/const_generics_expanded.ori — str, char, byte, user enum, user struct as const params
Update Spec: grammar.ebnf — remove const_type = "int" | "bool" restriction
Update Spec: 06-types.md — const generic eligibility section
Verify: ./test-all.sh passes

18.9 Associated Consts in Traits (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 4

Add $name: Type syntax to trait definitions and impls. Extends the associated types pattern to compile-time values.

Blocked by: Section 18.0 (Const Evaluation Termination)

Implementation

Implement: Parser — accept $name: Type and $name: Type = expr as trait items
Implement: Parser — accept $name = expr as impl items
Implement: IR — add AssocConst to TraitItem and ImplItem
Implement: Type checker — register associated consts alongside methods and types
Implement: Type checker — const expression unification for T.$rank in where clauses
Implement: Evaluator — associated const resolution
Ori Tests: tests/spec/traits/associated_consts.ori
LLVM Support: Const folding for associated consts
Verify: ./test-all.sh passes

18.10 Const Functions in Type Positions (Capability Unification)

Proposal: proposals/approved/capability-unification-generics-proposal.md — Phase 5

Allow $product(S), $len(S) etc. in type positions and where clauses. Most complex phase.

Blocked by: Section 18.9 (Associated Consts)

Implementation

Implement: Const function analysis — identify which functions are compile-time evaluable
Implement: Type checker — const expression evaluation in type positions
Implement: Type checker — const unification ($product(FROM) unifies with concrete values)
Implement: Built-in const functions: $len, $product, $sum, $min, $max
Ori Tests: tests/spec/types/const_functions_in_types.ori
LLVM Support: Compile-time evaluation in LLVM codegen
Verify: ./test-all.sh passes