読者です 読者をやめる 読者になる 読者になる

hs2bf - Haskell段を考える(IO編)

ご存知のとおりBFのIOは

  • getChar :: IO Char
  • putChar :: Char -> IO ()

のふたつだけで表せます。

しかしたったこれだけのためにIOモナドを実装するのは考え物です。
というか実のところIOをモナドでやろうというのがあまり好きではないんです。


そこで代替案を考えます。

ストリームの変換

ぱっと思いつくのは
main :: [Char] -> [Char]
とする方法ですが、これではインタラクティブなプログラムが書けなく(書きにくく)なります。

例として電卓のようなプログラムを考えてみます(赤字はプログラムの出力)

>1+2
the answer is 3
>quit

この場合"1+2\nquit\n"を">the answer is 3\n>"に変換していることになるので

>the answer1+2
 is 3
>quit

のようなものと等価とみなされてしまいます。

実際には遅延評価の内部処理を考えつつ"the answer is 3"が"1+2"に依存するように書けばできるのですが、これでは何のためのFPLか分かりません。

DSL

data E
    =Input !(Char->E)
    |Output !Char E
    |Halt

main :: E

とすると任意のbrainfuckプログラムの動作を完全に記述できます。(BFの仕様には各コマンドの実行時間については書いていないので)

汎用性にかける方法ではありますが、ここではIOについての考察は目的としていないので問題無しとしましょう。

微妙なケースについて

上の例では何気なく!をつけていますが、これにはsemanticsを考える上で大きな意味があります。

例えばこのようにすると(Outputの!Eに注目)

data E
    =Input !(Char->E)
    |Output !Char !E
    |Halt

一文字だけ出力して無限ループするプログラムが書けなくなります。

他の!についても同様で、要するにE型のデータがWHNFにまで評価されたとき

  1. 一文字入力
  2. 一文字出力
  3. 終了

もしくは

  • 未定義(無限ループ)

が一意に定まってほしいのです。


こうすると

何もせずに終了するプログラム:

main=Halt

や何もせず終了もしないプログラム:

main=main -- main=⊥ と同じ

なども一意に書けて良いかんじです。

便利かどうか?

echo:

main=Input (\x->Output x main)

hello world:

main=outputStr Halt "Hello, world!"

outputStr :: E -> String -> E
outputStr cont []=cont
outputStr cont (x:xs)=Output x (outputStr cont xs)

どうみても継続渡しです本当に(ry

まとめ

純粋な計算は普通にかけるので問題ないでしょう。