core 教程

本教程介绍如何使用 luna-poly 的共享层：指数向量、具名变量、形状、能力 trait 和操作记录。读完后，你将能够编写一个适用于库中所有多项式表示的函数，并把你自己的表示接入其中。

快速开始

添加模块：

moon add Luna-Flow/luna-poly@0.2.0

用别名导入该包，以免与 Luna-Flow/type_theory/core 冲突，同时导入不可变门面包以使用具体多项式：

import {
  "Luna-Flow/luna-poly/core" @poly_core,
  "Luna-Flow/luna-poly/immut",
}

最小的实用程序构造两个单项式并将它们相乘：

test "quick start" {
  let xy = @poly_core.ExponentVector::from_array([1U, 1])
  let x2 = @poly_core.ExponentVector::from_array([2U])
  let product = xy * x2
  inspect(product, content="x^3x_1")
  inspect(product.degree(), content="4")
}

[1, 1] 是 $x_0 x_1$，[2] 是 $x_0^2$；它们的乘积 $x_0^3 x_1$ 打印为 x^3x_1。本教程中的每个类型也都由 immut 和 mutable 门面包重新导出，因此 @immut.ExponentVector 与 @poly_core.ExponentVector 是同一类型。

日常任务

读取和更新指数向量

指数向量从不存储末尾的零，读取超出其末尾的位置得到 0：

test "exponent vector basics" {
  let v = @poly_core.ExponentVector::from_array([2U, 0, 1, 0, 0])
  debug_inspect(v.to_array(), content="[2, 0, 1]")
  inspect(v.length(), content="3")
  inspect(v[2], content="1")
  inspect(v[10], content="0")
  let w = v.with_exponent(2, 0)
  debug_inspect(w.to_array(), content="[2]")
  debug_inspect(v.to_array(), content="[2, 0, 1]")
  assert_true(@poly_core.ExponentVector::from_array([1U, 0]) == @poly_core.ExponentVector::from_array([1U]))
}

with_exponent 返回新向量；v 保持不变。

对单项式排序

单项式先按总次数排序，再按它们不同的下标最大的变量排序：

test "monomial order" {
  let monomials = [
    @poly_core.ExponentVector::from_array([1U, 0, 1]),
    @poly_core.ExponentVector::from_array([0U, 2]),
    @poly_core.ExponentVector::one(),
    @poly_core.ExponentVector::from_array([3U]),
    @poly_core.ExponentVector::from_array([1U]),
  ]
  monomials.sort()
  inspect(
    monomials.map(m => m.to_string()).join(" < "),
    content="1 < x < x_1^2 < xx_2 < x^3",
  )
}

$x_1^2$ 和 $x_0 x_2$ 的次数都是 $2$；它们最后一个不同之处在变量 $2$，$x_0 x_2$ 在那里的指数更大，因此 $x_1^2 < x_0 x_2$。core 设计解释了为什么这个序是单项式序。

为变量命名

VariableContext 为每个名字分配一个稳定的下标：

test "contexts" {
  let ctx = @poly_core.VariableContext::from_names(["x", "y"])
  let (ctx, t) = ctx.extend_with("t")
  inspect(ctx, content="VariableContext(x, y, t)")
  inspect(t.index(), content="2")
  match ctx.variable("y") {
    Some(y) => inspect(y.index(), content="1")
    None => fail("y should exist")
  }
  assert_true(ctx.variable("z") is None)
  assert_true(ctx.extend_checked("x") is None)
}

上下文是值：extend_with 返回新的上下文及其添加的变量，并且从不对已有变量重新编号。

与 type_theory 交互

当名字来自 Luna-Flow/type_theory 时，通过上下文进行双向转换：

test "type theory names" {
  let ctx = @poly_core.VariableContext::from_names(["x", "y"])
  let y = ctx.require_variable("y")
  let name : @tt_core.Name = y.to_type_theory_name()
  inspect(name.text(), content="y")
  assert_true(ctx.variable_by_type_theory_name(name) == Some(y))
  assert_true(ctx.variable_by_type_theory_name(@tt_core.Name::new("q")) is None)
}

这需要在导入中加入 "Luna-Flow/type_theory/core" @tt_core。名字会丢弃下标；上下文会恢复它。

为所有表示编写同一个函数

用能力组合 trait 约束类型参数，并以限定形式调用 trait 方法：

fn[P : @poly_core.MultivariatePolynomial] summary(p : P) -> String {
  if @poly_core.IsZero::is_zero(p) {
    return "zero"
  }
  "\{@poly_core.HasTermCount::term_count(p)} terms in \{@poly_core.HasArity::arity(p)} variables"
}

test "generic over representations" {
  let terms = [([2U, 1], 3), ([0U, 0, 1], 1), ([], -2)]
  let a = @immut.TermPolynomial::from_array(terms)
  let b = @immut.SparsePolynomial::from_array(terms)
  let c = @mutable.SparsePolynomial::from_array(terms)
  inspect(summary(a), content="3 terms in 3 variables")
  inspect(summary(b), content="3 terms in 3 variables")
  inspect(summary(c), content="3 terms in 3 variables")
  inspect(summary(@immut.TermPolynomial::from_array([([1U], 0)])), content="zero")
}

当算法还需要构造或算术时，传入该类型的操作记录：

fn[P, A] square_all(ops : @poly_core.UnivariateOps[P, A], ps : Array[P]) -> Array[A] {
  ps.map(p => ops.eval(ops.pow(p, 2), ops.coefficient(p, 0)))
}

test "operation records" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let q = @mutable.DensePolynomial::from_coefficients([2, 0, 1])
  debug_inspect(square_all(@immut.DensePolynomial::ops(), [p]), content="[4]")
  debug_inspect(square_all(@mutable.DensePolynomial::ops(), [q]), content="[36]")
}

square_all 对任意一元表示计算 $p(c)^2$，其中 $c$ 是常数项：$(1 + 1)^2 = 4$，$(2 + 2^2)^2 = 36$。

组合之前先检查

形状告诉你两个值是否位于同一个多项式环中：

test "shapes" {
  let ctx = @poly_core.VariableContext::from_names(["x"])
  let other = @poly_core.VariableContext::from_names(["u"])
  let x = ctx.require_variable("x")
  let u = other.require_variable("u")
  let p = @immut.ContextPolynomial::from_named_terms_as_sparse(ctx, [([(x, 1U)], 1)])
  let q = @immut.ContextPolynomial::from_named_terms_as_sparse(other, [([(u, 1U)], 1)])
  let sp = @poly_core.HasShape::shape(p)
  let sq = @poly_core.HasShape::shape(q)
  assert_false(sp.is_compatible_with(sq))
  assert_true(p.add_checked(q) is None)
  inspect(sp.arity(), content="1")
}

深入了解

接入你自己的表示

能力 trait 是开放的，因此你自己的类型也可以加入通用代码。实现各项观察以及组合 trait：

struct Monic {
  degree : Int
}

impl @poly_core.HasShape for Monic with fn shape(self) {
  @poly_core.PolynomialShape::univariate(self.degree + 1)
}

impl @poly_core.HasLength for Monic with fn length(self) {
  self.degree + 1
}

impl @poly_core.HasDegree for Monic with fn degree(self) {
  Some(self.degree)
}

impl @poly_core.IsZero for Monic with fn is_zero(_self) {
  false
}

impl @poly_core.UnivariatePolynomial for Monic

fn[P : @poly_core.UnivariatePolynomial] describe_degree(p : P) -> String {
  match @poly_core.HasDegree::degree(p) {
    Some(d) => "degree \{d}"
    None => "zero polynomial"
  }
}

test "own representation" {
  inspect(describe_degree(Monic::{ degree: 3 }), content="degree 3")
  inspect(describe_degree(@immut.DensePolynomial::from_coefficients([0, 0])), content="zero polynomial")
}

对于操作，用 UnivariateOps::new、MultivariateOps::new 或 ContextOps::new 构建记录，并按 core API 中列出的顺序传入你的函数。

不中止地处理失败

每个会中止的访问器都有一个返回 None 的 *_checked 孪生版本。用 Option 组合子或 match 把它们串联起来：

fn exponent_of(v : @poly_core.ExponentVector, i : Int) -> String {
  match v.get_checked(i) {
    Some(e) => e.to_string()
    None => "invalid index"
  }
}

test "checked" {
  let v = @poly_core.ExponentVector::from_array([4U])
  inspect(exponent_of(v, 0), content="4")
  inspect(exponent_of(v, -1), content="invalid index")
}

Option 不会说明操作为何失败；需要错误信息时请自行检查前置条件。

常见陷阱

• 导入别名。 Luna-Flow/luna-poly/core 和 Luna-Flow/type_theory/core 的默认别名都是 @core。至少为其中一个指定别名，如快速开始中所示。
• 指数类型为 UInt。 将字面量写成 1U（至少数组的第一个元素如此），并记住指数之和按模 $2^{32}$ 回绕。
• 打印的单项式没有分隔符。 x * x_1 打印为 xx_1。需要无歧义的形式时请使用 to_array()。
• 多重约束的类型参数。 在 fn[P : A + B] 内部，或当方法来自父 trait 时，请写 Trait::method(p) 而不是 p.method()。
• 上下文按结构比较。 由相同名字、按相同顺序构造的两个上下文相等，它们的多项式可以组合。
• 形状忽略大小。 两个多元形状无论元数如何都是相容的；相容性只排除混用不同族或不同上下文。

后续步骤

• core API 列出了每一项及其签名。
• core 设计推导了单项式序和名字往返。
• 接下来请阅读 immut 教程了解具体多项式，或阅读上下文教程了解具名变量和代换。
• Luna-Flow/type_theory 记录了 Name 类型。