core 设计

设计目标

luna-generic 要给整个 LunaFlow 提供一套共享的代数词汇，让 arithmetic、luna-complex、linear-algebra、luna-poly 等包能够复用同一组能力边界。

核心设计决策

• trait 图保持分层且足够小。
• Ring、Field、Integral、Nat 这类结构 traits 与 Zero、One、 Inverse、Conjugate 这类操作 traits 分离。
• 转换被拆成在 ℤ（以 BigInt 表示）处汇合的两半。目标侧是典范映射 ℤ -> R（FromInteger），它唯一且总是同态。源侧是 Integral::normalize，它选取代表元，只有对 ℤ 本身才是同态。lift_to 把两者复合，不对运算作任何承诺。
• 两半都是单参数 trait，因为每个转换都经由初始环 ℤ 分解：没有哪个 trait 需要关联两个类型。
• Integral 以定律 from_integer(normalize(x)) == x 扩展 FromInteger，这使整数类型成为带有选定代表元的 ℤ 的商。FromInteger 接收 BigInt 而不是泛型的整数源，因此这些 trait 不会互相引用。
• 无符号类型不提供加法逆元，保证抽象在数学上保持诚实。
• Field 指交换域。与所有结构 trait 一样，它的定律是对实现者的契约，而不是编译器检查的内容。

数学背景

每个结构 trait 都是某个代数结构的签名，该结构的公理就是实例所承诺的定律。设 $x, y, z$ 取遍载体：

Trait	结构	在超 trait 之上增加的定律
AddMonoid	幺半群 $(A, +, 0)$	$(x+y)+z = x+(y+z)$, $0+x = x+0 = x$
MulMonoid	幺半群 $(A, \cdot, 1)$	$(xy)z = x(yz)$, $1x = x1 = x$
AddGroup	群 $(A, +, 0, -)$	$x + (-x) = (-x) + x = 0$
MulGroup	群 $(A, \cdot, 1, {}^{-1})$	$x x^{-1} = x^{-1} x = 1$
Semiring	半环	$x+y = y+x$, $x(y+z) = xy+xz$, $(x+y)z = xz+yz$, $0x = x0 = 0$
Ring	环	AddGroup 的定律
Field	域	$xy = yx$，对 $x \neq 0$ 有 $x x^{-1} = 1$，$x/y = x y^{-1}$

超 trait 图反映了结构之间的包含关系：每个环都是半环，每个半环既是加法幺半群也是乘法幺半群，以此类推。以 T : Ring 为约束的函数恰好可以使用环公理的推论，这正是泛型代码对每个实例都正确的原因。

这类结构之间的同态 $\varphi : A \to B$ 保持签名中的每个运算：

$$\varphi(0) = 0, \quad \varphi(1) = 1, \quad \varphi(x + y) = \varphi(x) + \varphi(y), \quad \varphi(xy) = \varphi(x)\varphi(y).$$

作为 ℤ 的商的整数

本节给出 FromNat、FromInteger、Integral 与 lift_to 背后的数学。core 教程演示了不依赖这些数学的用法。

典范映射是唯一的

对每个环 R，恰好存在一个环同态 ℤ -> R。环同态 φ 必须把 1 映到 1，加法性随即迫使 n > 0 时 φ(n) = 1 + ... + 1（n 个），且 φ(-n) = -φ(n)。反过来，由分配律，n ↦ n·1 保持 + 与 *。同样的论证说明，对每个半环 R 恰好存在一个半环同态 ℕ -> R。用范畴论的话说，ℕ 与 ℤ 是始对象。

下面给出完整推导，先看 ℕ。设 $R$ 为半环，递归定义 $\varphi : \mathbb{N} \to R$：

$$\varphi(0) = 0, \qquad \varphi(n + 1) = \varphi(n) + 1 .$$

可加性，对 $n$ 归纳（利用 $R$ 中 $+$ 的结合律）：

$$\begin{aligned} \varphi(m + 0) &= \varphi(m) = \varphi(m) + \varphi(0), \\ \varphi(m + (n+1)) &= \varphi((m + n) + 1) = \varphi(m + n) + 1 \\ &= (\varphi(m) + \varphi(n)) + 1 = \varphi(m) + \varphi(n + 1). \end{aligned}$$

可乘性，对 $n$ 归纳（利用吸收律 $x \cdot 0 = 0$、可加性与分配律）：

$$\begin{aligned} \varphi(m \cdot 0) &= 0 = \varphi(m) \cdot 0 = \varphi(m)\varphi(0), \\ \varphi(m(n+1)) &= \varphi(mn + m) = \varphi(m)\varphi(n) + \varphi(m) \\ &= \varphi(m)(\varphi(n) + 1) = \varphi(m)\varphi(n + 1). \end{aligned}$$

唯一性：任何半环同态 $\psi$ 都满足 $\psi(0) = 0$ 与 $\psi(n + 1) = \psi(n) + \psi(1) = \psi(n) + 1$，即同一递推，因此由归纳法 $\psi = \varphi$。

对 ℤ，设 $R$ 为环。每个整数都是自然数之差 $a - b$；令 $\hat\varphi(a - b) = \varphi(a) - \varphi(b)$。这是良定义的：$a - b = c - d$ 意味着在 ℕ 中 $a + d = b + c$，从而在 $R$ 中 $\varphi(a) + \varphi(d) = \varphi(b) + \varphi(c)$，两边同加 $-\varphi(b) - \varphi(d)$（$+$ 可交换）得 $\varphi(a) - \varphi(b) = \varphi(c) - \varphi(d)$。它逐项可加，并由分配律可乘：

$$\begin{aligned} \hat\varphi((a - b)(c - d)) &= \hat\varphi((ac + bd) - (ad + bc)) \\ &= \varphi(a)\varphi(c) + \varphi(b)\varphi(d) - \varphi(a)\varphi(d) - \varphi(b)\varphi(c) \\ &= (\varphi(a) - \varphi(b))(\varphi(c) - \varphi(d)). \end{aligned}$$

环同态还必须满足 $\psi(-n) = -\psi(n)$，因此它在负数上也与 $\hat\varphi$ 一致，$\hat\varphi$ 是唯一的。¹1 用范畴论的语言说，ℕ 是半环范畴的始对象，ℤ 是环范畴的始对象。ℤ 是加法幺半群 ℕ 的 Grothendieck 群，上文用的正是这一构造。

由于这个映射只依赖于 R，它是目标类型的性质，适合用单参数 trait 表达：FromNat::from_natural 与 FromInteger::from_integer。

定宽整数

Int 的加法与乘法按模 2^32 计算，因此作为环它是 ℤ/2^32。它的 from_integer 是满射的约化 ℤ -> ℤ/2^32。normalize 方向相反，在每个剩余类中选出一个整数，即位于 [-2^31, 2^31) 中的那个。定律 from_integer(normalize(x)) == x 恰好说明 normalize 是约化的截面：

• normalize 是单射，因为它有左逆。
• 它的像在每个类中恰好含一个元素：至多一个是因为它是单射，至少一个是因为定律。
• 它不是同态：normalize(2147483647 + 1) = -2^31，而 normalize(2147483647) + normalize(1) = 2^31。

用符号表示：设 $m = 2^k$，$\pi : \mathbb{Z} \to \mathbb{Z}/m$ 为约化映射，其核为 $m\mathbb{Z}$，随包实例使用

$$s_{\text{signed}}(\pi(n)) = \bigl((n + 2^{k-1}) \bmod 2^k\bigr) - 2^{k-1}, \qquad s_{\text{unsigned}}(\pi(n)) = n \bmod 2^k,$$

其中 $\bmod$ 取值于 $[0, 2^k)$。两者都是良定义的，因为 $n$ 与 $n + jm$ 给出相同的值；两者都满足 $\pi(s(x)) = x$，因为各自与 $n$ 相差 $m$ 的倍数。上文两步单射性论证写出来就是：

$$s(x) = s(y) \;\Longrightarrow\; x = \pi(s(x)) = \pi(s(y)) = y .$$

可加性的偏差是模数的倍数：

$$s(x) + s(y) - s(x + y) \in m\mathbb{Z}, \qquad\text{because}\qquad \pi\bigl(s(x) + s(y)\bigr) = x + y = \pi\bigl(s(x + y)\bigr).$$

在 Int 上取 $x = 2^{31} - 1$ 与 $y = 1$，偏差为 $2^{32}$，因此任何代表元选择都无法修复：$s$ 只在 $m = 0$ 时是同态，也就是对 BigInt。

hom 设计说明了截面究竟保持什么。

何时转换是同态

lift_to : S -> R 是 R::from_integer 与 S::normalize 的复合。当 S 是 ℤ/m（BigInt 对应 m = 0）时，环同态 ℤ/m -> R 存在当且仅当在 R 中 m·1 = 0：

• 若 ψ 是这样的同态，则在 R 中 0 = ψ(0) = ψ(m·1) = m·1。
• 若 m·1 = 0，典范映射 ℤ -> R 把 mℤ 映到 0，因此经由 ℤ/m 分解。由于 ℤ -> ℤ/m 是满射，这个分解是唯一的。

此时 lift_to 就是这个同态：把典范映射 ℤ -> R 写成 ψ ∘ π，其中 π : ℤ -> ℤ/m；则 lift_to = ψ ∘ π ∘ normalize = ψ。于是：

• Int64 -> Int 是同态，因为 2^64 ≡ 0 (mod 2^32)。
• Int -> Int64 不是，因为 2^32 ≢ 0 (mod 2^64)。
• 没有任何定宽整数能同态地映入 BigInt、Float 或 Double，因为在这些类型中对每个 m > 0 都有 m·1 ≠ 0。

把同一论证写成一条链：$\iota_R : \mathbb{Z} \to R$ 为典范映射，当 $m \cdot 1_R = 0$ 时 $\iota_R = \psi \circ \pi$：

$$\texttt{lift\_to} = \iota_R \circ s = \psi \circ \pi \circ s = \psi \circ \mathrm{id}_{\mathbb{Z}/m} = \psi .$$

对两个模数的例子：在 ℤ/2^32 中 $2^{64} \cdot 1 = 2^{32} \cdot (2^{32} \cdot 1) = 2^{32} \cdot 0 = 0$，而在 ℤ/2^64 中 $2^{32} \cdot 1 \neq 0$，因为 $0 < 2^{32} < 2^{64}$。

为什么无符号类型止步于 Semiring

UInt、UInt16 与 UInt64 被理解为会回绕的自然数：Nat 承诺代表元非负，使用它们的代码把值当作计数与尺寸。ℕ 没有加法逆元，因此它是半环而不是环：

$$1 + x = 0 \text{ in } \mathbb{N} \;\Longrightarrow\; 0 = 1 + x \geq 1,$$

矛盾。作为抽象环，无符号类型是 ℤ/2^k，它确实有负元 $-x = 2^k - x$。暴露它们会让 -1 在为环编写的泛型代码中悄悄变成 $2^k - 1$，这正是 Nat 的理解方式所要避免的混淆。核心库也没有为无符号类型提供 Neg，而 MoonBit 不允许本包为外部类型添加外部 trait 的实例，所以不借助包装类型本来也无法实现 AddGroup。典范映射依然是全的：UInt 上的 from_integer(-1) 是 $2^{32} - 1$，即 $-1$ 在 ℤ/2^32 中的像。

为什么这些 trait 不互相引用

每个转换都经由 ℤ 分解：S -> ℤ -> R。前半只依赖 S（Integral），后半只依赖 R（FromInteger），所以没有哪个 trait 需要关联两个类型。FromInteger 接收 BigInt 而不是泛型的整数源，这使 Integral 可以扩展它而不形成环。

域与除环

Field 是乘法可交换的 Ring + Inverse + Div。即使没有任何方法表述交换律，它也是契约的一部分。

定义

除环 是满足 $1 \neq 0$、且每个 $a \neq 0$ 都有双边逆元 $a a^{-1} = a^{-1} a = 1$ 的环。域 是乘法可交换（$ab = ba$）的除环。两者只差这一条定律，而 Ring + Inverse + Div 的方法签名无法区分它们。

不是域的除环的标准例子是 Hamilton 四元数 ℍ，基为 $1, i, j, k$，且 $i^2 = j^2 = k^2 = ijk = -1$。由 $ijk = -1$ 两边右乘 $k$ 得 $ij \cdot k^2 = -k$，所以 $ij = k$；同理 $ji = -k$：

$$ij = k, \qquad ji = -k, \qquad ij \neq ji .$$

没有交换律时什么会出错

在任何除环中，乘积的逆会颠倒顺序：

$$(ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1} = a a^{-1} = 1, \qquad\text{so}\qquad (ab)^{-1} = b^{-1}a^{-1}.$$

另一种顺序是另一个乘积的逆，$a^{-1}b^{-1} = (ba)^{-1}$，而求逆是单射，所以

$$(ab)^{-1} = a^{-1}b^{-1} \iff (ab)^{-1} = (ba)^{-1} \iff ab = ba .$$

在 ℍ 中 $(ij)^{-1} = k^{-1} = -k$，而 $i^{-1} j^{-1} = (-i)(-j) = ij = k$。除法同样有歧义：$a b^{-1}$ 与 $b^{-1} a$ 一般是不同的元素，而 Div 只提供其中之一。

以 F : Field 为约束的泛型代码可以依赖 $ab = ba$：把 $(ab)^{-1}$ 改写为 $a^{-1}b^{-1}$、把 $a/b \cdot c$ 算成 $ac/b$，或为节省计算而重排乘积。实现了 Field 的非交换类型能编译通过，却会从这样的代码中得到错误答案。这就是该 trait 声明交换律的原因，也是不是域的除环不得实现它的原因。同样适用于除环的泛型代码应要求 Ring + Inverse + Div，并保持因子的顺序。

每个有限除环都是交换的，²2 Wedderburn 小定理（1905）：有限除环是域。在实数上，Frobenius 定理（1877）进一步指出，有限维结合除代数只有 ℝ、ℂ 和 ℍ。 因此这一区别只出现在无限类型上。

浮点实例

Float 与 Double 在舍入意义下实现 Field。它们的乘法严格可交换，$\mathrm{fl}(ab) = \mathrm{fl}(ba)$，因为 IEEE 754 对精确乘积舍入，而精确乘积与顺序无关。结合律与分配律只近似成立，且 0 没有逆元：inv 在其上中止。

被否决的方案

• 双参数转换 trait Into[S, R]：MoonBit 的 trait 只有 Self，而经由 ℤ 的分解使它没有必要。
• 一个宽泛的“数”trait：它会掩盖 ℤ、ℤ/2^k、近似实数与域之间的差异，而这些恰恰是泛型代码必须尊重的差异。
• 把 NatHomomorphism 与 IntegralHomomorphism 作为转换接口：它们承诺了定宽源无法给出的同态。它们仅作为已弃用的 trait 保留。
• 单独的除环 trait：没有随包类型需要它，而必须在无交换律下工作的代码可以要求 Ring + Inverse + Div。

边界

• 本包不定义矩阵、复数、多项式、解析函数或数值算法。
• 它不会刻意抹平精确数值系统与近似数值系统之间的语义差异。
• 它不在编译期检查定律。每个结构 trait 的定律（包括 Field 的交换律）都是对实现者的契约，用 hom API 中的工具测试。
• 它不建模任意精度的 ℕ：这样的类型不是 ℤ 的商，因此不能是 Integral。

Footnotes

1. 用范畴论的语言说，ℕ 是半环范畴的始对象，ℤ 是环范畴的始对象。ℤ 是加法幺半群 ℕ 的 Grothendieck 群，上文用的正是这一构造。 ↩

2. Wedderburn 小定理（1905）：有限除环是域。在实数上，Frobenius 定理（1877）进一步指出，有限维结合除代数只有 ℝ、ℂ 和 ℍ。 ↩