第13回　Protocol-Oriented Programming

前回に引き続きPOP

今回はProtocol-Oriented Programmingが、実際どれほど使い物になるかを実例とともに紹介していきます。

PONS＝Protocol-Oriented Number Systemの紹介

前回取り上げた実例は、複素数（complexnumbers）の実装、swift-complexでした。記事にはこうあります。

誰かが任意精度の数値ライブラリを用意すれば、それを使うことも可能

でもそれって本当？

それが、今回紹介するPONS ＝ Protocol-Oriented Number Systemを書くことになったきっかけです（図1⁠）⁠。

使い方は簡単。

① git cloneしてPONS.xcworkspaceを開いて、Framework-OSXをビルドしたらOSX Playgroundの実例が実際に動くようになります。試しに(1...100).reduce(BigInt(1),combine:*)と打ってみてください。
②もちろんREPLでも動きます。make replするとREPLが立ち上がるので、import PONSしてから(1...100).reduce(BigInt(1),combine:*).descriptionとか打ってみてください。
③読者ご自身のプロジェクトで使いたい場合も、Frameworkをコピーしてもよし、ソースファイルをコピーしてもよしです。

これで、次のようなことができます。

RubyやPythonやHaskellではおなじみの任意精度整数（BigInt）が、GMPなどの外部ライブラリなしで使えるようになります。
→素数判定メソッドも付いてきます。いや、同じく任意精度整数が組込みのPerl6にも組込みだったので。
有理数型（Rational）もついてきます。分子と分母の型を引数とする総称型ですので、もちろん任意精度有理数＝Rational<BigInt>も使えます。よく使うのでBigRatととしてtypealiasしてあります。
任意精度浮動小数点数（BigFloat）もついています。BigRatだけでも好きなだけ小さな数も実現されているのですが、より高速かつ省スペースです。
→総称的に定義された初等関数（elementary functions）の実装も付いてきます。たとえばFloat128とか、新たな数値型を実装したときにexpやlogやsinやcosを書き直す必要はありません。実際BigRatとBigloatはそれぞれまったく別の型なのに、これらの関数のソースは共通です。

しかし、PONSの本当のウリはそこじゃないんです。

1つで十分ですよ、わかってくださいよ！

古のCの時代、同じことをするコードは、型ごとに必要でした。試しにman cosしてみると……、

NAME
     cos -- cosine function

SYNOPSIS
     #include <math.h>

     double
     cos(double x);

     long double
     cosl(long double x);

     float
     cosf(float x);

倍精度double用にcos()、単精度float用にcosf()、そして拡張精度long double用にcoslと、標準で用意されているだけで3種類もあります。四倍精度（float128）とかが標準装備になったらcosq()でも加えるんですか？昨今GPUで採用されはじめている半精度（float16）はcosh()ですか？でも待って、coshはもう双曲線コサイン（hyperbolic cosine）に取られちゃってますよ？

ぶっちゃけ付き合ってられませんよね？

Swiftは、はじめからこの問題にある程度対処されています。

#if os(Linux)
import Glibc
#else
import Darwin
#endif

された状態でXcodeにてcosと打つと……、図2のように、DoubleもFloatもCGFloatも、どれも同じcosで呼び出せることがわかります。

しかし、自分でこのような同名別型関数を用意しようとした場合、どうしたらよいでしょう？

こうですか？

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) }

だが断る！

だがしかし、Swiftには総称型があります。こうは書けないのでしょうか？

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

でもTを足したりTどうしを比較する方法をSwiftは知りませんから、残念！よろしい。ならばプロトコルだ。比較できて足せる型Hogeがあれば、

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

で行けるはずだ。でもそのHogeってどこにあるの？ PONSは、まさにそのためにあるのです。実際に試してみましょう。PONSでは、上記のHogeはPOIntegerが相当します。

import PONS

func fib<T:POInteger>(n:T)->T {
    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)

ぜひご自身でご確認を。

しかし、このプロトコルは既存の型だけではなく、どこからか持ってきた別の型にも適用できるのでしょうか？

BigIntでやってみましょう。

let F666 = fib(666 as BigInt)

  6859356963880484413875401302176431788073214234535725264860437720157972142108894511264898366145528622543082646626140527097739556699078708088

になりましたか？

でも、プロトコルなら運命を変えられる。避けようのない重複コードも、嘆きも、すべて君が覆せばいい。だからPONSと契約して、数学ガールになってよ！

……失礼しました。SEGVです。XcodeでProtocolを多様したプログラムを書いていると本当によくお目にかかれます:-(。

しかし数値は整数だけではありません。整数だけで満足できるのは小学生とクロネッカー先生[1]だけです。有理数も浮動小数点数もあるんだよ。

とはいえこれらを漠然と並べただけでは、体系（system）とはいえません。同じ/だって、整数型と実数型で違いますし。しかも、ただ符号なし整数→符号付き整数→実数→複素数とトップダウンにするわけにもいかないのです。確かに複素数は、四則演算と冪乗根（べきじょうこん）に対して閉じていますが、大小比較ができないというほかの数値型にはない特徴があります。

向き合った結果が、冒頭のグラフになります。ご覧いただければわかるとおり、複素数は実数からできているけど、大小比較はできないという関係が確かに成立しています。

だから、きちんとこのようになります。

Double.sqrt(-1) // NaN
Complex.sqrt(-1) // (0.0+1.0.i)
// そもそも比較できない
1.0+0.0.i < 2.0+0.0.i
// 絶対値を見ればおk
(1.0+0.0.i).abs < (2.0+0.0.i).abs

これが、「⁠本当の数値と向き合えますか？」の筆者なりの回答になります。

Protocol-Oriented Programming = 正しいものが報われる世界

PONSが目指したもの、それは「正しいものが報われる世界」ということに尽きます。掛け算1つとっても、固定長の数値型では、その半分の型におさまる数値しか安全にできません。63357を自乗するだけで、32ビット整数はオーバーフローするのです。『⁠C言語によるアルゴリズム辞典[2]⁠』というロングセラーがあります。PONSの実装でも大いに参考にさせていただいたのですが、intやdoubleの制約を回避するのに涙ぐましいほどの努力をしていて時代を感じさせます。正しい世界とは、そうではなくてアルゴリズムをそのまま書き下せばそのまま動く世界のはずです。

たとえばモンゴメリー乗算というアルゴリズムがあります。これを使うと割り算なしで冪剰余を計算できたりするので素数が捗ったりします。PONSにも実装されているのですが、普通に実装すると簡単に整数オーバーフローしてしまいます。そのため固定整数のみで実装しようとするとたいへんなのですが、BigIntがあれば「オーバーフローしそうならそこだけBigInt使って」ということがとても簡単に実現できます。実際に現時点におけるPONSの冪剰余はそのように実装されています。

その一方、BigIntは自分では文字列化メソッドを持っていません。整数の文字列化には、整数型に依存するアルゴリズムがすでに存在するからです。PONSでは、そのメソッドはPOIntegerでこう実装されています（リスト1⁠）⁠。

リスト1　PONSの実装例

public func toString(base:Int = 10)-> String {
    guard 2 <= base && base <= 36 else {
        fatalError("base out of range. \(base) is not within 2...36")
    }
    var v = self
    var digits = [Int]()
    repeat {
        var r:Int
        (v, r) = Self.divmod8(v, Int8(base))
        digits.append(r)
    } while v != 0
    return digits.reverse().map{"\(POUtil.int2char[$0])"}.joinWithSeparator("")

元の数を底（base）で割っていき、その余りをまとめるという操作は、その整数型の実装にはまったく依存しません。つまりPOIntegerに準拠した数値型は、何も加えなくても文字列化できるということです。

そもそもBigIntがあればほかの整数型はいらないという意見もあり得ます。大は小を兼ねるじゃないかという意見もごもっともですが、しかしSwiftを含め、多くの言語で整数型が固定なのには立派な理由があります。任意精度整数はとても重いのです。軽くベンチマークしてみると、64ビットにおさまる20! = 2432902008176640000を計算するのに、PONSのBigIntではSwift組込みIntのなんと500倍も時間がかかるのです。これはPONSの実装がしょぼいから、ではなく実は相場どおりで、Perl 5標準装備で、ただし組込みではないMath::BigIntもネイティブな64bit整数の250倍でした。ちなみにPONSのBigIntは世界最速の任意精度整数からはほど遠いのですが、それでも、SwiftがネイティブコードコンパイラーということもあってかMath::BigIntの5倍の速度が出ています。

コードを使い分けずとも、型は使い分けられる。

PONSでそのことを示せたと自負しています。

予告

実はPONSのようなものは、Swiftの中の人もTodoにしていたようです。Swift-Evolutionメーリングリストに、次のような書き込みがありました。

I have been working for some time on a rewrite of all the integer types and protocols https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb. One goal of this effort is to enable operations on mixed integer types, which as you can see is partially completed. In-place arithmetic (anInt32 += aUInt64) is next. Another important goal is to make the integer protocols actually useful for writing generic code, instead of what they are today:implementation artifacts used only for code sharing. As another litmus test of the usefulness of the resulting protocols, the plan is to implement BigInt in terms of the generic operations defined on integers, and make BigInt itself conform to those protocols.

「現在数値型の書き直しに取り組んでいる。その次には（anInt32 += aUInt64のような）異なる型通しの演算が控えている。もう1つのゴールは、整数型プロトコルが総称的なコードを書くのに実際に役立つようにすること。実際にプロトコルに準拠したBigIntを実装するというのは、そのためのリトマス試験紙となりうる」

Swift 2.1でもできちゃいましたが、何か？

ただし、現時点で組み込まれているIntegerTypeとかはそのまま使えませんでした。見てのとおり、現在の組込みプロトコルでは、複素数のように「整数や実数のできることはほとんど何でもできるけど、比較はできない」といったような関係を反映させるのが困難だったからです。とはいうものの、ComparableやHashableといった、準拠していないと利便性があまりに下がるプロトコルは控えめに導入しています。たとえばBigIntでも(1...100).reduce(BigInt(1),combine:*)できるのは、POIntegerがRandomAccessIndexTypeでもあるからです。

次回はそんな「隠れプロトコル」を取り上げます。それがわかれば、なぜsin(1.0)と書かなくてもsin(1)で型エラーを起こさないかが見えてきます。

本誌最新号をチェック！
Software Design 2022年9月号

2022年8月18日発売
B5判／192ページ
定価1,342円
（本体1,220円＋税10%）

第1特集
MySQL アプリ開発者の必修5科目
不意なトラブルに困らないためのRDB基礎知識
第2特集
「知りたい」「⁠使いたい」「⁠発信したい」をかなえる
OSSソースコードリーディングのススメ
特別企画
企業のシステムを支えるOSとエコシステムの全貌
［特別企画］Red Hat Enterprise Linux 9最新ガイド
短期連載
今さら聞けないSSH
［前編］リモートログインとコマンドの実行
短期連載
MySQLで学ぶ文字コード
［最終回］文字コードのハマりどころTips集
短期連載
新生「Ansible」徹底解説
［4］Playbookの実行環境（基礎編）