backends/default 设计

设计目标

只有当某个真实的稠密类型实现了 algebra trait，它们才有用。backends/default 通过包装具体的 @mutable 和 @immut 类型提供这一参考后端，同时让这些具体包不依赖实验性的 algebra 层。它是一个后端，而不是生态的中心：泛型算法依赖 trait，而本包只是满足它们的一种方式。

数学背景

实例是定律的证据

为某个类型实现 @algebra.MatMulMatrix，就是声称它满足 algebra 设计中列出的定律：只要有定义，* 满足结合律以及对 + 的分配律。对包装类型而言，这些定律继承自被包装的类型，因为每个运算符都定义为“解包、应用内部运算符、再包装”：

\mathrm{wrap}(A) \cdot \mathrm{wrap}(B) = \mathrm{wrap}(A \cdot B) .

因此 wrap 对每个运算都是同态，凡对内部类型成立的等式，对包装类型也成立。

稠密乘积的部分性

对于运行时确定形状的稠密矩阵，乘积定义在 $\{(A, B) : \operatorname{cols}(A) = \operatorname{rows}(B)\}$ 上。trait 方法返回 Self，因此在该集合之外包装类型必须有所处理；它和内部类型一样中止。这正是 MatMulMatrix 契约要求实现说明的运行时前置条件。

点积及其舍入误差

dot 按递推 $s_0 = 0$ 、 $s_i = s_{i-1} + u_i v_i$ 计算 $s_n = \sum_{i=1}^{n} u_i v_i$ 。在浮点运算中，每一步都会让此前所有项的误差再乘上一个因子 $(1 + \delta)$ ，标准论证给出

\big|\mathrm{fl}(s_n) - s_n\big| \le \gamma_n \sum_{i=1}^{n} |u_i v_i|, \qquad \gamma_n = \frac{n u}{1 - n u} .

因此当各项同号时相对误差很小，而当 $\sum |u_i v_i| \gg |s_n|$ （相消）时可能很大。matvec 由 $m$ 个这样的点积组成，逐行继承同样的界。

设计决策

自有的包装类型

问题。 MoonBit 只允许在拥有 trait 或类型的包中编写 impl Trait for Type。为 @mutable.Matrix 实现 @algebra.MatMulMatrix 要么得在 algebra 中进行（而它不得知道具体类型），要么得在 mutable 中进行（这样它就会依赖实验性的 algebra 层）。

决定。 在本包中定义新类型 DenseMatrix[T]、DenseVector[T] 及其不可变对应类型，每个都是带有一个公开字段 inner 的结构体，并在此为它们实现这些 trait。

理由。 包装类型归实现这些 trait 的包所有，因此满足规则，依赖方向保持为 backends/default → algebra, immut, mutable。代价是类型上多一层间接，可通过 inner() 和 from_backend 无复制地去除。

取标量值的映射作为后端方法

dot、scale、axpy 和 matvec 是包装类型的方法，而不是 trait：它们显式涉及标量类型，而 algebra trait 无法指称标量类型（见 algebra 设计）。将它们保留为方法，可以让每个后端选择自己的约束，例如可变向量上的 dot 要求 AddMonoid + Mul，不可变向量上则要求 Zero + Add + Mul。

`axpy` 返回新向量

BLAS 例程 axpy 原地更新 $y \leftarrow a x + y$ 。这里两个包装类型的 x.axpy(a, y) 都把 $x a + y$ 作为新向量返回，因此可变与不可变后端共享同一个返回值契约。原地更新仍可通过内部的 @mutable.Vector 进行。

标量右乘

scale 使用 right_scale，计算 $v_i a$ 。对可交换标量，这与 $a v_i$ 相同；对非交换标量，这一选择是可见的，因此在文档中说明而不是隐藏。

正确性与不变量

同态。 对每个运算符都有 inner(a op b) == inner(a) op inner(b)，因此包装类型恰好满足被包装类型的定律。
包装时不复制。 from_backend(x).inner() 在物理上就是 x；对可变内部值的写入可以通过包装类型看到。
转置。 transpose 会物化；它从不返回视图，因此 TransposeMatrix 定律 $(A^{\mathsf T})^{\mathsf T} = A$ 在值层面成立。
复杂度。 +、-、scale： $O(n)$ ；dot： $n$ 次乘加；matvec： $mn$ ；*： $rcn$ 次乘加；transpose： $O(rc)$ 次复制。

被否决的方案

在单个矩阵类型内部设置运行时后端选择器。 这会让每个运算都在后端之间分支，并隐藏实际运行的是哪个内核。后端按类型选择。
直接在 immut 和 mutable 中实现这些 trait。 这会把稳定的具体包与实验性的 algebra 层绑在一起。
原地 axpy。 这会让两个包装类型的同名方法语义不同。

边界

backends/default 不定义新的 trait，也不定义新的数值算法；mutable 的分解、逆矩阵和统计功能通过 inner() 获得。它不提供稀疏、惰性、静态尺寸或 GPU 后端；这些后端应当为自己的类型实现 algebra trait，而不是转换成这些包装类型。曾与它并列的原生 OpenBLAS 后端在本版本中已撤下，保存在 contrib/openblas_backend 中。