Sequence Operations Representation

Status: Normative Last Updated: 2026-01-19 Depends On: Closure Representation, Seq Representation

1. Overview

Clef implements sequence operations (Seq.map, Seq.filter, Seq.take, Seq.fold, Seq.collect) as wrapper sequences that compose the flat closure architecture. This chapter specifies the memory representation, copy semantics, and composition model for sequence transformations.

Key Insight: Seq operations create wrapper sequences that contain both an inner sequence AND a transformation closure, both inlined (copied by value), following the flat closure model.

2. Relationship to Prior Chapters

Sequence operations build on:

• Closure Representation - Mapper/predicate closures are flat closures
• Lazy Representation - Extended closure pattern with state prefix
• Seq Representation - Base seq struct with MoveNext state machine

Progressive Extension Pattern:

PRD-11 (Closures)     → Flat closure: (fn, {cap₀, cap₁, ...})
         ↓ extends
PRD-14 (Lazy)         → Extended closure: (thunk, {computed, value, cap₀...})
         ↓ extends
PRD-15 (SimpleSeq)    → State machine: (moveNext, {state, current, cap₀..., internal₀...})
         ↓ composes
PRD-16 (SeqOperations)→ Wrapper seq: (moveNext, {state, current, inner_env, closure_env, ...})

3. Operation Classification

3.1 Transformers vs Consumers

Transformers create a new seq struct that wraps the input sequence. Iteration is lazy.

Consumers immediately iterate the input sequence and return a non-sequence value.

3.2 Closure Requirements

Each operation takes a function argument:

These function arguments are flat closures (per Closure Representation) and may capture variables from their defining scope.

4. Memory Layout Specifications

4.1 MapSeq Structure

MapSeq<A, B> with inner: Seq<A>, mapper: Closure<A -> B>
┌─────────────────────────────────────────────────────────────────────────┐
│ state: i32              (4 bytes) - wrapper state (always 0 or 1)       │
├─────────────────────────────────────────────────────────────────────────┤
│ current: B              (sizeof(B) bytes) - current transformed value   │
├─────────────────────────────────────────────────────────────────────────┤
│ inner_seq: Seq<A>       (sizeof(Seq<A>) bytes) - INLINED, copied        │
├─────────────────────────────────────────────────────────────────────────┤
│ mapper: Closure         (sizeof(Closure) bytes) - INLINED, copied       │
└─────────────────────────────────────────────────────────────────────────┘

Field Indices:
  [0] = state
  [1] = current
  [2] = inner_seq (the inner sequence's environment, entire struct, not pointer)
  [3] = mapper (the mapper's environment, entire struct, not pointer)

A wrapper sequence is, like every seq, the pair (moveNext, env) of Seq Representation §4.1: MapMoveNext is the function-value half and the struct above is its environment. No function address is stored in the environment.

CRITICAL: Both inner_seq and mapper are inlined (copied by value into the wrapper struct), not stored by pointer. This follows the flat closure principle of self-contained structs. What is inlined is each one’s environment; their function values are bound at saturation: the inner sequence’s MoveNext and the mapper’s implementation are known at the Seq.map site whenever the arguments are lambda literals or named functions — the common case — and the wrapper’s MoveNext then calls them directly (the known-callee form of Closure Representation §7). Where a mapper arrives as a function-value parameter, the wrapper must carry that value; its memory form is the open placement decision recorded in clef/docs/fidelity/phg/Closure_Retooling_Plan.md and is not a cast.

4.2 FilterSeq Structure

FilterSeq<A> with inner: Seq<A>, predicate: Closure<A -> bool>
┌─────────────────────────────────────────────────────────────────────────┐
│ state: i32              (4 bytes)                                        │
├─────────────────────────────────────────────────────────────────────────┤
│ current: A              (sizeof(A) bytes) - current matching value       │
├─────────────────────────────────────────────────────────────────────────┤
│ inner_seq: Seq<A>       (sizeof(Seq<A>) bytes) - INLINED                 │
├─────────────────────────────────────────────────────────────────────────┤
│ predicate: Closure      (sizeof(Closure) bytes) - INLINED                │
└─────────────────────────────────────────────────────────────────────────┘

4.3 TakeSeq Structure

TakeSeq<A> with inner: Seq<A>
┌─────────────────────────────────────────────────────────────────────────┐
│ state: i32              (4 bytes)                                        │
├─────────────────────────────────────────────────────────────────────────┤
│ current: A              (sizeof(A) bytes)                                │
├─────────────────────────────────────────────────────────────────────────┤
│ inner_seq: Seq<A>       (sizeof(Seq<A>) bytes) - INLINED                 │
├─────────────────────────────────────────────────────────────────────────┤
│ remaining: i32          (4 bytes) - count of elements still to take      │
└─────────────────────────────────────────────────────────────────────────┘

Note: Seq.take does not have a closure parameter. The remaining counter serves as the configuration.

4.4 CollectSeq Structure (flatMap)

CollectSeq<A, B> with outer: Seq<A>, mapper: Closure<A -> Seq<B>>
┌─────────────────────────────────────────────────────────────────────────┐
│ state: i32              (4 bytes) - 0=initial, 1=iterating_inner, -1=done│
├─────────────────────────────────────────────────────────────────────────┤
│ current: B              (sizeof(B) bytes)                                │
├─────────────────────────────────────────────────────────────────────────┤
│ outer_seq: Seq<A>       (sizeof(Seq<A>) bytes) - INLINED                 │
├─────────────────────────────────────────────────────────────────────────┤
│ mapper: Closure         (sizeof(Closure) bytes) - INLINED                │
├─────────────────────────────────────────────────────────────────────────┤
│ inner_seq: Seq<B>       (sizeof(Seq<B>) bytes) - current inner seq       │
└─────────────────────────────────────────────────────────────────────────┘

Complexity Note: Seq.collect requires storing the current inner sequence state. The inner_seq field is updated when advancing to a new outer element.

5. Copy Semantics (NORMATIVE)

5.1 Value Copy at Wrapper Creation

When creating a wrapper sequence:

let mapped = Seq.map mapper innerSeq

The wrapper creation copies both innerSeq and mapper by value into the wrapper struct:

// Middle end — portable dialects only. E, E_inner, and E_mapper are literals at saturation.
%env = memref.alloca() : memref<Exi8>                          // the wrapper's environment
%c0 = arith.constant 0 : index
%sv = memref.view %env[%c0][] : memref<Exi8> to memref<1xi32>
memref.store %zero, %sv[%c0] : memref<1xi32>                   // state = 0 at [0]
%inner_dst = memref.view %env[%off_inner][] : memref<Exi8> to memref<E_innerxi8>
memref.copy %inner_env, %inner_dst : memref<E_innerxi8> to memref<E_innerxi8>   // COPY inner env
%mapper_dst = memref.view %env[%off_mapper][] : memref<Exi8> to memref<E_mapperxi8>
memref.copy %mapper_env, %mapper_dst : memref<E_mapperxi8> to memref<E_mapperxi8> // COPY mapper env
%mn = func.constant @MapMoveNext_site : (memref<Exi8>) -> i1   // the function-value half
// (%mn, %env) is the wrapper value.

5.2 Why Copy Semantics?

Independence: Each wrapper owns its own copy of the inner seq’s state. Multiple iterations of the same wrapper are independent.

No Aliasing: No shared mutable state between different wrappers created from the same source.

Lifetime Simplicity: The wrapper struct contains everything it needs, with no interior pointers into a separately-allocated inner seq or closure, so it has no dangling references. Because the inner seq and closure are inlined, the whole wrapper is one value with a single lifetime, and that lifetime is classified and placed by the four-point lattice of Closure Representation §3.3: the stack when scope-bounded, a region when region-bounded, static storage (Sram/Flash, memref.global) when its lifetime is the whole program, and the heap only when its extent is genuinely dynamic. On a target without a heap only the stack and static placements exist, and a wrapper that would classify as dynamic there is a compile-time lifetime error, not a silent heap allocation.

Example:

let source = seq { yield 1; yield 2; yield 3 }
let doubled = Seq.map (fun x -> x * 2) source

// First iteration
for x in doubled do printfn "%d" x  // 2 4 6

// Second iteration - independent, works correctly
for x in doubled do printfn "%d" x  // 2 4 6 again
 

Both iterations work because each for expression copies doubled into its own iteration state.

5.3 Closure Invocation from Wrapper

When invoking the mapper/predicate, its environment is viewed in place inside the wrapper’s environment and its implementation is called with that view, per Closure Representation §6:

// Middle end — portable dialects only. In MapMoveNext(%env: memref<Exi8>):
// 1. View the mapper's environment in place (no copy, no extraction of a code pointer).
%mapper_env = memref.view %env[%off_mapper][] : memref<Exi8> to memref<E_mapperxi8>

// 2. Call the mapper with its environment. The callee is known at saturation
//    (lambda literal or named function at the Seq.map site), so the call is direct.
%result = func.call @mapper_site(%mapper_env, %inner_val) : (memref<E_mapperxi8>, A) -> B

6. Composition Model

6.1 Nested Struct Pattern

When operations are composed:

let pipeline =
    source
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.map (fun x -> x * 2)
    |> Seq.take 5

The result is a nested struct:

TakeSeq env {
    state, current,
    inner: MapSeq env {
        state, current,
        inner: FilterSeq env {
            state, current,
            inner: source_seq env,
            predicate env: {...}
        },
        mapper env: {...}
    },
    remaining: 5
}
// The MoveNext of each level is the function-value half of its pair, bound at
// saturation; none is stored in the nested environment.

6.2 Struct Size Growth

Struct size is compile-time known and grows with composition depth:

size(TakeSeq(MapSeq(FilterSeq(source)))) = 
    base_TakeSeq + size(MapSeq(FilterSeq(source))) =
    base_TakeSeq + base_MapSeq + size(FilterSeq(source)) = ...

Trade-off: For typical pipeline depths (3-5 operations), struct sizes remain reasonable (hundreds of bytes). Very deep pipelines may benefit from alternative strategies (future optimization).

6.3 MoveNext Cascade

Calling MoveNext on the outermost wrapper cascades inward:

TakeMoveNext:
    if remaining > 0:
        if MapMoveNext(inner_map):    // <- calls into nested struct
            copy inner_map.current to current
            remaining--
            return true
    return false

MapMoveNext:
    if FilterMoveNext(inner_filter):  // <- calls into nested struct
        current = mapper(inner_filter.current)
        return true
    return false

FilterMoveNext:
    while SourceMoveNext(inner_source):
        if predicate(inner_source.current):
            current = inner_source.current
            return true
    return false

7. MoveNext Implementations

7.1 MapMoveNext Algorithm

MapMoveNext(env: MapSeq<A,B> env) -> bool:
    if inner.MoveNext():
        self.current = self.mapper(inner.current)
        return true
    return false

State Values: 0 = not started (same as 1), 1 = active, -1 = done (not used, delegated to inner)

7.2 FilterMoveNext Algorithm

FilterMoveNext(env: FilterSeq<A> env) -> bool:
    while inner.MoveNext():
        if self.predicate(inner.current):
            self.current = inner.current
            return true
    return false

Note: Filter loops internally until finding a match or exhausting the inner sequence.

7.3 TakeMoveNext Algorithm

TakeMoveNext(env: TakeSeq<A> env) -> bool:
    if self.remaining > 0:
        if inner.MoveNext():
            self.current = inner.current
            self.remaining--
            return true
    return false

Note: remaining is decremented on each successful iteration, providing count limiting.

7.4 CollectMoveNext Algorithm

CollectMoveNext(env: CollectSeq<A,B> env) -> bool:
    loop:
        // Try advancing current inner sequence
        if self.state == 1 and inner_seq.MoveNext():
            self.current = inner_seq.current
            return true
        
        // Inner exhausted or not started - advance outer
        if outer_seq.MoveNext():
            self.inner_seq = self.mapper(outer_seq.current)  // New inner seq
            self.state = 1
            continue loop
        
        // Outer exhausted
        self.state = -1
        return false

Complexity: Seq.collect maintains state for both outer and inner iteration.

8. Seq.fold: Eager Consumer

Unlike transformers, Seq.fold does not create a wrapper sequence. It immediately consumes the input:

let sum = Seq.fold (fun acc x -> acc + x) 0 source

Implementation on the LLVM target pathway (committed dialect, not middle-end output). The middle end emits the loop over portable scf/memref/arith and carries the closure over portable dialects; the LLVM pathway commits the alloca/getelementptr/load/store and the indirect call to the target ABI, per Backend Lowering Architecture §4.2:

func @seq_fold(%folder: !closure, %initial: i64, %source: !seq_type) -> i64 {
    // Allocate source on stack for mutation
    %seq_alloca = llvm.alloca 1 x !seq_type : !llvm.ptr
    llvm.store %source, %seq_alloca
    
    // Accumulator
    %acc_alloca = llvm.alloca 1 x i64 : !llvm.ptr
    llvm.store %initial, %acc_alloca
    
    // Iteration loop
    scf.while : () -> () {
        %moveNext_ptr = llvm.getelementptr %seq_alloca[0, 2] : !llvm.ptr
        %moveNext = llvm.load %moveNext_ptr : !llvm.ptr
        %has_next = llvm.call %moveNext(%seq_alloca) : (!llvm.ptr) -> i1
        scf.condition(%has_next)
    } do {
        // Get current element
        %curr_ptr = llvm.getelementptr %seq_alloca[0, 1] : !llvm.ptr
        %elem = llvm.load %curr_ptr : i64
        
        // Apply folder
        %acc = llvm.load %acc_alloca : i64
        %folder_code = llvm.extractvalue %folder[0] : !closure -> !llvm.ptr
        %new_acc = llvm.call %folder_code(%acc, %elem) : (i64, i64) -> i64
        llvm.store %new_acc, %acc_alloca
        
        scf.yield
    }
    
    %result = llvm.load %acc_alloca : i64
    return %result : i64
}

9. SSA Cost Formulas

9.1 Wrapper Creation Costs

9.2 MoveNext SSA Costs

10. Normative Requirements

1. Flat Representation: Seq operation wrappers SHALL use flat struct representation with inner seq and closure inlined
2. Copy Semantics: Wrapper creation SHALL copy inner seq and closure by value, not by pointer
3. Field Order: Wrapper environment fields SHALL be ordered: state, current, inner_seq, closure/config; no function address SHALL be stored in the environment, and a wrapper SHALL be the pair (moveNext, env) of Seq Representation §4.1
4. Closure Invocation: Mapper/predicate invocation SHALL follow the flat closure calling convention of Closure Representation §6: call the implementation with a view of its environment as the first argument, directly where the callee is known at saturation
5. Lifetime-Driven Placement: A wrapper sequence SHALL be placed by the four-point lifetime lattice of Closure Representation §3.3: the stack when scope-bounded, a region when region-bounded, static storage (Sram/Flash, memref.global) when its lifetime is the whole program, and the heap only when its extent is genuinely dynamic. A wrapper sequence SHALL NOT be allocated on a GC-managed heap. On a target without a heap, a wrapper that classifies as dynamic SHALL be a compile-time lifetime error, not a heap allocation.
6. Composition = Nesting: Composed operations SHALL produce nested structs, not linked structures
7. Eager Consumers: Seq.fold SHALL consume immediately, not create wrapper

11. Test Cases

11.1 Seq.map with Captured Value

let scale factor xs = Seq.map (fun x -> x * factor) xs
let scaled = scale 3 (seq { yield 1; yield 2; yield 3 })
// Expected: 3 6 9
 

Validates: Mapper closure captures factor correctly.

11.2 Deep Composition

let pipeline =
    source
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.map (fun x -> x * 2)
    |> Seq.filter (fun x -> x > 10)
    |> Seq.take 5

Validates: 4-level nested struct works correctly.

11.3 Copy Semantics Independence

let doubled = Seq.map (fun x -> x * 2) source
let iter1 = doubled |> Seq.take 3 |> Seq.toList  // [2; 4; 6]
let iter2 = doubled |> Seq.take 3 |> Seq.toList  // [2; 4; 6] - same, independent
 

Validates: Each pipeline copies doubled, maintaining independence.

12. References

• Closure Representation - Flat closure architecture
• Seq Representation - Base seq state machine
• PRD-16: SeqOperations - Implementation requirements
• PRD-11: Closures - Flat closure foundation