Luna Flow
简体中文

core API

作用

luna-generic 是 LunaFlow 的代数 trait 基础层。它本身不提供数值算法或容器，而是给上层包提供共享的能力边界。

本页列出 trait、转换函数和随包提供的实例。证书 Hom 与 Section 见 hom API 页面。这些形态背后的理由见 core 设计。

导入

把本包加入你的 moon.pkg：

import {
  "Luna-Flow/luna-generic",
}

本页示例用一条 using 声明把名字引入作用域，因此可以省略 @luna-generic. 前缀：

using @luna-generic {
  trait AddMonoid,
  trait MulMonoid,
  trait AddGroup,
  trait MulGroup,
  trait Semiring,
  trait Ring,
  trait Field,
  trait Num,
  trait Zero,
  trait One,
  trait Inverse,
  trait Conjugate,
  trait FromNat,
  trait FromInteger,
  trait Integral,
  trait Nat,
  lift_to,
}

定律即契约

下面的每个结构 trait 都是空 trait，其方法来自超 trait：MoonBit 的 Add、Mul、Neg、Sub 和 Div，以及本包的 Zero、One 和 Inverse。编译器检查这些方法是否存在，但不检查赋予 trait 意义的等式。这些等式列在各 trait 之下；违反它们的实现照样能编译，但基于该 trait 编写的泛型代码随后可能算出错误结果。请在边界值上测试它们，例如用 hom API 中的 Hom::check。

Float 与 Double 只在舍入意义下满足这些定律：浮点加法不满足结合律，因此它们是同一组 trait 的近似实例。

操作 trait

这些 trait 位于 src/operation.mbt。它们各自命名一个运算，本身不规定定律；结构 trait 赋予它们意义。

Zero

Zero::zero() 返回 Self 的加法单位元。

pub(open) trait Zero {
  fn zero() -> Self
}

在 AddMonoid 中它必须满足 0+x=x+0=x0 + x = x + 0 = x。所有默认数值类型都提供。

One

One::one() 返回 Self 的乘法单位元。

pub(open) trait One {
  fn one() -> Self
}

在 MulMonoid 中它必须满足 1⋅x=x⋅1=x1 \cdot x = x \cdot 1 = x。所有默认数值类型都提供。

test "zero and one" {
  let z : Int = Zero::zero()
  let o : Double = One::one()
  inspect(z, content="0")
  inspect(o, content="1")
}

Inverse

Inverse::inv(x) 返回乘法逆元 x−1x^{-1}。

pub(open) trait Inverse {
  fn inv(Self) -> Self
}

在 MulGroup 或 Field 中，对每个有逆元的 xx 它必须满足 x⋅x−1=x−1⋅x=1x \cdot x^{-1} = x^{-1} \cdot x = 1。随包提供的 Float 和 Double 实例在 0 上带消息中止，而不是像 1.0 / 0.0 那样返回无穷大。

test "inv" {
  inspect(Inverse::inv(4.0), content="0.25")
}

Conjugate

Conjugate::conjugate(x) 返回共轭 x‾\overline{x}。

pub(open) trait Conjugate {
  fn conjugate(Self) -> Self
}

本包不提供任何实例。实现者通常让它成为与运算相容的对合：x‾‾=x\overline{\overline{x}} = x、x+y‾=x‾+y‾\overline{x + y} = \overline{x} + \overline{y} 以及 xy‾=y‾ x‾\overline{xy} = \overline{y}\,\overline{x}；当乘法可交换时后者即 x‾ y‾\overline{x}\,\overline{y}。该 trait 并不强制这些定律。

priv struct Pair {
  re : Double
  im : Double
} derive(Eq, Debug)

impl Conjugate for Pair with fn conjugate(z) {
  { re: z.re, im: -z.im }
}

test "conjugate" {
  let z = Pair::{ re: 1.0, im: 2.0 }
  assert_eq(Conjugate::conjugate(Conjugate::conjugate(z)), z)
}

结构 traits

这些 trait 位于 src/structure.mbt。每个 trait 在其所扩展的 trait 之上增加定律；定律对该类型的所有 x,y,zx, y, z 成立。

AddMonoid

AddMonoid 是带有可结合的 + 与单位元 0 的类型。

pub(open) trait AddMonoid : Add + Zero {
}
(x+y)+z=x+(y+z),0+x=x+0=x.(x + y) + z = x + (y + z), \qquad 0 + x = x + 0 = x.

这里不要求 + 可交换；本包中所有建立在 AddMonoid 之上的结构（Semiring、Ring）都要求它可交换。

fn[T : AddMonoid] sum(xs : Array[T]) -> T {
  xs.fold(init=Zero::zero(), (acc, x) => acc + x)
}

test "sum" {
  inspect(sum([1, 2, 3]), content="6")
  inspect(sum(([] : Array[UInt])), content="0")
}

MulMonoid

MulMonoid 是带有可结合的 * 与单位元 1 的类型。

pub(open) trait MulMonoid : Mul + One {
}
(xy)z=x(yz),1⋅x=x⋅1=x.(xy)z = x(yz), \qquad 1 \cdot x = x \cdot 1 = x. 
fn[T : MulMonoid] power(x : T, n : Int) -> T {
  let mut acc : T = One::one()
  for _ in 0..<n {
    acc = acc * x
  }
  acc
}

test "power" {
  inspect(power(3, 4), content="81")
  inspect(power(2UL, 0), content="1")
}

AddGroup

AddGroup 是每个元素都有负元的 AddMonoid。

pub(open) trait AddGroup : AddMonoid + Neg + Sub {
}
x+(−x)=(−x)+x=0,x−y=x+(−y).x + (-x) = (-x) + x = 0, \qquad x - y = x + (-y).

无符号类型不实现它；见下文的语义说明。

fn[T : AddGroup] difference(x : T, y : T) -> T {
  x + -y
}

test "difference" {
  inspect(difference(3, 5), content="-2")
}

MulGroup

MulGroup 是带有逆元与除法的 MulMonoid。

pub(open) trait MulGroup : MulMonoid + Inverse + Div {
}
x⋅x−1=x−1⋅x=1,x/y=x⋅y−1.x \cdot x^{-1} = x^{-1} \cdot x = 1, \qquad x / y = x \cdot y^{-1}.

只有 Float 与 Double 实现它，且对它们而言定律只对非零元素成立：0 没有逆元。

Semiring

Semiring 把一个加法幺半群和一个乘法幺半群通过分配律结合起来。

pub(open) trait Semiring : AddMonoid + MulMonoid {
}
x+y=y+x,x(y+z)=xy+xz,(x+y)z=xz+yz,0⋅x=x⋅0=0.x + y = y + x, \qquad x(y + z) = xy + xz, \qquad (x + y)z = xz + yz, \qquad 0 \cdot x = x \cdot 0 = 0.

所有默认数值类型都实现 Semiring，包括无符号整数。

fn[T : Semiring] dot(xs : Array[T], ys : Array[T]) -> T {
  let mut acc : T = Zero::zero()
  for i, x in xs {
    acc = acc + x * ys[i]
  }
  acc
}

test "dot" {
  inspect(dot([1U, 2U, 3U], [4U, 5U, 6U]), content="32")
}

Ring

Ring 是加法构成群的 Semiring。

pub(open) trait Ring : Semiring + Neg + Sub {
}

它满足 Semiring 定律与 AddGroup 定律。乘法不必可交换。由有符号整数、BigInt、Float 和 Double 实现。

fn[T : Ring] square_of_difference(x : T, y : T) -> T {
  (x - y) * (x - y)
}

test "ring" {
  inspect(square_of_difference(2, 7), content="25")
}

Field

Field 是每个非零元素都有逆元的交换 Ring。

pub(open) trait Field : Ring + Inverse + Div {
}

实现者必须满足 Ring 定律，并且对所有 a,ba, b：

ab=ba,a⋅a−1=1  for a≠0,a/b=a⋅b−1  for b≠0.ab = ba, \qquad a \cdot a^{-1} = 1 \ \text{ for } a \neq 0, \qquad a / b = a \cdot b^{-1} \ \text{ for } b \neq 0.

交换律是契约的一部分，正如域的数学定义。编译器不检查它：乘法不可交换但有逆元的类型（除环）也能作为 Field 编译通过，而依赖 ab=baab = ba 的泛型代码（例如把 (ab)−1(ab)^{-1} 改写为 a−1b−1a^{-1}b^{-1}）对它就会给出错误答案。不要为这样的类型实现 Field。core 设计 解释了两者的区别。

Float 与 Double 在舍入意义下实现 Field。它们的 inv 在 0 上中止，而它们的 / 遵循 IEEE 754，返回无穷大或 NaN。

fn[F : Field] mean(xs : Array[F]) -> F {
  let mut total : F = Zero::zero()
  let mut count : F = Zero::zero()
  for x in xs {
    total = total + x
    count = count + One::one()
  }
  total / count
}

test "field" {
  inspect(mean([1.0, 2.0, 4.5]), content="2.5")
}

Num

Num 是带有绝对值与符号的 Ring。

pub(open) trait Num : Ring {
  fn abs(Self) -> Self
  fn signum(Self) -> Self
}

signum(x) 按 xx 的符号取 −1-1、00 或 11，并且

abs⁡(x)⋅signum⁡(x)=x.\operatorname{abs}(x) \cdot \operatorname{signum}(x) = x.

由有符号整数、BigInt、Float 和 Double 实现。在定宽类型上，该定律在最小负值处失效，因为它的绝对值回绕为它自身。在 Float 与 Double 上，signum 对 0.0、-0.0 和 NaN 返回其参数本身。

test "num" {
  inspect(Num::signum(-7), content="-1")
  inspect(Num::abs(-7) * Num::signum(-7), content="-7")
}

从 ℕ 与 ℤ 出发的典范映射

FromNat

FromNat::from_natural(n) 是唯一的半环同态 ℕ → Self，自然数以 BigInt 给出。

pub(open) trait FromNat {
  fn from_natural(@bigint.BigInt) -> Self
}

前提：n≥0n \ge 0。结果必须是 n⋅1=1+⋯+1n \cdot 1 = 1 + \dots + 1（共 nn 项），因此：

φ(0)=0,φ(1)=1,φ(m+n)=φ(m)+φ(n),φ(mn)=φ(m)φ(n).\varphi(0) = 0, \quad \varphi(1) = 1, \quad \varphi(m + n) = \varphi(m) + \varphi(n), \quad \varphi(mn) = \varphi(m)\varphi(n).

定宽整数按模 2k2^k 约化；Float 与 Double 舍入到最近的值。

FromInteger

FromInteger::from_integer(n) 是唯一的环同态 ℤ → Self，整数以 BigInt 给出。

pub(open) trait FromInteger : FromNat {
  fn from_integer(@bigint.BigInt) -> Self
}

它在整个 ℤ 上满足 from_natural 的定律，并且必须在非负参数上与 from_natural 一致。它对每个整数都有定义，在没有取负运算的类型上也是如此：在无符号类型上，from_integer(-1) 是 2k−12^k - 1。对 BigInt 精确，对定宽整数按模 2k2^k 约化，对 Float 与 Double 舍入。

test "from_integer" {
  let big = BigInt::from_string("4294967301") // 2^32 + 5
  let i : Int = FromInteger::from_integer(big)
  let u : UInt = FromInteger::from_integer(BigInt::from_int(-1))
  let d : Double = FromInteger::from_integer(big)
  inspect(i, content="5")
  inspect(u, content="4294967295")
  inspect(d, content="4294967301")
}

要让你自己的数值类型具备这些转换，请实现这两个 trait；core 教程 演示了做法。

整数类型

Integral

Integral 是整数类型：ℤ 本身，或者商 ℤ/2^k，例如定宽整数。

pub(open) trait Integral : Semiring + FromInteger {
  fn normalize(Self) -> @bigint.BigInt
}

normalize(x) 以 BigInt 返回 x 的代表元。其定律是 normalize 为典范映射的截面：

Self::from_integer(normalize⁡(x))=x.\texttt{Self::from\_integer}(\operatorname{normalize}(x)) = x .

随包实例的选择为：有符号类型取 [−2k−1,2k−1)[-2^{k-1}, 2^{k-1})，无符号类型取 [0,2k)[0, 2^k)，BigInt 取恒等映射。normalize 只对 BigInt 是同态；在定宽类型上不是，因为它们的运算会回绕。Section::of_integral 把这一对映射打包成可检查的证书。

test "normalize" {
  inspect(Integral::normalize(-1), content="-1")
  inspect(Integral::normalize(4294967295U), content="4294967295")
  inspect(Integral::normalize(2147483647 + 1), content="-2147483648")
}

Nat

Nat 是代表元非负的 Integral 类型：对每个 x 有 normalize⁡(x)≥0\operatorname{normalize}(x) \ge 0。

pub(open) trait Nat : Integral {
}

由 UInt、UInt16 和 UInt64 实现。任意精度的 ℕ 不是 ℤ 的商，因此不能是 Integral；见 core 设计。

fn[N : Nat] digits(x : N) -> Int {
  Integral::normalize(x).to_string().length()
}

test "nat" {
  inspect(digits((65535 : UInt16)), content="5")
}

lift_to

lift_to(x) 把整数值提升为其代表元，再映入任意 FromInteger 目标。

pub fn[S : Integral, R : FromInteger] lift_to(S) -> R

它就是 R::from_integer(x.normalize())。它是函数而非同态：它转换的是 x 当前持有的值，所以已在 S 中回绕的和依旧是回绕后的值。当且仅当 R 的模数整除 S 的模数时它保持运算，例如 Int64 -> Int；core 设计 推导了这一条件。

test "lift_to" {
  let a : Double = lift_to(-7)
  let b : BigInt = lift_to(4294967295U)
  let c : Int = lift_to(4294967301L) // truncation, a homomorphism
  inspect(a, content="-7")
  inspect(b, content="4294967295")
  inspect(c, content="5")
}

内置实例

类型Trait
Int, Int16, Int64AddMonoid, MulMonoid, AddGroup, Semiring, Ring, Num, Zero, One, FromNat, FromInteger, Integral
UInt, UInt16, UInt64AddMonoid, MulMonoid, Semiring, Zero, One, FromNat, FromInteger, Integral, Nat
BigInt与有符号整数相同，另加已弃用的 NatHomomorphism 与 IntegralHomomorphism
Float, DoubleAddMonoid、MulMonoid、AddGroup、MulGroup、Semiring、Ring、Field、Num、Zero、One、Inverse、FromNat、FromInteger，另加已弃用的 NatHomomorphism 与 IntegralHomomorphism

Byte 不实现其中任何一个。

语义说明

  • 定宽整数是 ℤ/2^k。它们的 from_integer 按模 2^k 约化，normalize 选取类型范围内的代表元：有符号类型为 [-2^(k-1), 2^(k-1))，无符号类型为 [0, 2^k)。
  • BigInt 就是 ℤ 本身：from_integer 与 normalize 都是恒等映射。
  • lift_to 当且仅当目标模数整除源模数时是同态，例如 Int64 -> Int。对定宽源而言，映到 BigInt、Float 或 Double 都不是同态，因为源侧运算会回绕。
  • Nat 涵盖代表元非负的整数类型。真正的任意精度 ℕ 不是 ℤ 的商，不在本包范围内。
  • 无符号整数实例止步于 Semiring，不会伪装成带加法逆元的结构。
  • Float 与 Double 在 from_natural 和 from_integer 中会舍入，因此非常大的值是近似的。
  • Field 要求乘法可交换。编译器无法检查这一点，因此由实现者负责。

已弃用

NatHomomorphism

NatHomomorphism::from_nat(x) 把 Nat 值提升为其代表元，再映入 Self。

pub(open) trait NatHomomorphism {
  fn[S : Nat] from_nat(S) -> Self
}

已弃用，因为对定宽源而言这一复合不是同态。替代方案：实现 FromNat 与 FromInteger，并调用 lift_to(x)。BigInt、Float 和 Double 仍实现它。

IntegralHomomorphism

IntegralHomomorphism::from_integral(x) 把 Integral 值提升为其代表元，再映入 Self。

pub(open) trait IntegralHomomorphism : NatHomomorphism {
  fn[S : Integral] from_integral(S) -> Self
}

因同样的理由弃用。替代方案：实现 FromInteger 并调用 lift_to(x)。BigInt、Float 和 Double 仍实现它。

源码入口

  • src/structure.mbt：trait 定义
  • src/operation.mbt：基础操作 traits
  • src/section.mbt: lift_to
  • src/impl_signed.mbt、src/impl_unsigned.mbt、src/impl_bigint.mbt、 src/impl_float.mbt、src/impl_dbl.mbt：默认实例