Luna Flow
日本語

core チュートリアル

このチュートリアルでは、luna-poly の共有レイヤー、すなわち指数ベクトル、名前付き変数、形状、能力トレイト、演算レコードの使い方を示します。最後には、ライブラリのすべての多項式表現で動く関数を 1 つ書き、そこに独自の表現を組み込めるようになります。

クイックスタート

モジュールを追加します。

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",
}

最小限の有用なプログラムは、2 つの単項式を構築して掛け合わせます。

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] は x0x1x_0 x_1、[2] は x02x_0^2 です。その積 x03x1x_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",
  )
}

x12x_1^2 と x0x2x_0 x_2 はどちらも次数 22 です。最後に異なるのは変数 22 で、そこでは x0x2x_0 x_2 の指数の方が大きいので x12<x0x2x_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 が必要です。名前は添字を忘れ、コンテキストがそれを復元します。

すべての表現に対して 1 つの関数を書く

型パラメータを能力バンドルで制約し、トレイトメソッドを修飾形式で呼び出します。

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 は、cc を定数項として p(c)2p(c)^2 を任意の一変数表現に対して計算します。(1+1)2=4(1 + 1)^2 = 4、(2+22)2=36(2 + 2^2)^2 = 36 です。

組み合わせる前にチェックする

形状によって、2 つの値が同じ多項式環に属するかどうかがわかります。

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")
}

さらに進む

独自の表現を組み込む

能力トレイトはオープンなので、独自の型も汎用コードに参加できます。観測とバンドルを実装します。

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 に記載された順序で関数を渡します。

中断せずに失敗を扱う

中断 (abort) するすべてのアクセサには、代わりに 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 と書き (少なくとも配列の最初の要素)、指数の和は 2322^{32} を法としてラップアラウンドすることに注意してください。
  • 表示される単項式には区切りがありません。 x * x_1 は xx_1 と表示されます。曖昧さのない形式が必要な場合は to_array() を使ってください。
  • 複数の制約を持つ型パラメータ。 fn[P : A + B] の内部や、メソッドがスーパートレイトに由来する場合は、p.method() ではなく Trait::method(p) と書いてください。
  • コンテキストは構造的です。 同じ名前を同じ順序で構築した 2 つのコンテキストは等しく、それらの多項式は組み合わせられます。
  • 形状はサイズを無視します。 2 つの多変数の形状はアリティにかかわらず互換です。互換性が排除するのは、異なる族やコンテキストを混ぜることだけです。

次のステップ