core チュートリアル

このチュートリアルでは、luna-generic の trait を使って多くの数値型に対して一つのアルゴリズムを書き、整数を任意の数値型に変換し、独自の型を同じ語彙に組み込めるようにします。設計の理由は core 設計にあります。

やりたいこと	使うもの
多くの数値型に対して一つのアルゴリズムを書く	`T : Ring` のような trait 制約
整数の定数や添字を `T` に変換する	`@luna-generic.lift_to(i)`（`T : FromInteger`）
自分の数値型を整数から構築できるようにする	`FromNat` と `FromInteger` を実装する
新しい整数型を定義する	さらに `Integral` を実装し、検査を一つ加える
任意の整数の正確な表現を一つ得る	`Integral::normalize(x)`（`BigInt`）

クイックスタート

モジュールにパッケージを追加します:

moon add Luna-Flow/luna-generic@0.4.0

使用するパッケージの moon.pkg でインポートします:

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

このページの例では、一つの using 宣言で trait をスコープに入れます:

using @luna-generic {
  trait Semiring,
  trait Ring,
  trait Field,
  trait Zero,
  trait One,
  trait FromNat,
  trait FromInteger,
  trait Integral,
}

最小の実用的なプログラムは、三つの型で使う一つのジェネリック関数です:

fn[T : Ring] double_and_add_one(x : T) -> T {
  x + x + One::one()
}

test "quick start" {
  inspect(double_and_add_one(20), content="41")
  inspect(double_and_add_one(0.25), content="1.5")
  inspect(double_and_add_one(BigInt::from_string("99999999999999999999")), content="199999999999999999999")
}

double_and_add_one は符号付き整数、BigInt、Float、Double、そして同じ trait を実装する将来の任意の型で動きます。

日常的なタスク

具体型ではなく構造に対してアルゴリズムを書く

アルゴリズムに必要なことを表す最小の trait を要求します。積の和に必要なのは 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")
  inspect(dot([0.5, 2.0], [4.0, 0.25]), content="2.5")
}

減算するなら Ring を、除算するときだけ Field を要求します。

`lift_to` で整数を自分の数値型に変換する

fn[T : Semiring + FromInteger] times_index(x : T, i : Int) -> T {
  x * @luna-generic.lift_to(i)
}

test "lift_to" {
  inspect(times_index(1.5, 4), content="6")
  inspect(times_index(BigInt::from_int(7), -3), content="-21")
}

lift_to は任意の整数型（Int、UInt64、BigInt など）の値を、FromInteger を持つ任意の型に変換します。見るのは整数が現在保持している値です。Int の計算がすでに回り込んでいれば、lift_to は回り込んだ後の値を変換します。全範囲が必要なら、BigInt か T で計算してください。

任意の体で平均を求める

fn[F : Field + FromInteger] mean(xs : Array[F]) -> F {
  let mut total : F = Zero::zero()
  for x in xs {
    total = total + x
  }
  total / @luna-generic.lift_to(xs.length())
}

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

任意の整数の正確な表現を一つ得る

fn[T : Integral] canonical_text(x : T) -> String {
  Integral::normalize(x).to_string()
}

test "normalize" {
  inspect(canonical_text(-5), content="-5")
  inspect(canonical_text((65535 : UInt16)), content="65535")
  inspect(canonical_text(9223372036854775807L), content="9223372036854775807")
}

複数の整数型にまたがって一つの厳密な表現が必要なときは Integral::normalize を使います。符号なしの値は非負になり、符号付きの値は符号を保ちます。

さらに進んで

自分の数値型を整数から構築できるようにする

例として 8 ビットの回り込む整数を使います。整数から作れればよいだけの型は、BigInt からの二つの変換を実装します:

priv struct I8 {
  v : Int // always in [-128, 128)
} derive(Eq, Debug)

fn I8::wrap(n : Int) -> I8 {
  let r = ((n % 256) + 256) % 256
  { v: if r >= 128 { r - 256 } else { r } }
}

impl Add for I8 with fn add(a, b) { I8::wrap(a.v + b.v) }
impl Mul for I8 with fn mul(a, b) { I8::wrap(a.v * b.v) }
impl Neg for I8 with fn neg(a) { I8::wrap(-a.v) }
impl Sub for I8 with fn sub(a, b) { I8::wrap(a.v - b.v) }
impl Zero for I8 with fn zero() { { v: 0 } }
impl One for I8 with fn one() { { v: 1 } }
impl @luna-generic.AddMonoid for I8
impl @luna-generic.MulMonoid for I8
impl @luna-generic.AddGroup for I8
impl Semiring for I8
impl Ring for I8

impl FromNat for I8 with fn from_natural(n) {
  I8::wrap((n % BigInt::from_int(256)).to_int())
}

impl FromInteger for I8 with fn from_integer(n) {
  I8::wrap((n % BigInt::from_int(256)).to_int())
}

from_natural は非負の値でのみ呼ばれます。どちらの変換も演算と整合していなければなりません。a + b の変換は変換結果の和に等しく、* も同様で、0 と 1 はそれぞれ自分の零と一になります。大きな値や負の値も含めて、いくつかの値で検査します:

test "from_integer is a homomorphism" {
  let h : @luna-generic.Hom[@luna-generic.RingSig, BigInt, I8] = @luna-generic.Hom::from_integer().to_ring()
  let samples = [0, 1, -1, 127, 128, -129, 1000].map(BigInt::from_int)
  assert_true(h.check(@luna-generic.Algebra::ring(), @luna-generic.Algebra::ring(), samples))
  inspect(h.apply(BigInt::from_int(200)).v, content="-56")
}

浮動小数点型は丸めの範囲でしか一致しません。許容誤差付きの検査方法はhom チュートリアルにあります。

新しい整数型を定義する

これはまれです。整数型は上の二つの変換に加えて Integral を実装します。normalize は x の値を、その型が表示するとおりに BigInt として返すので、変換し直すと元の x に戻ります。型の最小値と最大値でこの往復を検査します:

impl Integral for I8 with fn normalize(x) { BigInt::from_int(x.v) }

test "normalize is a section" {
  let s : @luna-generic.Section[@luna-generic.SemiringSig, I8, BigInt] = @luna-generic.Section::of_integral()
  let samples = [-128, -1, 0, 1, 127].map(I8::wrap)
  assert_true(s.check(samples))
  let n : Int = @luna-generic.lift_to(I8::wrap(127) + One::one())
  inspect(n, content="-128")
}

最後の行は回り込みを示しています。I8 では 127 + 1 は -128 で、lift_to は回り込んだ値を変換します。

兄弟パッケージとの組み合わせ

上位の Luna Flow パッケージはこれらの trait で要件を述べるので、それを実装した型はそれらのジェネリックなコードに渡せます。インスタンスは誠実に保ってください。型が trait の法則を満たすときだけ実装します。法則は core API に載っています。

よくある落とし穴

アルゴリズムが本当に必要とする最小の trait 集合を選ぶ。
逆元や除法が必要なときだけ Field を要求する。
Field は乗法の可換性を約束します。積が因子の順序に依存する型には実装しないでください。そのような型を受け付けるコードでは Ring + Inverse + Div を要求します。
Float と Double は同じ抽象面を持っていても近似バックエンドとして扱う。
Float と Double では Inverse::inv は 0.0 で中断しますが、/ は無限大を返します。逆元をとる前にゼロを確認してください。
符号なし整数は Ring ではありません。符号反転するジェネリックなコードは UInt を受け取れません。
lift_to は回り込んだ値を変換します。呼び出し前に起きたオーバーフローは元に戻りません。
非推奨の NatHomomorphism と IntegralHomomorphism よりも、lift_to、FromNat、FromInteger を使ってください。

次のステップ

core API にはすべての trait、その法則、同梱のインスタンスが載っています。
core 設計では、変換が ℤ を経由して分解する理由と、Field が可換でなければならない理由を導出しています。
hom チュートリアルでは、変換やその他の写像を証明書で検査します。