immut の設計

設計目標

immut ファサードは、luna-poly の値指向の半分を 1 つのインポートで使えるようにします。多項式を値として使いたいユーザーが、密・項・疎・コンテキストの多項式が 4 つのパッケージに分かれていることや、単項式とトレイトが core と luna-generic に由来することを知る必要はありません。

数学的背景

各イミュータブル型は多項式環の元をモデル化します。DensePolynomial では $R[x]$ 、TermPolynomial と SparsePolynomial では $R[x_0, x_1, \dots]$ 、ContextPolynomial では $R[\Gamma]$ です(core の設計を参照)。環の元は値です。 $f + g$ は新しい元であり、 $f$ は変化しません。イミュータブル層はこれをそのまま反映しています。既存の多項式を変更する演算はないため、多項式は整数とまったく同じように、共有したり、複数の場所に格納したり、どんな計算の後でも再利用したりできます。

設計上の判断

実装パッケージを覆うファサード

問題. 実装を immut/dense、immut/term、immut/sparse、immut/context に分割すると、各表現が小さく保たれ、各パッケージは使うものだけに依存できます(dense は多変数のコードに依存しません)。しかし、4 つのインポートに core と luna-generic を加えたものは、入口としては使いにくいものです。

選択. immut は pub using による再エクスポートだけで構成されます。別名は同じ型そのものでありラッパーではないため、ファサードをインポートするコードとサブパッケージをインポートするコードの間で、値を変換なしにやり取りできます。luna-generic のトレイトも再エクスポートしているので、A : @immut.Ring のような境界を同じインポートで書けます。

あらゆる場所での値セマンティクス

4 つの表現はいずれも、内容を永続ベクトルに保持するか、構築後に変更されない非公開フィールドの奥に保持し、すべてのコンストラクタは呼び出し側が所有する配列をコピーします。したがって:

公開関数がレシーバや引数を変更することはない。
同じ多項式を 2 回観測すると、どちらも同じ答えを返す。
多項式をデータ構造間で共有することは常に安全である。

その代償として、逐次的な更新 (SparsePolynomial::add_term) は結果を再構築します。逐次的なアルゴリズムは mutable 層に属します。

表現間の明示的な変換

表現は暗黙には変換されません。TermPolynomial と SparsePolynomial は to_terms() と from_terms を通じて変換され、その際に正規化が再適用されます。ContextPolynomial はどちらかをコンテキストとともに束縛し、to_term_polynomial または to_sparse_polynomial で元に戻します。変換を明示的にしておくことで、実装パッケージは互いに独立し、あらゆるコストがコード上に見えるようになります。

`mutable` との対称性

このファサードは mutable ファサードと同じトレイト集合と型名をエクスポートし、各イミュータブル型には、同じコンストラクタ、問い合わせ、演算子、チェック付き版を持つミュータブルな対応型があります。共有のトレイトや演算レコードに対して書いたコードは、どちらでも動作します。相違点は mutable の設計に列挙しています。

正しさ / 不変条件

エクスポートされる型はすべて、実装パッケージまたは core における定義と同一である。
すべてのイミュータブルな多項式は、どの公開演算の後でも正規形にある(末尾を切り詰めた密ベクトル、整列・マージ済みの項配列、ゼロを含まない疎なマップ)。したがって、Eq が提供されている場所ではどこでも == は多項式の等価性である。
既存の値を変更する公開演算はない。

採用しなかった代替案

単一のルートパッケージ. 0.1 の構成ではすべてが 1 つのパッケージにありました。分割によって依存関係が明示的になり、ファサードによって単一のインポートが保たれます。
ファサード内のラッパー型. ラッパーではパッケージ境界ごとに変換が必要になりますが、別名なら不要です。
暗黙の表現変換. ユーザーの知らないところで格納形式を選ぶとコストが隠れてしまいます。格納形式を選ぶのは ContextPolynomial だけであり、それも混在したオペランドの場合に限られます。

境界

ファサードは独自の関数、型、振る舞いを何も追加しない。
コンストラクタ Scalar と Polynomial は、再エクスポートされた ContextSubstitutionValue 型を通じて利用でき、ファサードの独立した値としては提供されない。
永続性はコピーとカプセル化によって実現されており、多項式と更新結果の間で構造共有は行われない。
その場での更新は対象外である。mutable を参照。