Luna Flow
简体中文

core 教程

本教程带你用 luna-generic 的 trait 为多种数值类型编写同一个算法，把整数转换为任意数值类型，并把你自己的类型接入同一套词汇。设计背后的理由见 core 设计。

我想要使用
为多种数值类型写同一个算法T : Ring 之类的 trait 约束
把整数常数或下标转成 T@luna-generic.lift_to(i)，要求 T : FromInteger
让我的数值类型能从整数构造实现 FromNat 与 FromInteger
定义新的整数类型再实现 Integral，并加一个检验
得到任意整数的唯一精确形式Integral::normalize(x)，结果是 BigInt

快速开始

把本包加入你的模块：

moon add Luna-Flow/luna-generic@0.4.0

在使用它的包的 moon.pkg 中导入：

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

本页示例用一条 using 声明把这些 trait 引入作用域：

using @luna-generic {
  trait Semiring,
  trait Ring,
  trait Field,
  trait Zero,
  trait One,
  trait FromNat,
  trait FromInteger,
  trait Integral,
}

最小的有用程序是一个在三种类型上使用的泛型函数：

fn[T : Ring] double_and_add_one(x : T) -> T {
  x + x + One::one()
}

test "quick start" {
  inspect(double_and_add_one(20), content="41")
  inspect(double_and_add_one(0.25), content="1.5")
  inspect(double_and_add_one(BigInt::from_string("99999999999999999999")), content="199999999999999999999")
}

double_and_add_one 适用于有符号整数、BigInt、Float、Double，以及将来任何实现相同 trait 的类型。

日常任务

面向结构写算法，而不是面向具体数字类型

只要求能表述算法需求的最小 trait。积之和只需要 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")
  inspect(dot([0.5, 2.0], [4.0, 0.25]), content="2.5")
}

做减法时要求 Ring，只有做除法时才要求 Field。

用 lift_to 把整数转成你的数值类型

fn[T : Semiring + FromInteger] times_index(x : T, i : Int) -> T {
  x * @luna-generic.lift_to(i)
}

test "lift_to" {
  inspect(times_index(1.5, 4), content="6")
  inspect(times_index(BigInt::from_int(7), -3), content="-21")
}

lift_to 把任意整数类型（Int、UInt64、BigInt 等）的值转成任意实现了 FromInteger 的类型。它看到的是整数当前持有的值：如果某个 Int 计算已经回绕，lift_to 转换的就是回绕后的值。需要完整范围时，请在 BigInt 或 T 中做运算。

在任意域中求平均值

fn[F : Field + FromInteger] mean(xs : Array[F]) -> F {
  let mut total : F = Zero::zero()
  for x in xs {
    total = total + x
  }
  total / @luna-generic.lift_to(xs.length())
}

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

得到任意整数的唯一精确形式

fn[T : Integral] canonical_text(x : T) -> String {
  Integral::normalize(x).to_string()
}

test "normalize" {
  inspect(canonical_text(-5), content="-5")
  inspect(canonical_text((65535 : UInt16)), content="65535")
  inspect(canonical_text(9223372036854775807L), content="9223372036854775807")
}

当你需要在多种整数类型之间使用同一种精确表示时，使用 Integral::normalize。无符号值得到非负结果，有符号值保留符号。

进阶

让你的数值类型可以从整数构造

贯穿示例是一个 8 位回绕整数。只需要能由整数构造的类型实现两个从 BigInt 出发的转换：

priv struct I8 {
  v : Int // always in [-128, 128)
} derive(Eq, Debug)

fn I8::wrap(n : Int) -> I8 {
  let r = ((n % 256) + 256) % 256
  { v: if r >= 128 { r - 256 } else { r } }
}

impl Add for I8 with fn add(a, b) { I8::wrap(a.v + b.v) }
impl Mul for I8 with fn mul(a, b) { I8::wrap(a.v * b.v) }
impl Neg for I8 with fn neg(a) { I8::wrap(-a.v) }
impl Sub for I8 with fn sub(a, b) { I8::wrap(a.v - b.v) }
impl Zero for I8 with fn zero() { { v: 0 } }
impl One for I8 with fn one() { { v: 1 } }
impl @luna-generic.AddMonoid for I8
impl @luna-generic.MulMonoid for I8
impl @luna-generic.AddGroup for I8
impl Semiring for I8
impl Ring for I8

impl FromNat for I8 with fn from_natural(n) {
  I8::wrap((n % BigInt::from_int(256)).to_int())
}

impl FromInteger for I8 with fn from_integer(n) {
  I8::wrap((n % BigInt::from_int(256)).to_int())
}

from_natural 只会收到非负值。两个转换都必须与你的运算一致：转换 a + b 等于各自转换后相加，* 同理，且 0 与 1 分别变成你的零与一。用几个值检验，包括很大的值和负值：

test "from_integer is a homomorphism" {
  let h : @luna-generic.Hom[@luna-generic.RingSig, BigInt, I8] = @luna-generic.Hom::from_integer().to_ring()
  let samples = [0, 1, -1, 127, 128, -129, 1000].map(BigInt::from_int)
  assert_true(h.check(@luna-generic.Algebra::ring(), @luna-generic.Algebra::ring(), samples))
  inspect(h.apply(BigInt::from_int(200)).v, content="-56")
}

浮点类型只在舍入意义下一致；hom 教程演示了如何用容差检验它们。

定义新的整数类型

这种情况很少见。整数类型在上面两个转换之外再实现 Integral。normalize 以 BigInt 返回 x 的值，与你的类型显示的值完全一致，因此再转换回来会得到原来的 x。用你的类型的最小值和最大值检验这个往返：

impl Integral for I8 with fn normalize(x) { BigInt::from_int(x.v) }

test "normalize is a section" {
  let s : @luna-generic.Section[@luna-generic.SemiringSig, I8, BigInt] = @luna-generic.Section::of_integral()
  let samples = [-128, -1, 0, 1, 127].map(I8::wrap)
  assert_true(s.check(samples))
  let n : Int = @luna-generic.lift_to(I8::wrap(127) + One::one())
  inspect(n, content="-128")
}

最后一行展示了回绕：在 I8 中 127 + 1 是 -128，而 lift_to 转换的是回绕后的值。

与兄弟包组合

更高层的 Luna Flow 包用这些 trait 表述其需求，因此实现了它们的类型可以传给这些包的泛型代码。保持实例诚实：只有当你的类型满足某个 trait 的定律时才实现它，这些定律列在 core API 中。

常见陷阱

  • 只要求算法真正需要的最小 trait 集合。
  • 只有确实需要倒数或除法时再要求 Field。
  • Field 承诺乘法可交换。不要为乘积依赖因子顺序的类型实现它；在必须接受这类类型的代码中，要求 Ring + Inverse + Div。
  • 即使共享同一抽象表面，也要把 Float 和 Double 当作近似后端来看。
  • 对 Float 与 Double，Inverse::inv 在 0.0 上中止，而 / 返回无穷大。求逆前先检查是否为零。
  • 无符号整数不是 Ring：会取负的泛型代码不能接受 UInt。
  • lift_to 转换的是回绕后的值。调用之前发生的溢出不会被撤销。
  • 优先使用 lift_to、FromNat 与 FromInteger，而不是已废弃的 NatHomomorphism 与 IntegralHomomorphism。

下一步

  • core API 列出了每个 trait、它的定律以及随包实例。
  • core 设计 推导了为什么转换经由 ℤ 分解，以及为什么 Field 必须可交换。
  • hom 教程 用证书检查转换和其他映射。