core API

役割

luna-generic は LunaFlow の代数 trait 基盤レイヤです。数値アルゴリズムやコンテナを直接提供するのではなく、上位パッケージが共有する能力境界を定義します。

このページでは trait、変換関数、同梱のインスタンスを一覧します。証明書 Hom と Section は hom API のページにあります。この形になっている理由は core 設計 を参照してください。

インポート

moon.pkg にパッケージを追加します:

import {
  "Luna-Flow/luna-generic",
}

このページの例では、一つの using 宣言で名前をスコープに入れるので、@luna-generic. 接頭辞なしで書けます:

using @luna-generic {
  trait AddMonoid,
  trait MulMonoid,
  trait AddGroup,
  trait MulGroup,
  trait Semiring,
  trait Ring,
  trait Field,
  trait Num,
  trait Zero,
  trait One,
  trait Inverse,
  trait Conjugate,
  trait FromNat,
  trait FromInteger,
  trait Integral,
  trait Nat,
  lift_to,
}

法則は契約

以下の構造 trait はすべて空の trait で、メソッドはスーパー trait から来ます。MoonBit の Add、Mul、Neg、Sub、Div と、このパッケージの Zero、One、Inverse です。コンパイラはメソッドの存在を検査しますが、trait に意味を与える等式は検査しません。等式は各 trait の下に記載しています。それを破る実装もコンパイルは通りますが、その trait に対して書かれたジェネリックなコードが誤った結果を出す可能性があります。境界値でテストしてください。たとえば hom API の Hom::check を使います。

Float と Double は丸めの範囲でしか法則を満たしません。浮動小数点の加算は結合的でないため、同じ trait の近似的なインスタンスです。

演算 trait

これらの trait は src/operation.mbt にあります。それぞれ一つの演算に名前を付けるだけで、それ自体は法則を持ちません。意味は構造 trait が与えます。

Zero

Zero::zero() は Self の加法単位元を返します。

pub(open) trait Zero {
  fn zero() -> Self
}

AddMonoid では $0 + x = x + 0 = x$ を満たさなければなりません。すべての既定の数値型に用意されています。

One

One::one() は Self の乗法単位元を返します。

pub(open) trait One {
  fn one() -> Self
}

MulMonoid では $1 \cdot x = x \cdot 1 = x$ を満たさなければなりません。すべての既定の数値型に用意されています。

test "zero and one" {
  let z : Int = Zero::zero()
  let o : Double = One::one()
  inspect(z, content="0")
  inspect(o, content="1")
}

Inverse

Inverse::inv(x) は乗法逆元 $x^{-1}$ を返します。

pub(open) trait Inverse {
  fn inv(Self) -> Self
}

MulGroup や Field では、逆元を持つすべての $x$ について $x \cdot x^{-1} = x^{-1} \cdot x = 1$ を満たさなければなりません。同梱の Float と Double のインスタンスは 0 に対してメッセージ付きで中断し、1.0 / 0.0 のように無限大を返すことはしません。

test "inv" {
  inspect(Inverse::inv(4.0), content="0.25")
}

Conjugate

Conjugate::conjugate(x) は共役 $\overline{x}$ を返します。

pub(open) trait Conjugate {
  fn conjugate(Self) -> Self
}

インスタンスは同梱されていません。実装者は通常、演算と両立する対合にします。$\overline{\overline{x}} = x$、$\overline{x + y} = \overline{x} + \overline{y}$、$\overline{xy} = \overline{y}\,\overline{x}$ で、乗法が可換なら最後は $\overline{x}\,\overline{y}$ になります。trait はこれらの法則を強制しません。

priv struct Pair {
  re : Double
  im : Double
} derive(Eq, Debug)

impl Conjugate for Pair with fn conjugate(z) {
  { re: z.re, im: -z.im }
}

test "conjugate" {
  let z = Pair::{ re: 1.0, im: 2.0 }
  assert_eq(Conjugate::conjugate(Conjugate::conjugate(z)), z)
}

構造 traits

これらの trait は src/structure.mbt にあります。各 trait は拡張元の trait に法則を追加します。法則は型のすべての $x, y, z$ について書かれています。

AddMonoid

AddMonoid は結合的な + と単位元 0 を持つ型です。

pub(open) trait AddMonoid : Add + Zero {
}

$$(x + y) + z = x + (y + z), \qquad 0 + x = x + 0 = x.$$

ここでは + の可換性は要求しません。このパッケージで AddMonoid の上に作られる構造（Semiring、Ring）はすべて可換性を要求します。

fn[T : AddMonoid] sum(xs : Array[T]) -> T {
  xs.fold(init=Zero::zero(), (acc, x) => acc + x)
}

test "sum" {
  inspect(sum([1, 2, 3]), content="6")
  inspect(sum(([] : Array[UInt])), content="0")
}

MulMonoid

MulMonoid は結合的な * と単位元 1 を持つ型です。

pub(open) trait MulMonoid : Mul + One {
}

$$(xy)z = x(yz), \qquad 1 \cdot x = x \cdot 1 = x.$$

fn[T : MulMonoid] power(x : T, n : Int) -> T {
  let mut acc : T = One::one()
  for _ in 0..<n {
    acc = acc * x
  }
  acc
}

test "power" {
  inspect(power(3, 4), content="81")
  inspect(power(2UL, 0), content="1")
}

AddGroup

AddGroup はすべての元が負元を持つ AddMonoid です。

pub(open) trait AddGroup : AddMonoid + Neg + Sub {
}

$$x + (-x) = (-x) + x = 0, \qquad x - y = x + (-y).$$

符号なし型は実装しません。下の意味論の注記を参照してください。

fn[T : AddGroup] difference(x : T, y : T) -> T {
  x + -y
}

test "difference" {
  inspect(difference(3, 5), content="-2")
}

MulGroup

MulGroup は逆元と除算を持つ MulMonoid です。

pub(open) trait MulGroup : MulMonoid + Inverse + Div {
}

$$x \cdot x^{-1} = x^{-1} \cdot x = 1, \qquad x / y = x \cdot y^{-1}.$$

実装しているのは Float と Double だけで、これらでは法則は非零の元についてのみ成り立ちます。0 には逆元がありません。

Semiring

Semiring は加法モノイドと乗法モノイドを分配法則で結び付けたものです。

pub(open) trait Semiring : AddMonoid + MulMonoid {
}

$$x + y = y + x, \qquad x(y + z) = xy + xz, \qquad (x + y)z = xz + yz, \qquad 0 \cdot x = x \cdot 0 = 0.$$

既定の数値型はすべて Semiring を実装します。符号なし整数も含みます。

fn[T : Semiring] dot(xs : Array[T], ys : Array[T]) -> T {
  let mut acc : T = Zero::zero()
  for i, x in xs {
    acc = acc + x * ys[i]
  }
  acc
}

test "dot" {
  inspect(dot([1U, 2U, 3U], [4U, 5U, 6U]), content="32")
}

Ring

Ring は加法が群をなす Semiring です。

pub(open) trait Ring : Semiring + Neg + Sub {
}

Semiring の法則と AddGroup の法則を満たします。乗法は可換でなくてもかまいません。符号付き整数、BigInt、Float、Double が実装します。

fn[T : Ring] square_of_difference(x : T, y : T) -> T {
  (x - y) * (x - y)
}

test "ring" {
  inspect(square_of_difference(2, 7), content="25")
}

Field

Field は非零の元がすべて逆元を持つ可換な Ring です。

pub(open) trait Field : Ring + Inverse + Div {
}

実装者は Ring の法則に加え、すべての $a, b$ について次を満たさなければなりません:

$$ab = ba, \qquad a \cdot a^{-1} = 1 \ \text{ for } a \neq 0, \qquad a / b = a \cdot b^{-1} \ \text{ for } b \neq 0.$$

可換性は、体の数学的定義と同じく契約の一部です。コンパイラはこれを検査しません。乗法が可換でないが逆元を持つ型（斜体）も Field としてコンパイルでき、$ab = ba$ に依存するジェネリックなコード（たとえば $(ab)^{-1}$ を $a^{-1}b^{-1}$ に書き換える）はその型に対して誤った答えを返します。そのような型に Field を実装しないでください。違いは core 設計 で説明しています。

Float と Double は丸めの範囲で Field を実装します。inv は 0 で中断しますが、/ は IEEE 754 に従い無限大または NaN を返します。

fn[F : Field] mean(xs : Array[F]) -> F {
  let mut total : F = Zero::zero()
  let mut count : F = Zero::zero()
  for x in xs {
    total = total + x
    count = count + One::one()
  }
  total / count
}

test "field" {
  inspect(mean([1.0, 2.0, 4.5]), content="2.5")
}

Num

Num は絶対値と符号を持つ Ring です。

pub(open) trait Num : Ring {
  fn abs(Self) -> Self
  fn signum(Self) -> Self
}

signum(x) は $x$ の符号に応じて $-1$、$0$、$1$ のいずれかで、

$$\operatorname{abs}(x) \cdot \operatorname{signum}(x) = x.$$

符号付き整数、BigInt、Float、Double が実装します。固定幅の型では最小の負の値で法則が破れます。その絶対値は回り込んで自分自身に戻るためです。Float と Double では、signum は 0.0、-0.0、NaN に対して引数をそのまま返します。

test "num" {
  inspect(Num::signum(-7), content="-1")
  inspect(Num::abs(-7) * Num::signum(-7), content="-7")
}

ℕ と ℤ からの標準写像

FromNat

FromNat::from_natural(n) は唯一の半環準同型 ℕ → Self で、自然数は BigInt で与えます。

pub(open) trait FromNat {
  fn from_natural(@bigint.BigInt) -> Self
}

前提条件は $n \ge 0$ です。結果は $n \cdot 1 = 1 + \dots + 1$（$n$ 項）でなければならないので、次が成り立ちます:

$$\varphi(0) = 0, \quad \varphi(1) = 1, \quad \varphi(m + n) = \varphi(m) + \varphi(n), \quad \varphi(mn) = \varphi(m)\varphi(n).$$

固定幅の整数は $2^k$ を法として簡約し、Float と Double は最も近い値に丸めます。

FromInteger

FromInteger::from_integer(n) は唯一の環準同型 ℤ → Self で、整数は BigInt で与えます。

pub(open) trait FromInteger : FromNat {
  fn from_integer(@bigint.BigInt) -> Self
}

ℤ 全体で from_natural の法則を満たし、非負の引数では from_natural と一致しなければなりません。符号反転を持たない型でも、すべての整数に対して定義されます。符号なし型では from_integer(-1) は $2^k - 1$ です。BigInt では厳密、固定幅の整数では $2^k$ を法とする簡約、Float と Double では丸めです。

test "from_integer" {
  let big = BigInt::from_string("4294967301") // 2^32 + 5
  let i : Int = FromInteger::from_integer(big)
  let u : UInt = FromInteger::from_integer(BigInt::from_int(-1))
  let d : Double = FromInteger::from_integer(big)
  inspect(i, content="5")
  inspect(u, content="4294967295")
  inspect(d, content="4294967301")
}

独自の数値型にこれらの変換を持たせるには、両方の trait を実装します。方法は core チュートリアル にあります。

整数型

Integral

Integral は整数型です。ℤ そのもの、または固定幅整数のような商 ℤ/2^k です。

pub(open) trait Integral : Semiring + FromInteger {
  fn normalize(Self) -> @bigint.BigInt
}

normalize(x) は x の代表元を BigInt として返します。法則は、normalize が標準写像の切断であることです:

$$\texttt{Self::from\_integer}(\operatorname{normalize}(x)) = x .$$

同梱のインスタンスは、符号付き型では $[-2^{k-1}, 2^{k-1})$、符号なし型では $[0, 2^k)$、BigInt では恒等写像を選びます。normalize が準同型になるのは BigInt だけで、固定幅の型では演算が回り込むため準同型ではありません。Section::of_integral はこの組を検査できる証明書にまとめます。

test "normalize" {
  inspect(Integral::normalize(-1), content="-1")
  inspect(Integral::normalize(4294967295U), content="4294967295")
  inspect(Integral::normalize(2147483647 + 1), content="-2147483648")
}

Nat

Nat は代表元が非負の Integral 型です。すべての x について $\operatorname{normalize}(x) \ge 0$ です。

pub(open) trait Nat : Integral {
}

UInt、UInt16、UInt64 が実装します。任意精度の ℕ は ℤ の商ではないため Integral にはなれません。core 設計 を参照してください。

fn[N : Nat] digits(x : N) -> Int {
  Integral::normalize(x).to_string().length()
}

test "nat" {
  inspect(digits((65535 : UInt16)), content="5")
}

lift_to

lift_to(x) は整数値を代表元に持ち上げ、任意の FromInteger 対象へ写します。

pub fn[S : Integral, R : FromInteger] lift_to(S) -> R

これは R::from_integer(x.normalize()) です。準同型ではなく関数です。x が現在持つ値を変換するので、S ですでに回り込んだ和は回り込んだままです。R の法が S の法を割り切るとき、かつそのときに限り演算を保存します（例: Int64 -> Int）。この条件は core 設計 で導出しています。

test "lift_to" {
  let a : Double = lift_to(-7)
  let b : BigInt = lift_to(4294967295U)
  let c : Int = lift_to(4294967301L) // truncation, a homomorphism
  inspect(a, content="-7")
  inspect(b, content="4294967295")
  inspect(c, content="5")
}

同梱インスタンス

型	Trait
Int, Int16, Int64	AddMonoid, MulMonoid, AddGroup, Semiring, Ring, Num, Zero, One, FromNat, FromInteger, Integral
UInt, UInt16, UInt64	AddMonoid, MulMonoid, Semiring, Zero, One, FromNat, FromInteger, Integral, Nat
BigInt	符号付き整数と同じ。加えて非推奨の NatHomomorphism と IntegralHomomorphism
Float, Double	AddMonoid、MulMonoid、AddGroup、MulGroup、Semiring、Ring、Field、Num、Zero、One、Inverse、FromNat、FromInteger。加えて非推奨の NatHomomorphism と IntegralHomomorphism

Byte はどれも実装しません。

意味論メモ

• 固定幅の整数は ℤ/2^k です。その from_integer は 2^k を法として簡約し、normalize は型の範囲内の代表元を選びます。符号付き型では [-2^(k-1), 2^(k-1))、符号なし型では [0, 2^k) です。
• BigInt は ℤ そのものです。from_integer と normalize は恒等写像です。
• lift_to が準同型になるのは、対象の法がソースの法を割り切るとき、かつそのときに限ります（例: Int64 -> Int）。固定幅のソースから BigInt、Float、Double への場合は、演算が回り込むため準同型ではありません。
• Nat は代表元が非負である整数型を表します。真の任意精度 ℕ は ℤ の商ではないため、範囲外です。
• 符号なし整数は Semiring までで止まり、加法逆元を持つ構造のふりをしません。
• Float と Double は from_natural と from_integer で丸めを行うため、非常に大きな値は近似になります。
• Field は乗法の可換性を要求します。コンパイラは検査できないので、実装者の責任です。

非推奨

NatHomomorphism

NatHomomorphism::from_nat(x) は Nat の値を代表元に持ち上げ、Self へ写します。

pub(open) trait NatHomomorphism {
  fn[S : Nat] from_nat(S) -> Self
}

固定幅のソースではこの合成が準同型にならないため非推奨です。代替: FromNat と FromInteger を実装し、lift_to(x) を呼びます。BigInt、Float、Double は引き続き実装しています。

IntegralHomomorphism

IntegralHomomorphism::from_integral(x) は Integral の値を代表元に持ち上げ、Self へ写します。

pub(open) trait IntegralHomomorphism : NatHomomorphism {
  fn[S : Integral] from_integral(S) -> Self
}

同じ理由で非推奨です。代替: FromInteger を実装し、lift_to(x) を呼びます。BigInt、Float、Double は引き続き実装しています。

ソース入口

• src/structure.mbt：trait 定義
• src/operation.mbt：基礎操作 traits
• src/section.mbt: lift_to
• src/impl_signed.mbt、src/impl_unsigned.mbt、src/impl_bigint.mbt、 src/impl_float.mbt、src/impl_dbl.mbt：既定インスタンス