遅延評価でデバッグが困難になる状況

問題1: 無限ループするパーサコンビネータ

Haskell にはモナディックパーサコンビネータと呼ばれるライブラリ群がある。これは、名前の通りプリミティブなパーサをモナディックに繋げていくことで、目的のパーサを書けるようなライブラリで、Parsec の名前を冠する系統が有名だ。パーサコンビネータのチュートリアルは、Hutton & Meijer [2] [3] [4] がおすすめなので、見てみるといいと思う。Hutton & Meijer では、パーサを StateT String [] で作るわけだけど、ここではそれを拡張して、

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

newtype Parser t a = Parser
  { unParser :: ParseState t -> ParseResult (a, ParseState t)
  }

type Position = Int
data ParseState t = ParseState Position [t]

data ParseResult a
  = ParseSuccess (NonEmpty a)
  | ParseFailure [(Position, String)]

のようなパーサを使っていくことにする。Hutton & Meijer との違いは、

• 状態が後読むべき文字列 String でなく、現在の位置と後読むべき t 型トークンの列になってること
• パース結果が空だった場合、エラーとみなして、エラー位置とメッセージを載せられるようになってること

だ。ParseResult はそれ単体でモナドになり、結果的に Parser は StateT (ParseResult t) ParseResult と同じと考えれば、やはりモナドになる。このパーサを使って、以下の文法を持つ言語をパースしていきたい:

$\mathit{ident}$、$\mathit{symbol}$、$\mathit{integer}$ やその他の記号は字句解析済で渡ってくるとする。AST は以下のようになる:

1
2
3
4
5
6
7
8
9

data Expr
  = App Expr Expr
  | InfixApp Expr Var Expr
  | Abs Var Expr
  | Var Var
  | Lit Lit

type Lit = Int
type Var = String

で、文法で示した属性規則に従って、AST を得たいわけだ。さて、勢いで書いてみたプログラムが、Problem01.hs になる。ところが、動かしてみるとどうもどこかで無限ループしているようだ。最終的に、あなたにはこのプログラムを4つの例の結果がちゃんと返るように修正して欲しい。

この問題の修正例は、Problem01A.hs になる。

さて、一般にパーサコンビネータライブラリは遅延評価を機能として利用している。これは、複雑なパーサのデバッグにおいて、個人的には常に厄介だ。今回の問題は、かなり難易度を緩めにしていて [5] 、常に無限ループが起こるわけだが、これがある (かなり特殊なケースの) プログラムでしか無限ループが起きないことを想定してみて欲しい。実際に、無限ループの原因を特定した人なら分かるはずだが、このような出来事は結構頻繁に起こる。このデバッグはかなりしんどく、なんならデバッグ文表示のために、変に評価を入れようものなら、通常問題ないところまで無限ループし始めるという大惨事が発生する。

また、パーサコンビネータのデバッグは、

• パーサの構築の際に問題があるのか
• パース結果の操作に問題があるのか

の切り分けが難しい。そのために、色々問題を切り分ける必要が出てくるが、その際にも遅延評価は結構悩みの種になる。なぜなら、パーサの構築と結果の操作が同時進行で、しかもデータの依存関係に沿って起こるからだ。多くの場合、データの依存関係とプログラマが想定する時系列はあっていない事が多く、結果トレースがめちゃくちゃになる。

で、解決策だけど、僕はパーサコンビネータを捨てて、

• 複雑なパースには Happy などのパーサジェネレータ
• 簡単なパースには、正規表現

を使うようになった。これはデバッグが辛い事だけが理由ではないけれど、この理由も大きい。なお、字句解析など、比較的簡単な、でも正規表現だけではやりにくい奴については、パーサコンビネータを使うこともある。

問題2: Zipper による複雑怪奇な評価器

次のような構造を考える:

1
2
3
4
5

data Inst a
  = GetChild Int (Inst a)
  | Put Char [Inst a]
  | Var a
  | Bottom

この構造は、次のような意味論を持つ:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

data Value
  = VPut Char [Value]
  | VBottom

evalInst :: (a -> Value) -> Inst a -> Value
evalInst f = go
  where
    go = \case
      GetChild i t -> getChild i $ go t
      Put c ts     -> VPut c [ go t | t <- ts ]
      Var x        -> f x
      Bottom       -> VBottom

getChild :: Int -> Value -> Value
getChild i = \case
  VPut _ ts -> case drop i ts of
    t:_ -> t
    []  -> VBottom
  t@VBottom -> t

つまり、Inst a は、文字による木とエラー値を値に持ち、GetChild という木の $i$ 番目の子供を取得するプリミティブな操作と変数が入ったシステムになる。ところで、このシステムは書き換えシステムとして実装することもできる。今回は、Zipper を使って変数への代入を行わない書き換えシステムを実装してみたい。さて、勢いで書いてみたプログラムが、Problem02.hs になる。ところが、動かしてみても、結果が著しく異なる。最終的に、あなたにはこのプログラムを4つの例の結果がちゃんと返るように修正して欲しい。

この問題の修正例は、Problem02A.hs になる。

さて、Haskell のプログラム例の多くは、再帰的な木に対してそれに沿って再帰を回すというものである。ところが、現実世界ではその形に沿わない状況も多い。その典型例がグラフ処理である。グラフは、あっちにいったりこっちに行ったりということを条件によって行う。また、停止性の条件も非自明な場合が多い。Haskell でグラフを扱うのは、少し厄介なので、今回はその気分を Zipper を使って再現してみた。こちらも難易度は控えめにしてある [6] 。

遅延評価は、一般に複雑な制御構造を持つプログラムのデバッグ難易度を結構上げる代物だと思う。というのは、そういうプログラムは、多くの場合制御フローが間違っているわけで、どこのフローが間違っているかを突き止める作業が主になるが、遅延評価はそもそもユーザが意図したフローで動いていない場合が多いからだ。意図したフローで動いていなくても結果は同じというのが遅延評価の特徴なわけだが、制御フローのデバッグは結果より過程が重要になり、過程が突き止めにくいことは大きな障壁になる。例えば、トレースを安直に挿入すると、トレース結果が意図したものと逆の時系列が出る経験をしたことはないだろうか？ これは、まあ慣れた Haskell プログラマなら、どういう場所に挿入したか想像がつくと思うが、個人的には一回はギョッとする奴だと思ってる。こういうトレース場所をよく考えて挿入しなきゃいけないというのは、結構不安を呼ぶ。トレースがちゃんとでない場合、それは制御フローがバグってるのか、自分が浅はかで評価フロー的に大事なポイントにトレースがちゃんと挿入できていないのかが一見して分からないからだ。

ところで、GHC 8.0 から Strict 拡張が追加された。これはとりあえずあらゆるところで bang pattern を付け、コンストラクタのフィールドも全部正格フラグをつけるというやつで、ちょっと厄介ポイントはあるものの、不安は結構解消される。僕は、最近この拡張デフォルト有効でプログラムを書いていて、正直 Strict 拡張ない頃には戻りたくないですね。なお、この拡張はパフォーマンス解析にも役に立つ。その理由はここで挙げた点と同じで、やはり評価フローが大体自分が意図した通りというのは大事という感じ。

問題3: ちゃんと機能しないベンチマーク

以下のようなプログラムを考える:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

data BinTree a
  = Node a (BinTree a) (BinTree a)
  | Leaf a

findRightOdd :: BinTree Int -> Maybe Int
findRightOdd = go
  where
    go (Leaf x)
      = maybeOdd x
    go (Node x lt rt)
      =   go rt
      <|> maybeOdd x
      <|> go lt

    maybeOdd x
      | x `mod` 2 == 1 = Just x
      | otherwise      = Nothing

なんて事のないプログラムで、数値を値に持つ二分木が与えられた場合に、一番右側にある奇数の値を取得するプログラムになる。さて、このプログラムは奇数が見つかればそこで木の探索を終了するはずなので、奇数が早めに見つかる場合は、全部探索して奇数を見つけるプログラムより速いはずだ。そこで、

1. 一番右側に奇数がある木
2. 奇数がない木
3. ランダムに値を埋め込んだ木

を作って、プログラムの速度を実測してみたところ、$1 \ll 3 \ll 2$ を期待したのに、$1 \ll 2 \ll 3$ という結果が得られた。一体上の簡単なプログラムのどこに間違いがあったんだろう？ 実測に使ったプログラムは、Problem03.hs になる。このプログラムに間違いがあれば指摘して欲しい。

この問題の修正例は、Problem03A.hs になる。

最後は、疲れちゃったので、易しい問題で。修正の仕方は色々考えられると思う。作者自身は、ちゃんとベンチマークしたいわけじゃなくて、プログラムが意図通り動いていそうか軽く確認したいというのがポイントだ。さて、デフォルト遅延評価でのパフォーマンス予測は常に厄介で、大体外れる (個人の感想です)。この原因は、主にパフォーマンスの問題が各関数で完結しておらず、相互作用によって決まる傾向にあるというのも大きいと思う。なので、Haskell でない言語でもイテレータやジェネレータを扱う場合のパフォーマンス解析は結構しんどい。ただ、そういう言語でも相互作用に決まるものと決まらないものはちゃんと区別されている。Haskell では区別されていない。これが一番きつい。これは、問題2でも共通だが、どこを疑えばいいのかが得られたデータからは判別しづらいからだと思う。なので、判別には経験が試される。

今回の場合、直接 Strict 拡張が役に立つわけではないが、Strict 拡張を使う事自体は判断の助けになるだろう。実はこのプログラムは、後輩が詰まっていた問題から着想を得ているんだけど、Haskell の経験が特にない人が Haskell を使って何かする必要に迫られ、しかもそれがパフォーマンスに関係する事である場合、まずは Strict 拡張を有効にする事をお勧めする。これは速くなるとかではなくて、単にパフォーマンス解析のしやすさからだ。後、Haskell では、何の気なしに結構遅延評価を使っている場合が多く、しかも案外ネック部分に知らない間に適用されており、Strict 拡張を有効にすると (アルゴリズムを変える必要があるレベルの) 大規模な改修が必要になったりする。そういう場面に気づくためにも、Strict 拡張は使っておいた方がいい。その結果、遅延評価の機能が使いたくなったら、lazy pattern なり lazy flag なりで使えば良いと思う。ただ、デフォルトは Strict 拡張有効の方が、変なところでつまづく確率が下がると思う。

まとめ

ということで、個人的に遅延評価で苦しい奴を3個ほど例示してみた。個人的には、最初に言った通り、

• プログラム自体が大きくて
• 複雑な制御構造をしていて

• (optional) 以下のいずれかの条件を満たす

  • 遅延評価を機能として使っている
  • デバッグ対象が効率に関するバグである

なプログラムにおいて、デフォルト遅延評価によるデバッグはかなり辛いと思っている。問題1は遅延評価を機能として使っている例、問題3は効率に関するバグの例になる。もっとそれぞれの例を洗練して、ちゃんと議論しやすい土壌に持ってくのが良いとは思ってる。思ってるが、正直苦心してそういう例を考えたくないほど遅延評価辛いので、誰かよろしくって感じ。後、こういう問題には、こう対処すると良いみたいなんがあれば、是非教えて欲しい。

GHC の抽象機械や GC 自体は遅延評価を想定してる面があるし、遅延評価由来の最適化も結構色々あって面白いとは思う。おそらく Haskell がデフォルト遅延評価を選んでいなければ、ここまでの発展はなかったんじゃないだろうか。それを考えると、技術的には面白いとは思うんだけど、如何せんプログラミングユーザとしては辛すぎるので、僕は遅延評価捨てて欲しいです。よろしくお願いします。