プログラミングHaskell 8.4 連結
ひきつづきプログラミングHaskellをScalaで書き換えつつ読んでいきます。
おそらく、二つのパーサーを組み合わせる最も単純な方法は、一方の後に他方を適用することだろう。一番目のパーサーの返す出力文字列が、二番目のパーサーの入力文字列となる。 連結演算子
>>=(そして)
を用いて、結果を処理する形でパーサーを連結させる方が経験上便利だ。
これは、flatMapのシグネチャだ!
// def >>=[A, B]: Parser[A] => Parser[B] => Parser[(A, B)] def >>=[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B] = (inp: String) => parse(p)(inp) match { case List() => List() case List((v, out)) => parse(f(v))(out) }
とここから、本の中ではdo記法を使っていくわけなのですが、ここまでの状態でfor文を書くと、以下のようになりますが、
// 動かない def p = for { x <- item _ <- item y <- item } yield (x, y)
Error:(50, 10) value flatMap is not a member of Parsers.Parser[Char] x <- item
Parser型にflatMapやmapを定義していないためにコンパイルできません。ここではParserはtypeで宣言しただけであって、それにflatMapをもたせる....?よくわからないけど、FPinScalaで見たことのある方法で可能そう....!(後ほど書いてあります)。
ここではfor式を展開したバージョンを書いて、本についていきます。
// ずるいけど、mapを書きます def map[A, B](p: Parser[A])(f: A => B): Parser[B] = (inp: String) => parse(p)(inp) match { case Seq() => Seq() case Seq((v, out)) => Seq((f(v), out)) } def p: Parser[(Char, Char)] = >>=(item)((c: Char) => >>=(item)((_: Char) => map(item)((ccc: Char) => (c, ccc)) ) )
以下のコードで実行します。
object Main extends App { .... println("sample5: " + parse(p)("abcdef")) }
sample5: List(((a,c),def))
確かに答えが得られています。何が起こっているんだ・・・・当てられる文字列の情報(今回の実行であれば"abcdef")がp
というメソッドでは一切でてこないのに、うまくいっている...?いつ消費されて、いつ返されているんだ。。。Stateモナドと呼ばれる類のやつなんだろうけど、不思議すぎる〜〜〜どうなってるか、を考えずに、flatMap(>>=)では、次に渡されているんだと無心で思って次に進んでいきたいと思います。
ちなみに、Scalaで上のやつをfor式で書けるようにするには以下のようにします。ParserはParserOpsへ自動的(暗黙的に)変換され、ParserOpsが持っているメソッドを使うことができます。定義はParsersオブジェクトに配置して、それらの定義をParserOpsから呼び出します。(説明あってるカナ)
object Parsers { self => type Parser[T] = (String) => Seq[(T, String)] .... // 上で書いた map とか >>= 書く .... implicit def parserOps[T](p: Parser[T]) = ParserOps(p) case class ParserOps[T](p: Parser[T]) { def flatMap[S](f: T => Parser[S]): Parser[S] = self.>>=(p)(f) def map[S](f: T => S): Parser[S] = self.map(p)(f) } def pp: Parser[(Char, Char)] = for { x <- item _ <- item y <- item } yield(x, y) }
以下のコードで実行。
object Main extends App { .... println("sample6: " + parse(pp)("abcdef")) }
sample6: List(((a,c),def))
今日のところまで。
基本的なパーサー
プログラミングHaskellより。
ここで、他のパーサーを構築するのに利用する基本的なパーサー三つを定義しよう。
ちょっと本の表記から変えます。
return
が予約語なので、メソッド名をreturn
->succeed
にします。String => List[Char]への変換は明示的に行う(Stringにunapplyメソッドがないからパターンマッチが行われてなさそう)*1
// def succeed[T]: T => Parser[T] // def failure[T]: Parser[T] // def item: Parser[Char] def succeed[T](t: T) = (inp: String) => Seq((t, inp)) def failure[T] = (inp: String) => Seq() def item = (inp: String) => inp.toList match { case List() => Seq() case x :: xs => Seq((x, xs.toString)) }
こんな感じだろうか.....
パーサーは関数なので、通常の関数適用を使って、パーサーを文字列へ適用できる。 しかし、パーサーの実現方法を抽象化して、独自の適用関数を定義するほうが望ましい
わからない!どうしてそっちのが望ましいんだろう。。
// def parse[T]: Parser[T] => String => Seq[(T, String)] def parse[T](p: Parser[T])(inp: String): Seq[(T, String)] = p(inp)
どう振る舞うのかの例を示す。
以下のように書いたScalaプログラムを動かしてみます。
object Main extends App { import Parsers._ println("sample1: " + parse(succeed(1))("abc")) println("sample2: " + parse(failure)("abc")) println("sample3: " + parse(item)("")) println("sample4: " + parse(item)("abc")) } object Parsers { type Parser[T] = (String) => Seq[(T, String)] def succeed[T](t: T) = (inp: String) => Seq((t, inp)) def failure[T] = (inp: String) => Seq() def item = (inp: String) => inp.toList match { case List() => Seq() case x :: xs => Seq((x, xs.mkString)) } def parse[T](p: Parser[T])(inp: String): Seq[(T, String)] = p(inp) }
結果。
sample1: List((1,abc)) sample2: List() sample3: List() sample4: List((a,bc))
早速心が折れてしまいそうだけどw、少しずつ続けよう。
パーサーの型
プログラミングHaskellより。 でもScalaで書いてみます。
適切な構文木の型Treeが与えられたとすると、パーサーはString -> Treeを持つ関数として表現できる。
type Parser = String => Tree
しかし、一般的にはパーサーがすべての文字列を使い切るとは限らない。 このため、消費しなかった文字列を返すように、パーサーの型を拡張する。
type Parser = String => (Tree, String)
同様に、構文の解析は常に成功するとは限らない。 失敗を扱えるように、パーサーの型をさらに拡張して、結果のリストを返すようにする。
Maybeを使えるって書いてあるけど、本のとおり、Seqでいきます。
type Parser = String => Seq[(Tree, String)]
最後に、パーサーが異なれば、異なる構文木を返すだろう。たとえば、数値パーサーは整数を返すだろう。そこで、返り値の型がTreeに限定されているのを抽象化し、型Parserの型変数にすると便利だ。
Scala的にはジェネリクス(って呼ばないのかな?)を使ってみます。
type Parser[T] = (String) => Seq[(T, String)]
リストの要素は、型Tの結果と、消費されなかった文字列との組である。
しょうじき、ここらへんで、どんな感じで返ってくるってこと????というのが想像が追いつきません。が次に進んでみます。
パーサーとは (1)
プログラミングHaskellより。
パーサーとは、文字列を取り、文字列の文法構造を表現する曖昧さのない構文木を返すプログラムである。
曖昧さをなくすってのが大事なんだろう。
たとえば、文字列 "2 * 3 + 4"が与えられたとき、数式のパーサーは以下のような形の構文木を生成するだろう。
+ / \ * 4 / \ 2 3
この構文木をどうやって型(クラス)で表現するかも大事そう。
ほとんどの実用的なプログラムは、入力をあらかじめ処理するためにパーサーを使うので、パーサーはコンピュータの重要な分野だ。たとえば、電卓プログラムは数式を評価する前に構文を解析し、HugsはHaskellのプログラムを実行する前に構文を解析し、また、Webブラウザはハイパーテキスト文書を表示する前に構文を解析する。
すごいすごい、解析しまくりだ。
入力の構造を明確にしておけば、以降の処理が格段に簡単になる。
たしかに!現実世界から、プログラミングの世界に移すにはすべてパーサーが必要そう!
パーサーを書けるようになりたい
パーサーを書けるようになりたい、と思いました。 JSONとかxmlとかcsvとか。
以下のようなことをフワ〜っと思っていました。
- 社会人になって2年半、もうプログラミング歴も同じだけ経ったから(やばい)、なにか動くものを作りたい。
- 全く新しいものを作るってのはまだ僕には無理そう。思いつかないし、腰も思い・・・車輪の再発明になるけど、いつも使えるようなツールを作ろう。
- インフラよりも、アプリケーションロジックを重視したい。
- ちょっと難しそうなやつをできるようになりたい。
- 関数型プログラミングに通じるものがいい。
そういえば、JSON, xml,...とか整形ツールってよく使うな〜、
日常の開発でもJSONパーサー使うな〜、
コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方 を読んでいたら、コンパイラにもパーサーって使われてんだな〜、
.......
あれ、パーサーってちょうどよさそう!と思いました。
- パーサーを書くには関数型プログラミングのメリットが十分に活かせる(らしい)
- FPinScala でJSONパーサーの章を読んで、全くわからないw ので、僕にはレベル高い。
ってことで、 なんとかして年内には、いちばん単純な 文字列=>JSONオブジェクト に解釈できるJSONパーサーが書けるように努力してみよう! ってことでブログを書くことにしました。
できるかな...(^_^;A