📖 Документация Qumir

← Вернуться в Playground

Qumir Compiler — Architecture Overview

Qumir is an educational programming language compiler with Russian keywords, inspired by the Soviet-era KUMIR/Ershov teaching language. It supports three execution backends — LLVM native, WASM, and an IR interpreter (VM) — and an online playground at https://qumir.dev.


1. Pipeline at a glance

Source (.kum / core-lang)
        │
        ▼
    [ Lexer / Parser ]
        │  raw AST
        ▼
 ┌─ Semantic passes ───────────────────────────────┐
 │  1. Source transform fixpoint                   │
 │     (resolve → annotate → rewrite)              │
 │  2. Definite assignment                         │
 │  3. Return normalization                        │
 │  4. Lifetime rewrite                            │
 │  5. Final resolve → annotate → lifetime validate│
 └─────────────────────────────────────────────────┘
        │  finalized AST with explicit lifetime operations
        ▼
  [ IR lowering ]  →  TModule (SSA IR)
        │
        ├── [ IR passes ]  (SSA, const-fold, de-SSA, …)
        │
        ├──────────────────────────────────────┐
        ▼                                      ▼
  [ VM / interpreter ]              [ LLVM codegen ]
  direct execution                  native binary / WebAssembly

The CLI tools are:

The web service lives in QumirLabs/qumir-service; it wraps qumirc as a subprocess and serves the playground frontend.


2. Two surface languages

2.1 Kumir (.kum)

The primary user-facing language. Keywords are Cyrillic:

Concept Keyword(s)
Algorithm алг / нач / кон
Types цел вещ лог лит сим таб
If / else если / то / иначе / все
Loop нц / кц / пока / для / шаг
Switch выбор / при
Param modes арг (in) рез/знач (out) аргрез
Module import использовать

2.2 Core lang (oz-lang)

A lower-level surface syntax for the same AST used for tests, golden files, and debugging. The playground exposes it as a "core syntax" mode. Core lang is useful because Kumir syntax is deliberately small and conservative: new constructs can be introduced, inspected, and debugged at the AST level first, before deciding whether they need .kum frontend syntax. It also supports source modules and computational kernels for embedding in host applications. The oz-lang guide develops complete examples from basic expressions through structures, generics, and SIMD vectors, followed by a syntax reference and compiler-output conventions.


3. AST and type system

3.1 Node hierarchy

All AST nodes derive from TExpr. Pattern matching uses TMaybeNode<T> — a wrapper that holds a shared_ptr<T> when the dynamic type matches:

if (auto call = TMaybeNode<TCallExpr>(expr)) { /* call.Cast() */ }

3.2 Type hierarchy

Types are shared_ptr<TType> subtypes, matched with TMaybeType<T>:

C++ type Language concept
TIntegerType цел — one 64-bit signed integer
TFloatType вещ — IEEE-754 double
TBoolType лог — boolean
TStringType лит — managed string handle
TSymbolType сим — Unicode code point (i32)
TVoidType procedure return / no value
TArrayType таб — heap-allocated array
TNamedType user-defined type alias
TFunctionType (param…) → ret
TPointerType internal low-level pointer

4. Semantic passes

The complete sequence runs via NTransform::Pipeline(). See AST transformation pipeline for the exact pass order, contracts, and fixpoint behavior.

4.1 Source transform fixpoint

Name resolution, type annotation, and source-level AST rewrites repeat until the tree stops changing. Name resolution builds the symbol table and resolves every identifier to its declaration. Module imports (использовать) are processed here. Type annotation infers and checks expression types. Rewrites include array-bound normalization, syntactic-sugar elimination, loop conversion, and optional coroutine annotation.

4.2 Definite assignment

Checks source-level control flow for reads of potentially uninitialized variables. It runs before internal lifetime nodes are introduced.

4.3 Return normalization

Makes function termination explicit. Void fallthrough receives an explicit return, while a non-void final expression becomes a return. Whether a nested block or conditional terminates is control-flow information; return itself remains a void-typed final expression and is never usable as a value.

4.4 Lifetime rewrite

Rewrites ownership into explicit internal AST operations. Assignments become replace, borrowed reads become borrow, ownership transfers become move, copies of reference-counted values use retain, literals use own-literal, and scope exits contain explicit destroy operations. Structured exits use cleanup-exit; module-level destruction uses one cleanup-global node.

4.5 Final semantic validation

The rewritten tree is resolved and annotated again because the lifetime pass introduces synthetic locals and expressions. The lifetime validator then rejects invalid ownership combinations before IR lowering.

4.6 Lifetime and ownership

Lifetime policy belongs to the semantic AST, not to IR lowering. Strings, arrays, aggregate traits, explicit ownership nodes, lexical and structured-exit cleanup, globals, validation, and the lowering boundary are documented in lifetime analysis.


5. IR (intermediate representation)

The IR is a custom SSA-like representation.

5.1 Structure

TModule
├── ExternalFunctions[]   imported runtime symbols
├── Functions[]
│   ├── Blocks[]
│   │   ├── Phis[]        φ-functions (SSA merge points)
│   │   └── Instrs[]      sequential instructions
│   └── LocalTypes[]      local variable type ids
├── GlobalTypes[]         module-level slot types
├── StringLiterals[]      constant pool
└── Types (TTypeTable)    type interning table

5.2 Instruction format

struct TInstr {
    TOp      Op;             // opcode: "add", "call", "ret", "jmp", "cmp", …
    TTmp     Dest;           // destination temporary (-1 = no result)
    TOperand Operands[4];    // Tmp | Imm | Label | Local | Slot
};

Opcodes are string-literal hashes ("add"_op, "call"_op, …) so new opcodes can be added without touching an enum.

5.3 IR passes

Pass Purpose
locals2ssa stack locals → SSA temporaries
const_fold constant folding
de_ssa insert copies at φ-joins before codegen
CFG analysis predecessor / successor computation

5.4 IR type table

TTypeTable interns IR-level types by kind: I1, I8, I32, I64, F32, F64, Void, Ptr, Struct, Func. AST types map to IR types via FromAstType().


6. VM / interpreter

The VM is a register-based bytecode interpreter. The IR is compiled to TVMInstr bytecode by TVMCompiler, which assigns stack-frame byte offsets to locals and aligned register-file byte offsets to temporaries. IR temporary ids remain unchanged; only VM operands contain the assigned byte offsets.

Each invocation uses one aligned byte buffer for all registers, including 128-bit integers. Existing scalar opcodes use eight-byte slots even for narrower types, while 128-bit slots use sixteen bytes with sixteen-byte alignment. An f32 value occupies the low four bytes of its slot and has its own scalar opcodes (FAdd32, FCmpLT32, FExt32, ...); an f32 immediate carries the float bits in the low four bytes of Imm.Value. Struct registers hold addresses of storage in the call frame. The registers of all active calls form one stack of windows inside a single reservation made up front. A call opens a window at the end of its caller's registers; the callee's parameters are its first registers, and the caller has written the arguments there, so the window overlaps the caller's. The rest of the window is zeroed. Returning reactivates the caller's window without copying or clearing it. The reservation never moves, so a register keeps its address while its call is active, and call/return cost does not depend on the caller's register-file size. The windows of active calls count toward the VM stack limit together with their locals; exceeding it is a Stack overflow in interpreter error, after which the next invocation starts from an empty stack. Each interpreter reserves a second 128 MiB virtual area next to Stack.reserve, so virtual size per instance doubles under strict overcommit or RLIMIT_AS. The layout of the parameters is computed once per function (TExecFunc::Params) and is the same for the callee and its callers. A parameter whose address is taken, a struct parameter (the register holds the address of the caller's struct) and any parameter of a function with debug info are copied into the frame at entry; the others are read and assigned in their registers. Arguments of extern calls still go through ArgTmp and ArgConst.

6.1 Execution model

Function locals live in a byte stack separate from registers. An explicit call stack keeps each caller's continuation and register window; returning releases the callee's local range and reactivates the caller's window. The interpreter loop dispatches on EVMOp enum values.

6.1.1 Prepared program and instances

Eval/EvalRaw compile lazily and pump the global async event queues, so they suit one interpreter at a time. For multi-threaded hosts, TVMCompiler::Prepare(roots) compiles all reachable functions and resolves externs up front (all or nothing); each thread then owns a TInterpreter and calls Initialize(), Invoke(function, args), Finalize(). Invoke compiles nothing, so the prepared program is read-only.

Limits: Prepare must not run concurrently with Invoke; non-struct arguments wider than 64 bits are rejected and an i128 result is truncated; io, robot and painter externs use unsynchronized globals. An exception from an extern makes Invoke return a TError; refcounted values (strings, arrays) in the frames it abandons are not released, which leaks memory but does not affect correctness.

6.2 Calling convention for external (runtime) functions

External functions — robot actions, math helpers, string operations — are registered by modules. Each external function has two representations:

Field Type Used by
Ptr void* — native function pointer LLVM backend
Packed uint64_t(*)(const uint64_t* args, size_t n) VM interpreter

The Packed thunk is the VM calling convention. All arguments are passed as a flat array of uint64_t values (integers, floats as bit-casts, string handles, pointers as integers). The return value is a single uint64_t.

// Typical registration
{
    .Name        = "вверх",
    .MangledName = "robot_up",
    .Ptr         = reinterpret_cast<void*>(static_cast<void(*)()>(robot_up)),
    .Packed      = [](const uint64_t*, size_t) -> uint64_t {
                       robot_up(); return 0;
                   },
}

The VM's ECall handler casts addr to TPacked and calls it directly, collecting pre-pushed arguments from Runtime.Args.

Additional flags on external functions:

6.3 LLVM JIT

The LLVM JIT runner compiles the IR module through the LLVM backend and runs it in-process via LLVM ORC JIT. External functions are resolved to their Ptr addresses at link time.


7. LLVM backend

Translates TModule to LLVM IR and then to native code or WebAssembly.

7.1 Function lowering

IR basic blocks map directly to LLVM basic blocks. IR temporaries become LLVM values (alloca-free after the de-SSA pass). Struct arguments and returns are modelled as ordinary LLVM values.

7.2 Target

Flag Triple Notes
(none) host triple native AOT or JIT
--wasm, --wasm32 wasm32-unknown-unknown requires wasm-ld for linking
--wasm64 wasm64-unknown-unknown requires wasm-ld -mwasm64 for linking

7.3 Optimization

cg.Emit(module, optLevel) runs the standard LLVM pass pipeline at the requested level (0–3).


8. Module system

User programs import modules with использовать <Name>. Each module implements IModule and registers external functions and types.

Built-in modules:

Module Purpose
System (default) I/O, file I/O, math, string operations
Робот Grid robot executor
Черепаха Turtle graphics executor
Рисователь Canvas drawing
Чертежник Vector drawing
Комплексные числа Complex number support
Цвета Named color constants

Runtime implementations exist in two forms: C++ (native / WASM) and JavaScript (browser playground).


9. Runtime Data Representation

Arrays, structs, and strings have non-trivial ABI and lifetime conventions, so the details live in separate notes: arrays describes таб as a pointer to a flat heap buffer with compiler-maintained bounds/strides, row-major multidimensional layout, and by-pointer function passing; structs describes struct layout, address-backed temporaries, LLVM value ABI for arguments/returns, and reference-parameter copies; and strings describes лит as TString::Data / browser handles with reference counting, ownership tracking, literal materialization, and retain/release rules around calls, returns, assignments, and destruction. The cross-type semantic ownership model is described in lifetime analysis.


10. Inspirations

The compiler's design and the way its implementation is explained were shaped by several books, production-language systems, and lecture series: