読者です 読者をやめる 読者になる 読者になる

try! Swift パーサーコンビネーター in Swift #tryswiftconf Day3-9

try! Swift 2016

Yasuhiro Inami

LINEでiOSエンジニアをしています。業務ではメッセンジャー、カメラ、ニュースといったアプリ開発に関わる一方、プライベートではReactKitやSwiftTaskといったオープンソースプロジェクトにコントリビュートしています。AppleSwiftそしてHearthstoneの大ファンです。Battle.netやGitHub: https://github.com/inamiy で出会うことができます。

twitter.com

パーサーコンビネーターは、関数型プログラミングにおける最も美しいコード記述法の一つです。JSON構文木などを簡単に生成することができます。このプレゼンテーションでは、パーサーコンビネーターが実際にどのように動作し、活用されているのか、具体例を交えて解説します。

ここから

楽しんでいますか?あと3つですね?

f:id:niwatako:20160304162917j:plain

今日は最も面白い関数型プログラミングのトピック、パーサーコンビネータの話をします。

聞いたことある方?

f:id:niwatako:20160304163127j:plain

f:id:niwatako:20160304163134j:plain

パーサーはテキストを受け取って解析します。字句解析、トークンという字句に分解します。

f:id:niwatako:20160304163207j:plain

ふたつの異なるアルゴリズムボトムアップ構文分析、トップダウン構文分析が有ります。

どのような順番で解析を行うのが良いでしょうか

下の方からツリーを形成していきます。そして最後にトップへ、パースはボトムからトップ。これがボトムアップ解析。

最上部から予想を立てつつツリーを形成するのはトップダウン

f:id:niwatako:20160304163337j:plain

アルゴリズム

f:id:niwatako:20160304163351j:plain

ここでは深掘りしません。きょうはトップダウン解析を行います。AppleSwiftのコードを読んだ方、C++で同じ方式を手続きプログラミングで解析しています。

ではコンビネータはどうでしょう。

f:id:niwatako:20160304163427j:plain

ただの関数、クロージャーと思ってもらっても構いません。複数組み合わせて面白い特性を持ちます。

f:id:niwatako:20160304163501j:plain

端的に言うと高階関数で組み合わせて大きな関数のようなものを作ります。

パーサーの中にパーサーがあってコラボレーションし、大きなパーサーに見えます、これがパーサーコンビネータ−。

 Swiftでの実装

f:id:niwatako:20160304163544j:plain

文字列を引数に受け取り結果と残りの文字列を返します。失敗することがあるので状態系モナドのOptionalを返します。

PureとEnptyを用意します。タプルを返しているのでPureは常に成功です。インプットを消費するわけではありません。

f:id:niwatako:20160304163638j:plain

Emptyは常に失敗です。

バインドはこのように掛けます。

f:id:niwatako:20160304163714j:plain

パーサーが成功したらタプルでFを適用します。これが2つ目のパーサーで、これを使って残りの入力に適用します。最初から出力がなければnilを返します。これをFlatmap演算子で、このようになります。スペシャルケースですが$ではなくキャラクタサイン(^)を使います。

選択演算子を見ていきましょう

f:id:niwatako:20160304163834j:plain

成功すればタプルを返して終了、失敗したらqを試します。

さらに3つの連続書利用のファンクションが有ります。

f:id:niwatako:20160304163941j:plain

pを使わない、あるいはq使わない用になっています。使わない方は棄却するということです。

f:id:niwatako:20160304164041j:plain

f:id:niwatako:20160304164048j:plain

どんな一文字もパース出来る、あるいは数値パーサー、あるいは特定一文字をぱーすするキャラパーサーが作れます。すべてシンプルですね。

これは複雑なパーサーです。

f:id:niwatako:20160304164120j:plain

特定文字列をパースします。

重要なパーサーでManyOneがあります。

f:id:niwatako:20160304164136j:plain

パーサーPを与えられて何度も使います。Pが最低一回成功しないと失敗します。2つが相互再帰しているのが特徴です。

SkipMany

f:id:niwatako:20160304164226j:plain

返り値がVoidになっている、意味のない結果です。しかしManyOneより効率的に実行できます。空白処理を行うことが出来るわけです。タブやラインフィード。

最後に、ナチュラルにシンボルパーサーを見てもらいます。

f:id:niwatako:20160304164317j:plain

中間パーサーが真ん中にあって、スキップパーサーにサンドイッチされています。空白をスキップして中間パーサーを提供して、スキップ。 空白ではなくストリングだけを見ている、ハンバーガーのようなものです。

両側にパンがあって美味しいお肉やチーズ、野菜がある、この部分が大事ですよね。ハンバーガーみたい。

いろんなパーサーの話をして来ました。

f:id:niwatako:20160304164447j:plain

3行や1行のものが有りました。

簡単な遊びができます。

f:id:niwatako:20160304164514j:plain

自然数のみの計算機を作ることが出来ます。

f:id:niwatako:20160304164536j:plain

一行で、実際には3行かも知れませんが、シンプルですね

f:id:niwatako:20160304164557j:plain

うまくいきますね?このスライドによると。

f:id:niwatako:20160304164620j:plain

1歳の子供でも解けそうな計算ですね!もっとかっこいいことがしたいですか?私は少なくともそうです。

安心して下さい。もう一つ有ります。

小さなライブラリを作りました。楽しいですよ。

f:id:niwatako:20160304164707j:plain

f:id:niwatako:20160304164716j:plain

このカンファレンス用のノマディックパーサコンビネータ−です。

TryParsecはdo try catch なんて使っていない名前的にはインチキライブラリですが、遊んでみてください。後で公開します。私の話を聞きに来たのでしょう?

ぜひ見てみて下さい。

f:id:niwatako:20160304164853j:plain

どのように動くのでしょうか

f:id:niwatako:20160304164916j:plain

これをどうパースするのでしょう

f:id:niwatako:20160304164928j:plain

自動でJsonenumツリーを得られます。

f:id:niwatako:20160304164945j:plain

標準JSONパース機能など使わず、ピュアSwiftで動いています。

カスタムモデルとしてこれらを使いたいわけですからJSONデコーディングとエンコーディングがほしいです。

Swiftに20,30のライブラリが有りますので、JSONデコードもEncodeも出来ます。

Structモデルを用意しマッピングします。

f:id:niwatako:20160304165045j:plain

JsonStringには無いが、意図的に加えたものが有ります、一番下。

そのまえにやるのは、fromJSONObjectに準拠することです。

f:id:niwatako:20160304165110j:plain

このような変わったものを十曽します。アプリカティブスタイルですね。アルゴ、を試したことがあれば、これはそれと同じように機能します。

f:id:niwatako:20160304165154j:plain

エンコードは?

f:id:niwatako:20160304165209j:plain

f:id:niwatako:20160304165221j:plain

まとめ

f:id:niwatako:20160304165230j:plain

まだ公開していませんがオープンソースでお試しいただけます。シンプルで、皆さんで簡単に作れます。Playground付きで遊べます。

注意点が有ります。パフォーマンスがNSJsonSeriarizationとくらべて遅いです、マッピングも制約があり、他のライブラリでも制約はあります、Swiftの制約のため。

そういったことから、JSONからそういったパフォーマンス面での遅いということ。

Swift3で問題は解決されると思っています。OpenSourceで毎日の業務に関係し、ここにこのようにコミュニティがあるからです。Swiftの改善と向上に期待し、私のライブラリも改善したいと思います。

f:id:niwatako:20160304165439j:plain

QA

どちらか答えて頂ければ。サポートは有りますか?パース失敗のエラーの場合。2つ目は、toJson

Printingは実装していません。パフォーマンスが既に悪いので改善してからエラーレポーティングに入って行きたいと思っています。

気に入った記事は はてなブックマーク

はてなブックマークアプリiOS開発チームから来ました! はてなブックマークにはSwift特集があります! 良い記事を見逃さないように、ご利用ください! http://b.hatena.ne.jp/hotentry/it/Swift

そして良いまとめ記事があったらはてなブックマークでブックマークしましょう! try! Swift の記事で盛り上がると嬉しいです!