algebra API

Luna-Flow/linear-algebra/algebra 定义了由整个向量和矩阵对象实现的结构 trait：形状、封闭的加法结构、Hadamard 乘法、转置和矩阵乘法。每个 trait 都比其下一层多要求一项能力，因此泛型算法可以准确声明自己用到了什么。该包不包含任何类型和函数；仓库自身稠密类型的实现位于 backends/default。

源码：src/algebra/linear_traits.mbt。该层次结构背后的数学见 algebra 设计，外部类型如何选择层级见集成指南。

导入

///|
import {
  "Luna-Flow/linear-algebra/algebra",
}

Trait 层次结构

Trait	Supertrait	新增能力
`VectorShape`	无	`length`
`AdditiveVector`	`VectorShape + Add + Neg + Sub`	封闭的 `+`、一元 `-`、二元 `-`
`VecMulVector`	`AdditiveVector + Mul`	按元素（Hadamard）`*`
`MatrixShape`	无	`shape`
`TransposeMatrix`	`MatrixShape`	同类型 `transpose`
`AdditiveMatrix`	`TransposeMatrix + Add + Neg + Sub`	封闭的 `+`、一元 `-`、二元 `-`
`MatMulMatrix`	`AdditiveMatrix + Mul`	矩阵乘积 `*`

所有 trait 都是 pub(open)：任何包都可以为自己拥有的类型实现它们。运算符 trait Add、Neg、Sub 和 Mul 是 MoonBit 内置 trait，因此加入某一层级的类型仍可继续使用普通运算符。

形状 trait

`VectorShape`

VectorShape 标记长度可被观察的对象。

pub(open) trait VectorShape {
  fn length(Self) -> Int
}

它不声明任何运算，也不提供元素访问。长度为 $n$ 的向量是某个集合中的元素，实现将该集合与 $\{0, \dots, n-1\}$ 相关联；该 trait 只暴露 $n$ 。

`VectorShape::length`

VectorShape::length 返回向量的分量个数。

fn VectorShape::length(Self) -> Int

对于本仓库中的每个实现，结果都是非负的。在泛型代码中请以 trait 限定形式 @algebra.VectorShape::length(v) 调用；具体类型也可以提供自己的 length 方法。

`MatrixShape`

MatrixShape 标记行数和列数可被观察的对象。

pub(open) trait MatrixShape {
  fn shape(Self) -> (Int, Int)
}

`MatrixShape::shape`

MatrixShape::shape 返回 (rows, cols)。

fn MatrixShape::shape(Self) -> (Int, Int)

两个分量都是非负的。退化形状 $0 \times n$ 和 $n \times 0$ 都是合法的矩阵，必须如实报告。

下面的示例为两个小类型实现了这两个形状 trait，并以泛型形式读回它们。

///|
struct AlgApiToyMatrix {
  rows : Int
  cols : Int
}

///|
struct AlgApiToyVector {
  size : Int
}

///|
impl @algebra.MatrixShape for AlgApiToyMatrix with fn shape(self) {
  (self.rows, self.cols)
}

///|
impl @algebra.VectorShape for AlgApiToyVector with fn length(self) {
  self.size
}

///|
test "shape traits report dimensions" {
  let matrix : AlgApiToyMatrix = { rows: 2, cols: 3, }
  let vector : AlgApiToyVector = { size: 4, }
  debug_inspect(@algebra.MatrixShape::shape(matrix), content="(2, 3)")
  inspect(@algebra.VectorShape::length(vector), content="4")
}

向量 trait

`AdditiveVector`

AdditiveVector 标记其值在 + 下构成阿贝尔群的向量类型。

pub(open) trait AdditiveVector : VectorShape + Add + Neg + Sub {
}

该 trait 自身没有方法。实现它即承诺：对于长度相等的值，

\begin{aligned} (u + v) + w &= u + (v + w), & u + v &= v + u, \\ (u + (-u)) + v &= v, & u - v &= u + (-v), \end{aligned}

并且结果保持操作数的长度。该 trait 不要求全局零元、标量作用、点积或范数；原因见设计页面。长度相等是运行时前置条件：本仓库中的实现在长度不匹配时会中止。

`VecMulVector`

VecMulVector 以 * 的形式增加按元素（Hadamard）乘积 $(u \odot v)_i = u_i v_i$ 。

pub(open) trait VecMulVector : AdditiveVector + Mul {
}

* 必须表示 Hadamard 积，而不是点积或叉积。有了它，环 $R$ 上固定长度 $n$ 的向量构成积环 $R^n$ ，因此 * 满足结合律，并对 + 满足分配律。

该示例为每个层级各写一个辅助函数，并在一个只有单个分量的玩具类型上运行它们。

///|
struct AlgApiMulVec {
  value : Int
}

///|
impl @algebra.VectorShape for AlgApiMulVec with fn length(_) {
  1
}

///|
impl Add for AlgApiMulVec with fn add(left, right) {
  { value: left.value + right.value, }
}

///|
impl Neg for AlgApiMulVec with fn neg(value) {
  { value: -value.value, }
}

///|
impl Sub for AlgApiMulVec with fn sub(left, right) {
  left + -right
}

///|
impl Mul for AlgApiMulVec with fn mul(left, right) {
  { value: left.value * right.value, }
}

///|
impl @algebra.AdditiveVector for AlgApiMulVec

///|
impl @algebra.VecMulVector for AlgApiMulVec

///|
fn[V : @algebra.AdditiveVector] alg_api_difference(left : V, right : V) -> V {
  left - right
}

///|
fn[V : @algebra.VecMulVector] alg_api_hadamard(left : V, right : V) -> V {
  left * right
}

///|
test "vector traits expose closed operators" {
  let left : AlgApiMulVec = { value: 7, }
  let right : AlgApiMulVec = { value: 3, }
  inspect(alg_api_difference(left, right).value, content="4")
  inspect(alg_api_hadamard(left, right).value, content="21")
}

矩阵 trait

`TransposeMatrix`

TransposeMatrix 标记在转置下封闭的矩阵类型。

pub(open) trait TransposeMatrix : MatrixShape {
  fn transpose(Self) -> Self
}

`TransposeMatrix::transpose`

TransposeMatrix::transpose 以同类型的值返回转置 $A^{\mathsf T}$ ，其中 $(A^{\mathsf T})_{ij} = A_{ji}$ 。

fn TransposeMatrix::transpose(Self) -> Self

实现必须满足

\operatorname{shape}(A^{\mathsf T}) = (n, m) \text{ when } \operatorname{shape}(A) = (m, n), \qquad (A^{\mathsf T})^{\mathsf T} = A .

转置是全函数：对任何形状都不会失败。该 trait 不要求稠密存储、元素访问或修改操作；也不规定结果是否与参数共享存储。

`AdditiveMatrix`

AdditiveMatrix 为可转置的矩阵类型增加封闭的按元素 +、一元 - 和二元 -。

pub(open) trait AdditiveMatrix : TransposeMatrix + Add + Neg + Sub {
}

其定律即形状相同的矩阵上 AdditiveVector 的定律，再加上 $(A + B)^{\mathsf T} = A^{\mathsf T} + B^{\mathsf T}$ 。形状相同是运行时前置条件。

`MatMulMatrix`

MatMulMatrix 以 * 的形式增加矩阵乘积。

pub(open) trait MatMulMatrix : AdditiveMatrix + Mul {
}

* 必须是乘积 $(AB)_{ik} = \sum_j A_{ij} B_{jk}$ ，绝不能是 Hadamard 积。它仅在左操作数的列数等于右操作数的行数时有定义，因此对于运行时确定形状的矩阵，它是一个偏运算。该 trait 不规定定义域之外的行为：每个实现都必须在文档中说明。backends/default 的稠密包装类型会以维度不匹配的消息中止。在两边都有定义的地方，实现必须满足

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A + B)C = AC + BC ,

并且在标量可交换时满足 $(AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}$ 。

该示例为固定 $1 \times 1$ 的类型实现了所有矩阵层级（此时所有运算都是全函数），并使用了一个泛型的 Gram 矩阵辅助函数。

///|
struct AlgApiScalarMatrix {
  value : Int
}

///|
impl @algebra.MatrixShape for AlgApiScalarMatrix with fn shape(_) {
  (1, 1)
}

///|
impl @algebra.TransposeMatrix for AlgApiScalarMatrix with fn transpose(self) {
  self
}

///|
impl Add for AlgApiScalarMatrix with fn add(left, right) {
  { value: left.value + right.value, }
}

///|
impl Neg for AlgApiScalarMatrix with fn neg(value) {
  { value: -value.value, }
}

///|
impl Sub for AlgApiScalarMatrix with fn sub(left, right) {
  left + -right
}

///|
impl Mul for AlgApiScalarMatrix with fn mul(left, right) {
  { value: left.value * right.value, }
}

///|
impl @algebra.AdditiveMatrix for AlgApiScalarMatrix

///|
impl @algebra.MatMulMatrix for AlgApiScalarMatrix

///|
fn[M : @algebra.MatMulMatrix] alg_api_gram(matrix : M) -> M {
  @algebra.TransposeMatrix::transpose(matrix) * matrix
}

///|
test "matrix traits compose" {
  let a : AlgApiScalarMatrix = { value: 3, }
  let b : AlgApiScalarMatrix = { value: 5, }
  inspect((a + b).value, content="8")
  inspect(alg_api_gram(a).value, content="9")
}

本仓库中的实现

类型	Trait
`@default.DenseVector[T]`	`VectorShape`；当 `T : Add + Neg` 时为 `AdditiveVector`；当 `T : Add + Neg + Mul` 时为 `VecMulVector`
`@default.ImmutableDenseVector[T]`	与 `DenseVector` 相同
`@default.DenseMatrix[T]`	`MatrixShape`、`TransposeMatrix`；当 `T : Add + Neg` 时为 `AdditiveMatrix`；当 `T : Add + Neg + AddMonoid + Mul` 时为 `MatMulMatrix`
`@default.ImmutableDenseMatrix[T]`	`MatrixShape`、`TransposeMatrix`；当 `T : Add + Neg` 时为 `AdditiveMatrix`；当 `T : Add + Neg + Zero + Mul` 时为 `MatMulMatrix`

具体的 @immut 和 @mutable 类型并不直接实现这些 trait；它们由 backends/default 包装，以便这些包保持各自的依赖方向（见架构指南）。