Multi-parameter class

Haskell

本当はTemplate Haskellについて勉強する予定の日だったのだけれど、ちょっと違う方向へそれてしまったので今日勉強したMulti-paramter classというものについて書きます。

きっかけは「ParsecでByteStringを使いたい」と思ったことです。同じ事に興味を持っている方もいらっしゃるようです。Google Summer of Codeに採用されてるみたいですね。

前からParsecはいろんな点で物足りないと思っていました。

  • リストしかパースできない。
  • ポジションがSourcePos(ファイル名、行番号、列番号)で固定。行単位のパーサとかだと列に対する演算が無駄。そもそもパースしたい対象が常にファイルとは限らない。
  • tryは出来れば書きたくない。でもいちいち文法を変形しないといけないのも面倒。
  • ほとんどの場合にdo記法になってしまい、可読性が悪い(と個人的に思う)

それでいろいろ考えていて、記法面はArrowが良さそうだとか、Template Haskellを使って非決定的にパース出来るところと出来ないところをコンパイル時に判別して最適化したら面白そうだなとか思ったりしているわけです。

んで今日は、リストしかパースできない問題とかポジションを表すデータが固定であるのを、どうすればユーザが外部から簡単に指定できるかについて考えていました。

SoCでやっている方がどういうやり方をするのかは分からないですが、多分自分が考えた方法よりずっと良いやり方なんだろうと思います。Monad Transformerとかいうよく分からないものを使っているみたいで、参考にしたいですがコードも開発状況も公開されていないので何とも。

本題

基本的なアイデアはC++でのコンセプトを真似て、「Parsableというコンセプトを満たしているならばParserの入力として使える」ということをしたいと思いました。んで、

class Parsable str where
    shift :: str -> (v, str)      -- 1文字読んで、その文字と残りを返す
    ...

みたいなクラスを定義したいのですが、vの型を決定できません。

class Parsable [a] where
    shift :: [a] -> (a, [a])

とか

class Parsable (t a) where
     shift :: t a -> (a, t a)

だと今度はByteStringが使えなくなります。

結局、C++で言えば

typename T::value_type

に相当することをしなきゃいけないわけで、いろいろ詰まっていた時にMulti-parameter classというものを知りました。

実装

単純化したParsableコンセプトの実装は下のようになります。このParsableコンセプトで定義された関数のみを使って、パーサライブラリの各関数を実装していくという感じになります。

{-# OPTIONS -fglasgow-exts
            -fallow-undecidable-instances
            -fallow-overlapping-instances
#-}
module Parsable 
    ( Parsable(..)
    ) where

import qualified Data.ByteString.Char8 as BS

-- Parsable container concept
-- c is a type of container
-- v is a value type of container
class Parsable c v | c -> v 
    where
    symbol_type :: c -> v
    symbol_type _ = undefined
    shift  :: c -> (v, c)
    eof    :: c -> Bool

instance Parsable [a] a where
    shift (x:xs) = (x, xs)
    shift []     = error "eof of input"
    eof          = Prelude.null

instance Parsable BS.ByteString Char where
    shift str    = (BS.head str, BS.tail str)
    eof          = BS.null

class Parsable c v | c -> v 
    where
    symbol_type :: c -> v
    symbol_type _ = undefined
    shift  :: c -> (v, c)
    eof    :: c -> Bool

の部分がMulti-parameter classです。文字列の型cと文字の型vの２つのパラメータを持っています。
" | c -> v "の部分はFunctional Dependenciesといって、型の依存関係を表します。この場合は型vは型cに依存し、型cが単一化された場合に型vも単一化されます。

上では配列と、ByteStringをParsableのInstanceにしましたが、例えばArrayやその他のコンテナもInstanceにすればパーサの入力として使えるようになります。

Functional Dependenciesの部分がどういう働きをするかをみてみます。まず、上のコードの場合

>:load "Parsable.hs"
>:t symbol_type "abcdefg"
symbol_type "abcdefg" :: Char
>:m +Data.ByteString.Char8
>let bs = pack "abcdefg"
>:t bs
bs :: ByteString
>:t symbol_type bs
symbol_type bs :: Char          <- ByteString型から要素であるChar型が導かれている

の様に文字列やByteStringから要素の型であるCharが導かれています。

よってshiftをByteStringについて呼び出すと自動的に型がByteString -> (Char, ByteString)であると推論され、以下のコードが通ります。

>let bs = pack "abcdefg"
>:t bs
bs :: ByteString
>shift bs
('a',"bcdefg")

" | c -> v"の部分を削除すると以下のようになります。

>:load "Parsable.hs"
[1 of 1] Compiling Parsable         ( Parsable.hs, interpreted )
Ok, modules loaded: Parsable.
>:t symbol_type "abcdefg"
symbol_type "abcdefg" :: (Parsable [Char] v) => v     <- 要素の型が導出されなくなる。
>:m +Data.ByteString.Char8
>let bs = pack "abcdefg"
>:t symbol_type bs
symbol_type bs :: (Parsable ByteString v) => v         <-

すると今度は、先ほどのコードが通らなくなります。

>let bs = pack "abcdefg"
>shift bs

<interactive>:1:0:
    No instance for (Parsable ByteString v)
      arising from use of `shift' at <interactive>:1:0-7
    Possible fix:
      add an instance declaration for (Parsable ByteString v)
    In the expression: shift bs
    In the definition of `it': it = shift bs

このMulti-parameter classを利用すると様々な互いに関係した型をうまく、型推論の枠組みに当てはめる事ができます。
同様にして、パーサの状態を表す型等もコンセプトにより規定できるようにすればかなり柔軟なパーサができるんではないかと思っています。

これを突き詰めていくと型で演算を行うという話になってきます->Strongly Typed Heterogeneous Collections。型リストとか完全にBoost.MPLの世界です。

class Fail a
data TypeNotFound e

とかいう名前のクラス、型を用意してコンパイルエラーを見やすくするとかModern C++ Designにもあったなとか思いだし、久々に、本を読んだりBoostライブラリを眺めてみたりしました。現状のHaskellの標準ライブラリだと例えばByteStringにFoldableやTraversableの関数を使うことはできないけれど、この方法だったらこれらに共通したアルゴリズムを用意することができるわけで、いろいろと遊びがいのある言語機能だなぁという感想です。