Parser Combinators in Swift

パーサコンビネータは、関数型プログラミングにおける最も美しいコード記述法の一つです。基本的な構文を解析する小さなパーサを組み合わせて、複雑で実践的なパーサを構築できます。JSON構文木などを簡単に生成することができます。try! Swiftのこの講演では、パーサコンビネータが実際にどのように動作し、活用されているのか、という具体例を交えて解説します。


概要 (00:00)

稲見泰宏です。メッセンジャーアプリのLINEで働いています。世界中から大勢の素晴らしい開発者が集まる中、try! Swiftという大きな舞台でスピーカーをさせていただくことに、とても光栄に思います。 今日は関数型プログラミングにおける最も面白いトピックの1つである、パーサコンビネータについてお話しします。

パーサコンビネータ (01:06)

パーサ (01:24)

パーサは文字列から構文木を作る解析器です。長い文字列をトークンと呼ばれる小さなかたまりに変換するレキサ(字句解析器)と、トークンを取得して構文木を作るシンタックスアナライザ(構文解析器)の2つで構成されます。

ボトムアップ、トップダウン (02:25)

構文解析の方法は主に2つあります。ボトムアップ構文解析とトップダウン構文解析です。

例えば一番下にA = B + C * 2 ; D = 1という文字列があります。どのような順番で解析を行うのが良いでしょうか?

ボトムアップ解析では、下部の文字列からスタートして、読み進めていくうちに、下の方からツリーを徐々に形成していきます。

トップダウン構文解析では、全体を見渡して、どのタイプのツリーを構築していくのが良いか、最上部で予想を立てて、徐々に下降しながら予想を立てつつツリーを形成していく、というものです。

構文解析アルゴリズム (03:35)

パーサコンビネータはこのトップダウンパーサに頼ります。AppleのSwiftコードを読んだことがあればそのコードがあります。同じ技術がC++で書かれています。DSLのない、手続き的プログラミングで構文解析をしています。

コンビネータ (04:12)

下記は、コンビネータロジックと呼ばれるものです。

I = λx.x = { x in x }
K = λxy.x = { x, y in x }
S = λxyz.xz(yz)
  = { x, y, z in x(z)(y(z))}
Y = S(K(SII))(S(S(KS)K)(K(SII)))
ι = λx.xSK

とりあえずはただの関数 (Swiftではクロージャ)と考えて構いません。これらを組み合わせるとさらにおもしろい性質を持つようになります。

パーサコンビネータ (04:48)

端的にいうと、パーサーコンビネーターとは高階関数のことで、複数のパーサを組み合わせて、新しいパーサを作る関数です。スライドにあるようにふたつのパーサが合わさって機能します。

Swiftによる簡単なパーサの実装 (05:23)

それでは、Swiftで簡単なパーサーを作ってみましょう。

パーサモナド (05:33)

struct Parser<A> {
    let parse: String -> (A, String)?
}

Parserという簡単な構造体を用意します(これはParser<A>というジェネリクスです)。クロージャのコンテナです(let parse)。文字列を入力してこの場合はタプルを出力します。タプルは”output”と”remaining input”を持ちます。パースが失敗することがあるのでオプショナルを使います。

この構造はモナドと呼ばれ、モナドやオプショナルのモナドを組み合わせることもできます。そして、ここから、モナド祭りです!もしモナドについてご存知なかったら、あまり深く考えず、祭りだと思ってください。

Applicativeなpure関数, Alternativeなempty関数 (06:27)

// Applicative pure
func pure<A>(a: A) -> Parser<A> {
    return Parser { (a, $0) }
}

// Alternative empty
func empty<A>() -> Parser<A> {
    return Parser { _ in nil }
}

pure関数は単にパーサをインスタンス化します。後にクロージャを評価し、タプルを返します。常にタプルを返すのでパースは必ず成功します。そして入力を消費しません(これについては後述します)。empty関数は常にnilを返します。つまり必ず失敗するパーサです。

モナドなbind、ファンクタなfmap (07:05)

// Monad bind (>>=)
func >>- <A, B>(p: Parser<A>, f: A -> Parser<B>) -> Parser<B> {
    return Parser { input in
        if let (result, input2) = p.parse(input) {
            return f(result).parse(input2)
        } else {
            return nil
        }
    }
}

// Functor fmap (<$>)
func <^> <A, B>(f: A -> B, p: Parser<A>) -> Parser<B> {
    return p >>- { a in pure(f(a)) }
}

まず入力を受け取り、クロージャを見ると入力が引数として渡されます。パーサpでパースします。パースが成功すればタプルが返り、resultを取り出してfを使います。fは2つ目のパーサの結果です。メイン入力にパーサを使います。この場合はinput2です。最初のパーサが失敗すればnilを返し、全体のパーサが失敗します。最初のパースが失敗するからです。

このfmapオペレータを使えばFunctor fmapを取得できます。Swiftでは$を使わず代わりに^を使います。カスタムオペレータとして$は使えません。

First, you receive the input, you see the closure, and the input is passed as an argument. You parse that with the given parser p. If that parsing succeeds: you get a tuple of it, you extract the result part, and apply f. And that f is the result of the second parser. You use that parser for the main input, in this case, input2. Otherwise, if the first parser fails in the first place, you would just return nil. That means the whole parser fails (because the first parsing fails).

記事の更新情報を受け取る

Once you have this fmap operator, you can immediately get the functor fmap. In Swift, we do not use $, instead we use a ^ sign (we cannot use $ for the custom operator).

Alternativeなchoice演算子 (08:18)

// Alternative choice (associative operation)
func <|> <A>(p: Parser<A>, q: Parser<A>) -> Parser<A> {
    return Parser { input in
        if let (result, input2) = p.parse(input) {
            return (result, input2)
        } else {
            return q.parse(input)
        }
    }
}

パーサpqがあり、まずpを試します。パースが成功すればタプルを返し、失敗すれば代わりにqを試します。

You have a parser p and q, you try parser p first. If that parsing succeeds, then finish, and you return that tuple. If it fails, you try q instead.

Applicativeな連続処理の演算子 (08:48)

次の3つは、Applicative(アプリカティブ)で重要な連続処理の演算子です。

// Applicative sequential application
func <*> <A, B>(p: Parser<A -> B>, q: Parser<A>) -> Parser<B> {
    return p >>- { f in f <^> q }
}

// Sequence actions, discarding the value of the second argument
func <* <A, B>(p: Parser<A>, q: Parser<B>) -> Parser<A> {
    return const <^> p <*> q
}

// Sequence actions, discarding the value of the first argument
func *> <A, B>(p: Parser<A>, q: Parser<B>) -> Parser<B> {
    return const(id) <^> p <*> q
}
  • 1つ目はモナド構造のファンクションアプリケーションです。

  • 2つ目は(矢印が左を差すような)シーケンスアクションです。パーサpqの両方を使います。ただpの出力の左側だけを使ってqの出力は破棄されます。

  • 最後は逆です。パーサpqを試します。2つ目と同じですがqの出力だけ使ってpは使いません。

  • The first one is a function application for monadic structure.

  • The second one is a sequence action (it looks like an arrow pointing to the left). It tries parser p then q; it uses both. But only uses the left side of the output of p; it discards the output of q.

  • The last of our operators is the opposite. We try parser p then q. It is the same as before, but it only uses the output of q (not p).

1文字のパース (10:08)

func satisfy(predicate: Character -> Bool) -> Parser<Character> {
    return Parser { input in
        if let (head, tail) = uncons(input) where predicate(head) {
            return (tail, head)
        } else {
            return nil
        }
    }
}

私が実装した基本的なsatisfyパーサです。入力をチェックします。uncons関数を使ってheadtailに分解します。predicateでheadをチェックして成功すればタプルに分解され、できなければ失敗します。

また文字をパースするany()パーサを作ることもでき、数字や特定の文字だけをパースするdigit()パーサやchar(c: Character)パーサを作ることもできます。読みやすくてシンプルです。

Here is the satisfy parser I implemented (it is fundamental). It examines the input. You decompose it using the uncons function, it is the head and tail. Examining the head part with a predicate: if that predicate succeeds, you get the decomposed tuple; otherwise, the poor parser fails.

You can also create any() parser (can parse any character), or digit() (can only parse the numeric number, and numeric character, or some specific character), and char(c: Character) parser. It is readable, simple:

func any() -> Parser<Character> {
    return satisfy(const(true))
}

func digit() -> Parser<Character> {
    return satisfy { "0"..."9" ~= $0 }
}

func char(c: Character) -> Parser<Character> {
    return satisfy { $0 == c }
}

文字列のパース (11:09)

簡単に言えば特定の文字列をパースします。文字列でなければ失敗します。

In short, this is parsing the specific string. Otherwise it fails.

func string(str: String) -> Parser<String> {
    if let (head, tail) = uncons(str) {
        return char(head) *> string(tail) *> pure(str)
    } else {
        return pure("")
    }
}

パーサを組合せる (11:29)

manymany1と呼ばれる重要なパーサです。パーサpを与えると何度も使います。まずmanyパーサはパーサpを0回から複数回使って失敗はしません。many1パーサは少なくとも1回はpを使いますが失敗することがあります。これらは相互再帰です。

Here are some important parsers called many and many1. The parser p is given, and they use that parser p many times. The first many parser uses the parser p from zero occurrence to many occurrences, and it never fails. The many1 parser must be able to parse at least one occurrence of p, otherwise it fails. They are mutually recursive.

func many<A>(p: Parser<A>) -> Parser<[A]> {
    return many1(p) <|> pure([])
}

func many1<A>(p: Parser<A>) -> Parser<[A]> {
    return cons <^> p <*> many(p)
}

スキッピングパーサのskipManyskipMany1です。manymany1と似ていますが、resultが空で無意味な出力である点に注意します。

このパーサを使うのと似ていますがmanymany1より効率的でパフォーマンスがよいです。そしてskipSpacesが重要です。ご覧のようにskipSpaces()はパースするときによく使われます。スペースをスキップしますが先頭や最下部の行は扱いません。

Here are skipping parsers: skipMany and skipMany1. It looks similarly to the previous many and many1, but notice that the result part is now an empty void, an empty tuple (meaningless output).

It seems similar to using this parser for the grounds, but it is more efficient, it has better performance than many and many1. And we can implement important particles, skipSpaces. As you can see, the implementation skipSpaces() is common when we want to parse things. We want to skip spaces, but we do not care whether it is top or line with feet.

func skipMany<A>(p: Parser<A>) -> Parser<()> {
    return skipMany1(p) <|> pure(())
}

func skipMany1<A>(p: Parser<A>) -> Parser<()> {
    return p *> skipMany(p)
}

func skipSpaces() -> Parser<()> {
    return skipMany(space)
}

トークンのパース (13:07)

symbol(str: String)natural()パーサを追加しましょう。skipSpaces()によってサンドイッチ🍞のようにはさまれた中間のパーサがあることに気づくかもしれません。Applicativeでこれを示すオペレータは好きではありません。まず先頭のスペースをスキップし、中間のパーサが機能して最後に末尾のスペースをスキップします。しかし中間のパーサの出力だけを使います。スペースは扱いません。ハンバーガーのように🍔文字列だけを扱います。symbolパーサでは美味しい肉のようなstringパーサを扱います。naturalパーサではstringからintegerへ変換するまたハンバーガーのような!many1(digit()))を扱います。たった3行だけです。1行で書けるときもあります。

Let’s add symbol(str: String) and natural() parsers. You might notice that there is a middle parser in the middle that is sandwiched 🍞 by skipSpaces() parser. With applicative, I do not like operators pointing this direction. It first skips the head white space, then uprising middle parser, and lastly, skips the tail space. But it only uses the output of the middle parser. It does not care about the spaces, it only cares about the string (like a hamburger! 🍔). For the simple parser, the relevant (delicious) part (meat) is a string parser. For natural parser, the relevant part is many1(digit())) (again, like a hamburger!), which converts the result party from string to integer. Only three lines, sometimes one line of code.

func symbol(str: String) -> Parser<String> {
    return skipSpaces() *> string(str) <* skipSpaces()
}
func natural() -> Parser<Int> {
    return skipSpaces() *>
    ({ Int(String($0))! } <^> many1(digit()))
    <* skipSpaces()
}

Let’s Play (14:40)

+*記号、かっこ、自然数を使って簡単な計算をしましょう。

Let’s use the + and * signs, parentheses, and natural numbers to make a simple calculator.

簡単な数学 (14:59)

次の数学的な表現はバッカス・ナウア記法(BNF)といいます。

The mathematical expression below is called Backus–Naur Form (BNF):

<expr> ::= <expr> + <term> | <term>
<term> ::= <factor> * <term> | <factor>
<factor> ::= ( <expr> ) | <number>
<number> ::= '0' | '1' | '2' | ...

パーサではよくある実装で、Swiftで次のように実装します。

It is common when you do parsing. In Swift, our first language, we implement the following:

func expr() -> Parser<Int> {
    return term() >>- { t in // uses right recursion
        (symbol("+") *> expr() >>- { e in pure(t + e) }) <|> pure(t)
    }
}

func term() -> Parser<Int> {
    return factor() >>- { f in
        (symbol("*") *> term() >>- { t in pure(f * t) }) <|> pure(f)
    }
}

func factor() -> Parser<Int> {
    return (symbol("(") *> expr() <* symbol(")")) <|> natural()
}

右再帰を使いましたがほぼ1行、もしくは3行程度で書けます。ちょっと変ですがシンプルです。では計算してみましょう。

I used the right recursion, but you can write it in almost one line. Less than three or maybe some more lines. A bit weird, but it is still simple. Here goes the calculation:

let (ans, _) = expr().parse(" ( 12 + 3 )    * 4+5")!
expect(ans) == 65

12 + 3, save on space plus 4+5 is expected to be equal to 65… and it works! 💪

さらに複雑な例: TryParsec (16:58)

TryParsecを開発しました。try! Swiftのために作ったモナドのパーサコンビネータです。Haskell、特にAttoparsecAesonというライブラリを参考にしています。CSV、XML、JSONをサポートしています。技術的にはデフォルトでバックトラッキングを使ってLL(*)をパースできます。このTryparsecはSwiftのdo-catchを使っていません。実際に何かをtryしていないですし、tryというキーワードを使ってないですがtryしてください。try! Swiftですからね。このライブラリはまだオープンソースではないですが、try! Swiftのあとで公開します。

これらがTryParsecの関数です。

  • Basic Operators: >>-, <^>, <*>, *>, <*, <|>, <?>

  • Combinators: many, many1, manyTill, zeroOrOne, skipMany, skipMany1, sepBy, sepBy1, sepEndBy, sepEndBy1, count, chainl, chainl1, chainr, chainr1

  • Text (UnicodeScalarView): peek, endOfInput, satisfy, skip, skipWhile, take, takeWhile, any, char, not, string, asciiCI, oneOf, noneOf, space, skipSpaces, number… (など)

For those who want more on parsing, I developed TryParsec. It is a monadic parser combinator for this try! Swift conference (nowhere else!). It is inspired by Haskell, and especially the Attoparsec and Aeson libraries. It supports CSV, XML, and JSON. Technically, it can parse LL(*), with backtracking by default. This library is not using the do track catch in Swift. This Tryparsec… does not actually try anything, it does not use any try keywords, but please try it (because this is the try! Swift conference). This library is not open source yet (I will, right after this conference).

Here are some functions of TryParsec:

  • Basic Operators: >>-, <^>, <*>, *>, <*, <|>, <?>

  • Combinators: many, many1, manyTill, zeroOrOne, skipMany, skipMany1, sepBy, sepBy1, sepEndBy, sepEndBy1, count, chainl, chainl1, chainr, chainr1

  • Text (UnicodeScalarView): peek, endOfInput, satisfy, skip, skipWhile, take, takeWhile, any, char, not, string, asciiCI, oneOf, noneOf, space, skipSpaces, number… (etc)

JSONのパース (19:02)

TryParsecがJSONを使ってどのように機能するか見てみましょう。

Let’s see how this TryParsec works with JSON.

enum JSON (19:12)

enum JSON {
    case String(Swift.String)
    case Number(Double)
    case Bool(Swift.Bool)
    case Null
    case Array([JSON])
    case Object([Swift.String : JSON])
}

TryParsecでは一般的なenum JSONを組み込んでいます。たとえばJSONはどのようにパースしますか?parseJSONを呼ぶだけでJSONの列挙型の木を取得します。シンプルで簡単です。

In TryParsec, the enum JSON is already built in (common, basic type). Let’s say we have a JSON String, how do we parse? All we need to do is call parseJSON, and you immediately get the JSON enum tree. Simple, easy.

JSONの例 (19:21)

{
    "string": "hello",
    "num": 123.45,
    "bool": true,
    "null": null,
    "array": ["hello", 9.99, false],
    "dict": { "key": "value" },
    "object": { "enabled": true }
}

JSONをパースしてASTへ (19:30)

let json = parseJSON(jsonString).value
print(json)

このプロセスではNSJSONSerializationやほかのオブジェクトは使いません。すべてSwiftで書かれていますがこの構造はおもしろくありません。これは中間表現です。マッピングするためのカスタムモデルがほしいですよね。みなさんが大好きな❤️JSONのデコードとエンコード機能が必要で、Swiftには20〜30ほどのライブラリがあります。TryParsecは31番目のライブラリです。💯

In this process, I do not use any NSJSONSerialization, or any object that is not involved in this process. It is all written in pure Swift. But we are not interested in this structure. This is an intermediate representation. We want our custom model to be mapped to it. We need JSON decoding and encoding features (which we all love ❤️), and Swift has about 20-30 libraries for doing so. Fortunately, TryParsec, is the 31st JSON decoding and encoding library. 💯

JSONのデコード (19:54)

struct Model (20:38)

JSONの例です。一番下にlet dummyを追加しました。JSONはこのフィールドを持ちませんが追加しています。

We saw the JSON string example, and we have model mapped this one. In the bottom I added a let dummy. The JSON string does not have this field, but I added it.

struct Model {
    let string: String
    let num: Double
    let bool: Bool
    let null: Any?
    let array: [Any]
    let dict: [String : Any]
    let subModel: SubModel
    let dummy: Bool?  // doesn't exist in raw JSON
}

FromJSONプロトコル (21:02)

FromJSONプロトコルに準拠して実装する必要があります。static func fromJSONを実装し、fromJSONObjectヘルパを使います。これはApplicativeスタイルの一般的な記法です。ArgoというJSONライブラリを試したことがあれば、TryParsecでも同じ技術を使います。decode関数を呼んでマッピングされたResultを取得します。

You have to implement the conformance to the FromJSON protocol. You implement the static func fromJSON, and you use the helper message code fromJSONObject. This is common writing code applicative style. If you have ever tried the JSON library called Argo, TryParsec uses the same technique. Call function decode, and you get the mapped result.

extension Model: FromJSON {
    static func fromJSON(json: JSON) -> Result<Model, JSON.ParseError> {
        return fromJSONObject(json) {
            curry(self.init)
                <^> $0 !! "string"
                <*> $0 !! "num"
                <*> $0 !! "bool"
                <*> $0 !! "null"
                <*> $0 !! "array"
                <*> $0 !! "dict"
                <*> $0 !! "object" // mapping to SubModel
                <*> $0 !? "dummy"  // doesn't exist in raw JSON
        }
    }
}

… シンプルですね。

… simple.

JSONエンコード (21:55)

ToJSONプロトコル (22:03)

JSONエンコードにはToJSONプロトコルに従ってtoJSONObject関数を使い、keyとvalueを渡します。

For JSON encoding, conform to the ToJSON protocol, use the function toJSONObject, and pass the array of the key-value pairs.

extension Model: ToJSON {
    static func toJSON(model: Model) -> JSON {
        return toJSONObject([
            "string" ~ model.string,
            "num" ~ model.num,
            "bool" ~ model.bool,
            "null" ~ model.null,
            "array" ~ model.array,
            "dict" ~ model.dict,
            "subModel" ~ model.subModel
        ])
    }
}

オブジェクトをJSONにエンコード (22:13)

encode関数を使ってjsonStringを返します。

Call the function encode, and you immediately get back the jsonString.

let jsonString = encode(model)
print(jsonString)

まとめ (TryParsec) (22:24)

TryParsecはJSON、CSV、XMLをサポートしています。シンプルで読みやすく簡単にパーサを作れるのでぜひ試してください。。またXcode playgroundを備えていていろいろ試すことができます

しかしいくつか注意点があります。

  1. NSJSONSerialization と比較してまだパフォーマンスがよくありません。
  2. FromJSON / ToJSON プロトコルには制約があり、Argoなどのすばらしいライブラリには制約があります。今のSwiftに制約があるからです。FromJSON / ToJSON はネストした構造では機能しません。

Swiftは新しいオープンソースで日々進化する素晴らしいコミュニティです。Swift 3でこれらの問題が解決されることを願っています。

私のライブラリを使ってみて改良を手伝っていただけるとうれしいです。

TryParsec supports JSON, CSV and XML. It is simple, readable, and easy to create your own parsers (please try it). I also have the Xcode playground (you can also play around with it).

But let me point out some caveats:

  1. It does not have good performance yet (compared to NSJSONSerialization).
  2. FromJSON / ToJSON protocols (the mapping) are limited. Any library (Argo and other great libraries) has limitations… because Swift is currently limited. FromJSON / ToJSON does not work in some nested structures.

Hopefully, Swift 3 will solve these problems. Swift is now open source, it is evolving every day, and we have a great community.

Please check out my library, and help me improve the code base.

Q&A (24:25)

Q: すばらしいですね。2つ質問がありますがどちらか選んでください。まず1つ目の質問はエラーをサポートしていますか?パースが失敗したときにエラー箇所をパーサコンビネータに伝えることはできますか?2つ目の質問はどのようにToJSONを実行しましたか?プリンタコンビネータライブラリを持っていますか?

稲見: まず2つ目の質問に答えます。Pretty printed JSONはまだ対応していません。実装する必要があると考えています。そして次に、エラー処理は大切ですがパフォーマンスが悪いので実装していません。まずパフォーマンスを改善してから取り入れます。

Q: Cool stuff. I have two questions, you can pick which one you want to answer. The first one is, is there any support for error? If the parsing fails can you annotate your parser combinators to say, “if this part fails, maybe I am going to throw this error here”. The second question is, how did you do the ToJSON, do you have a printer combinator library?

Yasuhiro: I will answer the second question first. There is no printed JSON yet. I think I need to implement that. Now it is just one line JSON string. And the second one, is an error porting is important. But I did not implement it, because the performance is already bad at this point. I need to improve that first, and then hit our importing. Sorry about that.

稲見泰宏

LINE株式会社でiOSエンジニアをしています。業務ではメッセンジャー、カメラ、ニュースといったアプリ開発に関わる一方で、プライベートではReactKitやSwiftTaskといったオープンソースプロジェクトに貢献しています。Apple、SwiftそしてHearthstoneの大ファンです。Battle.netやGitHubで活動しています。