Section 19: Existential Types (impl Trait)

Goal: Enable returning opaque types that implement a trait without exposing concrete type

Criticality: Low — API design improvement

Dependencies: Section 3 (Traits), Monomorphization infrastructure (for AOT compilation — impl Trait is statically dispatched/monomorphized)

Proposal: proposals/approved/existential-types-proposal.md

Sync Points: Opaque Type Representation (multi-crate sync required)

Adding impl Trait return types requires updates across these crates:

ori_ir — Add Type::ImplTrait { bounds, where_clause } variant in type AST
ori_types — Infer concrete type from function body, verify all return paths yield same type, check trait bounds satisfied, reject invalid positions (arg, struct field)
ori_eval — Evaluator sees concrete type (opaque only to callers), no special handling needed
ori_llvm — Monomorphize to concrete type at codegen time, no vtable needed (static dispatch)

Design Decisions

Question	Decision	Rationale
Syntax	`impl Trait where Assoc == Type`	Type-local where clause for associated types
Position	Return only	Argument position uses generics instead
Multiple traits	`impl A + B`	Flexibility
Inference	Per-function, from body	Predictable
Where clause	Type-local	Constraints on associated types, not type params

Reference Implementation

Rust

~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir/src/hir.rs     # OpaqueTy definition
~/projects/reference_repos/lang_repos/rust/compiler/rustc_hir_typeck/src/   # Type inference for impl Trait
~/projects/reference_repos/lang_repos/rust/compiler/rustc_middle/src/ty/    # Type representation

Swift

# Swift has `any Protocol` (existential) and `some Protocol` (opaque return)
~/projects/reference_repos/lang_repos/swift/lib/Sema/CSSimplify.cpp         # Existential type solving
~/projects/reference_repos/lang_repos/swift/lib/AST/Type.cpp                # ExistentialType representation

19.1 Return Position impl Trait

Spec section: spec/08-types.md § Existential Types

Syntax

// Return opaque type
@make_iterator (items: [int]) -> impl Iterator where Item == int = {
    items.iter()
}

// Caller sees: impl Iterator where Item == int
// Cannot access concrete type
let iter = make_iterator(items: [1, 2, 3])
for x in iter do print(msg: `{x}`)  // Works via Iterator trait

// Multiple bounds
@make_printable_iterator () -> impl Iterator + Clone where Item == int = ...

Semantics

Return type is opaque to caller
Compiler knows concrete type internally
All return paths must return same concrete type
Trait bounds must be satisfied

Implementation

19.2 Type Inference

Spec section: spec/08-types.md § Existential Type Inference

Rules

// Concrete type inferred from function body
@numbers () -> impl Iterator where Item == int = {
    [1, 2, 3].iter()  // Concrete: ListIterator<int>
}

// All return paths must have same concrete type
@maybe_numbers (flag: bool) -> impl Iterator where Item == int = {
    if flag then
        [1, 2, 3].iter()
    else
        [4, 5, 6].iter()  // OK: same concrete type
}

// Error: different concrete types
@bad_numbers (flag: bool) -> impl Iterator where Item == int = {
    if flag then
        [1, 2, 3].iter()       // ListIterator<int>
    else
        (1..10).iter()         // RangeIterator<int>
    // Error: impl Trait returns different types
}

Implementation

19.3 Associated Type Constraints

Spec section: spec/08-types.md § Existential Associated Types

Syntax

// Constrain associated type
@int_iterator () -> impl Iterator where Item == int = ...

// Use with other traits
@cloneable_ints () -> impl Iterator + Clone where Item == int = ...

// Multiple associated types
trait Mapping {
    type Key
    type Value
    @get (self, key: Self.Key) -> Option<Self.Value>
}

@string_int_map () -> impl Mapping where Key == str, Value == int = ...

Implementation

19.4 Limitations and Errors

Spec section: spec/08-types.md § Existential Limitations

Not Supported

// Argument position - NOT supported (use generics)
@take_iterator (iter: impl Iterator where Item == int) -> void = ...  // Error
// Correct:
@take_iterator<I: Iterator> (iter: I) -> void where I.Item == int = ...

// In struct fields - NOT supported (use generics)
type Container = {
    iter: impl Iterator where Item == int,  // Error
}
// Correct:
type Container<I: Iterator> = { iter: I } where I.Item == int

Error Messages

error: `impl Trait` is only allowed in return position
  --> src/main.ori:5:20
  |
5 | @foo (x: impl Trait) -> void
  |          ^^^^^^^^^^ impl Trait not allowed here
  |
  = help: use a generic parameter instead: @foo<T: Trait> (x: T) -> void

Implementation

19.5 impl Trait vs dyn Trait

Spec section: spec/08-types.md § Static vs Dynamic Dispatch

Comparison

Feature	`impl Trait`	`dyn Trait`
Dispatch	Static (monomorphized)	Dynamic (vtable)
Size	Concrete type size	Pointer + vtable
Performance	Better (inlined)	Overhead
Flexibility	One concrete type	Any type at runtime
Recursion	Cannot (infinite size)	Can (via Box)

When to Use

// Use impl Trait: single concrete type, performance matters
@fast_iterator () -> impl Iterator where Item == int = [1, 2, 3].iter()

// Use trait object: multiple types possible, flexibility needed
@any_iterator (flag: bool) -> Iterator where Item == int = {
    if flag then
        [1, 2, 3].iter()
    else
        (1..10).iter()
}

Implementation

Section Completion Checklist

All items above have all checkboxes marked [ ]
Spec updated: spec/08-types.md existential types section
CLAUDE.md updated with impl Trait syntax
Return position impl Trait works
Type inference correct
Associated type constraints work
Clear errors for invalid positions
All tests pass: ./test-all.sh

Exit Criteria: Can write iterator-returning functions with clean APIs

Example: Iterator Combinators

// Clean API with impl Trait in return position
// Note: impl Trait is only allowed in return position, not argument position
// Use generics for arguments instead

@map<I: Iterator, U> (
    iter: I,
    f: (I.Item) -> U,
) -> impl Iterator where Item == U = {
    MapIterator { inner: iter, transform: f }
}

@filter<I: Iterator> (
    iter: I,
    predicate: (I.Item) -> bool,
) -> impl Iterator where Item == I.Item = {
    FilterIterator { inner: iter, predicate: predicate }
}

@take<I: Iterator> (
    iter: I,
    n: int,
) -> impl Iterator where Item == I.Item = {
    TakeIterator { inner: iter, remaining: n }
}

// Usage - clean, composable
@first_10_even_squares () -> impl Iterator where Item == int = {
    (1..100)
        .filter(predicate: n -> n % 2 == 0)
        .map(transform: n -> n * n)
        .take(count: 10)
}

// Caller doesn't know concrete type (MapIterator<FilterIterator<...>>)
// but can use it as Iterator
let squares = first_10_even_squares()
for sq in squares do print(msg: `{sq}`)