Swift - Introducing PONS = Protocol Oriented Number System

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

* https://github.com/dankogai/swift-pons

![](https://github.com/dankogai/swift2-pons/raw/master/graph/typetree.png)


## 売り口上

これで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`にも対応しています。やったね！

````swift
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ってみる

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


### 勤勉なやり方

````swift
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には総称型があります。ならこう書ける?

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

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

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

````swift
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
}
````

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

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

````swift
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は標準で複素数をサポートしていません。というわけで書いたのが

* https://github.com/dankogai/swift-complex

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

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

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

````swift
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`。

````swift

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>`な関数が、総称型でも動くことを見せつければいい!

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

````swift
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)

````

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

````swift
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) が、数値型でも成立することを示すことにあります。

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

````swift: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)
}
````

````swift: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](https://upload.wikimedia.org/math/5/4/6/546ecab719ce73dfb34a7496c942972b.png)

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

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

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

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

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

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

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

Enjoy!

Dan the Protocol-Oriented Swift Programmer