Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Swift で filter や map 、flatMap などのコンビネータを実装してみる

今年の言語として Swift を選んで最近練習しています。Swift は iOS を作るために使用されることが多いですが、言語としての表現力が非常に豊かで、たとえば Web アプリケーションのサーバーサイド開発に利用できるのではないかと思っています。まだ Swift を学び始めでランタイムなどには詳しくないので、どこまでいけるのかはわかっていません。が、可能性を感じます。

新しい言語を学ぶ際にやることはいくつかあるのですが、型の表現が豊かそうな言語であればまっさきにやるのは「連結リストを作ってモナドっぽいものを足してみる」です。Swift にはジェネリクスがあるほか、言語に組み込みで Optional などの型が存在しており、それなりに型の表現力があるのではないかと感じました。なので、試してみました。

結論としては、

  • 連結リストは結構気持ちよく書ける上に、言語特有のおもしろい機能があるようです。
  • Swift には高カインド型（HKT）がサポートされていないのでモナドは実装できません。
  • Swift には検査例外があるので、それを考慮した実装にする必要がありそうです。

といったところでしょうか。

この記事は Swift を書き始めてまだ24時間経った程度の超初心者が書く記事です。したがって、各所に誤りを含む可能性があります。その点を留意してご覧ください。

実際に書いてみる

連結リストを作る

まずは連結リストを作ってみましょう。連結リストの概観がわからない方はこちらをご覧ください。

Swift では enum を使って次のように書くことができます。これは他の Rust や Scala 3 などとほぼ同じような記法で、後ほどパターンマッチングで中身を取り出せる点も同じです。

enum List<T: Equatable> {
    indirect case cons(head: T, tail: List<T>)
    case `nil`
}

Swift では nil は予約語です。なので、バッククオートで囲む必要があります。

注目すべきなのは indirect で、これは再帰的な enum （Recursive Enumerations）を作る際に使用するキーワードです。このキーワードを付与すると、ヒープ領域が確保され値がそこにコピーされるという動作が行われるようです*1。このケースの場合、cons が確保する必要のあるメモリサイズがわからないため、残念ながらスタック領域を使用したメモリの確保が難しくなります。そのため、ヒープ領域に値を確保することにしているといったところでしょうか*2。

Swift のメモリ管理

indirect キーワードの裏側を理解するためには、Swift における値型と参照型の違いの理解を必要とします。Swift には enum や struct といったキーワードを代表とする値型と呼ばれる概念と、class といったキーワードを代表とする参照型という概念があります。この2つの理解は、Swift のメモリモデルの理解につながってきます。

値型は、変数の値が参照ではなく直接値をもつ型のことをいいます。変数や定数に値を代入されたときや、引数として渡された際に値のコピーが裏で走り、新たにメモリ領域が確保されます。値型には struct と enum が該当しますが、これらの所有者は常に1つであることが保証されている型です。値型は再帰的なデータ構造をもつことは、コピー時に確保すべきメモリ領域が不明であることからできません。

参照型は、変数の値への参照をもつ型のことをいいます。値型とは異なり、変数や定数に値を代入された際や、引数として渡された際には、既存のインスタンスへの参照が渡されます。参照型には class が該当します。

値型は、使用されなくなるとすぐに確保されていたメモリ領域が解放されます。これは値型を使用するひとつのメリットになりえます。

参照型の方については、メモリ管理に ARC という仕組みが利用されます。要するに参照カウンタが後ろにいて、ある参照型への参照がどの程度残っているかをチェックしています。カウントがゼロになれば、その参照型が確保していたメモリ領域は解放されるという仕組みです。参照カウンタを利用している以上、循環参照によるメモリリークのリスクと隣り合わせであり、要するに注意して使う必要がありそうということがわかります。

値型は都度コピーコストが発生しますが、Swift はコレクションに対しては Copy on Write という最適化を適用するようです。これにより、評価が必要になるまでコピーを行わないという方式をとっているようです。*3

値型と参照型の使い分けは、調べた限りではケースバイケースの微妙な使い分けをはらんでいるようです。他の言語でもそうですが、局所的に参照をもたせてスコープを狭めながら使うのがよさそうです。Swift の標準ライブラリを読むと struct を基本にデータ構造を設計していることから、基本は struct 中心に構築していくものだと思います。使い分けについてはこちらの資料がわかりやすいです。

最後に、この enum は下記のようにして呼び出すことができます。

let list = List.cons(1, List.cons(2, List.cons(3, List.cons(4, List.`nil`))))

便利プロパティを生やす

プロパティをいくつか生やしていきます。プロパティとは、型に紐付いた値のことです。空判定や先頭の取り出しなどを定義していきます。

extension List {
    var isEmpty: Bool {
        return self == .`nil`
    }
    
    var head: T? {
        switch self {
        case .`nil`:
            return nil
        case .cons(let h, _):
            return h
        }
    }
    
    var tail: List<T>? {
        switch self{
        case .`nil`:
            return nil
        case .cons(_, let t):
            return t
        }
    }
    
    var len: Int {
        switch self {
        case .`nil`:
            return 0
        case .cons(_, let t):
            return 1 + t.len
        }
    }
    
    var first: T? {
        return self.head
    }
    
    var last: T? {
        switch self {
        case .`nil`:
            return nil
        case .cons(let h, .`nil`):
            return h
        case .cons(_, let t):
            return t.last
        }
    }

実装内容そのものは他の言語と変わりありませんが、いくつか注目すべきポイントがあります。 extension キーワード、 switch 文、そして Computed Property です。

extension キーワードは、すでに存在する型に対してプロパティやメソッド、イニシャライザなどの型を構成する要素をあとから追加できる機能です。型を拡張することができます。Scala などでは enrich my library という技法で親しまれていたほか、Scala 3 では extension キーワードが同じく使えるようになっています。内実はああいった機能と似ています。今回 enum への実装は extension を使って追加しています。

switch 文は Java や C などにある同等の機能とよく似ています。違いとしては、パターンマッチングができる点だと思います。switch 文を使いながら enum のヴァリアントに応じて処理を記述できます。なお、Swift では switch は文であることに注意が必要です。

Computed Property はアクセスがあるたびに毎回計算が走るプロパティです。計算元との値の整合が常に取れるという特徴があります。Swift に数あるプロパティのひとつです。Swift にはこの他にも Stored Property というものがあります。上の例では、isEmpty や len などが Computed Property として定義されています。

高階関数を書く

まだ関数の話もしていませんが、飛び石して高階関数を書いていきます。高階関数を書くためには、まず関数定義とクロージャーが必要です。Swift では、関数定義は func というキーワードで定義できます。クロージャーも言語機能として提供されています。

filter, map, flatMap などのコンビネータは、foldr という関数を使うことですべて実装可能です。foldr 関数を実装した後に各コンビネータを実装するという流れで実装していきます。

// extension の続き
    func foldr<U>(acc: U, f: (T, U) -> U) -> U {
        switch self {
        case .`nil`:
            return acc
        case .cons(let h, let t):
            return f(h, t.foldr(acc: acc, f: f))
        }
    }
    
    func map<U>(f: (T) -> U) -> List<U> {
        return self.foldr(acc: List<U>.`nil`, f: { acc, list in
            return List<U>.cons(head: f(acc), tail: list)
        })
    }
    
    func flatMap<U>(f: (T) -> List<U>) -> List<U> {
        return foldr(acc: List<U>.`nil`, f: { acc, list in
            return f(acc).append(another: list)
        })
    }
    
    func filter(p: (T) -> Bool) -> List<T> {
        return foldr(acc: List<T>.`nil`, f: { acc, list in
            if p(acc) {
                return List.cons(head: acc, tail: list)
            }
            return list
        })
    }

クロージャーの記法ですが、仮引数の際は (遷移元型) -> 遷移先型 で書くことができます。実引数として渡す場合には記法が変わり、{ 一時変数名 in 処理内容 } となるようです。他の言語では仮引数でも実引数でも記法がだいたい一致していると思いますが、Swift は異なるので注意が必要そうです。

ソースコードは下記にあります。

github.com

Swift 本体のコードを少し読んでみる

モナドにするのは厳しそうなことはわかったのですが、今度は Swift 本体がどのように Functor 等を構築しているのかが気になってきました。少し読んでみたのでそのことについて書きます。ただ、今回目を通したのは Optional 型だけなので、もしかすると見落としているかもしれません。

github.com

検査例外の存在

たとえば Optional の Map の実装は次のようになっています。

  @inlinable
  public func map<U>(
    _ transform: (Wrapped) throws -> U
  ) rethrows -> U? {
    switch self {
    case .some(let y):
      return .some(try transform(y))
    case .none:
      return .none
    }
  }

完全に見落としていたのですが、Swift には検査例外があります。throws や rethrows は検査例外があるがゆえの記述です。今回作ったリスト構造と付随するコンビネータを本番で使えるコードにするためには、高階関数であってもエラーの可能性を考慮した実装にする必要があるようですね。

throws はエラーを送出する可能性があることを示すキーワードです。Java につける同等のキーワードと同じ役割を果たしています。

rethrows は、引数のクロージャーが発生させるエラーを呼び出し元へ伝播させるためのキーワードです。これは Java にはなく、Java でラムダ式を実装した際には、例外をハンドリングできる自前のインタフェースを用意して対処した記憶があります。便利なキーワードです。

最後に try キーワードですが、これはエラーを発生させる可能性がある処理を実行するために使用します。つまりこの場合は、transform という関数はエラーを発生させる可能性がある処理だ、ということがわかります。実際、transform の型シグネチャは transform: (Wrapped) throws -> U ですから、これはエラーを発生させる可能性がある関数です。

Swift における2種類のエラーハンドリング

Swift はこれまで検査例外一筋だったようです。ただ、Swift の検査例外は Java のそれと比較するとかなり改善されているようです。実際、私も map 関数のコードを読んで各キーワードを軽く調べてみましたが、Java のそれと比べると使い心地も安全性も向上しているように思われます。

Swift には他にも、Swift 5.0 以降から利用できる Result 型が入ってきているようです。Rust の Result 型と使い方にほぼ差はありません。ただ、既存の検査例外との共存や使い分けが少々難しそうに見えました。Swift の Result 型は、現在のところ非同期的な処理のエラーハンドリングに利用されることが想定されているようです。

あまり抽象化はされていない

map 関数やその他の関数も読んでみましたが、どうやら Functor のような型を新たに作ってそちらに処理を集約させるといったことはしていないように思われました。

他にも配列の map や flatMap の実装も読んでみましたが、個別実装されています。

Swift を触った感想

  • 言語仕様はかなり野心的である一方、そうした野心的な機能を快適に利用できるようにする実用性も兼ね備えていると思いました。また、暗黙的に裏で言語のランタイムが気を利かせて何かをやらないようにしている感じがしており、明示的にキーワードを指定する必要があるのもよかったです。加えてたとえば、Int + Double の演算は暗黙的にはできません。どちらかを明示的にキャストする必要があります。
  • 触って24時間程度ですが、今のところびっくりするような挙動はありません。書いたら書いたとおりに動きますし、書いた以上のことはしません。これは極めて重要だと思います。資料を読んでいると参照型のあたりが少しびっくりするかもしれない予感がしていますが…。
  • iOS 開発に関連する Swift の情報はかなり充実している一方で、私のような道を外れた Swift の使い方をするための情報はなかなか Google さんが上に出してくれず、苦戦しました。最初 Xcode でどうやって素の Swift コードを動かすか、やり方がわからずまとめました…→Swift で iOS や MacOS アプリではない開発をはじめる
  • メモリの確保の仕方を厳密に定義しようと思えば、それなりにできそうなところはよいところだと思います。
  • mutability / immutability を明示的に管理できそうなところもよいポイントだと思います。
  • キーワードがとにかく多いです。もちろん特定の状況下でのみ有効になるキーワードもあるから一概には言えませんが、予約語が多くて、普段使っている変数名や関数名が不意にキーワードになってコンパイルエラーになったりします。ただこれは、ユーザーにとっては嬉しいかも。特定の機能を呼び出すために型パズルを作るか、増えたキーワードを覚えるかは言語のスタンスによりそうです。
  • 型推論はそこまで強くないように思いました。Scala 2 と同じくらいの強さかなと言う感じがします。サンプルで載せたコードをご覧いただいてもわかるとおり、比較的型注釈を必要とする傾向にあると思います。

*1:余談ですが、古い Swift のスナップショットでは Rust と同じように Box を使ってヒープ領域を確保していたように見受けられます。Swift をはじめて触った感想は「とにかく特殊な場面向けのキーワードが多いな」といったでした。Box 型も、言語のアップデートによって indirect キーワードに変わっていったようです。特殊な用途ごとに型ではなくキーワードを用意する――これはある種の Swift の設計思想なのでしょうか。参考: https://airspeedvelocity.net/2015/07/22/a-persistent-tree-using-indirect-enums-in-swift/

*2:このあたりを説明している資料を相当数探してみたが、見つけられませんでした。どこかにあるのだろうか。

*3:具体的な動きは下記の記事がわかりやすいです: https://medium.com/@lucianoalmeida1/understanding-swift-copy-on-write-mechanisms-52ac31d68f2f