core API

Luna-Flow/luna-poly/core 是本库的公共词汇层。它拥有指数向量单项式类型、命名变量层、形状元数据、每个具体多项式都会实现的能力 trait，以及用于字典传递式泛型代码的操作记录。它本身不包含任何多项式存储。

两个门面包 immut 和 mutable 都重新导出了本页的所有类型和 trait，因此大多数程序从不直接导入 core。若确需直接导入，请为它取一个不与 Luna-Flow/type_theory/core 冲突的别名：

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

本页示例均使用该别名。各项背后的数学原理见 core 设计。

单项式

`ExponentVector`

ExponentVector 是单项式 $x^\alpha = x_0^{\alpha_0} x_1^{\alpha_1} \cdots$ 的指数向量 $\alpha = (\alpha_0, \alpha_1, \dots)$ 。末尾的零指数从不存储，因此 [1, 0] 与 [1] 是同一个值；总次数 $|\alpha| = \sum_i \alpha_i$ 会被缓存。

type ExponentVector derive(@debug.Debug)
pub impl @luna-generic.One for ExponentVector
pub impl Compare for ExponentVector
pub impl Eq for ExponentVector
pub impl Hash for ExponentVector
pub impl Mul for ExponentVector
pub impl Show for ExponentVector

该值是不可变的。每次“更新”都返回一个新向量。

`ExponentVector::from_array`

由数组构造规范的指数向量，去除末尾的零。数组会被复制。

pub fn ExponentVector::from_array(Array[UInt]) -> Self

`ExponentVector::one`

返回空指数向量，即单项式 $1 = x^{0}$ 。它也是 ExponentVector 的 One::one()。

pub fn ExponentVector::one() -> Self

`ExponentVector::length`

返回存储长度：最后一个非零指数的下标加一；对单位元返回 0。

pub fn ExponentVector::length(Self) -> Int

`ExponentVector::degree`

以 $O(1)$ 返回总次数 $|\alpha| = \sum_i \alpha_i$ 。

pub fn ExponentVector::degree(Self) -> UInt

次数是 UInt 求和，若指数足够大，会按模 $2^{32}$ 回绕。

`ExponentVector::is_one`

当且仅当为单位向量（所有指数均为零）时返回 true。

pub fn ExponentVector::is_one(Self) -> Bool

`ExponentVector::get`

返回变量 index 的指数；v[index] 也由它实现。下标大于或等于 length() 时读作 0。负下标会中止（abort）。

#alias("_[_]")
pub fn ExponentVector::get(Self, Int) -> UInt

`ExponentVector::get_checked`

与 get 一样返回 Some(exponent)，负下标时返回 None。

pub fn ExponentVector::get_checked(Self, Int) -> UInt?

`ExponentVector::with_exponent`

返回一个新向量，其中 index 处的指数被替换为 value，并重新规范化（把最后一个非零指数设为 0 会使向量变短）。负下标会中止（abort）。

pub fn ExponentVector::with_exponent(Self, Int, UInt) -> Self

`ExponentVector::with_exponent_checked`

负下标时返回 None，否则返回 with_exponent 结果的 Some。

pub fn ExponentVector::with_exponent_checked(Self, Int, UInt) -> Self?

`ExponentVector::to_array`

返回规范指数的新副本，不含末尾的零。

pub fn ExponentVector::to_array(Self) -> Array[UInt]

`ExponentVector::mul`

通过逐分量相加指数来相乘两个单项式： $x^\alpha x^\beta = x^{\alpha+\beta}$ 。它也是 * 运算符。

pub fn ExponentVector::mul(Self, Self) -> Self

指数加法是 UInt 加法，按模 $2^{32}$ 回绕。

`ExponentVector::compare`

按本库的单项式序比较两个单项式：先比较总次数，再比较两者不同处下标最大的变量的指数，指数较大者为较大的单项式。这就是 $x_0 < x_1 < x_2 < \cdots$ 下的分次字典序。<、<=、> 和 >= 也由它驱动。

pub fn ExponentVector::compare(Self, Self) -> Int

该序是全序，以 $1$ 为最小元，并且与乘法相容： $\alpha < \beta$ 蕴含 $\alpha + \gamma < \beta + \gamma$ 。core 设计推导了这些性质。

`ExponentVector::equal`, `ExponentVector::hash`

equal 是规范向量的结构相等（即 ==）；hash 与之一致。

pub fn ExponentVector::equal(Self, Self) -> Bool
pub fn ExponentVector::hash(Self) -> Int

`ExponentVector::to_string`

用 x 表示变量 0、x_i 表示变量 i 来渲染单项式，单位元渲染为 1。各因子直接相邻书写，不加分隔符。

pub fn ExponentVector::to_string(Self) -> String

test "exponent vectors" {
  let a = @poly_core.ExponentVector::from_array([2U, 0, 1, 0])
  debug_inspect(a.to_array(), content="[2, 0, 1]")
  inspect(a.degree(), content="3")
  inspect(a[1], content="0")
  inspect(a[7], content="0")
  inspect(a, content="x^2x_2")
  let b = @poly_core.ExponentVector::from_array([0U, 1])
  inspect(a * b, content="x^2x_1x_2")
  assert_true(a.get_checked(-1) is None)
  assert_true(a.with_exponent(2, 0) == @poly_core.ExponentVector::from_array([2U]))
  // Same degree: the higher variable decides, so x_1 > x_0.
  let x0 = @poly_core.ExponentVector::from_array([1U])
  let x1 = @poly_core.ExponentVector::from_array([0U, 1])
  assert_true(x0 < x1)
  assert_true(x1 < x0 * x0)
}

命名变量

`Variable`

Variable 是一个命名变量，连同它在创建它的 VariableContext 中的位置。当名字和下标都相同时，两个变量相等。

type Variable derive(Compare, Eq, @debug.Debug)
pub impl Show for Variable

变量从上下文中获得；没有公开的构造函数。

`Variable::name`, `Variable::index`

name 返回变量名；index 返回它在上下文中的位置，这也是它的指数在 ExponentVector 中的位置。

pub fn Variable::name(Self) -> String
pub fn Variable::index(Self) -> Int

`Variable::to_type_theory_name`

以 Luna-Flow/type_theory 的 Name 形式返回变量名。下标不包含在结果中；可以通过 VariableContext::variable_by_type_theory_name 在上下文中查找该名字来恢复下标。

pub fn Variable::to_type_theory_name(Self) -> @Luna-Flow/type_theory/core.Name

`Variable::compare`, `Variable::equal`, `Variable::to_string`

compare 先按名字、再按下标对变量排序（派生实现）；equal 比较名字和下标；to_string 返回名字。

pub fn Variable::compare(Self, Self) -> Int
pub fn Variable::equal(Self, Self) -> Bool
pub fn Variable::to_string(Self) -> String

`VariableContext`

VariableContext 是一个有序、持久的互不相同变量名表。位置 $i$ 处的变量下标为 $i$ ，且名字唯一，因此在同一个上下文中名字与下标相互确定。

type VariableContext derive(Eq, @debug.Debug)
pub impl Show for VariableContext

上下文按结构比较：两个以相同顺序包含相同名字的上下文相等，无论它们在何处构建。

`VariableContext::new`

返回空上下文。

pub fn VariableContext::new() -> Self

`VariableContext::from_names`

构造一个变量依次为 names 的上下文。遇到重复名字时中止（abort）。

pub fn VariableContext::from_names(Array[String]) -> Self

`VariableContext::from_names_checked`

与 from_names 相同，但当某个名字出现两次时返回 None。

pub fn VariableContext::from_names_checked(Array[String]) -> Self?

`VariableContext::extend_checked`

返回追加了 name 的新上下文以及新变量；若该名字已存在，则返回 None。接收者保持不变。

pub fn VariableContext::extend_checked(Self, String) -> (Self, Variable)?

`VariableContext::extend_with`

与 extend_checked 相同，但遇到重复名字时中止（abort）。

#alias(extend, deprecated)
pub fn VariableContext::extend_with(Self, String) -> (Self, Variable)

旧名称 extend 作为已弃用的别名保留；参见已弃用。

`VariableContext::size`, `VariableContext::variables`, `VariableContext::get`

size 返回变量个数；variables 以下标顺序返回所有变量组成的新数组；get 返回某个下标处的变量，下标超出 0 ..< size() 时返回 None。

pub fn VariableContext::size(Self) -> Int
pub fn VariableContext::variables(Self) -> Array[Variable]
pub fn VariableContext::get(Self, Int) -> Variable?

`VariableContext::variable`, `VariableContext::require_variable`

variable 按名字查找变量，不存在时返回 None；require_variable 则会中止（abort）。查找是线性扫描。

pub fn VariableContext::variable(Self, String) -> Variable?
pub fn VariableContext::require_variable(Self, String) -> Variable

`VariableContext::contains`

当上下文中位于 variable.index() 的变量等于 variable 时返回 true。因此，来自结构相等的上下文的变量同样被视为包含在内。

pub fn VariableContext::contains(Self, Variable) -> Bool

`VariableContext::variable_by_type_theory_name`

把 type_theory 的 Name 解析为同名文本的变量，否则返回 None。

pub fn VariableContext::variable_by_type_theory_name(Self, @Luna-Flow/type_theory/core.Name) -> Variable?

对上下文 c 的每个变量 v，都有 c.variable_by_type_theory_name(v.to_type_theory_name()) == Some(v)。

`VariableContext::require_type_theory_name`

与 variable_by_type_theory_name 相同，但名字未知时中止（abort）。

pub fn VariableContext::require_type_theory_name(Self, @Luna-Flow/type_theory/core.Name) -> Variable

`VariableContext::equal`

结构相等，也可通过 == 使用。

pub fn VariableContext::equal(Self, Self) -> Bool

test "variable contexts" {
  let ctx = @poly_core.VariableContext::from_names(["x", "y"])
  inspect(ctx, content="VariableContext(x, y)")
  let (ctx2, z) = ctx.extend_with("z")
  inspect(z.index(), content="2")
  inspect(ctx.size(), content="2")
  assert_true(ctx.extend_checked("x") is None)
  assert_true(@poly_core.VariableContext::from_names_checked(["a", "a"]) is None)
  let y = ctx2.require_variable("y")
  let name = y.to_type_theory_name()
  inspect(name.text(), content="y")
  assert_true(ctx2.variable_by_type_theory_name(name) == Some(y))
  assert_true(ctx2.variable_by_type_theory_name(@tt_core.Name::new("w")) is None)
  assert_true(ctx.contains(y))
  assert_false(ctx.contains(z))
}

形状

`PolynomialShape`

PolynomialShape 描述多项式的维度信息，不含其系数。可以用下面的蛇形命名函数或构造器来构造它。

pub enum PolynomialShape {
  Univariate(length~ : Int)
  Multivariate(arity~ : Int, term_count~ : Int)
  Contextual(context~ : VariableContext, arity~ : Int, term_count~ : Int)
} derive(Eq, @debug.Debug)
pub fn PolynomialShape::equal(Self, Self) -> Bool

length 是稠密多项式存储的系数个数，arity 是使用中的变量个数（最长指数向量的长度），term_count 是非零项的个数。

`PolynomialShape::univariate`, `PolynomialShape::multivariate`, `PolynomialShape::contextual`

构造这三种形状。

pub fn PolynomialShape::univariate(Int) -> Self
pub fn PolynomialShape::multivariate(Int, Int) -> Self
pub fn PolynomialShape::contextual(VariableContext, Int, Int) -> Self

`PolynomialShape::arity`

返回元数；单变量形状的元数为 1。

pub fn PolynomialShape::arity(Self) -> Int

`PolynomialShape::term_count`

返回项数；对单变量形状返回 None，因为它不记录项数。

pub fn PolynomialShape::term_count(Self) -> Int?

`PolynomialShape::is_compatible_with`

当两种形状的值可以组合时返回 true：两个单变量形状、两个多变量形状，或基于相等上下文的两个上下文形状。元数和项数不参与判断。

pub fn PolynomialShape::is_compatible_with(Self, Self) -> Bool

`PolynomialShape::compatible_checked`

形状相容时返回 Some(())，否则返回 None，便于在 Option 管道中使用。

pub fn PolynomialShape::compatible_checked(Self, Self) -> Unit?

test "shapes" {
  let ctx = @poly_core.VariableContext::from_names(["x"])
  let a = @poly_core.PolynomialShape::multivariate(2, 5)
  let b = @poly_core.PolynomialShape::multivariate(3, 1)
  let c = @poly_core.PolynomialShape::contextual(ctx, 1, 1)
  assert_true(a.is_compatible_with(b))
  assert_false(a.is_compatible_with(c))
  inspect(a.arity(), content="2")
  assert_true(@poly_core.PolynomialShape::univariate(4).term_count() is None)
  assert_true(c.compatible_checked(c) is Some(_))
}

能力 trait

能力 trait 是小型的开放 trait（pub(open)），每个只陈述一种可观察的性质。组合 trait 把它们组合成泛型代码通常需要的约束。本库的所有具体多项式类型都实现了下表列出的组合 trait：

Trait	必需方法 / 父 trait	实现者
`UnivariatePolynomial`	`HasShape + HasLength + HasDegree + IsZero`	`DensePolynomial`
`MultivariatePolynomial`	`HasShape + HasTermCount + HasArity + HasTotalDegree + IsZero`	`TermPolynomial`, `SparsePolynomial`
`ContextualPolynomial`	`HasShape + HasContext + HasTermCount + HasArity + IsZero`	`ContextPolynomial`
`MutablePolynomial`	`Clearable + Copyable`	所有 `mutable` 容器

`HasLength`

稠密多项式存储的系数个数；零多项式为 0。

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

`HasDegree`

单变量多项式的次数，零多项式为 None。

pub(open) trait HasDegree {
  fn degree(Self) -> Int?
}

`IsZero`

该值是否为零多项式。在规范形式下即“没有存储任何项”。

pub(open) trait IsZero {
  fn is_zero(Self) -> Bool
}

`HasTermCount`

非零项的个数。

pub(open) trait HasTermCount {
  fn term_count(Self) -> Int
}

`HasArity`

使用中的变量个数：所有项的 ExponentVector::length 的最大值，常数为 0。

pub(open) trait HasArity {
  fn arity(Self) -> Int
}

`HasTotalDegree`

所有项的最大总次数，零多项式为 None。

pub(open) trait HasTotalDegree {
  fn total_degree(Self) -> UInt?
}

`HasContext`

多项式所绑定的变量上下文。

pub(open) trait HasContext {
  fn context(Self) -> VariableContext
}

`HasShape`

值的 PolynomialShape。

pub(open) trait HasShape {
  fn shape(Self) -> PolynomialShape
}

`Clearable`

将可变容器原地重置为零。

pub(open) trait Clearable {
  fn clear(Self) -> Unit
}

`Copyable`

返回可变容器的独立副本：此后修改其中任一个值都不会影响另一个。

pub(open) trait Copyable {
  fn copy(Self) -> Self
}

`UnivariatePolynomial`

稠密单变量多项式的组合 trait。

pub(open) trait UnivariatePolynomial : HasShape + HasLength + HasDegree + IsZero {
}

`MultivariatePolynomial`

按下标寻址的多变量多项式的组合 trait。

pub(open) trait MultivariatePolynomial : HasShape + HasTermCount + HasArity + HasTotalDegree + IsZero {
}

`ContextualPolynomial`

绑定到 VariableContext 的多项式的组合 trait。

pub(open) trait ContextualPolynomial : HasShape + HasContext + HasTermCount + HasArity + IsZero {
}

`MutablePolynomial`

可变容器的组合 trait。

pub(open) trait MutablePolynomial : Clearable + Copyable {
}

fn[P : @poly_core.MultivariatePolynomial] describe(p : P) -> String {
  let degree = match @poly_core.HasTotalDegree::total_degree(p) {
    Some(d) => d.to_string()
    None => "-"
  }
  "terms=\{@poly_core.HasTermCount::term_count(p)} arity=\{@poly_core.HasArity::arity(p)} degree=\{degree}"
}

test "capability traits" {
  let term = @immut.TermPolynomial::from_array([([2U, 1], 3), ([], 1)])
  let sparse = @immut.SparsePolynomial::from_array([([2U, 1], 3), ([], 1)])
  inspect(describe(term), content="terms=2 arity=2 degree=3")
  inspect(describe(sparse), content="terms=2 arity=2 degree=3")
}

在带有多 trait 约束的函数中，请像上面那样以限定形式 Trait::method(value) 调用 trait 方法。

操作记录

MoonBit 的 trait 只有 Self 这一个类型参数，因此 trait 无法表达“系数类型为 A 的多项式类型 P”。操作记录弥补了这一缺口：每个具体类型通过其 ops() 方法返回一个函数记录，泛型代码把该记录作为普通参数接收。各访问器方法只调用所存储的函数，不添加任何自身行为。

`UnivariateOps`

系数为 A 的单变量多项式类型 P 的操作。

type UnivariateOps[P, A]
pub fn[P, A] UnivariateOps::new(() -> P, () -> P, (Array[A]) -> P, (P) -> Array[A], (P, Int) -> A, (P, Int) -> A?, (P, A) -> A, (P, P) -> P, (P, P) -> P, (P, Int, A) -> P, (P, Int, A) -> P?, (P, UInt) -> P) -> Self[P, A]

new 依次接收：zero、one、from_coefficients、to_coefficients、coefficient、coefficient_checked、eval、add、mul、scale、scale_checked 和 pow，含义与 DensePolynomial 的同名方法相同。可用它包装你自己的单变量类型。

`UnivariateOps` 访问器

每个访问器调用对应的存储函数。

pub fn[P, A] UnivariateOps::zero(Self[P, A]) -> P
pub fn[P, A] UnivariateOps::one(Self[P, A]) -> P
pub fn[P, A] UnivariateOps::from_coefficients(Self[P, A], Array[A]) -> P
pub fn[P, A] UnivariateOps::to_coefficients(Self[P, A], P) -> Array[A]
pub fn[P, A] UnivariateOps::coefficient(Self[P, A], P, Int) -> A
pub fn[P, A] UnivariateOps::coefficient_checked(Self[P, A], P, Int) -> A?
pub fn[P, A] UnivariateOps::eval(Self[P, A], P, A) -> A
pub fn[P, A] UnivariateOps::add(Self[P, A], P, P) -> P
pub fn[P, A] UnivariateOps::mul(Self[P, A], P, P) -> P
pub fn[P, A] UnivariateOps::scale(Self[P, A], P, Int, A) -> P
pub fn[P, A] UnivariateOps::scale_checked(Self[P, A], P, Int, A) -> P?
pub fn[P, A] UnivariateOps::pow(Self[P, A], P, UInt) -> P

`MultivariateOps`

系数为 A 的按下标寻址多变量多项式类型 P 的操作。

type MultivariateOps[P, A]
pub fn[P, A] MultivariateOps::new(() -> P, () -> P, (Array[(ExponentVector, A)]) -> P, (P) -> Array[(ExponentVector, A)], (P, Array[A]) -> A, (P, Array[A]) -> A?, (P, P) -> P, (P, P) -> P, (P, ExponentVector, A) -> P, (P, UInt) -> P) -> Self[P, A]

new 依次接收：zero、one、from_terms、to_terms、eval_indexed、eval_indexed_checked、add、mul、scale 和 pow。eval_indexed 即 TermPolynomial 与 SparsePolynomial 的 eval 方法。

`MultivariateOps` 访问器

pub fn[P, A] MultivariateOps::zero(Self[P, A]) -> P
pub fn[P, A] MultivariateOps::one(Self[P, A]) -> P
pub fn[P, A] MultivariateOps::from_terms(Self[P, A], Array[(ExponentVector, A)]) -> P
pub fn[P, A] MultivariateOps::to_terms(Self[P, A], P) -> Array[(ExponentVector, A)]
pub fn[P, A] MultivariateOps::eval_indexed(Self[P, A], P, Array[A]) -> A
pub fn[P, A] MultivariateOps::eval_indexed_checked(Self[P, A], P, Array[A]) -> A?
pub fn[P, A] MultivariateOps::add(Self[P, A], P, P) -> P
pub fn[P, A] MultivariateOps::mul(Self[P, A], P, P) -> P
pub fn[P, A] MultivariateOps::scale(Self[P, A], P, ExponentVector, A) -> P
pub fn[P, A] MultivariateOps::pow(Self[P, A], P, UInt) -> P

`ContextOps`

系数为 A 的上下文绑定多项式类型 P 的操作。

type ContextOps[P, A]
pub fn[P, A] ContextOps::new((VariableContext, Array[(ExponentVector, A)]) -> P, (P) -> Array[(ExponentVector, A)], (P, Array[(Variable, A)]) -> A?, (P, P) -> P?, (P, P) -> P?) -> Self[P, A]

new 依次接收：from_terms、to_terms、eval_named_checked、add_checked 和 mul_checked，含义与 ContextPolynomial 的对应方法相同。

`ContextOps` 访问器

pub fn[P, A] ContextOps::from_terms(Self[P, A], VariableContext, Array[(ExponentVector, A)]) -> P
pub fn[P, A] ContextOps::to_terms(Self[P, A], P) -> Array[(ExponentVector, A)]
pub fn[P, A] ContextOps::eval_named_checked(Self[P, A], P, Array[(Variable, A)]) -> A?
pub fn[P, A] ContextOps::add_checked(Self[P, A], P, P) -> P?
pub fn[P, A] ContextOps::mul_checked(Self[P, A], P, P) -> P?

fn[P, A] sum_of_squares(ops : @poly_core.MultivariateOps[P, A], polys : Array[P]) -> P {
  let mut acc = ops.zero()
  for p in polys {
    acc = ops.add(acc, ops.pow(p, 2))
  }
  acc
}

test "operation records" {
  let x = @immut.SparsePolynomial::from_array([([1U], 1)])
  let y = @immut.SparsePolynomial::from_array([([0U, 1], 1)])
  let ops = @immut.SparsePolynomial::ops()
  let s = sum_of_squares(ops, [x, y])
  inspect(s, content="1 * x^2 + 1 * x_1^2")
  inspect(ops.eval_indexed(s, [3, 4]), content="25")
}

已弃用

已弃用	替代方案
`VariableContext::extend`	`VariableContext::extend_with`（行为相同；`extend` 现在是保留字）
`ExponentVector`、`Variable`、`VariableContext`、`PolynomialShape` 上的 `not_equal`、`op_lt`、`op_le`、`op_gt`、`op_ge` 方法	运算符 `!=`、`<`、`<=`、`>`、`>=`
`output` 方法（来自 `Show`）	`to_string` 或字符串插值
`to_repr` 方法（来自 `Debug`）	`Repr(x)` 或 `debug_inspect`
`ExponentVector::hash_combine`	通过 trait 调用 `Hash::hash_combine`

最后四行中的方法形式已从接口文件中隐藏，仅为源码兼容而保留。

core API

单项式

ExponentVector

ExponentVector::from_array

ExponentVector::one

ExponentVector::length

ExponentVector::degree

ExponentVector::is_one

ExponentVector::get

ExponentVector::get_checked

ExponentVector::with_exponent

ExponentVector::with_exponent_checked

ExponentVector::to_array

ExponentVector::mul

ExponentVector::compare

ExponentVector::equal, ExponentVector::hash

ExponentVector::to_string

命名变量

Variable

Variable::name, Variable::index

Variable::to_type_theory_name

Variable::compare, Variable::equal, Variable::to_string

VariableContext

VariableContext::new

VariableContext::from_names

VariableContext::from_names_checked

VariableContext::extend_checked

VariableContext::extend_with

VariableContext::size, VariableContext::variables, VariableContext::get

VariableContext::variable, VariableContext::require_variable

VariableContext::contains

VariableContext::variable_by_type_theory_name

VariableContext::require_type_theory_name

VariableContext::equal

形状

PolynomialShape

PolynomialShape::univariate, PolynomialShape::multivariate, PolynomialShape::contextual

PolynomialShape::arity

PolynomialShape::term_count

PolynomialShape::is_compatible_with

PolynomialShape::compatible_checked