純粋関数的 Haskell I/O プログラミング

HaskellはIOモナドを使えるので命令的Haskellプログラミングが可能になっているのだが,その代償としてプログラム全体の型は自明なIO ()に潰れてしまう.

プログラム全体の型が潰れないような仕組みを考えたのがoiパッケージ.以下は純粋に関数的にプログラムを構成したものである。(もちろん実際には、Haskellのプログラムとして起動するために、main :: IO () が必要であるし、実際の入出力を行うためのプリミティブ関数を構成するにはIOモナドが必要ではある。)

{-# LANGUAGE TypeOperators #-}
module Main where

import Data.OI
import Control.Parallel
import System.Environment

pmain ::  (FilePath,FilePath)
      ->  (FilePath,FilePath)
      ->  ((String, [String], ()), (String, [String], ()))
      :-> ()
pmain (kbd1,scr1) (kbd2,scr2)
  = uncurry par . (talk "Alice" (kbd1,scr1) |><| talk "Bob" (kbd2,scr2))

talk :: String                   -- 名前
     -> (FilePath,FilePath)      -- (キーボード, 端末スクリーン)
     -> [String]                 -- 相手からのメッセージ列
     -> OI (String,[String],())  -- 神託 (キーボード入力列,マージされたメッセージ列,プロセス結果)
     -> ([String],())            -- (相手へのメッセージ列,プロセス結果)
talk name (kbd,scr) msg r = (ins,showscr scr (mergeOI ins msg os) us)
  where
    (is,os,us) = deTriple r
    ins = map ((name ++ ": ")++) $ lines $ readkbd kbd is

----------

main :: IO ()
main = do { kbd1:scr1:kbd2:scr2:_ <- getArgs
          ; run $ pmain (kbd1,scr1) (kbd2,scr2)
          }

readkbd :: FilePath -> String :-> String
readkbd = iooi . readFile

showscr :: FilePath -> [String] -> () :-> ()
showscr s = iooi . writeFile s . unlines

命令的 Haskell プログラミング

めいっぱい imperative に書いてやったぜ :p
やってることはそれほど自明ではないのに、main :: IO () って型には何の情報もないなぁ。IO () なんて自明な型に潰れやがって。。。

module Main where

import Control.Concurrent
import System.Environment

main :: IO ()
main = do
     { kbd1:scr1:kbd2:scr2:_ <- getArgs
     ; chan1 <- newChan 
     ; chan2 <- newChan 
     ; fini1 <- newEmptyMVar
     ; fini2 <- newEmptyMVar
     ; forkIO $ talk "Alice" (kbd1,scr1) (chan1,chan2) fini1
     ; forkIO $ talk "Bob"   (kbd2,scr2) (chan2,chan1) fini2
     ; takeMVar fini1
     ; takeMVar fini2
     }

talk 
  :: String                     -- 名前
  -> (FilePath, FilePath)       -- (キーボード入力,端末スクリーン)
  -> (Chan String, Chan String) -- (相手へのメッセージチャネル,相手からのメッセージチャネル)
  -> MVar ()                    -- スレッドの終了通知変数
  -> IO ()
talk name (kbd,scrn) (input,output) fini 
  = do
  { keyboardIn    <- readFile kbd
  ; let myTweets  =  map (add name) $ lines keyboardIn
  ; yourTweets    <- getChanContents  input
  ; timeLines     <- mergeIO myTweets yourTweets
  ; let shownTLs  =  unlines timeLines
  ; forkIO $ writeFile scrn shownTLs
  ; writeList2Chan output myTweets
  ; putMVar fini ()
  }
  where
    add bird inputLine = bird ++": "++ inputLine

Purely Functional Lazy I/O についてまだ考えている

HaskellのI/O方式は以下のように変化している.

  1. Dialogue
  2. Handle-based Monadic I/O
  3. Iteratee-based (Monadic) I/O

1.から2.へはImperative functional Programming
2.から3.へはIncremental multi-level input processing and collection enumeration

読むといい.

2.から3.へのモチベーションの1つは,Handle-baseのI/OやLazy I/Oでは,resourceコントロールがまともにできないので安全ではないし,resource leakを起こしやすいので使いものにならん.というものである.さて,OIを使ったLazy I/Oがこの問題に応えられるんだろうか.

darcs pull が遅い件

darcs pullが遅すぎて作業にならなくなった.

なんとなくではあるが,

  • 時間的に古いパッチ列の間に時間的に新しいパッチ(基本的にconflictを解消するためのパッチ)をはさむ.
  • darcs unread

というのがパフォーマンスに悪影響を与えている気がする.

とりあえず,途中までのパッチを一つにまとめて,そいつを適用したところから始めてみた.
確かに,待てない状況は解消された.ふむ.ADHOCだけどこの作戦で行くことにする.

darcsリポジトリの最適化方法を教えて君

いままで比較的小規模のプロジェクトでしかdarcsを使っていなかったので,そのパフォーマンスはそれほど気にならなかった.

最近,あるプロジェクトから,1年以上前にフォークしたプロジェクトに関わるようになって,darcsのパフォーマンスがすこし気になっている.元のプロジェクトの進化(つまりパッチ)をひとずつフォークしたプロジェクトにあてて,テストするを作業するのにおそろしく時間がかかるのである.反映するべきパッチは現時点で730くらいあって,パッチをあてるにしたがって,だんだん,pullの時間が長くなる.150くらいパッチを進めたところ,darcs pullで最初の対話プロンプトが出るまでに40分かかるようになってしまった.

darcsにはoptimizeというコマンドがあるのだが...あまり効かないように感じる.なにか勘違いしているように思うんだけど...

xmonad

毎年恒例(だったかな)三日坊主の初日
gnome+xmonadという日和見気味の環境から単独xmonadという漢の環境(ほんとか?)へ移行をもくろむ.
インストールメモ(以下のメモは私個人の環境に依存しています.)

準備

各種ライブラリ,ヘッダファイルのインストール

% sudo apt-get install libgmp3-dev libbsd-dev zlib1g-dev freeglut3-dev

シンボリックリンク libgmp.so.3 の作成

% sudo ln -s /usr/lib/libgmp.so /usr/lib/libgmp.so.3

ghc 7.04 + Haskell Platform 2011.4.0.0

ghcとhaskell platformとはubuntuのパッケージは使わない.

ghc
% wget http://www.haskell.org/ghc/dist/7.0.4/ghc-7.0.4-i386-unknown-linux.tar.bz2
% tar xvf ghc-7.0.4-i386-unknown-linux.tar.bz2
% cd ghc-7.04
% ./configure
% make install
haskell platform
% wget http://lambda.haskell.org/platform/download/2011.4.0.0/haskell-platform-2011.4.0.0.tar.gz
% tar xvf haskell-platform-2011.4.0.0.tar.gz
% cd haskell-platform-2011.4.0.0
% ./configure
% make
% make install

xmonad-0.10 と xmonad-contrib-0.10

インストール
% sudo apt-get install libxft-dev
% cabal update
% cabal install xmonad xmonad-contrib --global
セッション設定
% sudo vi /usr/share/xsessions/xmonad.desktop
% cat /usr/share/xsessions/xmonad.desktop
[Desktop Entry]
Name=Xmonad
Comment=Tiling window manager
Exec=xmonad
Type=XSession
~/.xmonad/xmonad
% mkdir ~/.xmonad
% cp /usr/local/share/xmonad-0.10/man/xmonad.hs ~/.xmonad/

各種設定はなどはおいおい.

Purely Functional Lazy IO

ほんもののプログラマや浮世プログラマ(Real World Programmer)には評判の悪い「純粋に関数的で怠惰な入出力」ですが,私のような浮世離れの怠惰プログラマにはこの上なく魅力的に見えます.リソースも実行順序も考えない世界に逃避するための仕組みをつくってみました.「オイ」というデータ構造を使ってトイ未満プログラムです.

 {-# LANGUAGE TypeOperators #-}
 module Main where

 import Data.OI
 import Data.Char
 import System.IO

 main :: IO ()
 main = do { [] <- run pmain'
           ; return () }

 pmain :: ([Int], [()]) :-> [()]
 pmain = puts <| gets

 gets :: [Int] :-> String
 gets = map chr . takeWhile (eof /=) . mapOI getc

 puts :: String -> [()] :-> [()]
 puts s = dropWhile (()==) . snd . zipWithOI' putc s

これは単純に標準入力からデータを読んで標準出力に出すだけの処理を書いたものです.Haskellではプログラムの型は IO () なので一番外側では IO になっていますが,pmain を構成するのは IO ではなく関数だけで構成してあることに注目してください.

run :: (a :-> b) -> IO b は対話関数をIOに変換します.
(<|) :: (b -> c :-> d) -> (a :-> b) -> (a,c) :-> d は2つの対話関数を接続する高階関数です.

上の pmain では

  • 一文字読み込む関数 getc を合成して文字列を読み込む関数 getsを合成
  • 一文字書き出す関数 putc を合成して文字列を書き出す関数 putsを合成
  • gets と putsを連結して pmain を構成

ということを純粋に関数のみでおこなっています.pmain は以下のようにすることもできます.
型が違うことに注意してください.

 pmain' :: [(Int, ())] :-> [()]
 pmain' = dropWhile (()==) . mapOI echo

 echo :: (Int, ()) :-> ()
 echo = (putc . chr) <| getc

この pmain は合成のしかたが違いますね.これも純粋に関数だけで構成されています.
もちろん.getc や putc といった入出力のプリミティブは Haskell で実装する以上,IO を使わざるを得ませんが,iooi :: IO a -> (a :-> a) という変換関数を使って簡単に関数に変換できます.

getc :: Int :-> Int
getc = iooi getchar

putc :: Char -> () :-> ()
putc = iooi . putChar

eof :: Int
eof = -1

choice :: a -> a -> Bool -> a
choice t f c = if c then t else f

getchar :: IO Int
getchar = choice (return (-1)) (return . ord =<< getChar) =<< isEOF 

肝心の OI がでてきてませんが,type a :-> b = OI a -> b です.もうひとつトイ未満な例(トイ未満な例しかまだない :p)を挙げましょう.再帰的にディレクトリ内のファイルをたどって列挙するという例です.ちょいとナイーブな実装ですが,Purely Functional に構成していますので,lazy な性質が保持されていることが期待できます.実際にやってみるとちゃんと lazy になっていることが確認できます.

{-# LANGUAGE TypeOperators #-}
module Main where

import Data.OI

import Data.List

import System.FilePath
import System.Directory
import System.Environment

main :: IO ()
main = do { args <- getArgs
          ; case args of
              []  -> print =<< run (pmain ".")
              a:_ -> print =<< run (pmain a)
          }

pmain :: FilePath -> [(Bool, [FilePath])] :-> [FilePath]
pmain = recDirectoryContents

isDirectory :: FilePath -> Bool :-> Bool
isDirectory = iooi . doesDirectoryExist

directoryContents :: FilePath -> [FilePath] :-> [FilePath]
directoryContents f = map (f </>) . filter (`notElem` [".",".."])
                    . iooi (getDirectoryContents f)

recDirectoryContents :: FilePath -> [(Bool,[FilePath])] :-> [FilePath]
recDirectoryContents root = fst . recdircs root

recdircs :: FilePath -> [(Bool,[FilePath])] :-> ([FilePath], OI [(Bool,[FilePath])])
recdircs t <<rbfps? : rbfpss?>> = case rbfps of
  <<rb?,rfps?>> -> case isDirectory t rb of
      False -> ([t],rbfpss)
      True  -> let { ts        = directoryContents t rfps
                   ; (rs,tss)  = mapAccumL acc rbfpss ts
                   ; acc r' fp = swap (recdircs fp r')
                   } in 
               (concat tss, rs)
recdircs t <<[]>> = error $ "recdircs: impossible!"

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

<> や <> は OI 上の特殊なパターンマッチ表現で実際には使えません.実際のコードは以下のようになっています.

recdircs :: FilePath -> [(Bool,[FilePath])] :-> ([FilePath], OI [(Bool,[FilePath])])
recdircs t r = case deList r of
  Just (rbfps, rbfpss) -> case deTuple rbfps of
    (rb,rfps) -> case isDirectory t rb of
      False -> ([t],rbfpss)
      True  -> let { ts        = directoryContents t rfps
                   ; (rs,tss)  = mapAccumL acc rbfpss ts
                   ; acc r' fp = swap (recdircs fp r')
                   } in 
               (concat tss, rs)
  _ -> error $ "recdircs: impossible!"

ここで, deList と deTuple は以下のようになっています.

deList  :: OI [a]   -> Maybe (OI a, OI [a])
deTuple :: OI (a,b) -> (OI a, OI b)

型構成子 OI にはいろいろ性質があるだろうと思われます(歯切れば悪いのは形式的にまだ証明していないからです).Functor,Applicative,Monad,Comonad のインスタンスとして宣言してあります.(:->)は Category,Arrow のインスタンスを構成できるでしょう.

N.B. (:->)は型シノニムなので現在のGHCでは Category や Arrow のインスタンスとして宣言はできません.

容易に想像できるとおり, Data.OI モジュールのソースコードは伏魔殿です.トイ以上のプログラムを書けば隙間だらけであることも想像のとおりでしょうね.それでもどうしてもソース見たいとい方は Hackage からどうぞ

http://hackage.haskell.org/package/oi

当然無保証.上のトイ未満のプログラムでもすべての最適化を無効にしてコンパイルしないと上手く動きません.ソースコードを見て目が腐っても責任はもてません.もっとよい実装があるよと教えていただければ嬉しいです.