PureScriptでパーサーコンビネータを触る (1) 四則演算のパース

December 30, 2021

(last modified:

December 30, 2021

)

tags:

categories:

PureScriptのパーサーコンビネータにpurescript-parsingがある。これはHaskellのParsecが基になっているので、使い方はParsecとほとんど同じだと思われる(とはいえ、Parsecを使ったことはあまりない)。これを用いて四則演算のパーサーを実装してみたが、うまく動かず詰まる点がいくつかあった。その備忘録。

パーサーコンビネータの準備

% spago install parsing

後々使うので以下のパッケージもインストール。

% spago install either integers maybe strings arrays lists

src/Main.pursに以下の記述を追加。

import Text.Parsing.Parser (Parser)

parser :: Parser String String
parser = pure "Hello"

REPLを起動して、動くか確認する。どんな文字列を食わせても"Hello"としか結果を返さないパーサーの完成。

> import Main
> import Text.Parsing.Parser (runParser)
> runParser "hoge" parser
(Right "Hello")

REPLでMain.pursをリロードする場合は:rをREPLで実行する。

数字のパース

1文字取得

1文字の数字を読み取りたいなら、Text.Parsing.Parser.Tokenにdigitがあるのでそれを使う。

import Text.Parsing.Parser.Token (digit)


parser :: Parser String Char
parser = digit

> runParser "12345" parser
(Right '1')

1文字以上取得

1文字以上を取得したいなら、Data.Array.Someを使う。

import Data.Array as Array


parser :: Parser String (Array Char)
parser = Array.some digit

> runParser "12345" parser
(Right ['1','2','3','4','5'])

0文字以上の場合はData.Array.manyを使えば良い。ただし、この関数は実装で(:)を使っている。この計算量は O(配列の長さ) のため(参考)、もし効率を重視したいのであればData.List.manyもしくはData.List.someを使えば良い。

Charの配列ではなくStringが欲しいのであれば、Data.String.CodeUnits.fromCharArrayで変換すれば良い。

import Data.String.CodeUnits as CodeUnits

parser :: Parser String String
parser = do
  arr <- Array.some digit
  pure $ CodeUnits.fromCharArray arr

> runParser "12345" parser
(Right "12345")

数字を整数値で取得

Int.fromStringで整数に変換すれば良い。文脈的にこれに失敗することなどあり得ないのだが、関数の定義上仕方ないため、Maybeの値で場合分けをしている。

import Text.Parsing.Parser (fail)
import Data.Int as Int
import Data.Maybe (Maybe(..))


integer :: Parser String Int
integer = do
  arr <- Array.some digit
  case Int.fromString (CodeUnits.fromCharArray arr) of
    Just i -> pure i

    Nothing -> fail "parse error"

> runParser 12345 integer
(Right 12345)

符号付き整数

最初に符号の有無、有ったとして+と-のどちらなのかを確認する。

「+または-」をchar '+' <|> char '-'で表すのはなかなか直感的で良い。

import Control.Alt ((<|>))
import Text.Parsing.Parser.String (char)
import Text.Parsing.Parser.Combinators (optionMaybe)


signedInteger :: Parser String Int
signedInteger = do
  sign <- optionMaybe (char '+' <|> char '-')
  i <- integer
  case sign of
    Just '+' ->
      pure i

    Just '-' ->
      pure (-i)

    Nothing ->
      pure i

    _ ->
      fail "parse error" -- ここには来ないはず

> runParser "123" signedInteger
(Right 123)

> runParser "+123" signedInteger
(Right 123)

> runParser "-123" signedInteger
(Right -123)

failがあるのが気持ち悪いなら、以下のように書くことも可能。「符号+がついている」「符号-がついている」「符号がついていない」の3種類に分離した。

integer :: Parser String Int 
integer = do
  arr <- Array.some digit
  case Int.fromString (CodeUnits.fromCharArray arr) of
    Just i -> pure i

    Nothing -> fail "parse error"


plusInteger :: Parser String Int
plusInteger = do
  _ <- char '+'
  x <- integer
  pure x


minusInteger :: Parser String Int
minusInteger = do
  _ <- char '-'
  x <- integer
  pure (-x)


signedInteger :: Parser String Int
signedInteger = integer <|> plusInteger <|> minusInteger

ちなみにplusIntegerとminusIntegerはもっと短く書ける (いわゆる Applicative style と呼ばれるやつ)。

plusInteger :: Parser String Int
plusInteger =
  char '+' *> integer


minusInteger :: Parser String Int
minusInteger =
  (\x -> -x) <$> (char '-' *> integer)

すでに用意されているやつを使う

さて、整数値はトークンの一種である。

Text.Parsing.Parser.TokenのmakeTokenParserと使うと、様々なトークンのパーサーが使えるようになる。その中に整数値のパーサーがあるため、それを使ってみる。

makeTokenParserは、LanguageDef型の値を引数にとり、トークンパーサーが詰まったレコードを返す。 LanguageDefは、makeTokenParserを作るに当たっての設定の入ったレコードである。 LanguageDefという名前から察するに、makeTokenParserはプログラミング言語を字句解析する目的で使われるのだろう。

今回は特にプログラミング言語のパーサーを作るわけではないので、Text.Parsing.Parser.LanguageのemptyDefを指定する。

import Text.Parsing.Parser.Language (emptyDef)
import Text.Parsing.Parser.Token (makeTokenParser, GenTokenParser)
import Data.Identity (Identity)


tokenParser :: GenTokenParser String Identity
tokenParser = makeTokenParser emptyDef

GenTokenParserの定義を見ると、integerフィールドに整数のパーサーがあることがわかる．ソースコードまで見にいくと、各パーサーの説明が書かれているので見ると良い。

integer :: Parser String Int
integer = tokenParser.integer

> runParser "-123" integer
(Right -123)

> runParser "+123" integer
(Right 123)

> runParser "123" integer
(Right 123)

足し算のパース

手始めに、次のBNFのパーサーを書いてみる。

<expr> = <expr> + <integer> | <integer>

ただし、ここでは+は左結合とし、パース結果を以下のExprに入れる。

data Expr = Plus Expr Int | First Int


instance Show Expr where
  show (Plus e i) = "(" <> show e <> "+" <> show i <> ")"
  show (First i)  = show i

エラーになる例

BNF通りに素直に実装すると以下のようになる。

expr :: Parser String Expr
expr = plusExpr <|> (First <$> integer)
  where
    plusExpr = do
       e <- expr
       _ <- char '+'
       i <- integer
       pure (Plus e i)

ところが、以下のエラーが出る。

The value of expr is undefined here, so this reference is not allowed.

See https://github.com/purescript/documentation/blob/master/errors/CycleInDeclaration.md for more information,
or to contribute content related to this error.

エラーのURL先を見れば分かるが、要するにJavaScriptコードへの変換の際、func = funcのような、循環した代入が起こったらしい。

このエラーの原因場所を探るために、エラー場所以外のコードだけに絞る。

まずplusExprを無くす。

expr :: parser string expr
expr = (do e <- expr
           _ <- char '+'
           i <- integer
           pure (plus e i))
       <|> (first <$> integer)

First <$> integerの部分も関係ないので取り除く。

expr :: parser string expr
expr = do e <- expr
           _ <- char '+'
           i <- integer
           pure (plus e i)

do構文を>>=に直し、その後半を切り捨てる。

expr = expr >>= \e -> char '+'

さらに>>=はbind関数であったから、以下のように書き換える。

expr = bind expr (\e -> char '+')

この状態でも同じエラーが出ることが確認できる。

実は、exprの定義の中にexprが含まれていると、定義が循環してしまうため、このようなコンパイルエラーとなる。ただし、\_ -> exprのようにラムダ式の中にexprが含まれている場合はエラーとはならない。このことについて以下で詳しく見ていくが、細かい話なので面倒な場合は飛ばしても良い。

(寄り道) どんなJavaScriptコードが生成されるのか

ここでの環境はPureScript 0.14.5を想定する。バージョンが変わると生成されるコードも変わるかもしれない。

適当にsrc/Experiment.pursを作成し、以下のようなコードを書いてみる。func1はincをそのまま参照し、func2は適当な無名関数で包む。

inc :: Int -> Int
inc x = x + 1

func1 :: Int -> Int
func1 = inc

func2 :: Int -> Int
func2 = (\_ -> inc) unit

これをspago buildでビルドすると、JavaScriptのコードがoutput/Experiment/indes.jsに生成される。結果は以下のようになっていた。

var Data_Unit = require("../Data.Unit/index.js");
var inc = function (x) {
    return x + 1 | 0;
};
var func2 = (function (v) {
    return inc;
})(Data_Unit.unit);
var func1 = inc;

func1の方はincをそのまま代入しているが、後者はincが含まれた無名関数を呼び出すような形となっている。

よって、もし次のように書いたとすると、

func1 :: Int -> Int
func1 = func1

次のようにコードが生成されることが予想できる。右辺のfunc1はこの代入文の時点ではまだ定義されていないため、undefinedと評価される。実際にはPureScriptコンパイラの方でエラーとなる。

var func1 = func1;

もし次のように書いたとすると、

func1 :: Int -> Int
func1 = (\_ -> func1) unit


main :: Effect Unit
main = do
  logShow $ func1 0

次のようなコードとなる。このmain関数を実行したいなら、spago run -m Experimentとする。

var func1 = (function (v) {
    return func1;
})(Data_Unit.unit);

var main = Effect_Console.logShow(Data_Show.showInt)(func1(0));

こちらはPureScriptコンパイラの方では通る。ラムダ式の場合は細かくチェックせずにそのまま無名関数を生成するようだ。しかしコンパイルに成功しても、以下のランタイムエラーが発生する (！)。

TypeError: func1 is not a function

というのも、var func1 = ...の右辺を評価するとundefinedが返ってくるからである。func1(0)がundefined(0)と評価され、undefinedは関数じゃないと怒られている。

要するに、func1が定義される前に右辺のfunc1を評価しないで欲しいのである。そのためには次のようにすればよい。

func1 :: Int -> Int
func1 = \s -> (\_ -> func1) unit s

これは以下のJavaScriptコードに展開される。

var func1 = function (s) {
    return (function (v) {
        return func1;
    })(Data_Unit.unit)(s);
};

先ほどと違うのは、関数function (s) { ... }に包まれて返ってきた点である。これは関数オブジェクトとして評価され、その中身のfunc1までは評価されない。function (s) { ... }のsに具体的な値を入れて初めてfunc1が評価される。その時点ではfunc1はundefinedではなく、ちゃんと関数への参照が入っている。

これは、いわゆる評価を遅延させていることに対応する。遅延評価についての関数・型クラスはControl.Lazyで定義されており、Lazy型クラスを実装している型でればdeferで評価の遅延が行える。関数型a -> bはLazy型クラスのインスタンスであるため、次のコードで遅延させることができる (実質上のコードと同じである)。

import Control.Lazy (defer)

func1 :: Int -> Int
func1 = defer \_ -> func1

とはいえ、func1の中でfunc1を呼び出しているので、これは無限再帰となる。

RangeError: Maximum call stack size exceeded

ちなみに、次のコードはどうだろうか。

func1 :: Int -> Int
func1 x = func1 x

なんとこれはコンパイルが通り、次のようなコードが生成される。再帰の部分がwhileに置き換えられている (恐らく、末尾再帰最適化が働いた)。実行した際は無限ループとなる。

var func1 = function ($copy_x) {
    var $tco_result;
    function $tco_loop(x) {
        $copy_x = x;
        return;
    };
    while (!false) {
        $tco_result = $tco_loop($copy_x);
    };
    return $tco_result;
};

どうやらfunc xのように引数付きで定義していれば、PureScriptのコンパイラはfuncを関数だと認識し、それ専用のコードを生成するらしい。func = funcとfunc x = func xが区別できていないということは、PureScriptコンパイラはコード生成時に型を考慮していないということなのだろうか (PureScriptコードの型チェックを行うが、JSに変換する際には型の情報を捨てている？)。

遅延評価で\s -> (\_ -> func1) unit sのような記述をしたが、この定義は実際には冗長である。もっと簡潔に次のコード

func1 :: Int -> Int
func1 = \s -> func1 s

で動く。そして以下のJavaScriptコードに展開されるかも、と思うかもしれない。

var func1 = function (s) {
    return func1(s);
};

実際、以下の定義とほぼ同じコードが出力される。ただし、末尾再帰最適化が行われるようで、無限再帰ではなく単なる無限ループとなる (そもそも、これはfunc x = func xと同義)。

deferを使わず自分で\s -> ...を書いて遅延させる分には、上のような簡潔な書き方で良い。しかしdeferを使う際には必ず\_ -> func1の記述が必要になることに注意。実際、

func1 :: Int -> Int
func1 = defer func1

と書いてしまうと、右辺のfunc1がundefinedとなってしまいコンパイルエラーになる。

エラーを抑える方法

前節を踏まえて、コンパイルエラーを抑えるため方法がいくつか考えられる (ただし後述するが、コンパイルエラーが無くなるだけで期待した動作はしない)。

1つ目は、余分な_ <- pure unitを挟むことである。これだけで、do構文を外したときに pure unit >>= \_ -> expr >>= ...のように、exprが後ろのラムダ式の中に入る。

expr :: Parser String Expr
expr = plusExpr <|> (First <$> integer)
  where
    plusExpr = do
       _ <- pure unit
       e <- expr
       _ <- char '+'
       i <- integer
       pure (Plus e i)

2つ目は、exprに余分な引数を加えることである。

expr :: Unit -> Parser String Expr
expr _ = plusExpr <|> (First <$> integer)
  where
    plusExpr = do
       e <- expr unit
       _ <- char '+'
       i <- integer
       pure (Plus e i)

3つ目の方法は、defer関数を利用してパーサーの評価を遅延させることである。 ParserはLazy型クラスのインスタンスであるから、deferが使える。

import Control.Lazy (defer)


expr :: Parser String Expr
expr = plusExpr <|> (First <$> integer)
  where
    plusExpr = defer \_ -> do
       e <- expr
       _ <- char '+'
       i <- integer
       pure (Plus e i)

BNFの見直し

さて、コンパイルエラーはなくなったが、実際に実行してみると無限再帰に陥り、ランタイムエラーが発生する。

> runParser "1+2+3+4" expr

RangeError: Maximum call stack size exceeded

これは、コンパイルエラーを抑えたとしても、「exprはexprを呼び、その中でさらにexprを呼び…」という無限ループは排除できていないからである。

これを解決するには、BNFを見直す必要がある。すなわち、もっと具体的に

<expr> = <integer> + <integer> + ... + <integer>

と解釈する必要がある。左結合だから、foldlみたいな関数を実装すればよいことが分かる。

以下の補助関数expr'は、「+ <integer>をパースしてみて、失敗したら引数の値を返し、成功したら引数の値と結合させる」という処理を行っている。これでコードは動作する。

expr :: Parser String Expr
expr = do
  i <- integer
  expr' (First i)


expr' :: Expr -> Parser String Expr
expr' e0 =
  plusExpr <|> pure e0
  where
    plusExpr :: Parser String Expr
    plusExpr = do
      _ <- char '+'
      i <- integer
      expr' (Plus e0 i)

> runParser "1+2+3+4" expr
(Right (((1)+2)+3)+4)

ちなみに、plusExprはApplicative styleで次のように書ける。 '+' <integer>という文面がここから読み取れるため、慣れると読み易い。

plusExpr = Plus e0 <$ char '+' <*> integer

chinlの利用

再び以下のBNFを考える。

<expr> = <integer> + <integer> + ... + <integer>

実はText.Parsing.Parser.Combinatorsにchainlという関数があり、左結合の式をパースすることができる。今回は少なくとも1つ式が存在しなければならないバージョンのchainl1を使う。

chainl1 の型は以下の通り。

chainl1 :: forall m s a. Monad m => ParserT s m a -> ParserT s m (a -> a -> a) -> ParserT s m a

今回の例でいうと、第1引数にはintegerのパーサー、第2引数には+のパーサーを入れる。ただし、第2引数のパーサーの返却値は、foldlと同じような(accumulator, elem)を引数にとる関数である。

ただし、foldlとは違って関数の型がやや弱い。foldlの場合はb -> a -> bだったが、chainlはaccumulatorの型と要素の型が一致していないといけない。そのため、前節のExprをchainlで作るのは(おそらく)難しい。

代わりに次のようにする。データ型の方では式の結合順序の情報を無くしてしまう。

data Expr = Plus Expr Expr | Elem Int

instance Show Expr where
  show (Plus e1 e2) = "(" <> show e1 <> "+" <> show e2 <> ")"
  show (Elem i) = show i

その上でexprは次のように書ける。

import Text.Parsing.Parser.Combinators (chainl1)

expr :: Parser String Expr
expr = chainl1 (Elem <$> integer) do
  _ <- char '+'
  pure \acc e -> Plus acc e

ちなみに以下のようにもっと短く書ける。

expr :: Parser String Expr
expr = chainl1 (Elem <$> integer) (Plus <$ char '+')

型の定義では結合順序の情報が失われているが、パーサーの方で結合順序が考慮できている。

> runParser "1+2+3+4" expr
(Right (((1+2)+3)+4))

四則演算のパース

四則演算をパースし、その計算をパース結果とするようなプログラムを書く。BNFは以下の通り。

<expr> = <expr> + <term> | <expr> - <term> | <term>
<term> = <term> * <factor> | <term> / <factor> | <factor>
<factor> = ( <expr> ) | <integer>

数字は整数値しか受け取らないものとし、数値計算の結果は浮動小数点数とする。

今までのことを踏まえて、四則演算を計算するパーサーを書く。

素朴にこれを書くと以下のようになる。

expr :: Parser String Int
expr = chainl1 term
  ((char '+' *> pure (+)) <|> (char '-' *> pure (-)))


term :: Parser String Int
term = chainl1 factor
  ((char '*' *> pure (*)) <|> (char '/' *> pure (/)))


factor :: Parser String Int
factor = (char '(' *> expr <* char ')') <|> integer

ところが、これは動かない。再び次のエラーにぶつかる。

The value of expr is undefined here, so this reference is not allowed.

The value of term is undefined here, so this reference is not allowed.

The value of factor is undefined here, so this reference is not allowed.

ちなみにHaskellのParsecライブラリを使うと、以下のコードが動く(簡単のため割り算は省略)。

import           Data.Functor.Identity (Identity)
import           Lib
import           Text.Parsec           (Parsec, chainl1, char, (<|>))
import           Text.Parsec.Language  (emptyDef)
import qualified Text.Parsec.Token     as P

type Parser s = Parsec s ()


tokenParser :: P.GenTokenParser String () Identity
tokenParser = P.makeTokenParser emptyDef


integer :: Parser String Integer
integer = P.integer tokenParser


expr :: Parser String Integer
expr = chainl1 term
  ((char '+' *> pure (+)) <|> (char '-' *> pure (-)))


term :: Parser String Integer
term = chainl1 factor
  (char '*' *> pure (*))


factor :: Parser String Integer
factor = (char '('  *> expr <* char ')') <|> integer

このようにHaskellとPureScriptで同じコードを書いているにも関わらず異なる動作をする理由は、評価戦略の違いである。前者は遅延評価だが、後者は正格評価である。

今回の場合、exprの中でtermを参照し、termの中でfactorを参照し、factorの中でexprを参照するという定義の循環が起こっている。JavaScriptのコードの気持ちになって考えると、これら3つをどのように定義しても、一番最初の宣言の時点で右辺にundefinedが現れる。例えば、

var expr = ...
var term = ...
var factor = ...

の順番で行うと、var expr = ...の右辺のtermはまだ宣言されていないからundefinedである。また、

var factor = ...
var term = ...
var expr = ...

の順番だったとしても、var factor = ...の右辺のexprがまだ宣言されていないからundefinedである。このように、定義が循環しているとundefinedが現れてしまう。

これは正格評価だから起こってしまう問題である。もし右辺の値が宣言時にundefinedとも何とも評価されておらず、パーサーの実行の時にその値が評価されるのであれば、undefinedではなく確かに値が入っているはずである。

そこで、以下のようにdeferを挟んで評価を遅延させれば解決できる。

expr :: Parser String Int
expr = defer \_ ->
  chainl1 term
    ((char '+' *> pure (+)) <|> (char '-' *> pure (-)))


term :: Parser String Int
term = defer \_ ->
  chainl1 factor
    ((char '*' *> pure (*)) <|> (char '/' *> pure (/)))


factor :: Parser String Int
factor = defer \_ ->
  (char '('  *> expr <* char ')') <|> integer

> runParser "1+2+3" expr
(Right 6)

> runParser "4*(1+2+3)" expr
(Right 24)

整数以外の計算

Int.toNumberを使うとIntからNumberに変換できる。これで整数以外にも対応できる。 expr、term、factorの型を変更する必要があることに注意。

import Data.Int as Int

expr :: Parser String Number

term :: Parser String Number

factor :: Parser String Number
factor = defer \_ ->
  (char '('  *> expr <* char ')') <|> (Int.toNumber <$> integer)

buildExprParserの利用

なんとText.Parsing.Parser.Exprにて、式のパーサーを半自動で生成してくれる関数がある。手順は以下の通り。

演算子、その優先順位などをまとめたOperatorTableを定義。
buildExprParserで式のパーサーを生成。

OperatorTableの定義方法について。ドキュメントには使用例しか書かれていないが、ParsecのOperatorTableと同じだと思われる。一番外側のArrayが優先順位を決め、内側のArrayに演算子の情報を入れる。以下では、次の情報を定義している。

中値(Infix)演算子*と/は高順位で、左結合(AssocLeft)。
中値(Infix)演算子+と-は低順位で、左結合(AssocLeft)。

import Text.Parsing.Parser.String (string)
import Text.Parsing.Parser.Expr (OperatorTable, Operator(..), Assoc(..))


operatorTable :: OperatorTable
operatorTable =
  [ [ Infix (string "*" $> (*)) AssocLeft
    , Infix (string '/' $> (/)) AssocLeft
    ]
  , [ Infix (string "+" $> (+)) AssocLeft
    , Infix (string '-' $> (-)) AssocLeft
    ]
  ]

若干先ほどあげたBNFとずれてしまうが、以下のようにしてパーサーを生成する。 <term> [*/+-] <term> [*/+-] ...の形のパーサーを作成できる。

term :: Parser String Number
term = (char '(' *> expr <* char ')') <|> integer

expr :: Parser String Number
expr = buildExprParser operatorTable term

…としたいが再び The value of ... is undefinedのエラーがでるので、deferを使う。

term :: Parser String Number
term = defer \_ ->
  (char '(' *> expr <* char ')') <|> (toNumber <$> integer)

expr :: Parser String Number
expr = defer \_ ->
  buildExprParser operatorTable term

ちなみに、Control.Lazyのfix関数を使うと以下のように書くこともできる。 fix関数を使うと、expr自身を\e -> ...の引数eとして受け取り、自分自身を再帰させるような処理を書くことができる。 deferが消える代わりに、termがexprに相当する引数を取るようになる。

import Control.Lazy (fix)


term :: Parser String Number -> Parser String Number
term e = (char '(' *> e <* char ')') <|> (toNumber <$> integer)

expr :: Parser String Number
expr = fix \e ->
  buildExprParser operatorTable e

まとめ・感想

makeTokenParser、buildExprParserなどの便利な関数があることを知った。

CycleInDeclarationのエラーの原因を探るためにかなり時間を使ったが、その分PureScriptコンパイラの動作を、ほんの少しだが垣間見ることができた。

評価戦略の違いにより、HaskellのParsecで書いたコードがそのまま動かない場合があることを実感した。