この記事は型を実行時に作る：怖くないリフレクション（サンプルコードはHaskell）をSwiftに移植したものです。

型レベル自然数

剰余計算をする場合など、自然数に依存したデータ型を定義したいことがあります。この辺の動機付けは @taketo1024 さんの記事や SwiftyMath

を参照してください。

例えば、 Swift 以下のような感じで自然数を表す型（プロトコル）を定義できます。

protocol Nat {
    static var intValue: Int { get }
}

struct Zero : Nat { static let intValue = 0 }
struct Succ<T: Nat> : Nat {
    static var intValue: Int {
        T.intValue + 1
    }
}

typealias _0 = Zero
typealias _1 = Succ<_0>
typealias _2 = Succ<_1>
typealias _3 = Succ<_2>
typealias _4 = Succ<_3>
typealias _5 = Succ<_4>

プロトコル Nat に適合する型 T からは T.intValue という感じで整数値を取得できます。これを使って「mod m で計算する型」は、例えば次のように定義できます。

struct IntMod<m: Nat> {
    var x: Int
    init(_ x: Int) {
        self.x = x % m.intValue
    }
    static func + (_ lhs: Self, _ rhs: Self) -> Self {
        Self((lhs.x + rhs.x) % m.intValue)
    }
}

print(IntMod<_3>(5) + IntMod<_3>(2)) // => IntMod<Succ<Succ<Succ<Zero>>>>(x: 1)

いろいろ手抜きですが、そこは気にしないでください。（ちゃんとやるなら多倍長整数を使いたいところですが、ここでは簡略化のため Int を使っています）

実行時の値に基づいた型を作る

さて、普通は型と言ったらコンパイル時に決まっているものですが、実行時の値に依存した型を作りたい時があります。

例えば、筆者の「週刊代数的実数を作る」で紹介した整数係数多項式の因数分解アルゴリズムでは、入力となる多項式に応じて剰余計算の法を選びます。

週刊代数的実数を作る（#12 多項式の因数分解その4 整数係数の因数分解）

実行時の値に依存した型を作るというのは、どのプログラミング言語でもできることではありません。例えばC++やRustではそういうのは不可能でしょう。一方で、Haskellでは「型を実行時に作る：怖くないリフレクション」に書いたように、実行時の値を反映した型を構築することが可能です。

Haskellの場合でポイントとなっていたのは多相再帰でした。ではSwiftはどうなのかというと、多相再帰ができます。

例えば、次のような関数を考えます。この関数は Nat に適合する型 p に依存します。

func doSomeCalculation<p: Nat>(_: p) {
    print("doSomeCalculation \(p.intValue)")
    print(IntMod<p>(3) + IntMod<p>(2))
}

この関数を、実行時の値に基づいて呼び出してみましょう。つまり、次のような関数を定義します。

func doSomeCalculationWithDynamicVal(_ m: Int) {
    /*
       どうにかして
           doSomeCalculation(Succ<...Succ<Zero>...>())（Succがm回）
       みたいなことをしたい
    */
}

勿体ぶっても仕方がないのでコードを貼ってしまいますが、次のように書くと doSomeCalculation を値レベルの引数に基づいて呼び出せます：

func doSomeCalculationWithDynamicValRec<n: Nat>(_ acc: n, _ m: Int) {
    if m == 0 {
        doSomeCalculation(acc)
    } else {
        doSomeCalculationWithDynamicValRec(Succ<n>(), m-1)
    }
}

func doSomeCalculationWithDynamicVal(_ m: Int) {
    doSomeCalculationWithDynamicValRec(Zero(), m)
}

補助関数 doSomeCalculationWithDynamicValRec で多相再帰を行っています。与えられた型 n に対して、 Succ<n> によって自分自身を呼び出しています。C++やRustでこういうことをするとコンパイラーに怒られますが、Swiftでは怒られません。

この関数は、例えば次のように呼び出せます：

doSomeCalculationWithDynamicVal(3)
let x = Calendar(identifier: .iso8601).component(.minute, from: Date())
doSomeCalculationWithDynamicVal(x)

コンパイル時に決定しているリテラルだけではなく、実行時の日時のような動的な値に依存した計算もできることがわかります。

汎用的にする

型レベル自然数を使う処理ごとにさっきのような多相再帰を書くのは面倒です。

Haskellの場合はランク2多相があったので reifyNat :: Integer -> (forall n. (IsNat n) => Proxy n -> a) -> a みたいな関数を定義できましたが、Swiftにはランク2多相はなさそうです（あったら教えてください）。

仕方ないので、多相なメソッドを持つプロトコルを定義して、それを呼び出す関数という形で多相再帰の部分を汎用的にします。

protocol NatDependentAction {
    associatedtype Result
    func invoke<n: Nat>(_: n) -> Result
}

func reifyNatRec<n: Nat, F: NatDependentAction>(_ acc: n, _ m: Int, _ f: F) -> F.Result {
    if m == 0 {
        return f.invoke(acc)
    } else {
        return reifyNatRec(Succ<n>(), m-1, f)
    }
}

func reifyNat<F: NatDependentAction>(_ m: Int, _ f: F) -> F.Result {
    reifyNatRec(Zero(), m, f)
}

この NatDependentAction と reifyNat は、例えば次のような感じで使えます。

struct SomeCalc: NatDependentAction {
    typealias Result = Void
    func invoke<n: Nat>(_: n) -> Void {
        print("SomeCalc \(n.intValue)")
        if n.intValue != 0 {
            print(IntMod<n>(3) + IntMod<n>(2))
        }
    }
}

reifyNat(7, SomeCalc())

C++の関数オブジェクトやJavaのSingle Abstract Methodを彷彿とさせるやり方になりました。

効率化する

現在の実装では自然数の値に応じた Succ 型を使うため、例えば、法が 1000000007 だと 1000000007 回多相再帰して Succ を 1000000007 回適用することになってしまいます。これは大変非効率的です。スタックオーバーフロー待ったなしです。

実は、自然数の表し方を変えることで、再帰の深度を O(n) から O(log n) に落とすことができます。

struct Double<T: Nat> : Nat {
    static var intValue: Int {
        2 * T.intValue
    }
}
struct DoublePlus1<T: Nat> : Nat {
    static var intValue: Int {
        2 * T.intValue + 1
    }
}

func reifyNat2Rec<n: Nat, F: NatDependentAction>(_ acc: n, _ b: Int, _ m: Int, _ f: F) -> F.Result {
    if b < 0 {
        return f.invoke(acc)
    } else if (m & (1 << b) == 0) {
        return reifyNat2Rec(Double<n>(), b-1, m, f)
    } else {
        return reifyNat2Rec(DoublePlus1<n>(), b-1, m, f)
    }
}

func reifyNat2<F: NatDependentAction>(_ m: Int, _ f: F) -> F.Result {
    reifyNat2Rec(Zero(), Int.bitWidth - m.leadingZeroBitCount - 1, m, f)
}

何をしたかというと、自然数の2進展開を使いました。この方法なら reifyNat2(1000000007, SomeCalc()) も楽々表現できます。

任意の値を表す

自然数以外の値にもこの方法を適用できると便利です。

まず、自然数の有限列は1個の自然数にエンコードできるので、この方法を使えそうです。（具体的な方法はここでは割愛します。数理論理学を勉強された方には、ゲーデル数とかでおなじみのやつです）

そして、いわゆるシリアライズという操作は、オブジェクトをバイト列で表すということをやっています。バイト列というのは自然数の列なので、シリアライズ可能なオブジェクトならこの方法を適用できることになります。

シリアライズが出来なさそうなオブジェクトの場合でも、希望はあります。コンピューターの64ビットのアドレス空間に乗ったオブジェクトであれば、64ビット整数で表せるのではないでしょうか？……そう、ポインターです。ポインターを整数値として受け渡してやれば、任意の値を型レベル自然数を通して受け渡しできそうです。

残念ながら筆者はSwiftには明るくないので、この辺は読者への課題とします。