cps_study.md

attoparsecコードリーディング

自己紹介

• なかやん・ゆーき / ぺんぎん / もみあげ
• @pocketberserker
• Microsoft MVP (2013/04/01～ 2017/03/31)
• 仕事はScalaっぽい
• Haskell初心者です

パーザコンビネータ is 何

Wikipedia 曰く

In functional programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

てきとー訳

関数プログラミングでは、パーザコンビネータは入力としていくつかのパーザを受け取り、出力として新しいパーザを返す高階関数です。

attoparsec is 何

https://github.com/bos/attoparsec

Haskell製の速いパーサコンビネータライブラリ。

GHCはCPSだと高速に動作する場合があるらしい。

読んでみようattoparsec

http://pocketberserker.github.io/PEGStudy/#/

昔勉強会で作ったパーサコンビネータと比較しながら解説を試みる。

入り口

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Text/Lazy.hs#L78

parse :: A.Parser a -> Text -> Result a

パーサと入力を渡せば結果を得られる

パーサの結果とは？

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Text/Lazy.hs#L53

data Result r = Fail Text [String] String
              | Done Text r

• 失敗: 入力とエラー時のコンテキストとエラーメッセージ
• 成功: 入力と解析結果

ここまで

普通のパーサコンビネータっぽい

Parser

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L110

newtype Parser i a = Parser {
      runParser :: forall r.
                   State i -> Pos -> More
                -> Failure i (State i)   r
                -> Success i (State i) a r
                -> IResult i r
    }

日本語でおｋ。

State

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L118

type family State i
type instance State ByteString = B.Buffer
type instance State Text = T.Buffer

Bufferを使って高速化しようとしている（が本題ではないので略）

Pos

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L46

newtype Pos = Pos { fromPos :: Int }

解析位置情報。

More

読みおわったかどうか。

Failure

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L122

type Failure i t   r = t -> Pos -> More -> [String] -> String
                       -> IResult i r

失敗を表す継続。

Success

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L124

type Success i t a r = t -> Pos -> More -> a -> IResult i r

成功を表す継続。

IResult

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L54

data IResult i r =
  Fail i [String] String
  | Partial (i -> IResult i r)
  | Done i r

内部用の結果型。 Partialに入力を渡せば続行される。

失敗を表す

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L136

MonadErrorかな。

成功を表す

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L140

Monadかな。

or

https://github.com/bos/attoparsec/blob/0.13.0.2/Data/Attoparsec/Internal/Types.hs#L150

一つ目のパースで失敗した場合はもう一つを適用。 Alternative。