Hylo Programming Language Documentation

In Hylo, a generic signature is a set of generic parameter declarations and their associated constraints. To make sense of these signatures, the compiler constructs a generic environment.

A generic environment is a set of axioms used by the type system to prove properties about type or value terms. For example, if a signature constrains a type T to conform to Collection, the environment allows the compiler to prove that T.Element exists and has certain members (like infix+).

Key points:

• Trait declarations also define generic environments. All traits include an implicit Self parameter.
• Constraints on associated types and values add further axioms to the environment.
• The environment is used during name resolution to determine trait conformance and associated type/value lookups.

An Addressor is a specific type of subscript that does not synthesize (create) the value it projects. Instead, it exposes a stored part of one of its arguments.

Because it is exposing an existing address rather than creating new data, an Addressor does not require "slide" functions. It can simply compute the address of the projected value within its ramp and clean up its stack before returning.

Definite (De)Initialization (DI) is a mandatory transformation pass applied to Hylo's intermediate representation (IR) before code generation. It ensures that all objects are treated as linear resources by enforcing two primary guarantees:

1. Definite Initialization: All objects must be fully initialized before they are used (e.g., via loading, starting a let binding, or an inout binding).
2. Definite Deinitialization: All objects must be deinitialized before the end of their storage's lifetime (e.g., before deallocating the storage or starting a set borrow on uninitialized/consumed storage).

If the compiler cannot guarantee these properties, the DI pass will fail with a diagnostic error.

Hylo's generics design balances algorithm efficiency with the ability to maintain opaque module boundaries.

• Separate Type Checking: Generic functions are type-checked independently. This prevents users from encountering type errors inside a generic function's body that only trigger during specific usage patterns.
• Opaque Module Boundaries: A module's private implementation details (including type layouts and function implementations) can change without requiring clients to recompile. This enables binary-compatible library evolution.
• Optimization: While separate compilation can introduce costs when crossing boundaries, Hylo supports an optimization step that eliminates these costs without changing semantics. This optimization can be applied globally for performance or selectively at module boundaries to preserve binary compatibility.

In Hylo, a subscript is lowered as a single Hylo IR function. This function has no return value but must follow the 1-yield rule: it is expected to execute exactly one yield instruction on every possible execution path from the entry to each return instruction.

At the call site, a subscript is invoked using the project instruction. The lifetime pass ensures that a projection is closed with an end_project instruction after its last use.

subscript sum(_ x: Int, _ y: Int): Int { x + y }

fun foo(a: Int, b: Int) {
  let x = sum(a, b)
  print(x)
}

The Hylo compiler follows a multi-stage pipeline to transform source code into machine code. The process is orchestrated by the Driver module. Depending on the flags provided to the compiler, execution can exit early at any of these stages:

1. Tokenisation: Converts Hylo source strings into a stream of tokens (see Lexer.swift, Token.swift).
2. Parsing: Generates an Abstract Syntax Tree (AST) from tokens (see Parser.swift).
3. Type-checking: Validates the AST for type errors (see TypeChecking module).
4. IR-lowering: Generates Hylo Intermediate Representation (IR) from the AST (see IR module, Emitter.swift).
5. LLVM IR generation: Converts Hylo IR into LLVM IR (see Transpilation.swift).
6. Machine Code Generation: Handled entirely by the LLVM backend.

Hylo IR is composed of instructions defined in the Instruction module.

Generation Workflow:

1. The Emitter component creates the IR.
2. The Emitter inserts instructions into an IR/Module module-by-module.
3. These modules are aggregated into an IR/Program.

Validation: Hylo IR is only considered valid after it has undergone mandatory analysis passes defined in the IR/Analysis module (specifically within Module+* files). Once these passes are complete, the IR is valid and executable by a theoretical Hylo VM.

The subscripts-as-sessions approach also uses a ramp and slide structure, but the ramp returns the yielded value directly instead of calling a continuation.

Key Characteristics:

• Memory Management: To avoid dynamic allocation, the ramp accepts a pointer to a pre-allocated buffer representing its stack. The caller pushes this onto its own stack before the call.
• Lifecycle: The caller initiates a "session" by calling the ramp and terminates it by calling a slide.
• Trade-off: This approach requires code transformation and, to maintain ABI stability, requires careful management of frame sizes (often requiring a helper function to return size and alignment).

Hylo uses customization points to allow algorithms to optimize their behavior based on the properties of the data structures they operate on. This is achieved through traits and conformances.

For example, a generic reverse() algorithm might have a default $O(N \log N)$ implementation, but can be specialized to $O(N)$ for types that conform to BidirectionalCollection. Similarly, a Matrix multiplication algorithm can dispatch to high-performance libraries like BLAS when the Element type is a Float.

trait MutableCollection {
  // ...
  fun reverse() inout { /* O(N log N) implementation */ }
}

conformance<T: MutableCollection & BidirectionalCollection> T: MutableCollection {
  fun reverse() inout { /* O(N) implementation */ }
}