Haskellで分野向けの機械を開発する（１）

１．分野向けの機械

Haskellは純粋関数型言語である。自販機、改札機、ロボットなどのある分野に向けた機械に本来備わっている状態を扱うことはあまり得意としていないが、これを可能にしてくれるのが、オペレーショナル・モナドである。

オペレーショナル・モナドは、命令の集合と命令の解釈をプログラムの中で設定できるようになっている。従って、それぞれの分野ごとに、独自の命令とその解釈を与えれば、分野ごとの機械が作れることになる。また、命令を同じにして解釈を変えれば、外からの操作は全く同じだが、仕事の内容は全く異なる機械を提供することも可能だ。

このようなことができるオペレーショナル・モナドはHaskellの新しい応用分野を開拓する可能性を秘めている。そこで、数式から木構造に変換する独自の機械をオペレーショナル・モナドで作成することを考える。

２．オペレーショナル・モナドの基本部分を利用する

オペレーショナル・モナドは、基本的な部分とモナド演算子と呼ばれる拡張部分とを有している。まず、基本的な部分から説明する。ここでは、Program,singleton,Prompt,viewが用意されている。Programは次のようになっている。

type Program instr a = ProgramT instr Identity a

抽象的データ型である Program instr aはプログラムを表す。プログラムは、命令ツリーで表され、命令ツリーで使用される命令の集合はinstで定義したものである。また、aは型引数で、プログラムの戻りの型である。

具体的な例で考えたほうが分かりやすいので、オペレーショナル・モナドに載っている例で説明する。以下は、スタックに関する命令の集合を代数的データ型として定義したものである。これは、StackInstructionは型コンストラクタで、型引数aを有し、二つの値コンストラクタPushとPopを有すること、を意味する。

data StackInstruction a where
  Push :: Int -> StackInstruction ()
  Pop  :: StackInstruction Int

値コンストラクタPushは引数に整数をとり、戻り値は()(空のタプル、unit型ともいう)で、その型はStackInstruction ()である。戻り値がないのに型があるのは変に感じるが、Haskellは型言語なので戻り値がなくても型は返る。Pushは引数を有せず、戻り値はIntだが、その型はStackInstruction Intである。

このプログラムは次のようになっている。

type StackProgram a = Program StackInstruction a

ここでのスタックプログラム（StackProgram）は、StackInstructionで定義された命令から作られた命令のツリーである。

しかし、残念なことに、プログラムの中では、StackInstructionで定義された命令をそのまま使うことはできない。プログラムの中で使えるようにするのがsingletonである。それぞれの命令に関数singletonを適応するとプログラムの中で使えるようになる。singletonは次のようになっている。

singleton :: instr a -> ProgramT instr m a

型シノニムPromptは、命令のツリーを最初の命令と残りの命令ツリーに分離した型シノニムである。

type Prompt instr a = PromptT instr Identity a

viewは、命令ツリーで表されているプログラムを、最初の命令と残りの命令ツリーに分離する関数である。

view :: Program instr a -> Prompt instr a

ここでも、オペレーショナル・モナドに載っている例で説明する。例は次のようになっている。

interpret :: StackProgram a -> (Stack Int -> a)
interpret = eval . view
  where
  eval :: Prompt StackInstruction a -> (Stack Int -> a)
  eval (Push a :>>= is) stack     = interpret (is ()) (a:stack)
  eval (Pop    :>>= is) (a:stack) = interpret (is a ) stack
  eval (Return a)       stack     = a

ここでの処理を簡単に説明する。関数interpretはプログラム(ここではStackProgram aを受け取る。プログラムは命令ツリーになっているので、それを、関数viewによって最初の命令と残りの命令ツリーに分離する。関数evalは、この結果を受け取り、最初の命令を解釈実行し、新しいスタックを作成し、戻り値を返して、残りの命令ツリーの実行に移る。

命令の解釈は、パターン照合により行われる。この例では、Push,Pop,Returnがそうである。Returnは命令ツリーが終了したときに発生するものである。なお、残りの命令のツリーと戻り値は、Pushの場合には(is ())で、Popの場合には、(is a )である。また、スタックは、Pushの場合にはstackから(a:stack)に、Popの場合には(a:stack)からstackに変わる。