[epic] Array programming as a first-class optimization domain

Tracking issue for the design note "Array Programming as a First-Class Optimization Domain in Fern" (discussion draft, 18 September 2026). This issue is the ledger; the sub-issues are the work.

The proposal in one sentence. Treat whole-array operations as a compiler-visible algebra that Fern can fuse, vectorize, parallelize later, and map onto its existing uniqueness/reuse model — preserving value-oriented immutable semantics while recovering in-place execution and predictable space use.

The recommendation is explicitly not to make Fern look like APL. What is worth taking from APL is the algebra and the whole-array mental model: elementwise lifting, reduction, scan, selection, reshape/permute, generalized products, rank/axis operations. The notation is not.

Why this fits Fern specifically

The note is grounded in features Fern already has, and the grounding checks out against the tree today:

• Reference counting with Perceus-style elision and immutable reconstruction that reuses storage when a value is uniquely owned — docs/RC-PERCEUS-PLAN.md, docs/REUSE-CONTRACT.md. Reuse here is statically selected, dynamically guarded, and the shapes are named and test-locked.
• own consumes an argument, so a transform that takes own xs: f64[] has a clear licence to reuse the buffer it was handed.
• fip / fbip are compiler-checked on native (E068, internal/ir/fip_verify.go), which makes a checked space contract on array code reachable rather than aspirational. The self-host parse-tolerates them and verifies nothing until the reuse port (plan E4).
• Owned arrays T[] versus views [T] already exist, which is the seed of a strided-view model.
• A large eager 1-D array API already ships: map filter fold reduce zip scan chunks chunks_exact windows flat_map flatten take_while drop_while partition enumerate reverse rotate_left rotate_right dedup union intersection difference, plus the numeric helpers cumsum_f64 cumprod_f64 diff_f64 dot_f64 norm_f64 normalize_f64 scale_f64 variance_f64 stddev_f64 median_f64 (internal/stdlib/std/array.fern, 1843 lines).

So the raw vocabulary exists. What does not exist is any compiler meaning for it: today xs.map(f).map(g).reduce(z, h) is three unrelated opaque calls and two intermediate arrays.

What already exists that this must not duplicate

Read these before starting any sub-issue — two of them already decide things this proposal re-opens.

• docs/ITERATOR-FUSION-CONTRACT.md (plan item B3, shipped as a doc, unbuilt) already specifies what "can fuse" must mean: a compositional zero-allocation guarantee proved per operator rather than per pipeline shape, a named operator algebra in difficulty order (map/filter, then take, then flat_map, then zip as the hard one), hand-written-loop parity as the measurement bar, and visible failure rather than a silent per-stage allocation. That contract governs this work. The difference in scope is that the contract was written for lazy iterator chains, and this proposal targets the eager std/array combinators that ship today — the guarantee and the measurement bar carry over unchanged.
• docs/LANGUAGE-DIRECTION.md, "Things deliberately NOT cribbed", rejects Rust-style lazy iterator chains — "beautiful when the optimizer fuses them, allocation traps when it doesn't" — until the IR can fuse. This epic is the work that would flip that posture. It does not flip it in advance.
• docs/REUSE-CONTRACT.md is the model for how any new array-reuse shape gets specified: named shape, what statically qualifies, what taints the site, the runtime guard, the test that locks it. A new array reuse shape is an R-shape in that document or it is not shipped.
• docs/ALLOCATION-OBSERVABLE.md supplies the measurement: __heap_bump_bytes() (high-water mark) and __heap_alloc_count() (blocks handed out, which is the half the bump mark cannot see). Every fusion or reuse claim in this epic is asserted against those counters, not against RSS and not against a benchmark's wall clock alone.
• docs/ATLAS-PLATFORM-PLAN.md §3 defines the fused-intrinsic SIMD ABI: a kernel is one IR op whose entire vector lifetime stays inside its own emitted sequence, with no vector value live across an op boundary, a call, a branch, or a spill. Any "vectorize the fused loop" ambition meets that rule first — see the axis/kernel sub-issue.

Phases

1. Fusion over existing 1-D operations. Recognize a pure subset as an algebra, introduce an internal array/dataflow representation, fuse producer into consumer, and report what fused.
2. Ownership-aware materialization. Select existing storage when own/uniqueness proves reuse safe; make the interaction with fip/fbip explicit and testable.
3. Multidimensional arrays and a view model. Shape, strides, offset; which operations are metadata-only and when materialization is forced.
4. Axis/rank algebra and kernels. Reductions and scans along an axis, broadcasting, inner/outer products, lowering to SIMD kernels.
5. Parallel / accelerator backends, if justified. Deliberately not filed. The note is explicit that this is a later consequence of a stable algebra and IR, not a prerequisite, and filing it now would invite overfitting the first implementation to GPUs or BLAS.

Non-goals (from §12, binding on every sub-issue)

• Do not turn Fern into a numerical DSL at the expense of its general-purpose identity.
• Do not copy APL syntax for concision. Surface stays ordinary Fern receiver syntax; notation can be revisited independently, after the IR and semantics.
• Do not require all dimensions to be statically known, and do not reach for dependent types.
• Do not make mutation observable just because a buffer was reused.
• Do not let fusion silently change effect or error-order semantics.
• Do not introduce hidden copies in structural operations without a documented materialization rule.
• Do not promise that every chain of high-level operations is allocation-free. The value is a clear semantic model plus transparent optimization.

What success looks like

A programmer writes xs.map(f).map(g).reduce(z, h), can ask the compiler whether it fused and see map(f) -> map(g) -> reduce(h) as one traversal with no intermediate arrays, can consume the input with own when reuse matters, and can strengthen the hot path with fip/fbip when a space guarantee is required. That combination — whole-array thinking, immutable value semantics, compiler-recovered mutation, checked space behaviour — is unusual, and it extends Fern's existing memory philosophy rather than competing with it.

Order of work

The first two gate everything below them, in that order: measure before designing, decide before implementing.

#9728 may conclude that the eager combinators are already adequate in the shapes that matter. That is a legitimate outcome and the epic shrinks accordingly — which is the reason it comes first.

Treat this as an epic rather than a standalone implementation task. Read docs/ITERATOR-FUSION-CONTRACT.md, docs/REUSE-CONTRACT.md, docs/ALLOCATION-OBSERVABLE.md, and docs/ATLAS-PLATFORM-PLAN.md, then begin with sub-issue #9728 by measuring the three representative pipelines. Done means the prerequisite findings and subsequent sub-issues establish the specified array algebra, optimization behavior, and observable allocation rules.