Swift - Introducing PONS = Protocol Oriented Number System

  • 93
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

まだ荒削りですが、お披露目してもいいところまで来たので。

売り口上

これでSwiftでも

  • GMPとか外部ライブラリなしで任意精度整数(BigInt)や任意精度分数(BigRat)や任意精度浮動小数点数(BigFloat)が使えるようになります。
  • 外部依存がないので、Xcodeでなくてもswiftcがあれば使えます。もちろんOS XだけでなくてLinuxもサポート
  • その任意精度数も、四則演算以外の演算を最初からサポートしています。整数は素数判定できますし、任意精度実数は<math.h>の関数を使えます。

これだけでもかなりハッピーになれます。

でも本当のウリは、そこじゃないんですよ…

承前: 古き良きCの時代

例えばman powとしてみます。こんな答えが返ってくるでしょう。

SYNOPSIS
    #include <math.h>

    double
    pow(double x, double y);

    long double
    powl(long double x, long double y);

    float
    powf(float x, float y);

なんで全く同じことをする関数が三つあるのか?

異なった型ごとに、違う実装が必要だから。

20世紀までは仕方ないことだったのかもしれませんが、21世紀ももう1/8過ぎた2016年にこんなの付き合ってられませんよね?

で、Swiftでは、

同じpowという名前でDoubleにもFloatにも対応しています。やったね!

import Cocoa    // this is an OSX playground
let twelveTet = pow(2.0, 1.0/12)
pow(Float(twelveTet), 12)           // not exactly 2.0 but you get the point

でも、使う側でなくて作る側として、どうしたらそのような関数が書けるでしょう?

とりあえずfibってみる

とりあえずみんな大好きフィボナッチ数でも数えてみますか。前世紀脳だと、こんな感じになりますか。

勤勉なやり方

func fib(n:Int8)->Int8   { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int16)->Int16 { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int32)->Int32 { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int64)->Int64 { return n < 2 ? i : fib(n-2)+fib(n-1) }
// hey, don't forget UInt(8|16|32|64)?

つまり、型シグネチャーが異なる同名の関数を、型の数だけ繰り返す、と。

やってられるか!

<T:Hoge>でどうHogeる?

幸いSwiftには総称型があります。ならこう書ける?

func fib<T>(i:T)->T { return i < 2 ? i : fib(n-2)+fib(n-1) }

残念でした。T<できたり、Tどうし+できたりって誰が保証してくれるんですか?

それを保証してくれるのが、Protocolなんですが…

func fib<T:Hoge>(i:T)->T { return i < 2 ? i : fib(n-2)+fib(n-1) }

で、Hogeプロトコルが<+をサポートしてさえすれば、これは動くはずです。

が、そのHogeってどこにあるの?

import PONS

PONSの役割は、それを提供すること。

import PONS     // make sure you have built the framework before this!

func fib<T:POInteger>(n:T)->T { // with a little better algorithm
    if n < T(2) { return n }
    var (a, b) = (T(0), T(1))
    for _ in 2...n {
        (a, b) = (b, a+b)
    }
    return b
}

ちょっとアルゴリズムを改良しました。

で、これが本当に動くのか?

let F11 = fib(11 as Int8)
let F13 = fib(13 as UInt8)
let F23 = fib(23 as Int16)
let F24 = fib(24 as UInt16)
let F46 = fib(46 as Int32)
let F47 = fib(47 as UInt32)
let F92 = fib(92 as Int64)
let F93 = fib(93 as UInt64)

動くんです。

しかし、PONSの本領はここからがはじまりです。あなたが苦労して実装した新たな整数方も受け付けてGeneric Programmingを名乗れるというものです。

でもどうやってそれを証明する?

そのためにBigInt実装しちゃいましたよ。てへぺろ。

よってこれが動きます。

let F666 = fib(666 as BigInt)

ちなみに6859356963880484413875401302176431788073214234535725264860437720157972142108894511264898366145528622543082646626140527097739556699078708088だそうです。

整数だけで許されるのは小学生までだよねー

カントールをパワハラして後世の評判を多いに下げたクロネッカーは、こうのたまいました。

整数は神の作ったものだが、他は人間の作ったものである

人間上等、というわけで我々はさまざまな数を作ってきました。有理数に実数にそして複素数。あの古き良きCですらC99で複素数をサポートしたぐらいです。それくらい数値というのは切実なわけです。

ところがSwiftは標準で複素数をサポートしていません。というわけで書いたのが

なのですが、これを書いたことでむしろ欲求不満は高まりました。

「たしかに総称型で、たしかにIntDoubleも受け入れられるけど、BigIntとかRationalとか突っ込んでも大丈夫?っつうかそれ以前に突っ込むべき数値型が見当たらないんだが」

というわけで実装しましたよ。Genericで「整数」型ならBigIntだって分子と分母に使えるRationalに…

let bq = BigInt(1).over(bn)     // (1/18446744073709551617)
bq + bq // (2/18446744073709551617)
bq - bq // (0/1)
bq * bq // (1/340282366920938463500268095579187314689)
bq / bq // (1/1)
bq.denominator == bn            // true, of course!
bq.reciprocal.numerator == bn   // so is this

そのRational含め、「実数」型なら実部と虚部に使えるComplex


let bz = bq + bq.i  // ((1/18446744073709551617)+(1/18446744073709551617).i)
bz + bz // ((2/18446744073709551617)+(2/18446744073709551617).i)
bz - bz // ((0/1)+(0/1).i)
bz * bz // ((0/1)+(2/340282366920938463500268095579187314689).i)
bz / bz // ((1/1)+(0/1).i)

動くぞ、動くぞ!

でも、整数におけるfact(orial)やfib(onacci)なようなデモを、実数とか複素数でやるにはどうしたらいいの?

<math.h>な関数が、総称型でも動くことを見せつければいい!

という気持ちでやった。後悔はしていない。

Double.sqrt(2)
Double.sqrt(2)                  // 1.414213562373095
BigRat.sqrt(2)                  // (112045541949572279837463876455/79228162514264337593543950336)
BigFloat.sqrt(2)                // 1.414213562373095048801688724198
Complex.sqrt(-2)                // (0.0+1.4142135623731.i)
Complex.sqrt(BigRat(-2))        // 112045541949572279837463876455/79228162514264337593543950336).i)

個人的に一番感動したのは、これ。

Complex.exp(Double.PI.i)        // (-1.0+1.22464679914735e-16.i) != (-1.0+0.0.i) // :(
// default 64-bit precision is still not good enough…
Complex.exp(BigRat.pi().i)      // (-(1/1)-(1/4722366482869645213696).i)
// but with 128-bit precision…
Complex.exp(BigRat.pi(128).i)   // (-(1/1)+(0/1).i) // as it should be!

128bit精度の有理数型なら e ** πi == -1 に本当になるんです!(厳密にはsin(pi) < ulpのというわけなのですが)。

すべての型別実装を、生まれる前に消し去りたい

PONSの存在意義は、 Write once, runs on every type (that conform to the protocol) が、数値型でも成立することを示すことにあります。

例えば三角関数のcossinは、(現時点において)
以下のように定義されています。

cos()
public static func cos(x:Self, precision:Int = 64)->Self {
    if let dx = x as? Double { return Self(Double.cos(dx)) }
    let px = Swift.max(x.precision, precision)
    let epsilon = Self(Double.ldexp(1.0, -px))
    let x2 = x * x
    var (r, t) = (Self(1), Self(1))
    for i in 1...px {
        t *= x2.divide(Self((2 * i - 1) * 2 * i), precision:px)
        t.truncate(px + 32)
        r += i & 1 == 1 ? -t : t
        r.truncate(px + 32)
        if t < epsilon { break }
    }
    return r.truncate(px)
}
sin()
public static func sin(x:Self, precision:Int = 64)->Self {
    if let dx = x as? Double { return Self(Double.sin(dx)) }
    let px = Swift.max(x.precision, precision)
    let epsilon = Self(Double.ldexp(1.0, -px))
    let x2 = x * x
    var r = x < 0 ? -x : x
    var t = r
    for i in 1...px {
        t *= x2.divide(Self((2 * i + 1) * 2 * i), precision:px)
        t.truncate(px + 32)
        r += i & 1 == 1 ? -t : t
        r.truncate(px + 32)
        if t < epsilon { break }
    }
    return x < 0 ? -r.truncate(px) : r.truncate(px)
}

数学者でなくとも、これはテイラー展開

sincos

をほぼそのままであることが見て取れるかと思いますが、重要なのはこれがFloatDoubleはおろか、BigRat = Rational<BigInt>でもBigFloatでもまったく変更なしに動くこと。一行目に

if let dx = x as? Double { return Self(Double.sin(dx)) }

とはありますが、これはコメントアウトしても動きます(その分Double.cosDouble.sinは遅くはなりますが)。

なんで/でなくて.divideなのか、.truncateは何をしているかとかは後日別記事で紹介する予定ですが、いずれにせよ将来Float128とか実装したとしても、サインコサインできちゃうわけです。

とりあえず使ってみるには

git clone して PONS.xcworkspace開いて、フレームワークをbuildしたらplaygroundで遊べます。Xcodeがなくともmake replすればコマンドラインから遊べます。自分のプロジェクトで使いたい場合は、ソースをまるっとコピーするだけです。

当初予定を超えて大きなプロジェクトになったので、まだまだ全然説明したりないのですが、とりあえず「なんぞこれ」はこれで伝わっているといいなあ…

Enjoy!

Dan the Protocol-Oriented Swift Programmer