HN 日本語サマリー

← 一覧へ戻る
プログラミング

Show HN: Rustにおける composable な数値キャストのためのガロア接続

Show HN: Galois connections for composable numeric casts in Rust (github.com)

14 pointsby partialsolve1 コメント

要約

このRustクレートは、ガロア接続を第一級のRust値として提供し、数値型間の合法的なキャストを可能にします。これにより、コンパイル時に決定されるラウンドトリップ動作を持つ変換の連鎖を構築できます。各操作はプロパティテストされた不変量によって保証され、固定幅整数、Qフォーマット、NonZero、およびisoファミリーはSMT証明のためのKaniハーネスを備えています。

全文翻訳

記事一覧

[1] タイトル: Show HN: Galois connections for composable numeric casts in Rust
URL: https://github.com/cmk/connections
本文:
[画像: crates.io] [画像: docs.rs] [画像: docs] [画像: MSRV] [画像: CI]

ドキュメントはこちらでご覧ください: here または docs.rs。

Overview

Galois connectionをファーストクラスのRust値として扱います。これらを使用して、数値型の間で法に則ったキャストを行い、ラウンドトリップの挙動が偶然に任されるのではなく、単純な不等式によって決定される変換の連鎖を合成できます。Connから派生したすべての操作(丸め、飽和、中央値など)は、プロパティテスト済みの不変量を持ちます。生成された固定幅整数、Qフォーマット、NonZero、およびisoファミリーは、完全なビット幅SMT証明のためのKaniハーネスも備えています。浮動小数点数のSMTカバレッジは狭く、Testing → SMT verificationの下で言及されています。

MSRV: Rust 1.88。 MSRVの引き上げはマイナーバージョン変更として扱われます。connections = "0.1"をピン留めすると、パッチアップデートでのサイレントな破壊ではなく、0.2リリースとしてMSRVのアップグレードが表示されます。

このクレートは、HaskellライブラリconnectionsのRustネイティブポートです。

Why this crate

Galois connectionは、部分順序集合(例: f64 → f32、Duration → seconds、f32 → u32 → IpAddrなど)間の静的で法に則った変換に最適な形状です。各リンクはコンパイル時に指定できます。

標準のキャスト演算子 as、From、Into は一度に1つの方向しか提供しません。特に as は、丸め、飽和、および損失のある変換について沈黙します。このクレートが標準ツールでは提供しない具体的な2つの利点があります。

  1. 明確なセマンティクス。

    多くの x: f64 に対して (x as f32) as f64 != x となります。Connを使用すると、このクレートのすべての接続について、以下の不等式のペアの少なくとも一方がプロパティテストされます。

    • 左Galois: ceil(a) ≤ b ⇔ a ≤ upper(b)
    • 右Galois: lower(b) ≤ a ⇔ b ≤ floor(a)

    ConnはCopy、constで構築可能、ヒープフリーであり、クレートは#![forbid(unsafe_code)]です。

  2. 安全に合成可能。

    compose!マクロは、ペアワイズなConnのチェーンをコンパイル時に新しいConn<Src, Dst>に折りたたみます。合成されたConnは、構築により、そのコンポーネント接続と同じプロパティに従います。

Quick start

use connections::conn::ConnR;
use connections::core::u032::U032I032;

// Rustの`as`は下位ビットを保持しますが、このConnは飽和を明示します。
assert_eq!(u32::MAX as i32, -1);
assert_eq!(U032I032.floor(u32::MAX), i32::MAX);

// 逆方向のアームは、右Galois法則によって`floor`とペアになっています。
assert_eq!(U032I032.lower(-1), 0_u32);

EXAMPLES.mdには、さまざまなドメインでの10個の作業例のシーケンスがあります。

What are connections?

順序集合(preorder)AとBの間のGalois connectionは、単調写像のペア f: A → B と g: B → A であり、f(x) ≤ y ⇔ x ≤ g(y) を満たします。fを接続の左または下随伴(lower adjoint)、gを右または上随伴(upper adjoint)と呼びます。

ここに、2つの3要素集合間の単純な接続を示します。

[画像]

(画像提供: 7 Sketches in Compositionality)。

各行は (a, b) のペアです。矢印は f(A → B、下部の凡例)と g(B → A、上部の凡例)のアクションを示します。単一の矢印は単方向マップ(f(1) = 1、g(2) = 2)を示します。↔は両方の随伴が一致するペア(f(3) = 3、g(3) = 3)を示します。隣接する ↰ ↳ のグリフはレンズ f(2) ↔ g(1) を表します。これは、行2と1の間に交差しない2つの曲線であり、随伴性の幾何学的署名です。

How to use connections

Galois connectionは合成可能です: (f₁ ⊣ g₁) ∘ (f₂ ⊣ g₂) は再び随伴性であり、compose!はそれを静的に、全体として法則チェックされた複合体を構築します。デストラクタ(例: upper、lower、ceil、floorなど)を適用した瞬間、Conn代数を離れ、それ以上合成できない具体的な値を生成します。したがって、早期の分解は、完全なチェーンがそうでなければ享受したであろう静的保証を捨ててしまいます。そのため、2つのヒューリスティックに従うと最も効果的です。

Connを通してリフトする。 Connは小さなブラックボックスです。高位のarityヘルパー(例: ceil*、floor*、round*、truncate*など)は引数を取り、Connの別の(通常はより高精度な)ドメインで何かを実行し、結果を元のドメインに返します。ceil2(t, h, b1, b2)はf(h(g(b1), g(b2))) です。b1/b2をgを介してより広いドメインに埋め込み、そこでクロージャhを実行し、f`を介して丸めて戻します。オーバーフローしたり精度を失ったりするドメイン演算にはこれを使用してください。より広いドメインで行い、丸めて戻します。飽和演算を自分で実装しないでください。

サイトで合成する。 ライブラリレベルでConnをエクスポートし、get/set関数の代わりにConnL/ConnR/ConnK APIを使用します。クライアントコードがマルチホップ変換を必要とする場合、呼び出しサイトで静的にcomposeマクロ(compose、compose_l、compose_r、compose_k)を使用して正確なConnを構築します。中間値を手動でスレッドしないでください。クライアントコードがランタイムパラメータを受け取る場合、ヘルパーを通常の名前付き関数として保持するのが最善です。その本体は、依存する法的なConnと目に見えて合成されます。

ランタイムパラメータと変換ポリシーの選択を静的なConn呼び出しサイトに近づけるという規律は、ポリシーと静的キャストの両方が同じ本体で可視的になることを意味します。結果として、コードは目に見えて正しく、テストが容易で、将来のユースケースに拡張可能です。

Library

L & R kind connections

このライブラリの基本型は次のとおりです。

pub struct Conn<A, B, K: Kind = L> {
    f: fn(A) -> B,   // L-kind: ceil; R-kind: floor
    g: fn(B) -> A,   // L-kind: upper, R-kind: lower
    // プラスファントムのkindタグ K ∈ {L, R}
}

Conn<A, B, K>は正確にはGalois connectionです。単調関数 (f, g) のペアであり、その随伴の役割はkindタグに依存します。L-kind Connは f(a) ≤ b ⟺ a ≤ g(b) を満たし、R-kind Connは g(b) ≤ a ⟺ b ≤ f(a) を満たします。

kind K = {L, R} がAPIを決定します。L/ConnLは.ceil()と.upper()を公開し、R/ConnRは.floor()と.lower()を公開します。

  • 方向名 — ceil(上に丸める)とfloor(下に丸める) — は下流の直感に一致します。「天井キャストを取得する」は、呼び出し元が随伴のどちらの側にあるかを知る必要はありません。ただし、L-kind接続で.floor()を呼び出すか、R-kind接続でceilを呼び出すと、コンパイラエラーになります。
  • 位置名 — upper(Lペアの上随伴)とlower(Rペアの下随伴) — は数学に一致します。一般的な T: ConnK バウンドは、トリプルがどちらの方向で丸められるかに関わらず、両方の随伴を持つため、両方を公開します。
  • const vs マーカー - 通常の接続は pub const で、型は Conn<A, B, L> または Conn<A, B, R> です。双方向の ConnK 接続は pub struct として出荷されます。これはゼロサイズのマーカー型で、ConnLとConnRの両方を実装します。constとstructの形状は、一目でどちらのkindを参照しているかがわかります。

API

  • Conn<_, _, L>(およびデフォルトメソッドディスパッチを介した任意の ConnL 実装者)のLサイドメソッド: ceil、upper、および ceil1/2、upper1/2 リフター。
  • Conn<_, _, R>(およびデフォルトメソッドディスパッチを介した任意の ConnR 実装者)のRサイドメソッド: floor、lower、および floor1/2、lower1/2 リフター。
  • 両サイドヘルパー(クレートルートに再エクスポート): interval、round/round1/round2、truncate/truncate1/truncate2、median。すべて T: ConnK(同じ (A, B) に対する ConnL + ConnR のスーパー・トレイト)でバインドされるため、トリプルマーカーでのみ呼び出し可能で、片側Connでは呼び出せません。

kindの規律は構造的です。L-kind Connで.floor(...)を呼び出すとコンパイルエラーになります(メソッドは Conn<_, _, R> にのみ存在します)。同様にRでも.ceil(...)がコンパイルエラーになります。両サイドヘルパーも同様に片側オペランドをコンパイル時に拒否します。なぜなら、片側 Conn は ConnK を実装しないからです。

Modules

FamilyModule
IEEE-754 typesfloat
Q-format binary fixed-point (Q###Q###, i8/u8 … i128/u128 backing)fixed::{i008,…,i128, u008,…,u128} (fixed cargo feature)
Std-int widening + narrowing + cross-sign (I###I###, U###I###, U###U###, I###U###)core::{i008,…,i128, u008,…,u128}
iN/uN ↔ NonZero<{i,u}N> (I###N###, U###N###)core::{i008,…,i128, u008,…,u128}
Cross-crate iso Fixed{I,U}<U0> ↔ {i,u}{N} (Q000I###, Q000U###) and signed normalized bit isos (Q007I008 … Q127I128)fixed::{i008,…,i128, u008,…,u128} (fixed cargo feature)
Float narrowing f64 ↔ f32 ↔ f16 under N5 (F064F032, F032F016, F064F016)core::{f032,f064} (f16 cargo feature for f16)
time crate types (DATEJDAY, TIMENANO, TIMESECS, TDURSECS, F032TDUR, F064TDUR, PDTMDATE, ODTMNANO, ODTMSECS) and the std::time::Duration family (SDURU064, SDURU128, F064SDUR, F032SDUR) for users on std::timetime::{clock,date,datetime,duration,offset} (time cargo feature)
hifitime nanosecond Duration + Epoch Conns — calendar (MONTU008, WKDYU008), duration (HDURNANO, HDURSECS, F064HDUR), and per-timescale epoch bridges (EUNXNANO, ETAINANO, F064ETAI, EGPSNANO, …)hifi::{calendar,duration,epoch} (hifi cargo feature)
uhlc hybrid-logical-clock Conns — NTP64 ↔ u64 (NDURU064) and the HLC ID bridge (HLIDLX16)uhlc::{ntp64,id} (uhlc cargo feature)
std::net addresses (U032IPV4, U128IPV6, IPV6IPV4, IPVXIPV4, IPVXIPV6, SOVXSOV4, SOVXSOV6)addr
char codepoint projection (U032CHAR, surrogate-gap-aware)core::char
Pointer-width usize saturating casts (USZEU008, USZEU016, USZEU032, USZEU064, USZEU128)core::usize
Pointer-width isize casts (ISZEI008, ISZEI016, ISZEI128; → i32/→ i64 deferred)core::isize
Sortable byte encodings (U008BE01, U008LE01, I008BE01, I008LE01, BOOLBE01, BOOLLE01, through U128BE16, U128LE16, I128BE16, I128LE16)core::{bool, i008,…,i128, u008,…,u128}

Constant-name prefixesは文字で区別されます: QはQフォーマットラッパー(符号とホストビット幅はモジュールパスから)、I/Uは標準プリミティブ(数字=ビット幅)、NはNonZero<*>、FはIEEE浮動小数点数です。モジュール間の名前の衝突は許可されており、修飾インポートによって解決されます(例: fixed::i008::Q008Q000とfixed::i064::Q008Q000は共存します)。

ConnK connections

同じ inner 関数が upper と lower の両方として機能し、追加の順序を反映するプロパティ(Sandwich inequalityを参照)を満たす場合、ライブラリは結果として得られる2つの接続をゼロサイズのマーカ構造体に結合し、L側とR側を結びつけるスーパー・トレイトを介して3番目のグループの「両利き」ヘルパーを取得します。

  • ConnL — 関連型 type A: Copy; type B: Copy; とLビュー Conn<A, B, L> への conn_l() プロジェクションを持つ機能トレイト。デフォルトメソッドは .ceil() と .upper() を公開します。
  • ConnR — 同様の機能トレイトで、conn_r() がRビュー Conn<A, B, R> にプロジェクションします。デフォルトメソッドは .floor() と .lower() を公開します。
  • ConnK — 同じ (A, B) ペアに対する ConnL + ConnR のスーパー・トレイト。両サイドヘルパー(round、truncateなど)は ConnK でバインドされ、両方のビューを通過します。

トレイト名は意図的に値型のスペルと一致しています。impl ConnL for Conn<A, B, L>(およびRサイドのアナログ)のブランケット実装により、すべての片側値もトレイトを満たすため、ジェネリック T: ConnL バウンドはトリプルマーカーと生の Conn<A, B, L> 値を均一に受け入れます。inner はモジュールスコープのフリー関数として定義され、マーカーのトレイト実装から参照されます。クレート内のどの構造体も3つの関数ポインタを格納しません。

Adjoint triples

ceil、inner、floor の3つの関数を使用して、クレートで提供されるマクロのいずれかを使用して ConnK マーカーを構築します。ceil/inner と inner/floor の両方が上記の接続不等式を満たす必要があることに注意してください。さらに、ceil/floor は次の「サンドイッチ」不等式を満たす必要があります。すべての a に対して、floor(a) ≤ ceil(a)。

すべての3つのプロパティを満たすトリプル ceil/inner/floor は随伴トリプルとして知られています。これはExample 3で概説されている ceil ⊣ inner ⊣ floor の形状です。

サンドイッチ不等式は、inner が順序を反映するという以前の要件と同等です。prop::conn::law_battery! の full サブセットは、floor_le_ceil と order_reflecting の両方を強制します。

同等性の証明は、次のセクションで概説されています。

Sandwich inequality

同等性の両方向は、随伴法則の適用から導かれます。両方の証明は、L-Galois f ⊣ g、R-Galois g ⊣ h、単調性、および推移律のみを使用します。追加の仮定はありません。

十分性(innerが順序を反映する ⟹ floor(a) ≤ ceil(a))。任意の a ∈ A を取ります。2つの閉包法則は次を与えます。

inner(floor(a)) ≤ a ≤ inner(ceil(a))

したがって、推移律により inner(floor(a)) ≤ inner(ceil(a)) となります。inner は順序を反映するため、これは floor(a) ≤ ceil(a) に持ち上げられます。∎

必要性(すべての場所で floor(a) ≤ ceil(a) ⟹ inner が順序を反映する)。inner(x) ≤ inner(y) を満たす x, y ∈ B を取ります。連鎖:

x ≤ floor(inner(x))     -- inner ⊣ floor のカーネル、b = x とする
  ≤ ceil(inner(x))      -- a = inner(x) における仮定
  ≤ y                   -- L-Galois ceil(a) ≤ b ⇔ a ≤ inner(b)
                           -- a = inner(x), b = y とし、右辺
                           -- inner(x) ≤ inner(y) は与えられている

したがって x ≤ y となります。∎

(圏論的に言えば、順序集合上の随伴トリプル f ⊣ g ⊣ h において、g が全単射 ⇔ g ⊣ h の余単位が同型 ⇔ f ⊣ g の単位が同型 ⇔ h ≤ f。上記の2つの表示は、順序集合に対する同等性を表しています。「全単射」は「順序を反映する」に、「同型」は「等価」に還元されます。)

反例 — 必要性は鋭いです。A = {a}(1つの要素)と B = {b₁ < b₂ < b₃} とし、inner: B → A を定数写像(すべての b に対して inner(b) = a — 単調だが最大に非単射)とします。各サイドのGalois法則が何を強制するかを見てみましょう。

  • L-Galois ceil(a) ≤ b ⇔ a ≤ inner(b)。右辺は a ≤ a に還元され、常に真なので、すべての b ∈ B に対して ceil(a) ≤ b となります。そのような b の最小値は b₁ なので、ceil(a) = b₁。
  • R-Galois inner(b) ≤ a ⇔ b ≤ floor(a)。左辺は a ≤ a に還元され、常に真なので、すべての b に対して b ≤ floor(a) となり、floor(a) = b₃ となります。

両方の片側随伴性が保持され、すべての単調性チェックがパスします — それでも floor(a) = b₃ > b₁ = ceil(a) となります。「トリプル」は型チェックされ、片側法則は満たされますが、丸めサンドイッチは逆転しています。

両サイドヘルパーは、この逆転を引き継ぎます。round(a) は inner(floor(a)) = a と inner(ceil(a)) = a を比較して近い方の端点を選択しようとしますが、それらが等しいと判断し、truncate にフォールスルーします。truncate は、ソースゼロ規則が選択する側を返します。これは、問題が発生したことを示す帯域内信号を持たない値です。サンドイッチ不等式に失敗する接続は、学術的な不正ではなく、両サイドヘルパーはそれに対して積極的に誤動作します。

Installation

cargo add connections
MSRVRust 1.88 (matches rust-toolchain.toml)
Edition2024
LicenseMIT (see LICENSE-MIT)

オプションのcargoフィーチャー:

FeatureWhat it enablesToolchain
fixedconnections::fixed::{i008,…,u128} Q-format ladders, float→Q bridges, Q.0 primitive isos, and signed normalized bit isosstable
proptestRe-exports connections::prop::arb (proptest strategies) for downstream test suitesstable
macrosRe-exports the internal codegen macro families under connections::macros / crate-root macro pathsstable
timeCivil-calendar and time-span Conns backed by the time cratestable
hifiNanosecond-precision hifitime::Duration / Epoch Connsstable
f16IEEE binary16 connections (F016, F032F016, F064F016) and their proptest strategiesnightly (uses #![feature(f16)] — tracking #116909)
try_trait? operator (Try / FromResidual) support on Interval, Extended, N5 — extracts the success payload; Interval / Extended short-circuit on boundary variants, N5 is infalliblenightly (uses #![feature(try_trait_v2)] — tracking #84277)

connections::prop::conn および connections::prop::lattice 述語モジュールは常に公開されています。これらはこのクレート自身の型に対する純粋な bool を返す関数であり、proptest に依存しません。proptest フィーチャーは prop::arb、つまり通常の依存関係として proptest を引き込む戦略モジュールのみを追加します。

Testing

cargo test --workspace

すべての接続は、CIおよびリポジトリのプッシュ前ゲートで proptest 法則スイートを実行します。浮動小数点数ジェネレータは、NaN、±∞、±0、非正規数、およびULP境界値に偏っています。固定小数点数ジェネレータは、0、±PREC、および ±i64::MAX/PREC に偏っているため、飽和境界はすべての実行で実行されます。

ランタイム依存関係はフィーチャーゲートされています。fixed クレートは、オプションのバイナリ固定小数点ラダーをサポートし、time クレートは、オプションの民法カレンダー/クロックサーフェスをサポートし、hifitime クレートは、オプションの高精度時間サーフェスをサポートします。Proptestは開発依存関係であり、ダウンストリームテストスイートのために proptest フィーチャーの背後で公開されています。すべての接続には、次の法則のプロテストカバレッジが付属しています。述語は prop::conn にあり、ダウンストリームクレートが独自の接続に対して再実行可能です。

LawStatement
conn_galois_lceil(a) ≤ b ⇔ a ≤ inner(b)
conn_galois_rinner(b) ≤ a ⇔ b ≤ floor(a)
conn_closure_la ≤ inner(ceil(a)) (unit)
conn_closure_rinner(floor(a)) ≤ a
conn_kernel_lceil(inner(b)) ≤ b (counit)
conn_kernel_rb ≤ floor(inner(b))
conn_monotone_la₁ ≤ a₂ ⟹ ceil(a₁) ≤ ceil(a₂) ∧ floor(a₁) ≤ floor(a₂)
conn_monotone_rb₁ ≤ b₂ ⟹ inner(b₁) ≤ inner(b₂)
conn_idempotentinner ∘ ceil はその画像上で冪等

10番目の法則 conn_floor_le_ceil (floor(a) ≤ ceil(a)) は、inner が単射埋め込みである ConnK 接続でのみアサートされます。上記を参照してください。

浮動小数点数型の場合、≤ は N5 lattice です。特に、NaNは反射的であり、NaNは±∞の間に位置し、有限値は厳密に順序付けられています。N5 はこれらのセマンティクスを運びます。

SMT verification (Kani)

プロテスト法則スイート(サンプリング)に加えて、生成された固定幅整数/Qフォーマット/NonZero/iso接続ファミリー(src/kani.rsにリストされている)は、完全なビット幅ドメイン全体でのGalois法則述語のKaniハーネスを備えています。ポインタ幅の usize / isize ファミリー(core::usize / core::isize)は例外です。CBMCは実行ごとに単一の具体的なポインタ幅をモデル化するため、これらのConnはホストターゲットでのプロテストバッテリーではなく、幅に依存しないSMT証明によってカバーされます。証明ツリーはsrc/kani/にあり、#[cfg(kani)]によってゲートされているため、cargo kaniの下でのみコンパイルされます。リリースビルド、cargo test、およびダウンストリームコンシューマーは証明コードを見ません。新しいランタイム依存関係はありません。Kaniは証明時に独自のクレートを注入します。

浮動小数点数固有のSMT結果は意図的に狭くなっています。IEEEビット空間は、完全なGalois証明を扱うには大きすぎるため、src/core/f064.rsの f64 → f32 ULPウォーク(ceil_f64_f32 / floor_f64_f32)は、プロテストサンプルだけでなく、すべての有限非NaN f64に対して ≤ 2回の反復で収束することが証明されています。3つの階層化されたハーネス(完全なドメイン用の float_walk::t0_*、|x| ≤ 1e6 用の t1_*、[1, 2) ビンネード用の t2_*)はそれぞれ、入力制限を徐々に厳しくしながら境界を検証します。これらのハーネスは、NaN/±∞全体での完全な浮動小数点Galois法則を証明するものではなく、浮動小数点数から整数または浮動小数点数から固定小数点数へのマクロヘルパー本体をカバーするものでもありません。これらのブランチは、プロテスト法則バッテリーと明示的なヘルパー/単体テストによってカバーされます。

次で実行します。

cargo install --locked kani-verifier
cargo kani setup
cargo kani                                   # full proof tree
cargo kani --harness 'float_walk::t0_'       # the headline
cargo kani --harness 'int_narrow::'          # one family

ハーネスごとの壁時間はミリ秒から秒の範囲です。完全なツリーは2分未満で実行されます。