Help us understand the problem. What is going on with this article?

Swiftを始めてみた(パーザコンビネータを書いてみた)

最近、新しい言語を学んでいないなーと思ったので、ふと思い立って昨日くらいにSwiftを始めてみることにしました。Swiftを始めてみたといっても、Hello, Worldを出力するサンプルを書いたとか、なんらかのGUIアプリケーションを作ったわけでもなく、いつも通りのパーザコンビネータです。

コード自体はSwCombinatorに書いてあるので詳細はそれを見てもらうとして。基本的には、Scala福岡2019のために作ったusparseを直接的に移植するような戦略でいきました。

ただ、Swiftはfunction typeに対してメソッドを拡張できない(non-nominal typeというらしい)ので、以下のようなクラスにラップしてあげたのがちょっと違う点です。

class Parser<A> {
    let function: (String) -> Result<A>
    init(function: @escaping (String) -> Result<A>) {
        self.function = function
    }

    func parse(input: String) -> Result<A> {
        return self.function(input)
    }
}

パーズ結果を格納するResult<A>型は、SwiftがいわゆるADTをサポートしているので、簡単にかけました:

enum Result<A> {
    case Success(value: A, next: String)
    case Failure(next: String)
}

…何もいうことがないくらいに直接的ですね。

途中、無名関数(Swift用語でクロージャ?)の書き方でつまづいたり、returnが必要なことに気づかずにエラーが出たりと多少つまづきましたが、おおむね素直に書けたかなという印象です。

以下が、パーザコンビネータのライブラリ部分の実装です。

enum Result<A> {
    case Success(value: A, next: String)
    case Failure(next: String)
}
class Parser<A> {
    let function: (String) -> Result<A>
    init(function: @escaping (String) -> Result<A>) {
        self.function = function
    }

    func parse(input: String) -> Result<A> {
        return self.function(input)
    }
}
typealias P<A> = Parser<A>
extension Parser {
    func rep0() -> Parser<Array<A>> {
        return Parser<Array<A>> { (input: String) in
            func rep(input: String) -> Result<Array<A>> {
                switch self.function(input) {
                case let .Success(value, next1):
                    switch(rep(input:next1)) {
                    case let .Success(result, next2):
                        var newArray = result
                        newArray.insert(value, at:0)
                        return .Success(value:newArray, next:next2)
                    default:
                        abort()
                }
                case let .Failure(next):
                    return .Success(value:[], next:next)
                }
            }
            return rep(input:input)
        }
    }

    func plus<B>(right: Parser<B>) -> Parser<(A, B)> {
        return Parser<(A, B)> { (input: String) in
            let result1 = self.function(input)
            switch result1 {
            case let .Success(value1, next1):
                let result2 = right.function(next1)
                switch result2 {
                case let .Success(value2, next2):
                    return .Success(value:(value1, value2), next: next2)
                default:
                    return .Failure(next: next1)
                }
            default:
                return .Failure(next: input)
            }
        }
    }

    func or(right: Parser<A>) -> Parser<A> {
        return Parser<A> {(input: String) in
            switch self.function(input) {
            case let .Success(value, next):
                return .Success(value:value, next:next)
            case let .Failure(next):
                return right.function(next)
            }
        }
    }

    func map<B>(translator: @escaping (A) -> B) -> Parser<B> {
        return Parser<B> { (input: String) in
            switch self.function(input) {
            case let .Success(value, next):
                return .Success(value:translator(value), next:next)
            case let .Failure(next):
                return .Failure(next:next)
            }
        }
    }
}
func rule<A>(body: @escaping () -> Parser<A>) -> Parser<A> {
    return Parser<A> {(input: String) in
        return body().function(input)
    }
}
func +<A, B>(lhs: Parser<A>, rhs: Parser<B>) -> Parser<(A, B)> {
    return lhs.plus(right:rhs)
}
func |<A>(lhs: Parser<A>, rhs: Parser<A>) -> Parser<A> {
    return lhs.or(right:rhs)
}
func s(literal: String) -> Parser<String> {
    return Parser<String> {(input: String) in
        let literalLength = literal.lengthOfBytes(using:String.Encoding.utf8)
        let inputLength = input.lengthOfBytes(using: String.Encoding.utf8)
        if literalLength > 0 && inputLength == 0 {
            return .Failure(next:input)
        } else if input.starts(with: literal) {
            let from = input.index(input.startIndex, offsetBy:literalLength)
            return .Success(value:literal, next:String(input[from...]))
        } else {
            return .Failure(next:input)
        }
    }
}

パターンマッチなどの際に外側のResultの記述を省略できるのは、@omochimetaru さんに教えていただきました。多謝。

このライブラリ部分を使って、四則演算式をパーズするパーザを書いたのが以下のコードです。

class Expression {
    static let E: P<Int> = rule { A }
    static let A: P<Int> = rule {
        (M + ((s(literal:"+") + M) | (s(literal:"-") + M)).rep0()).map{ (l, rs) in
            rs.reduce(l) { (l, b) in
                let (op, r) = b
                return op == "+" ? l + r : l - r
            }
        }
    }
    static let M: P<Int> = rule {
        (P + ((s(literal:"*") + P) | (s(literal:"/") + P)).rep0()).map{ (l, rs) in
            rs.reduce(l) { (l, b) in
                let (op, r) = b
                return op == "*" ? l * r : l / r
            }
        }
    }
    static let P: P<Int> = rule {
        (
            (s(literal:"(") + E + s(literal:")")).map {v in
                let ((_, r), _) = v
                return r
            }
        |   N)
    }
    static let N: P<Int> = rule { Digit.map { Int($0)! } }

    static let Digit: Parser<String> = rule {
        s(literal:"0") | s(literal:"1") | s(literal:"2") | s(literal:"3") | s(literal:"4")
      | s(literal:"5") | s(literal:"6") | s(literal:"7") | s(literal:"8") | s(literal:"9")
    }
}
let E = Expression.E
print(E.parse(input:"(1+2)*3"))

相互再帰的なルールをどう書くのがいいのかな、というのが考えどころでしたが、手っ取り早くstaticなメンバを使ってしまいました。

感想としては、

  • 構文は普通(キーワードがちょっと変わってるところがあるくらい)
  • 無名関数+パターンマッチングを同時に行う構文が欲しい
  • return は基本的に書かなくてもいいくらいの仕様の方が好み
  • func での関数定義において、引数名と型の区切りは:なのに、返り値型の前に書くのが -> なのは何故なのか
  • switchでの網羅性チェックをちゃんとやってくれるのは嬉しい
  • 最近の言語らしいというか、文字列に関する扱いが比較的厳密(単純にStringに対して長さを取るというナイーヴな操作が一発でできない)

といったところでしょうか?プロトコルとかSwift特有の部分にはあまり触れなかった気がするので、これだけだとまだまだわからないところが多いですが、多少は馴染めたのかなという気がします。

全体を書き上げるのにかかった時間はだいたい3時間といったところでしょうか。ではでは。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away