Skip to content

Section 23: Collections and Data Structure Semantics

TECHSPEC-24 — Section 23 · Version 0.1 · Status: Initial Draft

Numbering note: this is file TECHSPEC-24.md but it contains Section 23 of the specification. File numbers and section numbers diverge from TECHSPEC-23 onward; neither has been renumbered. See the specification index and audit AUDIT-001 in reports/documentation-audit.md for details.

Status: draft. This section is an Initial Draft (Section 57 is a Working Register). It describes intended or proposed behavior, not a finalized, implemented language rule. Do not treat examples here as normative.

1. Collection Philosophy

Collections must have predictable behavior, explicit types, and defined access rules.

The language must prevent invalid indexing, unexpected mutation, and ambiguous collection operations.

Every collection must have documented ordering, uniqueness, and failure semantics.

2. Initial Collection Types

The initial language supports:

  • List<T>: Ordered collection of values.
  • Map<K, V>: Collection of key-value pairs.
  • Set<T>: Collection of unique values.
  • Tuple<T1, T2, ...>: Fixed-size collection of typed values.

Rules: - Collection element types must be explicit. - Collections must not silently accept incompatible values. - Nested collections must be supported. - Collection operations must preserve declared type constraints.

3. Lists

A List<T> stores values in a defined sequence.

Example:

LET scores: List<Integer> = [10, 20, 30]

Rules: - List elements must preserve insertion order. - Duplicate values are permitted. - Indexing begins at zero. - Invalid index access must produce an explicit failure. - List length must be available. - Mutation requires an explicitly mutable list or permitted mutable reference. - Removing an element must preserve the relative order of remaining elements.

4. Maps

A Map<K, V> stores unique keys associated with values.

Example:

LET prices: Map<String, Decimal> = {
    "apple": 1.50,
    "orange": 2.00
}

Rules: - Keys must have a defined equality and hashing behavior. - Duplicate keys are not permitted. - Inserting an existing key must follow an explicit replacement or rejection operation. - Missing-key access must produce an explicit failure or an Optional result. - Key and value types must remain consistent. - Iteration order must be explicitly defined by the collection implementation.

5. Sets

A Set<T> stores unique values.

Example:

LET identifiers: Set<Integer> = {10, 20, 30}

Rules: - Duplicate values must not be stored. - Equality must be defined for the element type. - Insertion must report whether a new value was added. - Removal of a missing value must have defined behavior. - Iteration order must not be assumed unless explicitly guaranteed.

6. Tuples

A Tuple stores a fixed number of values with individually defined types.

Example:

LET accountEntry: Tuple<Integer, Decimal> = (100, 250.00)

Rules: - Tuple size is fixed. - Each position has a defined type. - Tuple elements cannot be silently reordered. - Access must use a valid position. - Tuple immutability follows the declared mutability and ownership rules.

7. Collection Operations

The standard library must provide consistent operations for:

  • Creation.
  • Insertion.
  • Removal.
  • Lookup.
  • Iteration.
  • Filtering.
  • Mapping.
  • Sorting.
  • Searching.
  • Length and emptiness checks.
  • Conversion between compatible collection types.

Rules: - Operations must declare possible failures. - Mutation must respect ownership and borrowing rules. - Sorting must define its ordering behavior. - Filtering and mapping must preserve declared output types. - Collection conversions must not silently discard incompatible values. - Iteration must define behavior when the underlying collection changes.

8. Equality and Ordering

Collections require well-defined comparison semantics.

Rules: - Element equality must follow the language's equality rules. - Ordered collections must define their ordering behavior. - Unordered collections must not imply stable iteration order. - Custom comparison behavior must be explicitly declared. - Equality and hashing must remain consistent for map keys and set elements.

9. Performance and Resource Limits

Collection operations must have documented resource characteristics where practical.

Documentation should identify: - Expected time complexity. - Memory requirements. - Whether an operation copies or shares data. - Whether an operation modifies the original collection. - Whether an operation may allocate additional memory.

Rules: - Resource exhaustion must produce an explicit failure where recoverable. - Collection operations must not silently corrupt existing data. - Performance guarantees must not be claimed without supporting implementation guarantees.

10. Compiler and Runtime Responsibilities

The compiler and runtime must: - Enforce collection types. - Validate indexing operations. - Enforce mutability and ownership restrictions. - Preserve defined ordering behavior. - Validate map key and set equality requirements. - Detect invalid collection operations where possible. - Preserve source-language semantics during code generation.

11. Design Goal

AI agents must be able to use collections without guessing about indexing, ordering, uniqueness, mutation, or failure behavior.

Every collection operation must have explicit and predictable semantics.

Source file: TECHSPEC-24.md (preserved in source-original/LANG/). See the specification index, the glossary, and the cross-reference index.